From alexey.kupershtokh@gmail.com Thu May 29 09:37:15 2008 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 :)
From oleg@sai.msu.su Thu May 29 09:40:09 2008 Received: from localhost (unknown [200.46.204.183]) by developer.postgresql.org (Postfix) with ESMTP id 8808B2E0038 for ; Thu, 29 May 2008 06:40:09 -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 49184-05 for ; Thu, 29 May 2008 06:40:00 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from sn.sai.msu.ru (sn.sai.msu.ru [195.208.220.215]) by developer.postgresql.org (Postfix) with ESMTP id AE51A2E00AE for ; Thu, 29 May 2008 06:40:03 -0300 (ADT) Received: from sn.sai.msu.ru (localhost [127.0.0.1]) by sn.sai.msu.ru (8.14.1/8.12.8) with ESMTP id m4T9dvCK017498; Thu, 29 May 2008 13:39:57 +0400 Received: from localhost (megera@localhost) by sn.sai.msu.ru (8.14.1/8.12.8/Submit) with ESMTP id m4T9dvLv017495; Thu, 29 May 2008 13:39:57 +0400 X-Authentication-Warning: sn.sai.msu.ru: megera owned process doing -bs Date: Thu, 29 May 2008 13:39:57 +0400 (MSD) From: Oleg Bartunov X-X-Sender: megera@sn.sai.msu.ru To: Alexey Kupershtokh cc: pgsql-performance@postgresql.org Subject: Re: IN() statement values order makes 2x performance hit In-Reply-To: <483E799E.1070404@gmail.com> Message-ID: References: <483E799E.1070404@gmail.com> MIME-Version: 1.0 X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0.097 tagged_above=0 required=5 tests=AWL=-1.028, DNS_FROM_RFC_BOGUSMX=2.125, RCVD_IN_DNSWL_LOW=-1 X-Spam-Level: Content-Type: TEXT/PLAIN; charset=koi8-r; format=flowed Content-Transfer-Encoding: QUOTED-PRINTABLE X-Archive-Number: 200805/367 X-Sequence-Number: 30335 You may try contrib/intarray, which we developed specially for denormalization. Oleg On Thu, 29 May 2008, Alexey Kupershtokh wrote: > Hello everybody! >=20 > 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. >=20 > So this is what I have: > * RHEL > * PostgreSQL 8.3.1 > * A table ext_feeder_item with ~4.6M records. > kia=3D# \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 =3D 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=9A (cost=3D1463104.22..1463104.25 rows=3D11 width=3D16) (actual > time=3D4585.420..4585.452 rows=3D11 loops=3D1) > =9A ->=9A Sort=9A (cost=3D1463104.22..1464647.29 rows=3D617228 width= =3D16) > (actual time=3D4585.415..4585.425 rows=3D11 loops=3D1) > =9A=9A=9A=9A=9A=9A=9A Sort Key: pub_date, id > =9A=9A=9A=9A=9A=9A=9A Sort Method:=9A top-N heapsort=9A Memory: 17kB > =9A=9A=9A=9A=9A=9A=9A ->=9A Bitmap Heap Scan on ext_feeder_item i > (cost=3D13832.40..1449341.79 rows=3D617228 width=3D16) (actual > time=3D894.622..4260.441 rows=3D185625 loops=3D1) > =9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A Recheck Cond: (feed_id =3D AN= Y ('{54461, > ...}'::bigint[])) > =9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A ->=9A Bitmap Index Scan on ex= t_feeder_item_idx > (cost=3D0.00..13678.10 rows=3D617228 width=3D0) (actual > time=3D884.686..884.686 rows=3D185625 loops=3D1) > =9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A Index Cond:= (feed_id =3D 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=9A (cost=3D1463104.22..1463104.25 rows=3D11 width=3D16) (actual > time=3D9330.267..9330.298 rows=3D11 loops=3D1) > =9A ->=9A Sort=9A (cost=3D1463104.22..1464647.29 rows=3D617228 width= =3D16) > (actual time=3D9330.263..9330.273 rows=3D11 loops=3D1) > =9A=9A=9A=9A=9A=9A=9A Sort Key: pub_date, id > =9A=9A=9A=9A=9A=9A=9A Sort Method:=9A top-N heapsort=9A Memory: 17kB > =9A=9A=9A=9A=9A=9A=9A ->=9A Bitmap Heap Scan on ext_feeder_item i > (cost=3D13832.40..1449341.79 rows=3D617228 width=3D16) (actual > time=3D1018.401..8971.029 rows=3D185625 loops=3D1) > =9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A Recheck Cond: (feed_id =3D AN= Y ('{... > ,54461}'::bigint[])) > =9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A ->=9A Bitmap Index Scan on ex= t_feeder_item_idx > (cost=3D0.00..13678.10 rows=3D617228 width=3D0) (actual > time=3D1008.791..1008.791 rows=3D185625 loops=3D1) > =9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A=9A Index Cond:= (feed_id =3D 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. >=20 > 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 :) >=20 > Regards, Oleg _____________________________________________________________ Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru), Sternberg Astronomical Institute, Moscow University, Russia Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/ phone: +007(495)939-16-83, +007(495)939-23-83= From alexey.kupershtokh@gmail.com Thu May 29 09:51:38 2008 Received: from localhost (unknown [200.46.204.183]) by developer.postgresql.org (Postfix) with ESMTP id 5F7CF2E00B7 for ; Thu, 29 May 2008 06:51:38 -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 59975-10 for ; Thu, 29 May 2008 06:51:29 -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.157]) by developer.postgresql.org (Postfix) with ESMTP id 21C652E0038 for ; Thu, 29 May 2008 06:51:31 -0300 (ADT) Received: by fg-out-1718.google.com with SMTP id 16so2145555fgg.23 for ; Thu, 29 May 2008 02:51:29 -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:references:in-reply-to:content-type:content-transfer-encoding; bh=U0gsIi6ptACW5YFMcI4ZDBbtlAqFvgiMWgsNOLA2qN0=; b=R9anh7awi1IAK2pGLR/Rm/dtd7ozJnBbWp2593+J0L86txjHbO+Wpx05Xzc0gtHlnretSt9dBEiQAw9T1TlDG7JoYO+7bOoEfJJYARwrnMuJfo47Sttpv+5TMkKA6ddpLZNG6sq5XdhRtbvWMyskGn5pRxF1nYCLLyYP1TQTLYw= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:user-agent:mime-version:to:subject:references:in-reply-to:content-type:content-transfer-encoding; b=YoJiMSEOHoClkkcYzBP6wxGs0/+ZV9Vzswqii96OP9oSSZ6bmqPp+ExJ0sl3qnbMDThHV0DmkR2F521zToQdSJU1zQIURQrYPKbPXeKXw0WRH/fyOcEmJrq+Sf0kzqSS6OEEAqvhg8IHzgB1ajYBRwNKLGjuu5wDiCoq8znmFYA= Received: by 10.86.9.8 with SMTP id 8mr1395800fgi.41.1212054689483; Thu, 29 May 2008 02:51:29 -0700 (PDT) Received: from ?192.168.1.5? ( [193.33.28.71]) by mx.google.com with ESMTPS id j12sm1111941fkf.0.2008.05.29.02.51.26 (version=SSLv3 cipher=RC4-MD5); Thu, 29 May 2008 02:51:28 -0700 (PDT) Message-ID: <483E7CFB.7010800@gmail.com> Date: Thu, 29 May 2008 16:52:59 +0700 From: Alexey Kupershtokh User-Agent: Thunderbird 2.0.0.14 (Windows/20080421) MIME-Version: 1.0 To: pgsql-performance@postgresql.org Subject: Re: IN() statement values order makes 2x performance hit References: <483E799E.1070404@gmail.com> In-Reply-To: Content-Type: text/plain; charset=KOI8-R; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0.558 tagged_above=0 required=5 tests=AWL=0.558 X-Spam-Level: X-Archive-Number: 200805/368 X-Sequence-Number: 30336 Thanks for the response. I've taken a look at this feature. But it seems unapplicable to my case: this table is not a many2many relation which seems the most common case of the intarray usage. The table just stores an information about items (rss posts): what feeds (rss) are they from, and their publication date. Id in the table is PK. Oleg Bartunov wrote: > You may try contrib/intarray, which we developed specially for > denormalization. > > Oleg > On Thu, 29 May 2008, Alexey Kupershtokh wrote: > >> 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 :) >> >> > > Regards, > Oleg > _____________________________________________________________ > Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru), > Sternberg Astronomical Institute, Moscow University, Russia > Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/ > phone: +007(495)939-16-83, +007(495)939-23-83