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
