索引概述

介绍查询优化器首先要从索引开始。索引在计算机系统中应用非常广泛，是提高查询效率的常用手段。如果没有索引，MongoDB必须遍历集合中所有文档才能找到匹配的结果；如果存在一个适当的索引可以限制MongoDB必须检查的文档数量。

在MongoDB中，索引是一种特殊的数据结构，以一种便于遍历的方式存储集合数据的部分信息。

常见的索引有几种组织模型，其中，B-Tree索引可以看做将键值映射到有序数组中的位置；Hash索引将键值映射到无序数组中的位置。MongoDB默认采用B-Tree组织索引文件，在2.4版本后也允许建立Hash索引。

索引的创建

MongoDB索引是在集合上创建的，通过ensureIndex方法可以方便的设置索引。MongoDB集合可以创建多个索引。恰当的索引可以显著提高查询效率，但是当数据发生变动时，不仅需要修改更新文档，还要更新集合上的索引，这无疑会导致写操作要花费更多的时间。因此，MongoDB限制每个集合最多可以有64个索引，当然，只要设计合理，这个上限也是足够的。
我们用《MongoDB 权威指南》中的例子做一下修改，假设用MongoDB存储百万级用户数据，包括姓名(name), 性别(sex), 年龄(age)，电话(tel)信息。为了便于说明问题，这里只写四条数据：

> db.users.find()
{ "_id" : ObjectId("5a2f8e7bd24b2183ae3b9fab"), "name" : "Andy", "sex" : "male", "age" : 16, "tel" : "1300000001" }
{ "_id" : ObjectId("5a2f97c7eb221206e13c7c3f"), "name" : "Bale", "sex" : "male", "age" : 18, "tel" : "1300000002" }
{ "_id" : ObjectId("5a2fa15beb221206e13c7c40"), "name" : "Cindy", "sex" : "female", "age" : 17, "tel" : "1300000003" }
{ "_id" : ObjectId("5a2fa1cbeb221206e13c7c41"), "name" : "Dany", "sex" : "male", "age" : 20, "tel" : "1300000004" }

我们创建三个索引：

> db.users.ensureIndex({"age": 1, "sex": 1});
{
    "createdCollectionAutomatically" : false,
    "numIndexesBefore" : 1,
    "numIndexesAfter" : 2,
    "ok" : 1
}
> db.users.ensureIndex({"age": 1});
{
    "createdCollectionAutomatically" : false,
    "numIndexesBefore" : 2,
    "numIndexesAfter" : 3,
    "ok" : 1
}
> db.users.ensureIndex({"sex": 1, "age": 1});
{
    "createdCollectionAutomatically" : false,
    "numIndexesBefore" : 3,
    "numIndexesAfter" : 4,
    "ok" : 1
}

在创建集合时，MongoDB会默认在_id字段上创建一个唯一索引，并且不能删除。所以当我们创建第一个索引时numIndexesBefore值是1。需要注意的是，B-Tree索引是有序的，上面三个索引大致结构是：

# {"age": 1, "sex": 1}
[16, male]      ->  ObjectId("5a2f8e7bd24b2183ae3b9fab")
[17, female]    ->  ObjectId("5a2fa15beb221206e13c7c40")
[18, male]      ->  ObjectId("5a2f97c7eb221206e13c7c3f")
[20, male]      ->  ObjectId("5a2fa1cbeb221206e13c7c41")

# {"age": 1}
[16]      ->  ObjectId("5a2f8e7bd24b2183ae3b9fab")
[17]      ->  ObjectId("5a2fa15beb221206e13c7c40")
[18]      ->  ObjectId("5a2f97c7eb221206e13c7c3f")
[20]      ->  ObjectId("5a2fa1cbeb221206e13c7c41")

# {"sex": 1, "age": 1}
[female, 17]    ->  ObjectId("5a2fa15beb221206e13c7c40")
[male, 16]      ->  ObjectId("5a2f8e7bd24b2183ae3b9fab")
[male, 18]      ->  ObjectId("5a2f97c7eb221206e13c7c3f")
[male, 20]      ->  ObjectId("5a2fa1cbeb221206e13c7c41")

索引的选择

MongoDB一个集合可以创建多个索引，查询优化器为索引创建查询计划，将选择索引转换为选择查询计划或者说选择查询计划对应的游标。

由于最近版本中几乎看不到优化器的概念，我们从较早的版本中开始介绍，以MongoDB-2.4.14为例，具体的选择过程可以分为三个阶段：首先根据查询模式（Query pattern）判断是否存在CachedPlan，如果存在直接选择，这里查询模式是除了数值外其他查询条件完全相同；其次，如果没有缓存记录，查询优化器创建新查询计划并标记类型，如果类型为Optimal Plan则直接执行该Plan；最后，如果不存在Optimal Plan，MongoDB会并发尝试可能的Helpful Plan以及不使用索引的基础查询。查询优化器会对比选择表现最好的查询计划继续执行，并将查询模式与最终查询计划的映射写入CachedPlan。

Optimal Plan

Optimal Plan的索引首先应该包含所有查询的过滤字段和排序字段，其次，字段在索引中的顺序是范围过滤和排序字段位于相等字段之后。有多个Optimal Plan时，会执行第一个。

Helpful Plan

不存在Optimal Plan时，查询优化器会并发执行所有Helpful查询计划。最早得到101个结果的查询计划会被选中继续执行，并将该查询计划暂存。其他查询计划会被中止。

下面列举几个例子，为了便于说明，我们将集合文档数扩大到1000000：

> var names = ["Andy", "Bale", "Cindy", "Dany", "Emmy", "Ford", "Gill"]
> var sexs = ["male", "female"]
> for (i=0; i<1000000; i++) {
    db.users.insert(
        {"name": names[Math.floor(Math.random()*7)],
         "sex": sexs[Math.floor(Math.random()*2)],
         "age": Math.floor(Math.random()*100),
         "tel": 13000000001+i
        } 
    ); 
}

首先查询age为18的所有记录，这里只截取部分输出信息：

> db.users.find({"age": 18}).explain({"verbose": true})
{
    "cursor" : "BtreeCursor age_1_sex_1",
    "isMultiKey" : false,
    "n" : 9777,
    "nscannedObjects" : 9777,
    "nscanned" : 9777,
    "millis" : 2168,
    "allPlans" : [
        {
            "cursor" : "BtreeCursor age_1_sex_1",
            "n" : 9777,
            "nscannedObjects" : 9777,
            "nscanned" : 9777,
        }
    ],
}

根据定义“age_1_sex_1”和“age_1”对应的查询计划都是Optimal Plan，这里选取了第一个便不再查找其他Plan，所以allPlans也只有“age_1_sex_1”一个。
下面第二次查询age为18的记录，同样截取部分输出：

> db.users.find({"age": 18}).explain({"verbose": true})
{
    "cursor" : "BtreeCursor age_1_sex_1",
    "isMultiKey" : false,
    "n" : 9777,
    "nscannedObjects" : 9777,
    "nscanned" : 9777,
    "millis" : 1686,
    "allPlans" : [
        {
            "cursor" : "BtreeCursor age_1_sex_1",
            "n" : 9777,
            "nscannedObjects" : 9777,
            "nscanned" : 9777,
        }
    ],
    "oldPlan" : {
        "cursor" : "BtreeCursor age_1_sex_1",
    },
}

与第一次不同，这里多了oldPlan。注意：

• 根据查询模式查找缓存查询计划，此时如果查找age为20只有值不同，同样会命中缓存。
• 由于指定了explain()，本次查询并没有直接使用缓存计划而是需要重新评估。

缓存的查询计划在以下条件下会清空并重新评估：

• 集合收到1000次写操作
• 执行reindex
• 添加或删除索引
• mongod进程重启
• 查询时指定explain()

第三个例子，我们查询name为Andy，age为18的记录：

> db.users.find({"age": 18, "name": "Andy"}).explain({"verbose": true})
{
    "cursor" : "BtreeCursor age_1",
    "isMultiKey" : false,
    "n" : 1392,
    "nscannedObjects" : 9777,
    "nscanned" : 9777,
    "millis" : 889,
    "allPlans" : [
        {
            "cursor" : "BtreeCursor age_1",
            "n" : 1348,
            "nscannedObjects" : 9777,
            "nscanned" : 9777,
        },
        {
            "cursor" : "BtreeCursor age_1_sex_1",
            "n" : 91,
            "nscannedObjects" : 700,
            "nscanned" : 700,
        },
        {
            "cursor" : "BasicCursor",
            "n" : 0,
            "nscannedObjects" : 700,
            "nscanned" : 700,

        }
    ],
}

