Logo image
Back
Secondary bitmap indexes with vertical and horizontal partitioning
Conference proceeding

Secondary bitmap indexes with vertical and horizontal partitioning

Guadalupe Canahuate, Tan Apaydin, Ahmet Sacan and Hakan Ferhatosmanoglu
Proceedings of the 12th International Conference on extending database technology, pp.600-611
EDBT '09
03/24/2009
DOI: 10.1145/1516360.1516430

View Online

Abstract

Traditional bitmap indexes are utilized as a special type of primary or clustered indexes where the queries are answered by performing fast logical operations supported by hardware. Answers are mapped to the physical data by using the row id of each tuple. Bitmaps represent the i-th tuple in the original table with the i-th bit position of the index. Run-length compression is used to reduce the size of the bitmaps and it has been shown that ordered data is significantly better compressed. However, for large-scale and dynamic datasets it is infeasible to keep the data always sorted. Partitioning can be used to keep the data in smaller and manageable chunks, where a different bitmap index is built for each chunk. We propose a novel bitmap index design with partitioning which serves as basis for non-clustered bitmap indexes. Individual bitmaps are not stored, only an Existence Bitmap (EB) for the existing ranks of the full table is maintained. This approach improves update performance of sorted bitmaps and does not require maintaining a heap as the underlying table, nor the same ordering for all the partitions. A one dimensional index is used over the ranks to map the bits in the EB to the physical order of the data, which allows queries to run even faster. The proposed approach, called ranked Non-Clustered Bitmaps (rNCB), is compared against traditional bitmaps using FastBit and shows significant performance gains.

Details

Metrics

13 Record Views
Logo image