Re: dum query plan: more info.

On 16 Apr 2003 15:02:49 -0700, Jonathan Moore <moore@discern.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