Reordering Columns for Smaller Indexes Export

@article{citeulike:5765040, 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. For many cases, we prove that the number of runs in table columns is minimized if we sort columns by increasing cardinality. Yet-maybe surprisingly-we must sometimes maximize the number of runs to minimize the index size. Experimentally, sorting based on Hilbert space-filling curves is poor at minimizing the number of runs.}, archivePrefix = {arXiv}, author = {Lemire, Daniel and Kaser, Owen}, citeulike-article-id = {5765040}, citeulike-linkout-0 = {http://arxiv.org/abs/0909.1346}, citeulike-linkout-1 = {http://arxiv.org/pdf/0909.1346}, day = {7}, eprint = {0909.1346}, month = {Sep}, posted-at = {2009-09-10 04:26:32}, priority = {2}, title = {Reordering Columns for Smaller Indexes}, url = {http://arxiv.org/abs/0909.1346}, year = {2009} }

TY - JOUR ID - citeulike:5765040 L3 - citeulike-article-id:5765040 N2 - 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. For many cases, we prove that the number of runs in table columns is minimized if we sort columns by increasing cardinality. Yet-maybe surprisingly-we must sometimes maximize the number of runs to minimize the index size. Experimentally, sorting based on Hilbert space-filling curves is poor at minimizing the number of runs. TI - Reordering Columns for Smaller Indexes AU - Lemire, Daniel AU - Kaser, Owen PY - 2009/Sep/07/ UR - http://arxiv.org/abs/0909.1346 ER -