Best way to scan on-disk bitmaps - Mailing list pgsql-hackers

From Victor Y. Yegorov
Subject Best way to scan on-disk bitmaps
Date
Msg-id 20050512192107.GA18096@mits.lv
Whole thread Raw
Responses Re: Best way to scan on-disk bitmaps  (Tom Lane <tgl@sss.pgh.pa.us>)
List pgsql-hackers
Greetings.

I have questions on how to implement on-disk bitmap scan.


I've been working on on-disk bitmaps as an ordinary Index Access Method, but
now it's clear to me, that it'll lose all it's strengths this way. One on-disk
bitmap has exactly one list of indexed table's TIDs and potentially unlimited
number of bitmaps (number of index attributes multiplied by attribute's
cardinality, to be precise).

So, for better performance, one should first retrieve all the needed bitmaps
from the index, then join all bitmaps according to the query clauses and, as
the last phase, retrieve TIDs from index, that matches final bitmap.

According to the docs "the index access method is responsible for
regurgitating the TIDs ...", but for on-disk bitmaps index scan is devided
into 3 phases. So, to perform the scan in phases, to my mind, executor
should be involved. (I'd like to mention again, that this is the first time
I got so deep inside postgres code).

I wanted to use Tom's nodeBitmap* stuff, but it's problematic a bit. Bitmaps
in nodeBitmap* are built upon list of TIDs retrieved during relation scan.
For on-disk bitmap indexes, there's no need for that, as all bitmaps are
already inside the index.

The question is: Is it possible to extend nodeBitmap functionality in such a
way, that Executor can either build bitmap after list of TIDs, obtained from
RelationScan, or ask index access method to give bitmaps it contain (and TIDs
at given position in the map later)?
This will, probably, require more functions in the pg_am catalog.

Or should I create a completely new node for on-disk bitmaps?


--

Victor Y. Yegorov


pgsql-hackers by date:

Previous
From: "Michael Paesold"
Date:
Subject: Re: patches for items from TODO list
Next
From: Tom Lane
Date:
Subject: Re: Views, views, views: Summary of Arguments