Re: Improving NOT IN

"Simon Riggs" <simon(at)2ndquadrant(dot)com> writes:
> First we need to show that the referenced table's PK values are a fully
> continuous sequence of integers with no gaps.

Since that is unlikely to be the case, I can't see that this is worth
implementing...

> I'll describe this using SQL statements, which execute as SeqScans of
> the PK and then FK tables. There is no preparatory step - no building a
> sort table or preparing a hash table, so these SQL statements always
> execute faster than the fastest current plan.

Except that when you fail to prove it, as you usually will, you have
wasted a complete seqscan of the table, and still have to fall back on
a regular plan. If the thing were amenable to falling out fairly
quickly on proof failure, it would be better, but AFAICS you don't know
anything until you've completed the whole scan.

I think the NOT IN optimization that *would* be of use is to
automatically transform the NOT IN representation to an
outer-join-with-null-test type of operation, so as to give us a wider
choice of join methods. However, I'm not sure about correct handling
of NULLs on the RHS in such a scenario. The existing hashed-IN code
has to jump through some really ugly hoops to give spec-compliant
answers with NULLs.

BTW, your sketch fails in the presence of NULLs on the RHS ...

regards, tom lane