Improved Query Performance with Variant Indexes
Patrick O'Neil (University of Massachusetts at Boston)
Dallan Quass (Stanford University)
Abstract: The read-mostly environment of data warehousing makes it possible
to use more complex indexes to speed up queries than in situations where
concurrent updates are present. The current paper presents a short review of
current indexing technology, including row-set representation by Bitmaps, and
then introduces two approaches we call Bit-Sliced indexing and Projection
indexing. A Projection index materializes all values of a column in RID
order, and a Bit-Sliced index essentially takes an orthogonal bit-by-bit view
of the same data. While some of these concepts started with the MODEL 204
product, and both Bit-Sliced and Projection indexing are now fully realized in
Sybase IQ, this is the first rigorous examination of such indexing
capabilities in the literature. We compare algorithms that become feasible
with these variant index types against algorithms using more conventional
indexes. The analysis demonstrates important performance advantages for
variant indexes in some types of SQL aggregation, predicate evaluation, and
grouping. The paper concludes by introducing a new method whereby multi-
dimensional group-by queries, reminiscent of OLAP/Datacube queries but with
more flexibility, can be very efficiently performed.
To download the paper or the extended paper, link to:
Pat O'Neil's Publication
List