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 EE1FE54423; Mon, 25 Apr 2005 17:43:27 -0300 (ADT) 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 14577-02; Mon, 25 Apr 2005 20:43:20 +0000 (GMT) Received: from trolak.mydnsbox2.com (ns1.mydnsbox2.com [207.44.142.118]) by svr1.postgresql.org (Postfix) with ESMTP id 315045406E; Mon, 25 Apr 2005 17:43:13 -0300 (ADT) Received: from [192.168.1.103] (cpe-024-211-165-134.nc.res.rr.com [24.211.165.134]) (authenticated (0 bits)) by trolak.mydnsbox2.com (8.11.6/8.11.6) with ESMTP id j3PJsdG27856; Mon, 25 Apr 2005 14:54:39 -0500 Message-ID: <426D565E.8040400@dunslane.net> Date: Mon, 25 Apr 2005 16:43:10 -0400 From: Andrew Dunstan User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.7) Gecko/20050417 Fedora/1.7.7-1.3.1 X-Accept-Language: en-us, en MIME-Version: 1.0 To: josh@agliodbs.com Cc: pgsql-perform , pgsql-hackers@postgresql.org Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested? References: <200504191209.05181.josh@agliodbs.com> <19276.1114442580@sss.pgh.pa.us> <1114454941.21529.245.camel@localhost.localdomain> <200504251213.18565.josh@agliodbs.com> In-Reply-To: <200504251213.18565.josh@agliodbs.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.024 tagged_above=0 required=5 tests=AWL X-Spam-Level: X-Archive-Number: 200504/713 X-Sequence-Number: 12110 Josh Berkus wrote: >Simon, Tom: > >While it's not possible to get accurate estimates from a fixed size sample, I >think it would be possible from a small but scalable sample: say, 0.1% of all >data pages on large tables, up to the limit of maintenance_work_mem. > >Setting up these samples as a % of data pages, rather than a pure random sort, >makes this more feasable; for example, a 70GB table would only need to sample >about 9000 data pages (or 70MB). Of course, larger samples would lead to >better accuracy, and this could be set through a revised GUC (i.e., >maximum_sample_size, minimum_sample_size). > >I just need a little help doing the math ... please? > > After some more experimentation, I'm wondering about some sort of adaptive algorithm, a bit along the lines suggested by Marko Ristola, but limited to 2 rounds. The idea would be that we take a sample (either of fixed size, or some small proportion of the table) , see how well it fits a larger sample (say a few times the size of the first sample), and then adjust the formula accordingly to project from the larger sample the estimate for the full population. Math not worked out yet - I think we want to ensure that the result remains bounded by [d,N]. cheers andrew