pg.ddx.io  pgsql-hackers@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: 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: Jie Zhang <jzhang@greenplum.com>
Cc: pgsql-hackers@postgresql.org, Luke Lonergan <LLonergan@greenplum.com>
Subject: Re: On-disk bitmap index patch
Date: Wed, 26 Jul 2006 10:26:01 -0400
Message-ID: <1593.1153923961@sss.pgh.pa.us> (raw)
In-Reply-To: <44C6C8CB.9030802@paradise.net.nz>
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>
	<24309.1153860389@sss.pgh.pa.us>
	<44C6C8CB.9030802@paradise.net.nz>

I wrote:
>> ...  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.

I'm surprised no one caught me making this bogus computation.  I
realized this morning it's wrong: if there are 10000 distinct values
then on the average the 1-bits would be about 10000 bits apart, not 100.
At that rate there *is* substantial compression.  The representation
used in the bitmap patch isn't amazingly efficient for this (I wonder
whether they oughtn't use 16-bit instead of 8-bit HRL_WORDs) but it
still manages to get down to something like 11 bytes per 1-bit.  Since
each 1-bit corresponds to a btree entry, this means the bitmap does come
out somewhat smaller than a btree (16 bytes per entry ignoring overhead)
--- at least if overhead such as wasted space on a page doesn't kill it.

Still, this isn't going to make the difference between fitting in RAM or
not.  For small numbers of distinct values, like less than 100, the
bitmap representation looks more plausible.  In that range you're down
to a byte or two per entry and so there is (very roughly) a 10x storage
savings over btree.  I don't believe the 100x numbers that have been
bandied around in this discussion, but 10x is plenty enough to be
interesting.

			regards, tom lane



view thread (52+ messages)  latest in thread

Message-ID: <1593.1153923961@sss.pgh.pa.us>
Permalink:  ../1593.1153923961@sss.pgh.pa.us/
Also on:    postgresql.org/message-id/1593.1153923961@sss.pgh.pa.us

 · 

reply
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, markir@paradise.net.nz, josh@agliodbs.com, swm@linuxworld.com.au, jzhang@greenplum.com, LLonergan@greenplum.com
  Subject: Re: On-disk bitmap index patch
  In-Reply-To: <1593.1153923961@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