Skip site navigation (1) Skip section navigation (2)

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 (view raw or flat)
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

pgsql-hackers by date

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

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group