CODEWITHSUNDEEP
sqlindexing
Samuel Edwin Ward
Samuel Edwin Ward

Reputation: 6675

Does the sort order of a one-column index make any difference?

I can understand how the sort order on a column in an index might make a difference if there was more than one column, but if there is only one column in the index is ascending just as good as descending?

It seems like it could just start at the end instead of the beginning if the index was sorted the wrong way.

Is there something I'm missing?

Upvotes: 1

Views: 96

Answers (1)

Gordon Linoff
Gordon Linoff

Reputation: 1269873

The sort order of the column in the index should not make a difference. However, there may be cases where there is a subtle difference.

There are different ways to implement indexes in different databases. However, they are typically tree-based data structures with the leaves containing the ordered values and "addresses" of the records where the value occurs.

Two indexes that are identical, except for the ordering of their children, will have the same performance. For equality comparisons, the process works by walking down the tree to find the value. Because the indexes are identical, two versions have an equivalent path.

Non-equality ("<" and ">") comparisons work essentially the same way, by first finding the threshold value and then scanning the index forward or backward from there.

So, the question is: would two indexes be created "identically" for ascending and descending values? This is where it gets complicated. For all practical purposes, I believe the indexes would be pretty equivalent. However, there may be some cases with a b-tree, for instance, where the splits would not be identical. This occurs due to asymmetries that arise in the tree.

For example, on the Wikipedia page describing b-trees, scroll down to the example from Knuth. At the step where "4" is inserted there is an asymmetry. The nodes are (1),(2),(3,4). With the opposite sort order, the nodes would be (4),(3),(1,2).

In the end, the indexes would probably be functionally equivalent. However, asymmetries could arise that would affect the depth of some of the leaves.

By the way, when I started thinking about this answer, I thought the correct answer was that the indexes would be identical. After thinking about it, that seems not to be the case.

Upvotes: 1

Related Questions