Reordering Columns for Smaller Indexes

Details Reordering Columns for Smaller Indexes Reordering Columns for Smaller Indexes

2009-09-07

arxiv.org/abs/0909.1346v8

Daniel Lemire and Owen Kaser, Reordering Columns for Smaller Indexes, Information Sciences 181 (12), 2011

Computer Science

Databases

to appear in Information Sciences

Scientific paper

10.1016/j.ins.2011.02.002

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.

Affiliated with

Also associated with

No associations

Rating

Reordering Columns for Smaller Indexes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reordering Columns for Smaller Indexes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reordering Columns for Smaller Indexes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-107458