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

Re: Question about indexes

From: Hannu Krosing <hannu(at)tm(dot)ee>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: Bruce Momjian <pgman(at)candle(dot)pha(dot)pa(dot)us>,Greg Stark <gsstark(at)mit(dot)edu>, pgsql-hackers(at)postgresql(dot)org
Subject: Re: Question about indexes
Date: 2004-01-30 23:21:42
Message-ID: 1075504902.4007.43.camel@fuji.krosing.net (view raw or flat)
Thread:
Lists: pgsql-hackers
Tom Lane kirjutas L, 31.01.2004 kell 01:02:
> Hannu Krosing <hannu(at)tm(dot)ee> writes:
> > Another idea would be using bitmaps where we have just one bit per
> > database page and do a seq scan but just over marked pages.
> 
> That seems a bit too lossy for me,

I originally thought of it in context of data-warehousing and persistent
bitmap indexes. there the use of these same bitmaps for clustering would
un-lossify this approach.

>  but I really like your later idea
> about folding.  Generalizing that a little, we can choose any fold point
> we like.  We could allocate, say, one 32-bit word per page and set the
> (i mod 32) bit when item i is fingered by the index.  After retrieving
> the heap page, we'd need to test all the valid rows that have item
> numbers matching a set bit mod 32.  On typical tables (with circa 100
> items per page) this would require testing only about 3 rows per page.
> ORing and ANDing of such bitmaps still works, with the understanding
> that it's lossy and you have to double check each retrieved tuple.
> 
> If the fold point is above about 100, your idea of keeping track of
> whether we actually set any wrapped-around bits would become useful,
> but below that I think we'd just be wasting a bit.

Not only wasting bits, but also making the code hairier - we can't just
do simple ANDs and ORs.

--------------
Hannu


In response to

pgsql-hackers by date

Next:From: Orion HenryDate: 2004-01-30 23:35:14
Subject: segfault in psql on x86_64
Previous:From: markwDate: 2004-01-30 23:07:43
Subject: Re: DBT-2 pulls PostgreSQL from CVS for STP

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