Many database indexes, including bitmap indexes, are sensitive to the order of the rows in your table. Many data warehousing practitioners urge you to sort your tables to get better results, especially with Oracle systems. In fact, column-oriented database systems like Vertica are built on sorted tables.

What do I mean by sorting the rows? It turns out that finding the best row reordering is a NP-hard problem. You might as well use something cheap like lexicographical sort as a heuristic. Finding an equally scalable technique that work much better is probably impossible. Ah! But there are different ways to sort lexicographically!

We wrote a few papers on this issue including one for DOLAP 2008. Here are the slides of our presentation:

Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes

View SlideShare presentation or Upload your own. (tags: dolarp2008)

No Comments »

No comments yet.

Leave a comment

Warning: When entering a long comment, please ensure that you make copy of your text prior to submitting it. If the server should fail or if you hit a bug, you might lose your work. I am not responsible for your lost effort.

To spammers: I carefully review every single post and make sure that spam gets deleted. You are wasting your time if you are manually entering spam using this form. Read my terms of use to see what I consider to be abusive.

Example: duo plus septem is '9'. The numbers are expressed in latin numerals but you should give your answers using ordinary digits.

 

« « Previous: Leaves in the web of knowledge
Next: Measuring the diversity of recommended lists, at last » »

« Blog's main page

Powered by WordPress

© 2004-2012, (lemire at gmail dot com). This work is licensed under a Creative Commons License.