Thread

IN list processing performance (yet again)

Dave Tenny <tenny@attbi.com> — 2003-05-28T12:51:49Z

Having grepped the web, it's clear that this isn't the first or last 
time this issue will be raised.

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, ...)

Performance is critical, and the size of these lists depends a lot on 
how the larger 3-tier applicaiton is used,
but it wouldn't be out of the question to retrieve 3000-10000 items.

PostgreSQL 7.3.2 seems to have a lot of trouble with large lists. 

I ran an experiment that ran queries on a table of two integers  (ID, 
VAL), where ID is a primary key and the subject
of IN list predicates.  The test used a table with one million rows  ID 
is appropriately indexed,
and I have VACUUMED/analyzed the database after table load.

I ran tests on in-lists from about 100 to 100,000 entries.

I also ran tests where I picked the rows out one-by-one using 
parameterized statements, e.g.

SELECT val FROM table WHERE id = ?

I'm trying to decide how much I should use parameterized statements and 
when to work around buffer size limitations
in JDBC transport, general query processing, etc.

So here are my questions as a prelude to the data noted below:

1) What is the acceptable limit of jdbc Statement buffer sizes for 
executeQuery()?
      (Presumably it's not really a JDBC question, but a PostgreSQL 
query/buffering/transport question).

2) What is the expected acceptable limit for the number of items in an 
IN list predicate such as
      those used here.  (List of constants, not subselects).

3) What should I expect for performance capabilities/limitations from 
PostgreSQL on this type of problem?
      (Set my expectations, perhaps they're unrealistic).
 
4) What are my alternatives for picking specific rows for thousands of 
elements with sub-second response times
      if not IN lists?      (This is crucial!)

---------------------------------------------

Here is a summary of my observations of query times, and I've attached 
the test program (more on that below).

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

2) Parameterized statements exhibit the expected linear performance 
characteristics.

3) The break-even point for using IN lists vs. parameterized statements 
in my environment

      (RedHat Linux 9.0, PostgreSQL 7.3.2, 512MB memory, 7200RPM 100UDMA 
IDE disks, AMD1600Mhz)

      is about 700 items in the IN list.  Beyond that, IN the IN list 
scalability curve makes it impractical.

4)  God help you if you haven't vacuum/analyzed that the newly loaded 
table.  Without this,
      IN list processing is even worse!

     For just 10 elements in the IN list:

     *Without* VACUUMDB, IN lists suck beyond measure:
    Elapsed time for 10 IN list elements: 2638 ms
    Elapsed time for 10 parameterized elements: 9 ms

   *With* VACUUMDB: IN lists recover a bit:
   Elapsed time for 10 IN list elements: 10 ms
   Elapsed time for 10 parameterized elements: 24 ms

    However it's VERY interesting to note that parameterized statements 
worked well.  That implies
    probable disparity in plan generation.  It's worth noting that it 
didn't *feel* like I was getting the same
    delay when I ran the query from the 'psql' client, but since it 
doesn't report times I can't be sure.

5) Rest of my results are vacuumed, (and listed in the attached program 
in detail).
    
     The interesting points are:

      For an IN list of 700 elements:

         MySQL 3.23.56 (with INNODB tables)  takes 19ms, 73ms with 
parameterized statements.
         PostgreSQL takes 269ms, 263ms with parameterized statements.

      For larger lists, MySQL happily processed a 90,000 element IN list 
in 1449ms,
      9283 ms using parameterized statements.

      PostgreSQL  craps out trying to process 8000 elements with the error:
      out of free buffers: time to abort!    
   
      PostgreSQL takes 45,566ms for 7000 elements in an IN list (ouch!) 
, and 2027ms for a parameterized statement.
      MySQL easily beats that with 10 times the data.

6) Using a remote client on the lan (10/100) to run the client piece on 
a separate machine from the database
     server yielded little change int he results.  Prepared statements 
worked pretty well even with actual wire latency,
     surprise!  (Of course it's very little latency on my lan, not like, 
say, the database server running in a different city
     which customers have been known to do).
 
The MySQL and PostgreSQL installations are the default RedHat 9.0 
distribution packages,
I haven't tweaked either's installation parameters. (though MySQL was 
updated by RedHat from 3.23.54a to 3.23.56
as part of an automatic upgrade).

My goal here isn't to say "why aren't you like MySQL".  I've been using 
PostgreSQL for a year as the development database of choice
with satisfactory results.  But I won't be able to support customers who 
want to use PostgreSQL on large deployments of my products
if I can't selectively retrieve data for several thousand elements in 
sub-second times.

