X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org Received: from localhost (unknown [200.46.204.144]) by svr1.postgresql.org (Postfix) with ESMTP id A19F73A4BB6 for ; Mon, 13 Dec 2004 22:44:31 +0000 (GMT) Received: from svr1.postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 09317-10 for ; Mon, 13 Dec 2004 22:44:25 +0000 (GMT) Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130]) by svr1.postgresql.org (Postfix) with ESMTP id 86E6B3A622E for ; Mon, 13 Dec 2004 22:44:26 +0000 (GMT) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.13.1/8.13.1) with ESMTP id iBDMh777028821; Mon, 13 Dec 2004 17:43:07 -0500 (EST) To: Sven Willenberger Cc: pgsql-performance@postgresql.org, andrew@catalyst.net.nz Subject: Re: Using LIMIT changes index used by planner In-reply-to: <41BE1270.7060908@dmv.com> References: <41BD3317.9090507@dmv.com> <1102931789.11712.9.camel@lamb.mcmillan.net.nz> <41BE1270.7060908@dmv.com> Comments: In-reply-to Sven Willenberger message dated "Mon, 13 Dec 2004 17:06:40 -0500" Date: Mon, 13 Dec 2004 17:43:07 -0500 Message-ID: <28820.1102977787@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.006 tagged_above=0 required=5 tests=AWL X-Spam-Level: X-Archive-Number: 200412/172 X-Sequence-Number: 9547 Sven Willenberger writes: > explain analyze select storelocation,order_number from custacct where > referrer = 1365 and orderdate between '2004-12-07' and '2004-12-07 > 12:00:00' order by custacctid limit 10; > QUERY PLAN > ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- > Limit (cost=0.00..43065.76 rows=10 width=43) (actual > time=1306957.216..1307072.111 rows=10 loops=1) > -> Index Scan using custacct2_pkey on custacct > (cost=0.00..92083209.38 rows=21382 width=43) (actual > time=1306957.205..1307072.017 rows=10 loops=1) > Filter: ((referrer = 1365) AND (orderdate >= '2004-12-07 > 00:00:00'::timestamp without time zone) AND (orderdate <= '2004-12-07 > 12:00:00'::timestamp without time zone)) > Total runtime: 1307072.231 ms > (4 rows) I think this is the well-known issue of lack of cross-column correlation statistics. The planner is well aware that this indexscan will be horridly expensive if run to completion --- but it's assuming that stopping after 10 rows, or 10/21382 of the total scan, will cost only about 10/21382 as much as the whole scan would. This amounts to assuming that the rows matching the filter condition are randomly distributed among all the rows taken in custacctid order. I suspect that your test case actually has a great deal of correlation between custacctid and referrer/orderdate, such that the indexscan in custacctid order ends up fetching many more rows that fail the filter condition than random chance would suggest, before it finally comes across 10 that pass the filter. There isn't any near-term fix in the wind for this, since storing cross-column statistics is an expensive proposition that we haven't decided how to handle. Your workaround with separating the ORDER BY from the LIMIT is a good one. regards, tom lane