Subject Re: [IB-Architect] Question to b-tree and bitmap mechanism
Author Jim Starkey
At 11:29 AM 11/23/2002 -0000, Michael G. wrote:
>I read somewhere that IB will build up a 'bitmap' from the
>table rows (more exact: their reference entries) before reading them
>in, so that the sequence for physical access is optimized, i.e. they
>will be read in in their physical (block-)order from the database
>So I draw the conclusion that none of the m blocks will be accessed
>more than once, even if more than one matching row reside in one

That is correct.

>Then m would be the maximum block access for reading in
>all rows (assuming that each row resides on max. one block)?
>And (k+m) blocks would be the worst case cost for the whole query?


>Does the bitmap mechanism also otimize range queries on
>unique/non-unique idexes (Select * from A where > x;) ?


It also handles multi-index retrievals by computing separate
bitmaps then anding/oring the bitmaps before starting record
retrieval. This not only optimizes retrieval performance, but
simplifies and speeds up the optimizer by eliminating the need
to consider index selection.

The technique isn't original with Interbase/Firebird. It was swiped,
lock, stock, and barrel, from DEC's Rdb/ELN. It is also used in

Jim Starkey