From: Tom Lane <tgl@sss.pgh.pa.us>
To: Josh Berkus <josh@agliodbs.com>
Cc: Gavin Sherry <swm@linuxworld.com.au>
Cc: Jie Zhang <jzhang@greenplum.com>
Cc: pgsql-hackers@postgresql.org, Luke Lonergan <LLonergan@greenplum.com>
Subject: Re: On-disk bitmap index patch
Date: Tue, 25 Jul 2006 16:46:29 -0400
Message-ID: <24309.1153860389@sss.pgh.pa.us> (raw)
In-Reply-To: <44C6652C.1020203@agliodbs.com>
References: <C0E1CD9D.8DC0%jzhang@greenplum.com>
<Pine.LNX.4.58.0607240720180.19004@linuxworld.com.au>
<28525.1153698215@sss.pgh.pa.us>
<Pine.LNX.4.58.0607240952250.19854@linuxworld.com.au>
<28750.1153700718@sss.pgh.pa.us>
<44C6652C.1020203@agliodbs.com>
Josh Berkus <josh@agliodbs.com> writes:
> One particular compelling situation for on-disk bitmaps is for terabyte
> tables where a btree index would not fit into memory. Index
> performance for an index which is 10x or more the size of RAM really
> sucks ... I can come up with some test results if you doubt that.
Sure...
> Also note that "low cardinality" is relative. For a 1 billion row
> table, a column with 10,000 values is "low-cardinality", having around
> 100,000 rows per value ... but that's still 0.01% of the table per
> value, making index use still applicable.
And your point is? Assuming a reasonable datatype like int4, a btree
index on this table would occupy say 20GB (16 bytes per entry plus
fillfactor overhead). The bitmap version would require 10,000 bitmaps
of 1G bits apiece, or 1250GB (not even counting overhead). You need
some wildly optimistic assumptions about the compressibility of the
bitmaps to get even within hailing distance of the btree, let alone
fit in RAM. A realistic assumption for the numbers you mention is
that the bitmaps have 1-bits about 100 bits apart, which means you
could get maybe 3-to-1 compression using the runlength scheme that's
in there ... leaving the bitmap a factor of 20 bigger than the btree.
AFAICS "low cardinality" has to mean just that, a few dozen distinct
values at most, for this scheme to have any hope.
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, josh@agliodbs.com, swm@linuxworld.com.au, jzhang@greenplum.com, LLonergan@greenplum.com
Subject: Re: On-disk bitmap index patch
In-Reply-To: <24309.1153860389@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