Improved Query Performance with Variant Indexes

Abstract

The read-mostly environment of data warehousingmakes it possible to use more complex indexes to speed upqueries than in situations where concurrent updates are present.The current paper presents a short review of current indexingtechnology, including row-set representation by Bitmaps, andthen introduces two approaches we call Bit-Sliced indexing andProjection indexing. A Projection index materializes all valuesof a column in RID order, and a Bit-Sliced index essentially takesan orthogonal bit-by-bit view of the same data. While some ofthese concepts started with the MODEL 204 product, and bothBit-Sliced and Projection indexing are now fully realized inSybase IQ, this is the first rigorous examination of such index-ing capabilities in the literature. We compare algorithms thatbecome feasible with these variant index types against algo-rithms using more conventional indexes. The analysis demon-strates important performance advantages for variant indexes insome types of SQL aggregation, predicate evaluation, and group-ing. The paper concludes by introducing a new method wherebymulti-dimensional group-by queries, reminiscent ofOLAP/Datacube queries but with more flexibility, can be very ef-ficiently performed.1.IntroductionData warehouses are large, special-purpose databases that con-tain data integrated from a number of independent sources, sup-porting clients who wish to analyze the data for trends andanomalies. The process of analysis is usually performed withqueries that aggregate, filter, and group the data in a variety ofways. Because the queries are often complex and the warehousedatabase is often very large, processing the queries quickly is acritical issue in the data warehousing environment.Data warehouses are typically updated only periodically, in abatch fashion, and during this process the warehouse is unavail-able for querying. This means a batch update process can reor-ganize data and indexes to a new optimal clustered form, in amanner that wou