Why does direction of index matter in MongoDB?

by

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

More Related Contents:

  1. How does sorting with an index work in MongoDB?
  2. Fastest way to remove duplicate documents in mongodb
  3. MongoDB sort documents by array elements
  4. Mongodb Aggregation Framework: Does $group use index?
  5. Higher cardinality column first in an index when involving a range?
  6. mgo – query performance seems consistently slow (500-650ms)
  7. How does the order of compound indexes matter in MongoDB performance-wise?
  8. How does MongoDB order their docs in one collection? [duplicate]
  9. Sort nested array of objects
  10. PostgreSQL LIKE query performance variations
  11. How does MongoDB sort records when no sort order is specified?
  12. How to listen for changes to a MongoDB collection?
  13. Cascade style delete in Mongoose
  14. Add new field to every document in a MongoDB collection
  15. Check that Field Exists with MongoDB
  16. ‘Failed to unlink socket file” error in MongoDB 3.0
  17. MongoDB aggregation comparison: group(), $group and MapReduce
  18. MongoDB group by array inner-elements
  19. Multiple Counts with single query in mongodb
  20. NoSQL (MongoDB) vs Lucene (or Solr) as your database [closed]
  21. Delete everything in a MongoDB database
  22. mongodb how to get max value from collections
  23. How to aggregate by year-month-day on a different timezone
  24. Problems to run examples in Meteor
  25. How to use Elasticsearch with MongoDB?
  26. Meteor: difference between names for collections, variables, publications, and subscriptions?
  27. MongoDB – how to query for a nested item inside a collection?
  28. What’s the fastest way to copy a collection within the same database?
  29. Mongoose: deep population (populate a populated field)
  30. How do I rename fields when performing search/projection in MongoDB?

Leave a Comment