Received: from localhost (unknown [200.46.204.183]) by mail.postgresql.org (Postfix) with ESMTP id 9603165042B for ; Fri, 12 Dec 2008 15:11:19 -0400 (AST) Received: from mail.postgresql.org ([200.46.204.86]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 35418-02-6 for ; Fri, 12 Dec 2008 15:11:16 -0400 (AST) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from mail-bw0-f14.google.com (mail-bw0-f14.google.com [209.85.218.14]) by mail.postgresql.org (Postfix) with ESMTP id B5B3F6502A5 for ; Fri, 12 Dec 2008 15:11:11 -0400 (AST) Received: by bwz7 with SMTP id 7so3617333bwz.19 for ; Fri, 12 Dec 2008 11:11:09 -0800 (PST) Received: by 10.223.116.205 with SMTP id n13mr4531863faq.103.1229108919137; Fri, 12 Dec 2008 11:08:39 -0800 (PST) Received: by 10.223.125.139 with HTTP; Fri, 12 Dec 2008 11:08:38 -0800 (PST) Message-ID: <4136ffa0812121108i7b75490cq93f599adfd6f564a@mail.gmail.com> Date: Fri, 12 Dec 2008 19:08:38 +0000 From: "Greg Stark" To: "Simon Riggs" Subject: Re: benchmarking the query planner Cc: "Tom Lane" , "Robert Haas" , "Kevin Grittner" , "jd@commandprompt.com" , "Josh Berkus" , "Greg Smith" , pgsql-hackers@postgresql.org In-Reply-To: <1229106717.8673.88.camel@ebony.2ndQuadrant> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <603c8f070812061019r5aca3aajeaa5493b11c5feff@mail.gmail.com> <1229039044.13078.193.camel@hp_dx2400_1> <4136ffa0812111823u645b6ec9wdca60b3da4b00499@mail.gmail.com> <1229072675.13078.196.camel@hp_dx2400_1> <603c8f070812120344m67ef2c1fs41806cfb4ff9e396@mail.gmail.com> <1229093975.13078.275.camel@ebony.2ndQuadrant> <87tz99s7bu.fsf@oxford.xeocode.com> <1229100057.8673.29.camel@ebony.2ndQuadrant> <8020.1229105929@sss.pgh.pa.us> <1229106717.8673.88.camel@ebony.2ndQuadrant> X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0 tagged_above=0 required=5 tests=none X-Spam-Level: X-Archive-Number: 200812/990 X-Sequence-Number: 129619 On Fri, Dec 12, 2008 at 6:31 PM, Simon Riggs wrote: > > Why not keep the random algorithm we have now, but scan the block into a > separate hash table for ndistinct estimation. That way we keep the > correct random rows for other purposes. It seems to me that what you have to do is look at a set of blocks and judge a) how many duplicates are in the typical block and b) how much overlap there are between blocks. Then extrapolate to other blocks based on those two values. So for example if you look at 1% of the blocks and find there are 27 distinct values on each of the blocks then you extrapolate that there are somewhere between 100*27 distinct values table-wide (if those blocks have no intersections) and 27 distinct values total (if those blocks intersect 100% -- ie, they all have the same 27 distinct values). I haven't had a chance to read that paper, it looks extremely dense. Is this the same idea? -- greg