Thus, an SBI is best for database tables with a small number of records and
small cardinality attributes. For these reasons, SBIs are not considered in our performance
comparison.
Applications.of.Bitmap.Indexes
We describe two techniques, dynamic bitmap indexes and bitmap join indexes, that
are referred to as bitmap indexes in the literature but are really applications of BIs.
They can use the SBI or any other kind of BI that we present in this chapter; we
discuss them here for the sake of completeness.
The dynamic bitmap index (DBI) (Sarawagi, 1997) is a temporary structure that is
built from a permanent index as needed by a query optimizer to include or eliminate
records for selection. It is constructed dynamically from a vertically partitioned
table in which each column stores a compressed representation of the values in the
Indexing in Data Warehouses 8
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission
of Idea Group Inc. is prohibited.
corresponding attribute column. For example, if there are n different values of an
attribute, they are mapped to continuous integers and each value is represented by
logn bits, which represents its integer map. When a predicate requires a subset of
values in that column, the required values are converted to their integer maps and
represented in an in-memory array or hash table.
Pages:
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356