Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.80) (envelope-from ) id 1XYmw1-0002gj-7H for pgsql-performance@arkaria.postgresql.org; Tue, 30 Sep 2014 02:13:01 +0000 Received: from localhost ([127.0.0.1] helo=postgresql.org) by malur.postgresql.org with smtp (Exim 4.80) (envelope-from ) id 1XYmw0-0007ZW-Az for pgsql-performance@arkaria.postgresql.org; Tue, 30 Sep 2014 02:13:00 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.2:DHE_RSA_AES_256_CBC_SHA256:256) (Exim 4.80) (envelope-from ) id 1XYmvz-0007ZP-3w for pgsql-performance@postgresql.org; Tue, 30 Sep 2014 02:12:59 +0000 Received: from mbx.knossos.net.nz ([202.160.48.10]) by magus.postgresql.org with esmtp (Exim 4.80) (envelope-from ) id 1XYmvq-00021y-Rz for pgsql-performance@postgresql.org; Tue, 30 Sep 2014 02:12:56 +0000 Received: from [10.1.1.3] (121-99-185-67.bng1.nct.orcon.net.nz [121.99.185.67]) (authenticated bits=0) by mbx.knossos.net.nz (8.14.4/8.14.4) with ESMTP id s8U2C0Xw019630 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NOT); Tue, 30 Sep 2014 15:12:08 +1300 Message-ID: <542A1170.2010600@archidevsys.co.nz> Date: Tue, 30 Sep 2014 15:12:00 +1300 From: Gavin Flower Organization: ArchiDevSys User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0 MIME-Version: 1.0 To: Tom Lane , Simon Riggs CC: Merlin Moncure , Josh Berkus , postgres performance list Subject: Re: Yet another abort-early plan disaster on 9.3 References: <541A2335.3060100@agliodbs.com> <541C7891.7000902@agliodbs.com> <541DC87F.3030800@agliodbs.com> <5420B71C.6010208@agliodbs.com> <13982.1412031637@sss.pgh.pa.us> In-Reply-To: <13982.1412031637@sss.pgh.pa.us> Content-Type: multipart/alternative; boundary="------------040201060604070607030107" X-Pg-Spam-Score: -1.9 (-) List-Archive: List-Help: List-ID: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: X-Mailing-List: pgsql-performance Precedence: bulk Sender: pgsql-performance-owner@postgresql.org This is a multi-part message in MIME format. --------------040201060604070607030107 Content-Type: text/plain; charset=ISO-8859-15; format=flowed Content-Transfer-Encoding: 7bit On 30/09/14 12:00, Tom Lane wrote: > Simon Riggs writes: >> The way I'm seeing it, you can't assume the LIMIT will apply to any >> IndexScan that doesn't have an index condition. If it has just a >> filter, or nothing at all, just an ordering then it could easily scan >> the whole index if the stats are wrong. > That statement applies with equal force to *any* plan with a LIMIT; > it's not just index scans. > > The real question is to what extent are the tuples satisfying the extra > filter condition randomly distributed with respect to the index order > (or physical order, if it's a seqscan). The existing cost estimation > code effectively assumes that they're perfectly uniformly distributed; > which is a good average-case assumption but can be horribly wrong in > the worst case. > > If we could settle on some other model for the probable distribution > of the matching tuples, we could adjust the cost estimates for LIMIT > accordingly. I have not enough statistics background to know what a > realistic alternative would be. > > Another possibility is to still assume a uniform distribution but estimate > for, say, a 90% probability instead of 50% probability that we'll find > enough tuples after scanning X amount of the table. Again, I'm not too > sure what that translates to in terms of the actual math, but it sounds > like something a statistics person could do in their sleep. > > I do not think we should estimate for the worst case though. If we do, > we'll hear cries of anguish from a lot of people, including many of the > same ones complaining now, because the planner stopped picking fast-start > plans even for cases where they are orders of magnitude faster than the > alternatives. > > regards, tom lane > If you analyzed the tables in most production databases, you would find that they are almost invariably not uniformly distributed. Most likely they will be clumped, and if you plotted the frequency of values of a given column in a given range against the number of blocks, you are likely to see one or more distinct peaks. If the table has been CLUSTERed on that column, then they will very likely to be in one clump spanning contiguous blocks. I suspect that there are two distinct populations: one relating to values present before the last VACUUM, and ones added since. There are so many factors to consider, pattern of CRUD operations, range of values in query, ... that probably prevent using very sophisticated approaches, but I would be happy to be proved wrong! Though I am fairly confident that if the distribution is not known in advance for a given table, then the percentage required to process to satisfy the limit is likely to be a lot larger than a uniform distribution would suggest. Would it be feasible to get a competent statistician to advise what data to collect, and to analyze it? Maybe it is possible to get a better estimate on how much of a table needs to be scanned, based on some fairly simple statistics. But unless research is done, it is probably impossible to determine what statistics might be useful, and how effective a better estimate could be. I have a nasty feeling that assuming a uniform distribution, may still end up being the best we can do - but I maybe being unduly pessimistic!. Cheers, Gavin --------------040201060604070607030107 Content-Type: text/html; charset=ISO-8859-15 Content-Transfer-Encoding: 7bit
On 30/09/14 12:00, Tom Lane wrote:
Simon Riggs <simon@2ndquadrant.com> writes:

The way I'm seeing it, you can't assume the LIMIT will apply to any
IndexScan that doesn't have an index condition. If it has just a
filter, or nothing at all, just an ordering then it could easily scan
the whole index if the stats are wrong.

That statement applies with equal force to *any* plan with a LIMIT;
it's not just index scans.

The real question is to what extent are the tuples satisfying the extra
filter condition randomly distributed with respect to the index order
(or physical order, if it's a seqscan).  The existing cost estimation
code effectively assumes that they're perfectly uniformly distributed;
which is a good average-case assumption but can be horribly wrong in
the worst case.

If we could settle on some other model for the probable distribution
of the matching tuples, we could adjust the cost estimates for LIMIT
accordingly.  I have not enough statistics background to know what a
realistic alternative would be.

Another possibility is to still assume a uniform distribution but estimate
for, say, a 90% probability instead of 50% probability that we'll find
enough tuples after scanning X amount of the table.  Again, I'm not too
sure what that translates to in terms of the actual math, but it sounds
like something a statistics person could do in their sleep.

I do not think we should estimate for the worst case though.  If we do,
we'll hear cries of anguish from a lot of people, including many of the
same ones complaining now, because the planner stopped picking fast-start
plans even for cases where they are orders of magnitude faster than the
alternatives.

			regards, tom lane



If you analyzed the tables in most production databases, you would find that they are almost invariably not uniformly distributed.

Most likely they will be clumped, and if you plotted the frequency of values of a given column in a given range against the number of blocks, you are likely to see one or more distinct peaks.  If the table has been CLUSTERed on that column, then they will very likely to be in one clump spanning contiguous blocks.

I suspect that there are two distinct populations: one relating to values present before the last VACUUM, and ones added since.

There are so many factors to consider, pattern of CRUD operations, range of values in query, ... that probably prevent using very sophisticated approaches, but I would be happy to be proved wrong!

Though I am fairly confident that if the distribution is not known in advance for a given table, then the percentage required to process to satisfy the limit is likely to be a lot larger than a uniform distribution would suggest.

Would it be feasible to get a competent statistician to advise what data to collect, and to analyze it?  Maybe it is possible to get a better estimate on how much of a table needs to be scanned, based on some fairly simple statistics.  But unless research is done, it is probably impossible to determine what statistics might be useful, and how effective a better estimate could be.
I have a nasty feeling that assuming a uniform distribution, may still end up being the best we can do - but I maybe being unduly pessimistic!.


Cheers,
Gavin
--------------040201060604070607030107--