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 F33909FB1BC for ; Thu, 27 Jul 2006 03:22:19 -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 46522-10 for ; Thu, 27 Jul 2006 03:22:11 -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 7CAD19FA6B2 for ; Thu, 27 Jul 2006 03:21:41 -0300 (ADT) Received: from 172.16.1.112 by mail.mi8.com with ESMTP (- Welcome to Mi8 Corporation www.Mi8.com (D2)); Thu, 27 Jul 2006 02:21:32 -0400 X-Server-Uuid: 7829E76E-BB9E-4995-8473-3C0929DF7DD1 Received: from MI8NYCMAIL05.Mi8.com ([172.16.1.189]) by D01SMTP02.Mi8.com with Microsoft SMTPSVC(6.0.3790.1830); Thu, 27 Jul 2006 02:21:32 -0400 Received: from 71.146.16.17 ([71.146.16.17]) by MI8NYCMAIL05.Mi8.com ( [172.16.1.77]) via Exchange Front-End Server mi8owa.mi8.com ( [172.16.1.106]) with Microsoft Exchange Server HTTP-DAV ; Thu, 27 Jul 2006 06:21:27 +0000 User-Agent: Microsoft-Entourage/11.2.5.060620 Date: Wed, 26 Jul 2006 23:21:26 -0700 Subject: Re: On-disk bitmap index patch From: "Jie Zhang" To: "Tom Lane" , "Mark Kirkwood" cc: "Josh Berkus" , "Gavin Sherry" , pgsql-hackers@postgresql.org, "Luke Lonergan" Message-ID: Thread-Topic: [HACKERS] On-disk bitmap index patch Thread-Index: AcaxROOJIhqq0h04EduI7QARJITXBg== In-Reply-To: <29908.1153977283@sss.pgh.pa.us> MIME-Version: 1.0 X-OriginalArrivalTime: 27 Jul 2006 06:21:32.0213 (UTC) FILETIME=[E73DFE50:01C6B144] X-WSS-ID: 68D684E62W0586777-01-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.668 tagged_above=0 required=5 tests=AWL, FORGED_RCVD_HELO, RCVD_NUMERIC_HELO X-Spam-Level: * X-Archive-Number: 200607/1337 X-Sequence-Number: 87192 On 7/26/06 10:14 PM, "Tom Lane" wrote: > Mark Kirkwood writes: >> An obvious deduction is that the TPCH dataset is much more amenable to >> run compression than my synthetic Zipfian data was. The interesting >> question is how well "real" datasets are run compressable, > > Yeah --- the back-of-the-envelope calculations I was making presupposed > uniform random distribution, and we know that's often not realistic for > real datasets. 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. The constraint for this equation is \sum(p_i)=1. Therefore, when all p_i are equal, or the attribute has randomly distributed values, the size of the bitmap index is the largest.