Received: from localhost (unknown [200.46.204.183]) by developer.postgresql.org (Postfix) with ESMTP id BB0822E00AE for ; Thu, 29 May 2008 06:37:15 -0300 (ADT) Received: from developer.postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 45889-08 for ; Thu, 29 May 2008 06:37:07 -0300 (ADT) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from fg-out-1718.google.com (fg-out-1718.google.com [72.14.220.153]) by developer.postgresql.org (Postfix) with ESMTP id 126C12E0038 for ; Thu, 29 May 2008 06:37:09 -0300 (ADT) Received: by fg-out-1718.google.com with SMTP id 16so2142813fgg.23 for ; Thu, 29 May 2008 02:37:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:user-agent:mime-version:to:subject:content-type:content-transfer-encoding; bh=45Fs07CWTcyW+ZBNXRTpfCdnPHtw8y9yDIlESSDZUz8=; b=smMtL1i2MbYbTdrJvlDiHmMxIfshx7T9m9jE2opC9hvbgbvENODKFBXUC/XUMSaCwCNHpidh23sDcP+DGIZtTkoGgqhfWWGqGHVEYCrWcD/qZxfP9U7Ms2bBWIwwKX1rG7uN9fuTiZ0xXOZ6iILPjpT7uUrI/0XVGmV4oRz1aoA= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:user-agent:mime-version:to:subject:content-type:content-transfer-encoding; b=ojtuhWM5Dv/vuNpcx/Y4QpyTD1W2dw+lzek8yOCP1yxPujjSg71RQgHAc/QlPe4CvWL5mhNjmnvaq4Wc4Z6kffpsRsHWSl6sFUimTGk0chqAk2TGu2OrKX3vTTRfOgWbdddUi9mJae+1euFjQEMBDYVGhjyYhtUAOMFBKAYWEp4= Received: by 10.86.76.16 with SMTP id y16mr3183880fga.36.1212053827789; Thu, 29 May 2008 02:37:07 -0700 (PDT) Received: from ?192.168.1.5? ( [193.33.28.71]) by mx.google.com with ESMTPS id p38sm1072184fke.17.2008.05.29.02.37.06 (version=SSLv3 cipher=RC4-MD5); Thu, 29 May 2008 02:37:07 -0700 (PDT) Message-ID: <483E799E.1070404@gmail.com> Date: Thu, 29 May 2008 16:38:38 +0700 From: Alexey Kupershtokh User-Agent: Thunderbird 2.0.0.14 (Windows/20080421) MIME-Version: 1.0 To: pgsql-performance@postgresql.org Subject: IN() statement values order makes 2x performance hit Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=1.255 tagged_above=0 required=5 tests=AWL=-0.418, HTML_MESSAGE=0.001, MIME_HTML_ONLY=1.672 X-Spam-Level: * X-Archive-Number: 200805/366 X-Sequence-Number: 30334 Hello everybody!

I have found a performance issue with 2 equivalent queries stably taking different (~x2) time to finish. In just a few words it can be described like this: if you have a lot of values in an IN() statement, you should put most heavy (specifying most number of rows) ids first.
This is mostly just a bug submit, than looking for help.

So this is what I have:

RHEL
PostgreSQL 8.3.1
A table ext_feeder_item with ~4.6M records.
kia=# \d+ ext_feeder_item; Table "public.ext_feeder_item" Column | Type | Modifiers | Description ----------+--------------------------+--------------------------------------------------------------+------------- id | bigint | not null default nextval('ext_feeder_item_id_seq'::regclass) | feed_id | bigint | not null | pub_date | timestamp with time zone | | Indexes: "ext_feeder_item_pkey" PRIMARY KEY, btree (id) "ext_feeder_item_feed_id_pub_date_idx" btree (feed_id, pub_date) "ext_feeder_item_idx" btree (feed_id) Triggers: .... Has OIDs: no
Statistics for the fields feed_id and pub_date are set to 1000;
The table have just been vacuumed and analyzed.
A simple query to the table:
SELECT id FROM ext_feeder_item AS i WHERE i.feed_id IN (...) ORDER BY pub_date DESC, id DESC LIMIT 11 OFFSET 0;with many (~1200) ids in the IN() statement.
The count of rows distribution for these ids (may be thought of as foreign keys in this table) is the following:
id = 54461: ~180000 - actually the most heavy id in the whole table.
other ids: a single id at most specifies 2032 rows; 6036 rows total.
If I perform a query with
IN(54461, ...)
it stably (5 attempts) takes 4.5..4.7 secs. to perform.
QUERY PLAN Limit (cost=1463104.22..1463104.25 rows=11 width=16) (actual time=4585.420..4585.452 rows=11 loops=1) -> Sort (cost=1463104.22..1464647.29 rows=617228 width=16) (actual time=4585.415..4585.425 rows=11 loops=1) Sort Key: pub_date, id Sort Method: top-N heapsort Memory: 17kB -> Bitmap Heap Scan on ext_feeder_item i (cost=13832.40..1449341.79 rows=617228 width=16) (actual time=894.622..4260.441 rows=185625 loops=1) Recheck Cond: (feed_id = ANY ('{54461, ...}'::bigint[])) -> Bitmap Index Scan on ext_feeder_item_idx (cost=0.00..13678.10 rows=617228 width=0) (actual time=884.686..884.686 rows=185625 loops=1) Index Cond: (feed_id = ANY ('{54461, ...}'::bigint[])) Total runtime: 4585.852 ms
If I perform a query with
IN(..., 54461)it stably (5 attempts) takes 9.3..9.5 secs. to perform.
QUERY PLAN Limit (cost=1463104.22..1463104.25 rows=11 width=16) (actual time=9330.267..9330.298 rows=11 loops=1) -> Sort (cost=1463104.22..1464647.29 rows=617228 width=16) (actual time=9330.263..9330.273 rows=11 loops=1) Sort Key: pub_date, id Sort Method: top-N heapsort Memory: 17kB -> Bitmap Heap Scan on ext_feeder_item i (cost=13832.40..1449341.79 rows=617228 width=16) (actual time=1018.401..8971.029 rows=185625 loops=1) Recheck Cond: (feed_id = ANY ('{... ,54461}'::bigint[])) -> Bitmap Index Scan on ext_feeder_item_idx (cost=0.00..13678.10 rows=617228 width=0) (actual time=1008.791..1008.791 rows=185625 loops=1) Index Cond: (feed_id = ANY ('{... ,54461}'::bigint[])) Total runtime: 9330.729 ms

I don't know what are the roots of the problem, but I think that some symptomatic healing could be applied: the PostgreSQL could sort the IDs due to the statistics.
So currently I tend to select the IDs from another table ordering them due to their weights: it's easy for me thanks to denormalization.

Also I would expect from PostgreSQL that it sorted the values to make index scan more sequential, but this expectation already conflicts with the bug described above :)