From: Tom Lane <tgl@sss.pgh.pa.us>
To: Dave Tenny <tenny@attbi.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: IN list processing performance (yet again)
Date: Wed, 28 May 2003 19:44:01 -0400
Message-ID: <9207.1054165441@sss.pgh.pa.us> (raw)
In-Reply-To: <3ED4B0E5.3050703@attbi.com>
References: <3ED4B0E5.3050703@attbi.com>
Dave Tenny <tenny@attbi.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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients from your mail client; the link fills in
the headers below: reply via email
Some clients, webmail especially, drop In-Reply-To and References from
a link, and the reply then starts a new thread: use the mbox below.
To: pgsql-performance@postgresql.org
Cc: tgl@sss.pgh.pa.us, tenny@attbi.com
Subject: Re: IN list processing performance (yet again)
In-Reply-To: <9207.1054165441@sss.pgh.pa.us>
References: <3ED4B0E5.3050703@attbi.com> <9207.1054165441@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox