pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
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



view thread (23+ messages)  latest in thread

Message-ID: <9207.1054165441@sss.pgh.pa.us>
Permalink:  ../9207.1054165441@sss.pgh.pa.us/
Also on:    postgresql.org/message-id/9207.1054165441@sss.pgh.pa.us

 · 

reply

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