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 1A1349FB1E9 for ; Thu, 27 Jul 2006 13:14:53 -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 15343-04 for ; Thu, 27 Jul 2006 13:14:48 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey- Received: from mail.mi8.com (d01gw02.mi8.com [63.240.6.46]) by postgresql.org (Postfix) with ESMTP id 0D1239FB1E3 for ; Thu, 27 Jul 2006 13:14:47 -0300 (ADT) Received: from 172.16.1.148 by mail.mi8.com with ESMTP (- Welcome to Mi8 Corporation www.Mi8.com (D2)); Thu, 27 Jul 2006 12:13:25 -0400 X-Server-Uuid: 7829E76E-BB9E-4995-8473-3C0929DF7DD1 Received: from MI8NYCMAIL05.Mi8.com ([172.16.1.189]) by D01HOST02.Mi8.com with Microsoft SMTPSVC(6.0.3790.1830); Thu, 27 Jul 2006 12:13:23 -0400 Received: from 71.146.46.130 ([71.146.46.130]) by MI8NYCMAIL05.Mi8.com ( [172.16.1.77]) via Exchange Front-End Server mi8owa.mi8.com ( [172.16.1.105]) with Microsoft Exchange Server HTTP-DAV ; Thu, 27 Jul 2006 16:13:22 +0000 User-Agent: Microsoft-Entourage/11.2.5.060620 Date: Thu, 27 Jul 2006 09:13:21 -0700 Subject: Re: On-disk bitmap index patch From: "Jie Zhang" To: "Tom Lane" cc: "Mark Kirkwood" , "Josh Berkus" , "Gavin Sherry" , pgsql-hackers@postgresql.org, "Luke Lonergan" Message-ID: Thread-Topic: [HACKERS] On-disk bitmap index patch Thread-Index: Acaxl5Qg0sTRbB2KEduI7QARJITXBg== In-Reply-To: <748.1153983035@sss.pgh.pa.us> MIME-Version: 1.0 X-OriginalArrivalTime: 27 Jul 2006 16:13:23.0339 (UTC) FILETIME=[9585CDB0:01C6B197] X-WSS-ID: 68D639AA2W0848066-02-01 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=1.664 tagged_above=0 required=5 tests=AWL, FORGED_RCVD_HELO, RCVD_NUMERIC_HELO X-Spam-Level: * X-Archive-Number: 200607/1371 X-Sequence-Number: 87226 On 7/26/06 11:50 PM, "Tom Lane" wrote: > "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. Yes, you are right -- each value is still uniformly distributed. But this will be the worst case in terms of the size of a bitmap vector. As for how to model the size of a bitmap vector for an non-uniformly distributed value, that's a good question. I don't really know. But we do know the best case and the worse case.