Обсуждение: dum query plan
I am wondering why it uses the O(n^2) nested loop when there is a O(N)
methoud using btree indexes for a merg join. I am using 7.2.1 would
upgrading fix my problime or is it somthing else?
Given the schema:
drop table Entry_Pairs;
create table Entry_Pairs (
left_entry int REFERENCES Entry ON DELETE RESTRICT,
right_entry int REFERENCES Entry ON DELETE RESTRICT,
relation int NOT NULL ,
subtract bool NOT NULL ,
comment int NULL REFERENCES Comment ON DELETE SET NULL,
UNIQUE (left_entry, right_entry, relation)
);
CREATE INDEX entry_pairs_left_index ON entry_pairs (left_entry);
CREATE INDEX entry_pairs_right_index ON entry_pairs (right_entry);
--
You get this"
dblex=> explain select A.left_entry from entry_pairs A, entry_pairs B
where A.right_entry != B.left_entry;
NOTICE: QUERY PLAN:
Nested Loop (cost=100000000.00..102876671.17 rows=97545252 width=12)
-> Seq Scan on entry_pairs a (cost=0.00..167.77 rows=9877 width=8)
-> Seq Scan on entry_pairs b (cost=0.00..167.77 rows=9877 width=4)
EXPLAIN
That is dum. If you just walk both B-Tree indexes there is a O(n)
search. I tryed to turn off netsed loops but it still did it. (the
reason the cost is 100000000.00 is a artifact from turing off loops)
-Jonathan
On 15 Apr 2003, Jonathan Moore wrote: > I am wondering why it uses the O(n^2) nested loop when there is a O(N) > methoud using btree indexes for a merg join. I am using 7.2.1 would > upgrading fix my problime or is it somthing else? > > Given the schema: > > drop table Entry_Pairs; > create table Entry_Pairs ( > left_entry int REFERENCES Entry ON DELETE RESTRICT, > right_entry int REFERENCES Entry ON DELETE RESTRICT, > relation int NOT NULL , > subtract bool NOT NULL , > comment int NULL REFERENCES Comment ON DELETE SET NULL, > UNIQUE (left_entry, right_entry, relation) > ); > CREATE INDEX entry_pairs_left_index ON entry_pairs (left_entry); > CREATE INDEX entry_pairs_right_index ON entry_pairs (right_entry); > -- > > You get this" > > dblex=> explain select A.left_entry from entry_pairs A, entry_pairs B > where A.right_entry != B.left_entry; > NOTICE: QUERY PLAN: > > Nested Loop (cost=100000000.00..102876671.17 rows=97545252 width=12) > -> Seq Scan on entry_pairs a (cost=0.00..167.77 rows=9877 width=8) > -> Seq Scan on entry_pairs b (cost=0.00..167.77 rows=9877 width=4) > > EXPLAIN > > That is dum. If you just walk both B-Tree indexes there is a O(n) > search. I tryed to turn off netsed loops but it still did it. (the > reason the cost is 100000000.00 is a artifact from turing off loops) Can you describe the algorithm you think it should be taking with perhaps a small set of data like say (given only left and right): (1,2) (3,4) (5,6) (I think the query should return 1,1,1,3,3,3,5,5,5 for this case)
Jonathan Moore <moore@discern.com> writes:
> I am wondering why it uses the O(n^2) nested loop when there is a O(N)
> methoud using btree indexes for a merg join.
With an inequality for the WHERE condition? I don't think so. The
expected output is of size O(N^2), so how could the algorithm take
less than O(N^2) steps?
> dblex=> explain select A.left_entry from entry_pairs A, entry_pairs B
> where A.right_entry != B.left_entry;
regards, tom lane
Your WHERE clause is the reason you get O(N^2). How about describing in words what you want. maybe what you really want is: select left_entry from entry_pairs A where not exists ( select 1 from entry_pairs B where A.right_entry = B.left_entry) JLL Jonathan Moore wrote: > > I am wondering why it uses the O(n^2) nested loop when there is a O(N) > methoud using btree indexes for a merg join. I am using 7.2.1 would > upgrading fix my problime or is it somthing else? > > Given the schema: > > drop table Entry_Pairs; > create table Entry_Pairs ( > left_entry int REFERENCES Entry ON DELETE RESTRICT, > right_entry int REFERENCES Entry ON DELETE RESTRICT, > relation int NOT NULL , > subtract bool NOT NULL , > comment int NULL REFERENCES Comment ON DELETE SET NULL, > UNIQUE (left_entry, right_entry, relation) > ); > CREATE INDEX entry_pairs_left_index ON entry_pairs (left_entry); > CREATE INDEX entry_pairs_right_index ON entry_pairs (right_entry); > -- > > You get this" > > dblex=> explain select A.left_entry from entry_pairs A, entry_pairs B > where A.right_entry != B.left_entry; > NOTICE: QUERY PLAN: > > Nested Loop (cost=100000000.00..102876671.17 rows=97545252 width=12) > -> Seq Scan on entry_pairs a (cost=0.00..167.77 rows=9877 width=8) > -> Seq Scan on entry_pairs b (cost=0.00..167.77 rows=9877 width=4) > > EXPLAIN > > That is dum. If you just walk both B-Tree indexes there is a O(n) > search. I tryed to turn off netsed loops but it still did it. (the > reason the cost is 100000000.00 is a artifact from turing off loops) > > -Jonathan > > ---------------------------(end of broadcast)--------------------------- > TIP 6: Have you searched our list archives? > > http://archives.postgresql.org