X-Original-To: pgsql-hackers-postgresql.org@postgresql.org Received: from localhost (mx1.hub.org [200.46.208.251]) by postgresql.org (Postfix) with ESMTP id 022DF9FB1BC for ; Thu, 27 Jul 2006 03:50:55 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.208.251]) (amavisd-new, port 10024) with ESMTP id 51077-05 for ; Thu, 27 Jul 2006 03:50:44 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey- Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130]) by postgresql.org (Postfix) with ESMTP id 52F989FB1BA for ; Thu, 27 Jul 2006 03:50:44 -0300 (ADT) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.13.6/8.13.6) with ESMTP id k6R6oaDn000749; Thu, 27 Jul 2006 02:50:36 -0400 (EDT) To: "Jie Zhang" cc: "Mark Kirkwood" , "Josh Berkus" , "Gavin Sherry" , pgsql-hackers@postgresql.org, "Luke Lonergan" Subject: Re: On-disk bitmap index patch In-reply-to: References: Comments: In-reply-to "Jie Zhang" message dated "Wed, 26 Jul 2006 23:21:26 -0700" Date: Thu, 27 Jul 2006 02:50:35 -0400 Message-ID: <748.1153983035@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0.039 tagged_above=0 required=5 tests=AWL, SPF_HELO_PASS, SPF_PASS X-Spam-Level: X-Archive-Number: 200607/1338 X-Sequence-Number: 87193 "Jie Zhang" writes: > On 7/26/06 10:14 PM, "Tom Lane" wrote: >> ... A nonuniform distribution would probably mean that some >> of the bitmaps compress better-than-expected and others worse. I have >> no idea how to model that and guess what the overall result is ... > The paper "Optimizing Bitmap Indices With Efficient Compression" by Kesheng > Wu et al gave an approximate answer for this question. Assume that there are > c distinct values. Let the i-th value has a probability of p_i, the number > of rows r, and the word size w. then the total size of the compressed bitmap > index is about (N/(w-1))(c- \sum(1-p_i)^(2w-2) - \sum(p_i)^(2w-2)), where in > both \sum's, i is from 1 to c. Hm, but that's still begging the question no? It's still assuming that any one value is uniformly distributed. ISTM the cases that would break my simplistic calculation involve clustering of particular values, such that some areas of the bitmap are all-zero while other areas have lots of ones. regards, tom lane