Reordering Columns for Smaller Indexes

Abstract

Column-oriented indexes-such as projection or bitmap indexes-are compressed by run-length encoding to reduce storage and increase speed. Sorting the tables improves compression. On realistic data sets, permuting the columns in the right order before sorting can reduce the number of runs by a factor of two or more. Unfortunately, determining the best column order is NP-hard. For many cases, we prove that the number of runs in table columns is minimized if we sort columns by increasing cardinality. Experimentally, sorting based on Hilbert space-filling curves is poor at minimizing the number of runs.

to appear in Information Sciences

References in corpus (3)

• Sorting improves word-aligned bitmap indexes
• Teaching an Old Elephant New Tricks
• Attribute Value Reordering For Efficient Hybrid OLAP

Cited by in corpus (9)

• Decoding billions of integers per second through vectorization
• Hilbert curve vs Hilbert space: exploiting fractal 2D covering to increase tensor network efficiency
• Compressed bitmap indexes: beyond unions and intersections
• Sampling-based Estimation of the Number of Distinct Values in Distributed Environment
• Diamond Dicing
• Processing a Trillion Cells per Mouse Click
• MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model
• Reordering Rows for Better Compression: Beyond the Lexicographic Order
• Threshold and Symmetric Functions over Bitmaps