Best way to scan on-disk bitmaps

From: "Victor Y(dot) Yegorov" <viy(at)mits(dot)lv>
To: Postgres Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Best way to scan on-disk bitmaps
Date: 2005-05-12 19:21:08
Message-ID: 20050512192107.GA18096@mits.lv
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: 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

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Tom Lane 2005-05-12 19:30:59 Re: Views, views, views: Summary of Arguments
Previous Message Michael Paesold 2005-05-12 19:06:28 Re: patches for items from TODO list