From: Tom Lane <tgl@sss.pgh.pa.us>
To: Jie Zhang <jzhang@greenplum.com>
Cc: 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: Thu, 27 Jul 2006 02:50:35 -0400
Message-ID: <748.1153983035@sss.pgh.pa.us> (raw)
In-Reply-To: <C0EDA976.90E7%jzhang@greenplum.com>
References: <C0EDA976.90E7%jzhang@greenplum.com>
"Jie Zhang" <jzhang@greenplum.com> writes:
> On 7/26/06 10:14 PM, "Tom Lane" <tgl@sss.pgh.pa.us> 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
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: tgl@sss.pgh.pa.us, jzhang@greenplum.com, markir@paradise.net.nz, josh@agliodbs.com, swm@linuxworld.com.au, LLonergan@greenplum.com
Subject: Re: On-disk bitmap index patch
In-Reply-To: <748.1153983035@sss.pgh.pa.us>
* 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