(PostgreSQL devos, if you want a feel good bullet, note that I don't 
support MySQL at all since lack of MVCC transactions
is a showstopper from a multi-user performance standpoint).

So I'm looking for (a) solutions, answers to my questions above, and (b) 
a statement of "we're on this" or "you're stuck with it" from
PostgreSQL devos who know.

----------------------------------------------------------------
On the attached program. (a Java JDBC program) Sorry, you can't just run 
it "as is".  Search for formfeeds (^L) if you want
to skip all the result data I logged.  Compilation is straightforward, 
simply supply the location of your JDBC jar file for compiling and running
(mine is noted in the program).

First, move the "if (false)" element below the table creation statements 
and run the program to create the table.
Then VACUUM/analyze your database (suuuuure would be nice not to have to 
vacuum).
Then move the "if (false)" element above the table creation so you won't 
have to do it every time.
Then move past the formfeed and adjust the 'tryAmount' for loop to test 
the amounts you're interested.
100 to 1000 by 100's is a good starting point.

Ignore the section (part of the if (false) logic) that attempts to 
figure out what the largest query size is. 
Unless you want to reproduce a hung postmaster in a CPU loop, which is 
what I got when I tried to run that logic,
though whan I ran it I was missing the closing ')' in my IN list, which 
I've since added to that code.

Thanks for any help!

Dave

Re: IN list processing performance (yet again)

Shridhar Daithankar <shridhar_daithankar@persistent.co.in> — 2003-05-28T13:16:38Z

On Wednesday 28 May 2003 18:21, Dave Tenny wrote:
> Having grepped the web, it's clear that this isn't the first or last
> time this issue will be raised.
>
> 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, ...)

How do you derive this list of number? If it is from same database, can you 
rewrite the query using a join statement?

HTH

 Shridhar

Re: IN list processing performance (yet again)

Andreas Pflug <andreas.pflug@web.de> — 2003-05-28T13:19:22Z

Dave Tenny wrote:

> Having grepped the web, it's clear that this isn't the first or last 
> time this issue will be raised.
>
> 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, ...)
>
> Performance is critical, and the size of these lists depends a lot on 
> how the larger 3-tier applicaiton is used,
> but it wouldn't be out of the question to retrieve 3000-10000 items.
>
> PostgreSQL 7.3.2 seems to have a lot of trouble with large lists.
> I ran an experiment that ran queries on a table of two integers  (ID, 
> VAL), where ID is a primary key and the subject
> of IN list predicates.  The test used a table with one million rows  
> ID is appropriately indexed,
> and I have VACUUMED/analyzed the database after table load.
>
> I ran tests on in-lists from about 100 to 100,000 entries. 

Hi Dave,

it sounds as if that IN-list is created by the application. I wonder if 
there are really so many variances and combinations of it or whether you 
could invent an additional column, which groups all those individual 
values. If possible, you could reduce your IN list to much fewer values, 
and probably would get better performance (using an index on that col, 
of course).

Regards,

Andreas

Re: IN list processing performance (yet again)

Mario Weilguni <mweilguni@sime.com> — 2003-05-28T14:31:37Z

>
> 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, ...)
>
> Performance is critical, and the size of these lists depends a lot on
> how the larger 3-tier applicaiton is used,
> but it wouldn't be out of the question to retrieve 3000-10000 items.
>
> PostgreSQL 7.3.2 seems to have a lot of trouble with large lists.

you should rewrite your query if the query is created from an applition:

SELECT val
   FROM table
 WHERE id between 43 and 100002
       AND id IN (43, 49, 1001, 100002, ...)

where 43 is the min and 100002 the max of all values.

I had this case with postgresql 7.2 and the planner made much smarter
choices in my case.

Regards,
    Mario Weilguni

Re: IN list processing performance (yet again)

Stephan Szabo <sszabo@megazone23.bigpanda.com> — 2003-05-28T14:54:26Z

On Wed, 28 May 2003, Dave Tenny wrote:

> Having grepped the web, it's clear that this isn't the first or last
> time this issue will be raised.
>
> 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, ...)
>
> Performance is critical, and the size of these lists depends a lot on
> how the larger 3-tier applicaiton is used,
> but it wouldn't be out of the question to retrieve 3000-10000 items.
>
> PostgreSQL 7.3.2 seems to have a lot of trouble with large lists.

