pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Andrew Dunstan <andrew@dunslane.net>
To: josh@agliodbs.com
Cc: pgsql-perform <pgsql-performance@postgresql.org>
Cc: pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested?
Date: Mon, 25 Apr 2005 16:43:10 -0400
Message-ID: <426D565E.8040400@dunslane.net> (raw)
In-Reply-To: <200504251213.18565.josh@agliodbs.com>
References: <200504191209.05181.josh@agliodbs.com>
	<19276.1114442580@sss.pgh.pa.us>
	<1114454941.21529.245.camel@localhost.localdomain>
	<200504251213.18565.josh@agliodbs.com>



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





view thread (53+ messages)  latest in thread

Message-ID: <426D565E.8040400@dunslane.net>
Permalink:  ../426D565E.8040400@dunslane.net/
Also on:    postgresql.org/message-id/426D565E.8040400@dunslane.net

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-performance@postgresql.org
  Cc: andrew@dunslane.net, josh@agliodbs.com, pgsql-hackers@postgresql.org
  Subject: Re: [HACKERS] Bad n_distinct estimation; hacks suggested?
  In-Reply-To: <426D565E.8040400@dunslane.net>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox