Re: IN list processing performance (yet again)

Dave Tenny <tenny(at)attbi(dot)com> writes:
> My application relies heavily on IN lists. The lists are primarily
> constant integers, so queries look like:
> SELECT val FROM table WHERE id IN (43, 49, 1001, 100002, ...)

> 1) PostgreSQL exhibits worse-than-linear performance behavior with
> respect to IN list size.

Yeah. There are a couple of places in the planner that have O(N^2)
behavior on sufficiently large WHERE clauses, due to building lists
in a naive way (repeated lappend() operations). The inner loop is
very tight, but nonetheless when you do it tens of millions of times
it adds up :-(

I have just committed some fixes into CVS tip for this --- I see about
a 10x speedup in planning time on test cases involving 10000-OR-item
WHERE clauses. We looked at this once before; the test cases I'm using
actually date back to Jan 2000. But it seems some slowness has crept
in due to subsequent planning improvements.

> 4) God help you if you haven't vacuum/analyzed that the newly loaded
> table.

Without knowledge that the id field is unique, the planner is likely to
tilt away from an indexscan with not too many IN items. I don't
consider this a bug.

> PostgreSQL craps out trying to process 8000 elements with the error:
> out of free buffers: time to abort!

This is a known bug in 7.3.2; it's fixed in 7.3.3.

regards, tom lane