It gets converted into a sequence like col=list[0] or col=list[1] and it
seems the planner/optimizer is taking at least a large amount of time for
me given that explain takes just over 80 seconds for a 9900 item list on
my machine (I don't have a data filled table to run the actual query
against).

The best plan may be generated right now from making a temporary
table, copying the values into it, and joining.

> 2) What is the expected acceptable limit for the number of items in an
> IN list predicate such as
>       those used here.  (List of constants, not subselects).

As a note, 7.4 by default seems to limit it to 10000 unless you up
max_expr_depth afaics.

Re: IN list processing performance (yet again)

Dave Tenny <tenny@attbi.com> — 2003-05-28T17:58:14Z

A join isn't an option, these elements come a a selection of entity ID's 
that are specific to some client context.
Some other people suggested joins too. 

Consider it something like this, say there's a database that represents 
the entire file system content
of a set of machines, hundreds of thousands of files.  A single user 
wants to do something
related to the ID's of 3000 files.  The requests for those 3000 files 
can be built up in a number of ways,
not all of which rely on data in the database.  So I need to retrieve 
data on those 3000 files using IN lists or some alternative.

Dave

Shridhar Daithankar wrote:

>On Wednesday 28 May 2003 18:21, Dave Tenny wrote:
>  
>
>>Having grepped the web, it's clear that this isn't the first or last
>>time this issue will be raised.
>>
>>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, ...)
>>    
>>
>
>How do you derive this list of number? If it is from same database, can you 
>rewrite the query using a join statement?
>
>HTH
>
> Shridhar
>
>
>---------------------------(end of broadcast)---------------------------
>TIP 4: Don't 'kill -9' the postmaster
>
>  
>

Re: IN list processing performance (yet again)

Dave Tenny <tenny@attbi.com> — 2003-05-28T18:08:02Z

Andreas Pflug wrote:

> Dave Tenny wrote:
>
>> Having grepped the web, it's clear that this isn't the first or last 
>> time this issue will be raised.
>>
>> 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, ...)
>>
>> Performance is critical, and the size of these lists depends a lot on 
>> how the larger 3-tier applicaiton is used,
>> but it wouldn't be out of the question to retrieve 3000-10000 items.
>>
>> PostgreSQL 7.3.2 seems to have a lot of trouble with large lists.
>> I ran an experiment that ran queries on a table of two integers  (ID, 
>> VAL), where ID is a primary key and the subject
>> of IN list predicates.  The test used a table with one million rows  
>> ID is appropriately indexed,
>> and I have VACUUMED/analyzed the database after table load.
>>
>> I ran tests on in-lists from about 100 to 100,000 entries. 
>
>
> Hi Dave,
>
> it sounds as if that IN-list is created by the application. I wonder 
> if there are really so many variances and combinations of it or 
> whether you could invent an additional column, which groups all those 
> individual values. If possible, you could reduce your IN list to much 
> fewer values, and probably would get better performance (using an 
> index on that col, of course).

There are over 50 tables in the schema,
and dozens of client commands that manipulate the schema in a 
persistent-checkout kind of way over time, as well as spurious reporting 
requests
that require incredibly complex filtering and combination of data from 
many tables.
I'm pretty much up to my keister data (and am resisting impulses for 
denormalization), so this approach
probably isn't viable for me.  Now I *could* create a temporary table 
with the group of values, but I suspect the cost of that
substantially outweighs the negative performance of current IN lists or 
parameterized statements.

I'm reminded to relay to the PostgreSQL devos that I might be able to do 
more in the  join or subquery department if
PostgreSQL had better performing MAX functions and a FIRST function for 
selecting rows from groups.
("Performing" being the operative word here, since the extensible 
architecture of PostgreSQL currently makes for poorly
performing MAX capabilities and presumably similar user defined 
aggregate functions).

>
> Regards,
>
> Andreas
>
>
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 3: if posting/reading through Usenet, please send an appropriate
> subscribe-nomail command to majordomo@postgresql.org so that your
> message can get through to the mailing list cleanly
>

Re: IN list processing performance (yet again)

Dave Tenny <tenny@attbi.com> — 2003-05-28T18:17:21Z

Mario Weilguni wrote:

