X-Original-To: pgsql-hackers-postgresql.org@localhost.postgresql.org Received: from localhost (unknown [200.46.204.144]) by svr1.postgresql.org (Postfix) with ESMTP id 1C1755375F; Tue, 3 May 2005 23:52:24 -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 62434-09; Wed, 4 May 2005 02:52:13 +0000 (GMT) Received: from priv-edtnes51.telusplanet.net (outbound04.telus.net [199.185.220.223]) by svr1.postgresql.org (Postfix) with ESMTP id 1308053726; Tue, 3 May 2005 23:52:12 -0300 (ADT) Received: from localhost ([199.185.220.240]) by priv-edtnes51.telusplanet.net (InterMail vM.6.01.04.04 201-2131-118-104-20050224) with ESMTP id <20050504025216.HOTO13643.priv-edtnes51.telusplanet.net@localhost>; Tue, 3 May 2005 20:52:16 -0600 Received: from 64.180.225.200 ( [64.180.225.200]) as user a3a18850@192.168.200.1 by webmail.telus.net with HTTP; Tue, 3 May 2005 19:52:16 -0700 Message-ID: <1115175136.427838e0ae263@webmail.telus.net> Date: Tue, 3 May 2005 19:52:16 -0700 From: Mischa Sandberg To: pgsql-perform , pgsql-hackers@postgresql.org Subject: Re: [PERFORM] Bad n_distinct estimation; hacks suggested? References: <200504191209.05181.josh@agliodbs.com> <4277774F.7040205@logix-tt.com> <1115155990.4277ee16aba34@webmail.telus.net> <200505031443.44859.josh@agliodbs.com> In-Reply-To: <200505031443.44859.josh@agliodbs.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit User-Agent: Internet Messaging Program (IMP) 3.1-cvs X-Originating-IP: 64.180.225.200 X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=1.067 tagged_above=0 required=5 tests=AWL, DNS_FROM_RFC_POST, FORGED_RCVD_HELO X-Spam-Level: * X-Archive-Number: 200505/270 X-Sequence-Number: 67146 Quoting Josh Berkus : > Mischa, > > > Okay, although given the track record of page-based sampling for > > n-distinct, it's a bit like looking for your keys under the > streetlight, > > rather than in the alley where you dropped them :-) > > Bad analogy, but funny. Bad analogy? Page-sampling effort versus row-sampling effort, c'est moot. It's not good enough for stats to produce good behaviour on the average. Straight random sampling, page or row, is going to cause enough untrustworthy engine behaviour,for any %ages small enough to allow sampling from scratch at any time. I'm curious what the problem is with relying on a start-up plus incremental method, when the method in the distinct-sampling paper doesn't degenerate: you can start when the table is still empty. Constructing an index requires an initial full scan plus incremental update; what's the diff? > Unless, of course, we use indexes for sampling, which seems like a > *really > good* idea to me .... "distinct-sampling" applies for indexes, too. I started tracking the discussion of this a bit late. Smart method for this is in VLDB'92: Gennady Antoshenkov, "Random Sampling from Pseudo-ranked B+-trees". I don't think this is online anywhere, except if you have a DBLP membership. Does nybod else know better? Antoshenkov was the brains behind some of the really cool stuff in DEC Rdb (what eventually became Oracle). Compressed bitmap indices, parallel competing query plans, and smart handling of keys with hyperbolic distributions. -- Engineers think equations approximate reality. Physicists think reality approximates the equations. Mathematicians never make the connection.