From: Jie Zhang <jzhang@greenplum.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
To: Mark Kirkwood <markir@paradise.net.nz>
Cc: Josh Berkus <josh@agliodbs.com>
Cc: Gavin Sherry <swm@linuxworld.com.au>
Cc: pgsql-hackers@postgresql.org, "Luke Lonergan" <LLonergan@greenplum.com>
Subject: Re: On-disk bitmap index patch
Date: Wed, 26 Jul 2006 23:21:26 -0700
Message-ID: <C0EDA976.90E7%jzhang@greenplum.com> (raw)
In-Reply-To: <29908.1153977283@sss.pgh.pa.us>
On 7/26/06 10:14 PM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> Mark Kirkwood <markir@paradise.net.nz> 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.
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: jzhang@greenplum.com, tgl@sss.pgh.pa.us, markir@paradise.net.nz, josh@agliodbs.com, swm@linuxworld.com.au, LLonergan@greenplum.com
Subject: Re: On-disk bitmap index patch
In-Reply-To: <C0EDA976.90E7%jzhang@greenplum.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox