55

We need to create a compound index in the same order as the parameters are being queried. Does this order matter performance-wise at all?

Imagine we have a collection of all humans on earth with an index on sex (99.9% of the time "male" or "female", but string nontheless (not binary)) and an index on name.

If we would want to be able to select all people of a certain sex with a certain name, e.g. all "male"s named "John", is it better to have a compound index with sex first or name first? Why (not)?

6
  • 3
    I don't think the ordering matters performance-wise, but reuse-wise - when you create a compound index "name, sex", the index can be reused when querying "name" only (but not for "sex" only) - respectively, when you create a compound index "sex, name", the index can be reused when querying "sex" only (but not for "name" only).
    – Smutje
    Commented Nov 5, 2015 at 13:14
  • Will you ever have to sort them? Commented Nov 5, 2015 at 13:14
  • @inspired not these keys
    – Redsandro
    Commented Nov 5, 2015 at 13:43
  • It really depends on your usage. Mong has a lot of options on how you deal with indexes. You can define compound indexes or single indexes; Mongo can intersect single indexes in other to execute your query. There are other concepts, like an index to cover your query, that have some limitations. So it really depends on each specific query you want to make and their expected document format. Can you give more details about your use case?
    – cenouro
    Commented Nov 5, 2015 at 15:30
  • @MarkPieszak This question is not a dupe of that other question also "MongoDB concatenates the compound key in some way" is not a very good answer and the answer is kind of right (would be for normal compound forming of indexes) but also not
    – Sammaye
    Commented Nov 5, 2015 at 15:49

3 Answers 3

153

Redsandro,

You must consider Index Cardinality and Selectivity.


1. Index Cardinality

The index cardinality refers to how many possible values there are for a field. The field sex only has two possible values. It has a very low cardinality. Other fields such as names, usernames, phone numbers, emails, etc. will have a more unique value for every document in the collection, which is considered high cardinality.

  • Greater Cardinality

    The greater the cardinality of a field the more helpful an index will be, because indexes narrow the search space, making it a much smaller set.

    If you have an index on sex and you are looking for men named John. You would only narrow down the result space by approximately %50 if you indexed by sex first. Conversely if you indexed by name, you would immediately narrow down the result set to a minute fraction of users named John, then you would refer to those documents to check the gender.

  • Rule of Thumb

    Try to create indexes on high-cardinality keys or put high-cardinality keys first in the compound index. You can read more about it in the section on compound indexes in the book:

    MongoDB The Definitive Guide


2. Selectivity

Also, you want to use indexes selectively and write queries that limit the number of possible documents with the indexed field. To keep it simple, consider the following collection. If your index is {name:1}, If you run the query { name: "John", sex: "male"}. You will have to scan 1 document. Because you allowed MongoDB to be selective.

{_id:ObjectId(),name:"John",sex:"male"}
{_id:ObjectId(),name:"Rich",sex:"male"}
{_id:ObjectId(),name:"Mose",sex:"male"}
{_id:ObjectId(),name:"Sami",sex:"male"}
{_id:ObjectId(),name:"Cari",sex:"female"}
{_id:ObjectId(),name:"Mary",sex:"female"}

Consider the following collection. If your index is {sex:1}, If you run the query {sex: "male", name: "John"}. You will have to scan 4 documents.

{_id:ObjectId(),name:"John",sex:"male"}
{_id:ObjectId(),name:"Rich",sex:"male"}
{_id:ObjectId(),name:"Mose",sex:"male"}
{_id:ObjectId(),name:"Sami",sex:"male"}
{_id:ObjectId(),name:"Cari",sex:"female"}
{_id:ObjectId(),name:"Mary",sex:"female"}

Imagine the possible differences on a larger data set.


A little explanation of Compound Indexes

It's easy to make the wrong assumption about Compound Indexes. According to MongoDB docs on Compound Indexes.

MongoDB supports compound indexes, where a single index structure holds references to multiple fields within a collection’s documents. The following diagram illustrates an example of a compound index on two fields:

enter image description here

When you create a compound index, 1 Index will hold multiple fields. So if we index a collection by {"sex" : 1, "name" : 1}, the index will look roughly like:

["male","Rick"] -> 0x0c965148
["male","John"] -> 0x0c965149
["male","Sean"] -> 0x0cdf7859
["male","Bro"] ->> 0x0cdf7859
...
["female","Kate"] -> 0x0c965134
["female","Katy"] -> 0x0c965126
["female","Naji"] -> 0x0c965183
["female","Joan"] -> 0x0c965191
["female","Sara"] -> 0x0c965103

If we index a collection by {"name" : 1, "sex" : 1}, the index will look roughly like:

["John","male"] -> 0x0c965148
["John","female"] -> 0x0c965149
["John","male"] -> 0x0cdf7859
["Rick","male"] -> 0x0cdf7859
...
["Kate","female"] -> 0x0c965134
["Katy","female"] -> 0x0c965126
["Naji","female"] -> 0x0c965183
["Joan","female"] -> 0x0c965191
["Sara","female"] -> 0x0c965103

Having {name:1} as the Prefix will serve you much better in using compound indexes. There is much more that can be read on the topic, I hope this can offer some clarity.

10
  • 2
    You forgot to mention about selectivity for one which is very important
    – Sammaye
    Commented Nov 5, 2015 at 15:47
  • Upvoted for now. I get the theory and it makes sense. It implies though that collections are matched against compount indexes one field at a time. (As opposed to field_a == index_a && field_b == index_b, where the order wouldn't matter, which I hypothesized because it makes sense to loop through the collection only once.) Is there a source to verify this?
    – Redsandro
    Commented Nov 5, 2015 at 17:26
  • 1
    @Redsandro compound indexes are basically trees and MongoDB traverses the tree down, the easiest way to see this is to perform cardinal $ins blog.mongolab.com/2012/06/cardinal-ins most DBs implement one tree or another, but techs like MySQL tend to house much larger trees which also allow traversing up and down and side to side etc etc
    – Sammaye
    Commented Nov 5, 2015 at 17:34
  • 1
    @Redsandro checkout what i added to my answer. Commented Nov 6, 2015 at 17:53
  • 1
    @AbdullahRasheed I should have accepted this answer a long time ago.
    – Redsandro
    Commented Apr 9, 2020 at 18:09
3

I'm going to say I did an experiment on this myself, and found that there seems to be no performance penalty for using the poorly distinguished index key first. (I'm using mongodb 3.4 with wiredtiger, which may be different than mmap). I inserted 250 million documents into a new collection called items. Each doc looked like this:

{
    field1:"bob",
    field2:i + "",
    field3:i + ""

"field1" was always equal to "bob". "field2" was equal to i, so it was completely unique. First I did a search on field2, and it took over a minute to scan 250 million documents. Then I created an index like so:

`db.items.createIndex({field1:1,field2:1})`

Of course field1 is "bob" on every single document, so the index should have to search a number of items before finding the desired document. However, this was not the result I got.

I did another search on the collection after the index finished creating. This time I got results which I listed below. You'll see that "totalKeysExamined" is 1 each time. So perhaps with wired tiger or something they have figured out how to do this better. I have read the wiredtiger actually compresses index prefixes, so that may have something to do with it.

db.items.find({field1:"bob",field2:"250888000"}).explain("executionStats")

{
    "executionSuccess" : true,
    "nReturned" : 1,
    "executionTimeMillis" : 4,
    "totalKeysExamined" : 1,
    "totalDocsExamined" : 1,
    "executionStages" : {
        "stage" : "FETCH",
        "nReturned" : 1,
        "executionTimeMillisEstimate" : 0,
        "works" : 2,
        "advanced" : 1,
        ...
        "docsExamined" : 1,
        "inputStage" : {
            "stage" : "IXSCAN",
            "nReturned" : 1,
            "executionTimeMillisEstimate" : 0,
            ...
            "indexName" : "field1_1_field2_1",
            "isMultiKey" : false,
            ...
            "indexBounds" : {
                "field1" : [
                    "[\"bob\", \"bob\"]"
                ],
                "field2" : [
                    "[\"250888000\", \"250888000\"]"
                ]
            },
            "keysExamined" : 1,
            "seeks" : 1
        }
    }

Then I created an index on field3 (which has the same value as field 2). Then I searched:

db.items.find({field3:"250888000"});

It took the same 4ms as the one with the compound index. I repeated this a number of times with different values for field2 and field3 and got insignificant differences each time. This suggests that with wiredtiger, there is no performance penalty for having poor differentiation on the first field of an index.

2
  • keysExamined here means the number of distinct indexes that it looked at -- it doesn't mean the number of parts of the index that it's looking at. I think any difference between the two index orders is going to be incredibly small compared to the overall time to fetch the document, so if we wanted to get a real idea of the performance difference, we'd want to run a load testing script over a pretty long period of time.
    – klhr
    Commented May 9, 2019 at 9:34
  • 1
    I don't think your use case is a good example of low cardinality performance hit, since in the end the compound key has high cardinality. True, to retrieve the item the engine had to read one extra node of the tree ("bob") but you would't notice that; the next read behaves like a high cardinality index anyway. The problem comes when you want to find a person whose name is "john mckenzy", age 34 among 250M persons but your index is only for "age". There the engine will find the 5M records with age=34 and has to look for that particular record in that list. Here the index is useless. Commented Jul 20, 2019 at 14:55
3

Note that multiple equality predicates do not have to be ordered from most selective to least selective. This guidance has been provided in the past however it is erroneous due to the nature of B-Tree indexes and how in leaf pages, a B-Tree will store combinations of all field’s values. As such, there is exactly the same number of combinations regardless of key order.

https://www.alexbevi.com/blog/2020/05/16/optimizing-mongodb-compound-indexes-the-equality-sort-range-esr-rule/

This blog article disagrees with the accepted answer. The benchmark in the other answer also shows that it doesn't matter. The author of that article is a "Senior Technical Services Engineer at MongoDB" which sounds like a creditable person to me on this topic, so I guess the order really doesn't affect performance after all on equality fields. I'll follow the ESR rule instead.

Also consider prefixes. Filtering for { a: 1234 } won't work with a index of { b: 1, a: 1 }: https://docs.mongodb.com/manual/core/index-compound/#prefixes

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.