Re: BUG #3826: Very Slow Execution of examplequery (wrong plan?)

Gregory Stark <stark@enterprisedb.com> writes:
>> insert into t1
>> select distinct (t1.a + t2.a)*2
>> from t1,t2
>> where not exists (
>> select * from t1  tt where tt.a = (t1.a + t2.a)*2
>> )

> What plan does MS-SQL use to complete this? I wonder whether it's producing
> the same answer Postgres is.

AFAICS there is just no very good way to execute a query with such
little structure.  You pretty much have to form the cartesian product
of t1 x t2 and then do a rather expensive subquery probe for each row.
There isn't even an index on tt.a to help :-(

You could probably make it slightly less bad by changing the query to

select distinct (t1.a + t2.a)*2
from t1,t2
where (t1.a + t2.a)*2 not in (
 select tt.a from t1 tt
);

which would enable PG to use a hashed-subplan implementation of the NOT
IN probe.  This transformation is not legal in general --- it will
produce different answers if t1.a or t2.a could be NULL --- but if you
know you don't care about that then it's OK.

It's possible that MS-SQL is doing something analogous to the
hashed-subplan approach (hopefully with suitable tweaking for the NULL
case) but even then it's hard to see how it could take only 9 sec.
The cartesian product is too big.

BTW, increasing work_mem should help; it looks to me like a sizable
amount of time goes into the sort for the final DISTINCT.

            regards, tom lane