performance - Why does direction of index matter in MongoDB?

Question

To quote the docs:

When creating an index, the number associated with a key specifies the direction of the index, so it should always be 1 (ascending) or -1 (descending). Direction doesn't matter for single key indexes or for random access retrieval but is important if you are doing sorts or range queries on compound indexes.

However, I see no reason why direction of the index should matter on compound indexes. Can someone please provide a further explanation (or an example)?

Answer 1

MongoDB concatenates the compound key in some way and uses it as the key in a BTree.

When finding single items - The order of the nodes in the tree is irrelevant.

If you are returning a range of nodes - The elements close to each other will be down the same branches of the tree. The closer the nodes are in the range the quicker they can be retrieved.

With a single field index - The order won't matter. If they are close together in ascending order they will also be close together in descending order.

When you have a compound key - The order starts to matter.

For example, if the key is A ascending B ascending the index might look something like this:

Row   A B
1     1 1
2     2 6
3     2 7 
4     3 4
5     3 5
6     3 6
7     5 1

A query for A ascending B descending will need to jump around the index out of order to return the rows and will be slower. For example it will return Row 1, 3, 2, 6, 5, 4, 7

A ranged query in the same order as the index will simply return the rows sequentially in the correct order.

Finding a record in a BTree takes O(Log(n)) time. Finding a range of records in order is only OLog(n) + k where k is the number of records to return.

If the records are out of order, the cost could be as high as OLog(n) * k