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 3945D925A10 for ; Wed, 28 May 2003 19:44:05 -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 70096-05 for ; Wed, 28 May 2003 19:44:03 -0400 (EDT) Received: from sss.pgh.pa.us (unknown [192.204.191.242]) by developer.postgresql.org (Postfix) with ESMTP id 776789259E8 for ; Wed, 28 May 2003 19:44:03 -0400 (EDT) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.12.9/8.12.9) with ESMTP id h4SNi2U6009208; Wed, 28 May 2003 19:44:02 -0400 (EDT) To: Dave Tenny Cc: pgsql-performance@postgresql.org Subject: Re: IN list processing performance (yet again) In-reply-to: <3ED4B0E5.3050703@attbi.com> References: <3ED4B0E5.3050703@attbi.com> Comments: In-reply-to Dave Tenny message dated "Wed, 28 May 2003 08:51:49 -0400" Date: Wed, 28 May 2003 19:44:01 -0400 Message-ID: <9207.1054165441@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: by amavisd-new X-Archive-Number: 200305/254 X-Sequence-Number: 2033 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 :-( 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