To improve your indexes: sort your tables!

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)

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

Leave a Reply

Your email address will not be published.

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks: 

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax

Or, you can subscribe without commenting.

You may subscribe to this blog by email.