>>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, ...)
>>
>>Performance is critical, and the size of these lists depends a lot on
>>how the larger 3-tier applicaiton is used,
>>but it wouldn't be out of the question to retrieve 3000-10000 items.
>>
>>PostgreSQL 7.3.2 seems to have a lot of trouble with large lists.
>>    
>>
>
>you should rewrite your query if the query is created from an applition:
>
>SELECT val
>   FROM table
> WHERE id between 43 and 100002
>       AND id IN (43, 49, 1001, 100002, ...)
>
>where 43 is the min and 100002 the max of all values.
>
>I had this case with postgresql 7.2 and the planner made much smarter
>choices in my case.
>
>Regards,
>    Mario Weilguni
>  
>
Very interesting!  I tried it out, but it didn't appreciably change the 
thresholds in my results for going by for IN list
sizes 100 - 1000.  It's also likely to be of use only if the range for 
the between is fairly restricted,
which isn't necessarily characteristic of my data.

Dave

Re: IN list processing performance (yet again)

Mario Weilguni <mweilguni@sime.com> — 2003-05-28T18:29:43Z

> I'm reminded to relay to the PostgreSQL devos that I might be able to do
> more in the  join or subquery department if
> PostgreSQL had better performing MAX functions and a FIRST function for
> selecting rows from groups.
> ("Performing" being the operative word here, since the extensible
> architecture of PostgreSQL currently makes for poorly
> performing MAX capabilities and presumably similar user defined
> aggregate functions).

MIN/MAX is almost in every case replaceable:
select bar
   from foo
 order by bar limit 1;

instead of
select max(bar) from foo;

Re: IN list processing performance (yet again)

Bruno Wolff III <bruno@wolff.to> — 2003-05-28T18:39:14Z

On Wed, May 28, 2003 at 14:08:02 -0400,
  Dave Tenny <tenny@attbi.com> wrote:
> Andreas Pflug wrote:
> 
> I'm reminded to relay to the PostgreSQL devos that I might be able to do 
> more in the  join or subquery department if
> PostgreSQL had better performing MAX functions and a FIRST function for 
> selecting rows from groups.
> ("Performing" being the operative word here, since the extensible 
> architecture of PostgreSQL currently makes for poorly
> performing MAX capabilities and presumably similar user defined 
> aggregate functions).

Have you tried replacing max with a subselect that uses order by and limit?

Re: IN list processing performance (yet again)

Bruno Wolff III <bruno@wolff.to> — 2003-05-28T18:41:50Z

On Wed, May 28, 2003 at 13:58:14 -0400,
  Dave Tenny <tenny@attbi.com> wrote:
> A join isn't an option, these elements come a a selection of entity ID's 
> that are specific to some client context.
> Some other people suggested joins too. 

You can union the values together and then join (or use where exists) with the
result. This may not be faster and you may not be able to union several
thousand selects together in a single statement. But it shouldn't be too
much work to test it out.

Re: IN list processing performance (yet again)

Dave Tenny <tenny@attbi.com> — 2003-05-28T19:57:22Z

Mario Weilguni wrote:

>>I'm reminded to relay to the PostgreSQL devos that I might be able to do
>>more in the  join or subquery department if
>>PostgreSQL had better performing MAX functions and a FIRST function for
>>selecting rows from groups.
>>("Performing" being the operative word here, since the extensible
>>architecture of PostgreSQL currently makes for poorly
>>performing MAX capabilities and presumably similar user defined
>>aggregate functions).
>>    
>>
>
>MIN/MAX is almost in every case replaceable:
>select bar
>   from foo
> order by bar limit 1;
>
>instead of
>select max(bar) from foo;
>  
>
Yup, been there, done that, but thanks, it's a good tidbit for the 
postgresql unaware.

There are some places however where it doesn't work well in query logic, 
though I don't have an example off the top of my head
since I've worked around it in all my queries.

Re: IN list processing performance (yet again)

Dave Tenny <tenny@attbi.com> — 2003-05-28T20:01:34Z

Bruno Wolff III wrote:

>On Wed, May 28, 2003 at 14:08:02 -0400,
>  Dave Tenny <tenny@attbi.com> wrote:
>  
>
>>Andreas Pflug wrote:
>>
>>I'm reminded to relay to the PostgreSQL devos that I might be able to do 
>>more in the  join or subquery department if
>>PostgreSQL had better performing MAX functions and a FIRST function for 
>>selecting rows from groups.
>>("Performing" being the operative word here, since the extensible 
>>architecture of PostgreSQL currently makes for poorly
>>performing MAX capabilities and presumably similar user defined 
>>aggregate functions).
>>    
>>
>
>Have you tried replacing max with a subselect that uses order by and limit?
>  
>

I'm uncertain how that would work, since somewhere in there I still need 
to elaborate on the
1000 items I want, and they're not necessarily in any particular range, 
nor do they bear any
contiguous group nature.

