Re: dum query plan: more info.

On 16 Apr 2003 15:02:49 -0700, Jonathan Moore <moore(at)discern(dot)com>
wrote:
>select A.left form pairs A, pairs B where A.left != B.right;
>
>take the DB:
>
>(1,2)
>(2,1)
>(1,5)
>(4,5)
>(5,2)
>
>[...] 4 is the only value that is on the left and only
>on the left.

But this is not the answer to your SQL statement. The correct answer
is:
left
------
1
1
1
1
2
2
2
1
1
1
1
4
4
4
4
4
5
5
5
(19 rows)

What you are looking for is more like

SELECT left FROM pairs
EXCEPT
SELECT right FROM pairs;

>This methoud is order O(n) if both colums have b-tree indexes so you
>don't have to pre sort them othere wise it is O(n*log(n)) as the sort is
>the greatest complexity. In eathere case it is way better then O(n^2)
>for almost any n.

And I'm sure it will not take O(n^2) time in Postgres.

Servus
Manfred