mongodb - MongoDB中的 `$or`和 `$in`查询如何排序？

Question

这是this question的后续内容-有关上下文，请参见。

这个问题涉及链接问题的几个特殊情况-即在使用$in或$or运算符时MongoDB中的排序如何工作，以及如何确保使用索引进行排序与​​内存中排序。

$ in:

例如，假设我们有一个集合，其中文档结构为

{a: XXX, b: XXX}

...，并且我们按此顺序在 a和 b上有一个复合索引，并希望运行查询

{a: {$in: [4, 6, 2, 1, 3, 10]}, b: {$gt: 1, $lt: 6}}

如果排序在 a或 b上，将如何进行？ $in是排序的相等运算符，但在我看来，即使是这样，也无法对带有索引的 b进行排序。我认为，仅当 a值数组排在第一位时，才可以使用索引对 $in进行排序-但我不知道MongoDB是否这样做。

$ or:

由于 $or查询IIUC是作为多个查询处理的，并且大概可以使用它们各自的索引进行排序，因此排序后的结果是否以某种方式合并，或者 $or是否对所有结果强制进行内存排序？如果是前者，这个过程的时间复杂度是多少？

Answer 1

注意:该答案基于MongoDB 3.2.4。

值得在MongoDB中发现 explain() 的使用。查询的 explain() 输出(例如db.collection.explain().find(...))使您可以检查查询中使用了哪个索引，并且由于内存中db.collection.explain('executionStats')的限制，使用 SORT 还将显示查询是成功还是失败。

$ in
$in查询可以视为一系列相等查询。例如，{a: {$in: [1,3,5]}}可以被认为是{a:1}, {a:3}, {a:5}。 MongoDB将在继续查询之前对$in数组进行排序，因此{$in: [3,5,1]}与{$in: [1,3,5]}没什么不同。

假设集合的索引为

{a:1, b:1}

按a排序

  db.coll.find({a: {$in: [1,3,5]}}).sort({a:1})

MongoDB将能够使用{a:1,b:1}索引，因为可以将此查询视为{a:1}, {a:3}, {a:5}查询的并集。按{a:1}排序允许使用index prefix，因此MongoDB不需要执行内存中排序。

同样的情况也适用于查询:

  db.coll.find({a: {$in: [1,3,5]} ,b:{$gte:1, $lt:2}}).sort({a:1})

由于sort({a:1})也使用索引前缀(在这种情况下为a)，因此不需要内存中的SORT阶段。

按b排序

与按a排序相比，这是一个更有趣的情况。例如:

  db.coll.find({a: {$in: [1,3,5]}}).sort({b:1})

此查询的explain()输出将具有一个称为SORT_MERGE的阶段。请记住，查询的find()部分可以被视为{a:1}, {a:3}, {a:5}。

由于db.coll.find({a:1}).sort({b:1})索引的性质，查询SORT不需要具有内存中的{a:1,b:1}阶段:也就是说，在满足b的相等性参数之后，MongoDB可以简单地遍历(排序的)索引并返回按a排序的文档。例如，对于每个a，由于索引，已经有许多b已按b排序。

使用$in，整个查询可以认为是:

db.coll.find({a:1}).sort({b:1})

db.coll.find({a:3}).sort({b:1})

db.coll.find({a:5}).sort({b:1})

获取上面的单个查询结果，并使用b的值执行合并。该查询不需要在内存中进行排序，因为各个查询结果已经通过b进行了排序。 MongoDB只需要将(已排序的)子查询结果合并为一个结果。

同样，查询

  db.coll.find({a: {$in: [1,3,5]} ,b:{$gte:1, $lt:2}}).sort({b:1})

还使用了 SORT_MERGE阶段，与上面的查询非常相似。不同之处在于，每个查询基于每个 b(根据索引 b进行排序，按 a排序)的 b范围(而不是每个 {a:1,b:1})查询输出文档。因此，查询不需要在内存中进行排序。
$或

为了使 $or查询使用索引 every clause in the $or expression must have an index associated with it。如果满足此要求，则查询可以像 SORT_MERGE查询一样使用 $in阶段。例如:

db.coll.explain().find({$or:[{a:1},{a:3},{a:5}]}).sort({b:1})

与上面的 SORT_MERGE示例中的查询计划，索引使用和 $in阶段几乎相同。本质上，查询可以认为是:

db.coll.find({a:1}).sort({b:1})

db.coll.find({a:3}).sort({b:1})

db.coll.find({a:5}).sort({b:1})

获取上面的单个查询结果，并使用b的值执行合并。

就像前面的 $in示例一样。

但是，此查询:

db.coll.explain().find({$or:[{a:1},{b:1}]}).sort({b:1})

不能使用任何索引(因为我们没有 {b:1}索引)。该查询将导致集合扫描，并且由于没有使用索引，因此将具有内存中排序阶段。

但是，如果我们创建索引 {b:1}，则查询将像下面这样进行:

db.coll.find({a:1}).sort({b:1})

db.coll.find({b:1}).sort({b:1})

接受上面的单个查询结果，并使用b的值执行合并(由于索引{a:1,b:1}和{b:1}，该值已经在两个子查询中进行了排序)。

MongoDB将合并 {a:1}和 {b:1}查询的结果，并对结果进行合并。合并过程是线性时间，例如 O(n)。

总之，在 $or查询中，每个词都必须有一个索引，包括 sort()阶段。否则，MongoDB将必须执行内存中排序。