Stanford InfoLab Publication Server

Improved Query Performance with Variant Indexes

O'Neil, P. and Quass, D. (1997) Improved Query Performance with Variant Indexes. In: ACM International Conference on Management of Data (SIGMOD 1997), May 13-15, 1997, Tucson, Arizona.




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

Item Type:Conference or Workshop Item (Paper)
Uncontrolled Keywords:indexes, indexing, bitmap, data warehousing, olap
Subjects:Computer Science > Query Processing
Related URLs:Project Homepage
ID Code:253
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:01 Jan 2009 12:32

Download statistics

Repository Staff Only: item control page