此次查询没有最优索引，两个索引“age_1_sex_1”和“age_1”对查询有帮助，连同基础查询总共创建三个查询计划。
评估候选查询计划会在以下情况之一发生时结束：

• 获取到所有查询结果；
• 最先得到101个查询结果（enoughCumulativeMatchesToChooseAPlan）
  上面例子中，“age_1”最先返回101个查询结果，对应的查询计划执行到最后，其他查询计划被中止。

在MongoDB较新的版本中(以3.2.10为例)，查询优化器做了很大的改变。对于每个查询，系统首先在查询计划缓存中匹配相同查询信息(Query Shape)选择查询计划；如果没有命中缓存，查询计划生成器会评估所有候选查询计划，选择一个最优计划(Winning Plan)，并将最有计划写入缓存。
当缓存命中时，系统会重新评估该缓存计划，作出是否合格的判定，并根据判定结果保留或清除缓存计划。
下面是3.2.10版本的一次查询：

replset:PRIMARY> db.users.find({"age": 18, "sex": "male"}).explain("queryPlanner")
{
    "queryPlanner" : {
        "namespace" : "date.users",
        "indexFilterSet" : false,
        "winningPlan" : {
            "stage" : "FETCH",
            "inputStage" : {
                "indexName" : "sex_1_age_1",
            }
        },
        "rejectedPlans" : [
            {
                "inputStage" : {
                    "indexName" : "age_1",
                }
            },
            {
                "inputStage" : {
                    "indexName" : "age_1_sex_1",
                }
            }
        ]
    },
}

两个版本最主要的区别就是新版本取消了直接通过规则选择Optimal Plan的逻辑，按照以前的匹配规则，有“sex_1_age_1”这样的Optimal Plan不会再执行其他Optimal Plan和Helpfun Plan。取消Optimal Pan是因为往往Optimal Plan并不是最优的。下面是MongoDB-2.4.14的两个例子，同样只截取部分信息说明：

> db.users.find({"age": 18}, {"age": 1, "sex": 1, "_id": 0}).explain("verbose")
{
    "cursor" : "BtreeCursor age_1",
    "n" : 9777,
    "nscannedObjects" : 9777,
    "nscanned" : 9777,
    "indexOnly" : false,
    "millis" : 755,
    "allPlans" : [
        {
            "cursor" : "BtreeCursor age_1",
            "n" : 9777,
            "nscannedObjects" : 9777,
            "nscanned" : 9777,
        }
    ],
}
> db.users.find({"age": 18}, {"age": 1, "sex": 1, "_id": 0}).hint("age_1_sex_1").explain("verbose")
{
    "cursor" : "BtreeCursor age_1_sex_1",
    "n" : 9777,
    "nscannedObjects" : 0,
    "indexOnly" : true,
    "millis" : 27,
    "allPlans" : [
        {
            "cursor" : "BtreeCursor age_1_sex_1",
            "n" : 9777,
            "nscannedObjects" : 0,
            "nscanned" : 9777,
        }
    ],
}

上面的两次查询中，第一次查询“age_1”首先匹配到Optimal Plan并执行到最后，用时755毫秒，“age_1_sex_1”虽然同样是Optimal Plan，但是索引的顺序排在“age_1”之后，所以没有被选中。第二次查询中通过hint显式指定“age_1_sex_1”，通过该索引查询是“indexOnly”，不需要扫描文档就可以完成查询，所以效率更高，用时只有27毫秒。

另外，查询优化器还有一个变化，匹配缓存计划由Query Pattern变为Query Shape。官网上对二者的定义分别是：

• Query pattern refers to query select conditions that differ only in the values.
• A query shape consists of a combination of query, sort, and projection specifications.

Query Pattern 关注的是Fileds，Range和Sort，而Query Shape增加了Projection。

总结

查询优化器极大提升了查询性能，随着版本的升级，虽然最新的代码中已经很难找到“optimizer”的字段，但是逻辑仍然保留并且变得更加完善。
目前，查询优化器并不能保证每次查询都是最优的，无论是OptimalPlan 还是WinningPlan都是相对的，配合hint，index filter会使查询优化器更精准。
查询优化器是一次MongoDB查询的一个重要环节，深入了解可以帮助我们更合理的设计索引，更高效的使用MongoDB。