Also, IN (subquery) is a known performance problem in PGSQL, at least if 
the subquery is going to return many rows.
It's too bad, since I'm rather fond of subqueries, but I avoid them like 
the plague in PostgreSQL.

Perhaps I don't understand what you had in mind.

Re: IN list processing performance (yet again)

Dave Tenny <tenny@attbi.com> — 2003-05-28T20:13:17Z

Bruno Wolff III wrote:

>On Wed, May 28, 2003 at 13:58:14 -0400,
>  Dave Tenny <tenny@attbi.com> wrote:
>  
>
>>A join isn't an option, these elements come a a selection of entity ID's 
>>that are specific to some client context.
>>Some other people suggested joins too. 
>>    
>>
>
>You can union the values together and then join (or use where exists) with the
>result. This may not be faster and you may not be able to union several
>thousand selects together in a single statement. But it shouldn't be too
>much work to test it out.
>  
>
I assume you mean something like:

test=# select million.id, million.val from million, (select 10000 as a 
union select 20000 as a) t2 where million.id = t2.a;
  id   |  val
-------+-------
 10000 |     0
 20000 | 10000
(2 rows)

Ouch!  That's deviant.   Haven't tried it yet and I cringe at the 
thought of it, but I might take a run at it.  However that's going to
run up the buffer space quickly.  That was one of my as yet unsnaswered 
questions, what is the pragmatic buffer size limit
for queries?

I'm /really/ hoping we'll come up with something better, like an 
understanding of why IN lists are non-linear in the first
place when the column is indexed, and whether it's fixable through some 
other means or whether it's a bug that should be fixed.

After all, I'm trying to support multiple databases, and other databases 
kick butt on this.  It's just postgresql that's
having difficulty.

(Btw, I've also tried statement batching, but that's a lose for now, at 
least with the current JDBC drivers and 7.3.2).

Re: IN list processing performance (yet again)

Bruno Wolff III <bruno@wolff.to> — 2003-05-28T20:24:18Z

On Wed, May 28, 2003 at 16:01:34 -0400,
  Dave Tenny <tenny@attbi.com> wrote:
> 
> Perhaps I don't understand what you had in mind.
> 

I was refering to your comment about max causing problems. But it seems
you are aware of the standard work around.

Re: IN list processing performance (yet again)

Bruno Wolff III <bruno@wolff.to> — 2003-05-28T20:29:05Z

On Wed, May 28, 2003 at 16:13:17 -0400,
  Dave Tenny <tenny@attbi.com> wrote:
> Bruno Wolff III wrote:
> 
> I assume you mean something like:
> 
> test=# select million.id, million.val from million, (select 10000 as a 
> union select 20000 as a) t2 where million.id = t2.a;
>  id   |  val
> -------+-------
> 10000 |     0
> 20000 | 10000
> (2 rows)
> 
> Ouch!  That's deviant.   Haven't tried it yet and I cringe at the 
> thought of it, but I might take a run at it.  However that's going to
> run up the buffer space quickly.  That was one of my as yet unsnaswered 
> questions, what is the pragmatic buffer size limit
> for queries?

That is what I was referring to. I have used this in some cases where
I knew the list was small and I wanted to do a set difference without
loading a temporary table. Or to do an insert of multiple rows with
one insert statement.

> I'm /really/ hoping we'll come up with something better, like an 
> understanding of why IN lists are non-linear in the first
> place when the column is indexed, and whether it's fixable through some 
> other means or whether it's a bug that should be fixed.

It also might be worth seeing if the development version is going to
speed things up for you. Beta is one month away. My guess is that the
production release will be in September.

Re: IN list processing performance (yet again)

Tom Lane <tgl@sss.pgh.pa.us> — 2003-05-28T23:44:01Z

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

Re: IN list processing performance (yet again)

Dave Tenny <tenny@attbi.com> — 2003-05-29T01:19:56Z

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

Re: IN list processing performance (yet again)

Tom Lane <tgl@sss.pgh.pa.us> — 2003-05-29T01:46:13Z

Dave Tenny <tenny@attbi.com> writes:
> </blockquote>
> There is one very interesting thing in my test case though.&nbsp; It
> certainly <i>seemed</i> as if the<br>
> parameterized statements were successfully using the index of the
> freshly-created-but-unanalyzed table,<br>
> or else the times on those queries would have been terrible too.&nbsp; It
> was only the IN list form<br>
> of query that wasn't making correct use of the index.&nbsp; How can the
> planner recognize uniqueness for<br>
> one case but not the other?

