X-Original-To: pgsql-performance@postgresql.org Received: from localhost (developer.postgresql.org [64.117.224.193]) by developer.postgresql.org (Postfix) with ESMTP id 7091692544F for ; Wed, 28 May 2003 21:19:58 -0400 (EDT) Received: from developer.postgresql.org ([64.117.224.193]) by localhost (developer.postgresql.org [64.117.224.193:10024]) (amavisd-new) with ESMTP id 90682-03 for ; Wed, 28 May 2003 21:19:57 -0400 (EDT) Received: from sccrmhc03.attbi.com (sccrmhc03.attbi.com [204.127.202.63]) by developer.postgresql.org (Postfix) with ESMTP id 8095C925441 for ; Wed, 28 May 2003 21:19:57 -0400 (EDT) Received: from attbi.com (dtenny.ne.client2.attbi.com[24.60.113.221]) by attbi.com (sccrmhc03) with SMTP id <2003052901195700300pf617e>; Thu, 29 May 2003 01:19:57 +0000 Message-ID: <3ED5603C.2020800@attbi.com> Date: Wed, 28 May 2003 21:19:56 -0400 From: Dave Tenny User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.3.1) Gecko/20030425 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Tom Lane Cc: pgsql-performance@postgresql.org Subject: Re: IN list processing performance (yet again) References: <3ED4B0E5.3050703@attbi.com> <9207.1054165441@sss.pgh.pa.us> In-Reply-To: <9207.1054165441@sss.pgh.pa.us> Content-Type: multipart/alternative; boundary="------------050408010506090807030801" X-Virus-Scanned: by amavisd-new X-Archive-Number: 200305/255 X-Sequence-Number: 2034 This is a multi-part message in MIME format. --------------050408010506090807030801 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Tom Lane wrote: >Dave Tenny 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 :-( > > > It was also showing up very clearly in the timings I attached for just a couple hundred IN list entries too. Does that mean that the time for the O(1) portions of the logic are perhaps also in need of a tuneup? (I would think O(N^2) for trivial operations on a fast machine wouldn't manifest quite so much for smallish N). >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. > > > So what version might that equate to down the road, so I can be sure to check it out? I'm afraid I'm not up to testing CVS tips. > > >>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. > > > There is one very interesting thing in my test case though. It certainly /seemed/ as if the parameterized statements were successfully using the index of the freshly-created-but-unanalyzed table, or else the times on those queries would have been terrible too. It was only the IN list form of query that wasn't making correct use of the index. How can the planner recognize uniqueness for one case but not the other? (Since I ran both forms of query on the same table with and without vacuuming). > > >> 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. > > Thanks, that's good to know. Dave --------------050408010506090807030801 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit Tom Lane wrote:
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 :-(

  
It was also showing up very clearly in the timings I attached for just a couple hundred IN list entries too.
Does that mean that the time for the O(1) portions of the logic are perhaps also in need of a tuneup?
(I would think O(N^2) for trivial operations on a fast machine wouldn't manifest quite so much
for smallish N).
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.

  
So what version might that equate to down the road, so I can be sure to check it out?
I'm afraid I'm not up to testing CVS tips.
  
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.

  
There is one very interesting thing in my test case though.  It certainly seemed as if the
parameterized statements were successfully using the index of the freshly-created-but-unanalyzed table,
or else the times on those queries would have been terrible too.  It was only the IN list form
of query that wasn't making correct use of the index.  How can the planner recognize uniqueness for
one case but not the other? (Since I ran both forms of query on the same table with and without vacuuming).
  
      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.
  
Thanks, that's good to know.

Dave
--------------050408010506090807030801--