Bitmap index thoughts

From: Heikki Linnakangas <heikki(at)enterprisedb(dot)com>
To: swm(at)linuxworld(dot)com(dot)au, PostgreSQL-development <pgsql-hackers(at)postgresql(dot)org>
Subject: Bitmap index thoughts
Date: 2006-12-26 19:47:39
Message-ID: 45917C5B.6090709@enterprisedb.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

I've been skimming through the bitmap index patch...

A scan needs to access at least five pages:

1. B-tree index (root+others, depending on depth)
2. The auxiliary heap page
3. bitmap index meta page
4. LOV page
5. bitmap page

That seems like a lot of indirection. A high startup cost is probably ok
for typical bitmap index use cases and most of the needed pages should
stay in memory, but could we simplify this? Why do we need the auxiliary
heap, couldn't we just store the blk+offset of the LOV item directly in
the b-tree index item?

And instead of having separate LOV pages that store a number of LOV
items, how about storing each LOV item on a page of it's own, and using
the rest of the page to store the last chunk of the bitmap. That would
eliminate one page access, but more importantly, maybe we could then get
rid of all the bm_last_* attributes in BMLOVItemData that complicate the
patch quite a bit, while preserving the performance.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Andrew Dunstan 2006-12-26 19:47:41 Re: Win32 WEXITSTATUS too simplistic
Previous Message Martijn van Oosterhout 2006-12-26 18:22:21 Re: Possible documentation error