The question is whether a seqscan will be faster than an indexscan; at
some point there's less I/O involved to just scan the table once.  If
the planner doesn't know the index is unique then it's going to estimate
a higher cost for the indexscan (due to more rows fetched) and there is
some number of rows at which it will flip over to a seqscan.  The same
will happen even if it *does* know the index is unique, it's just that
it will take more IN elements to make it happen.  This is reasonable
behavior IMHO, although whether the flip-over point is anywhere near
the actual breakeven point on your hardware is anyone's guess.  The cost
estimates are often far enough off that it's not very close.

			regards, tom lane

Re: IN list processing performance (yet again)

Christopher Kings-Lynne <chriskl@familyhealth.com.au> — 2003-05-29T01:47:53Z

The IN list processing has been fixed in 7.4CVS.  It now uses a hash based lookup rather than a list, so it's vastly faster.

Chris
  ----- Original Message ----- 
  From: Dave Tenny 
  To: Shridhar Daithankar 
  Cc: pgsql-performance@postgresql.org 
  Sent: Thursday, May 29, 2003 1:58 AM
  Subject: Re: [PERFORM] IN list processing performance (yet again)

  A join isn't an option, these elements come a a selection of entity ID's that are specific to some client context.
  Some other people suggested joins too.  

  Consider it something like this, say there's a database that represents the entire file system content
  of a set of machines, hundreds of thousands of files.  A single user wants to do something
  related to the ID's of 3000 files.  The requests for those 3000 files can be built up in a number of ways,
  not all of which rely on data in the database.  So I need to retrieve data on those 3000 files using IN lists or some alternative.

  Dave

  Shridhar Daithankar wrote:

On Wednesday 28 May 2003 18:21, Dave Tenny wrote:
  Having grepped the web, it's clear that this isn't the first or last
time this issue will be raised.

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, ...)

How do you derive this list of number? If it is from same database, can you 
rewrite the query using a join statement?

HTH

 Shridhar

---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster

Re: IN list processing performance (yet again)

Christopher Kings-Lynne <chriskl@familyhealth.com.au> — 2003-05-29T01:53:55Z


> Also, IN (subquery) is a known performance problem in PGSQL, at least if
the subquery is going to return > many rows.
> It's too bad, since I'm rather fond of subqueries, but I avoid them like
the plague in PostgreSQL.

You're not really using a subquery - really just a long list of integers.
Subqueries are lightning fast, so long as you conver to the EXISTS form:

SELECT * FROM tab WHERE id IN (SELECT id2 FROM tab2);

converts to:

SELECT * FROM tab WHERE EXISTS (SELECT id2 FROM tab2 WHERE id2=id);

Chris

Re: IN list processing performance (yet again)

Bruno Wolff III <bruno@wolff.to> — 2003-05-29T10:55:31Z

On Wed, May 28, 2003 at 21:19:56 -0400,
  Dave Tenny <tenny@attbi.com> wrote:
> 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.

7.4

7.4 is suppsoed to go into beta July 1.

If you are used to installing from source tarballs, you can grab a
development snapshot tarball. There is probably a day or two delay
depending on if you get it from a mirror or the primary site.

Re: IN list processing performance (yet again)

Dave Tenny <tenny@attbi.com> — 2003-05-29T12:48:41Z

Christopher Kings-Lynne wrote:

>  
>
>>Also, IN (subquery) is a known performance problem in PGSQL, at least if
>>    
>>
>the subquery is going to return > many rows.
>  
>
>>It's too bad, since I'm rather fond of subqueries, but I avoid them like
>>    
>>
>the plague in PostgreSQL.
>
>You're not really using a subquery - really just a long list of integers.
>

Oops, you got that out of context, it was a different piece of 
conversation about subqueries in IN predicate,
not the scalar forms that was my overall discussion point.  You're 
right, I'm using lists of integers,
someone else was suggesting using subqueries in some context and I was 
responding to that.

>Subqueries are lightning fast, so long as you conver to the EXISTS form:
>
>SELECT * FROM tab WHERE id IN (SELECT id2 FROM tab2);
>
>converts to:
>
>SELECT * FROM tab WHERE EXISTS (SELECT id2 FROM tab2 WHERE id2=id);
>
>Chris
>  
>
I hadn't thought of that, it's an excellent tip.  I'll have to remember 
it next time I want to use subqueries.
(Again, it's a side topic, my primary concern is scalar-form IN lists.)

Thanks,

Dave