SERVER-42090 Ensure query planner produces a stable ordering of OR branches.

5 files changed, 150 insertions, 14 deletions

diff --git a/src/mongo/db/matcher/expression_tree.cpp b/src/mongo/db/matcher/expression_tree.cpp
index cb1eb248898..f03d49bce2d 100644
--- a/src/mongo/db/matcher/expression_tree.cpp
+++ b/src/mongo/db/matcher/expression_tree.cpp
@@ -217,7 +217,13 @@ bool AndMatchExpression::matchesSingleElement(const BSONElement& e, MatchDetails
 
 void AndMatchExpression::debugString(StringBuilder& debug, int indentationLevel) const {
     _debugAddSpace(debug, indentationLevel);
-    debug << "$and\n";
+    debug << "$and";
+    MatchExpression::TagData* td = getTag();
+    if (td) {
+        debug << " ";
+        td->debugString(&debug);
+    }
+    debug << "\n";
     _debugList(debug, indentationLevel);
 }
 
@@ -260,7 +266,13 @@ bool OrMatchExpression::matchesSingleElement(const BSONElement& e, MatchDetails*
 
 void OrMatchExpression::debugString(StringBuilder& debug, int indentationLevel) const {
     _debugAddSpace(debug, indentationLevel);
-    debug << "$or\n";
+    debug << "$or";
+    MatchExpression::TagData* td = getTag();
+    if (td) {
+        debug << " ";
+        td->debugString(&debug);
+    }
+    debug << "\n";
     _debugList(debug, indentationLevel);
 }
 
diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript
index ef3c6075095..b6254bcf452 100644
--- a/src/mongo/db/query/SConscript
+++ b/src/mongo/db/query/SConscript
@@ -255,6 +255,7 @@ env.CppUnitTest(
         "parsed_projection_test.cpp",
         "plan_cache_indexability_test.cpp",
         "plan_cache_test.cpp",
+        "planner_access_test.cpp",
         "planner_analysis_test.cpp",
         "planner_ixselect_test.cpp",
         "projection_ast_test.cpp",
diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp
index 580bc87fa32..581b6f84fd3 100644
--- a/src/mongo/db/query/canonical_query.cpp
+++ b/src/mongo/db/query/canonical_query.cpp
@@ -303,7 +303,7 @@ void CanonicalQuery::sortTree(MatchExpression* tree) {
     }
     std::vector<MatchExpression*>* children = tree->getChildVector();
     if (nullptr != children) {
-        std::sort(children->begin(), children->end(), matchExpressionLessThan);
+        std::stable_sort(children->begin(), children->end(), matchExpressionLessThan);
     }
 }
 
diff --git a/src/mongo/db/query/index_tag.cpp b/src/mongo/db/query/index_tag.cpp
index 61e0204d3da..6d636662f16 100644
--- a/src/mongo/db/query/index_tag.cpp
+++ b/src/mongo/db/query/index_tag.cpp
@@ -43,7 +43,9 @@ using TagType = MatchExpression::TagData::Type;
 
 namespace {
 
-bool TagComparison(const MatchExpression* lhs, const MatchExpression* rhs) {
+// Compares 'lhs' for 'rhs', using the tag-based ordering expected by the access planner. Returns a
+// negative number if 'lhs' is smaller than 'rhs', 0 if they are equal, and 1 if 'lhs' is larger.
+int tagComparison(const MatchExpression* lhs, const MatchExpression* rhs) {
     IndexTag* lhsTag = static_cast<IndexTag*>(lhs->getTag());
     size_t lhsValue = (nullptr == lhsTag) ? IndexTag::kNoIndex : lhsTag->index;
     size_t lhsPos = (nullptr == lhsTag) ? IndexTag::kNoIndex : lhsTag->pos;
@@ -55,36 +57,54 @@ bool TagComparison(const MatchExpression* lhs, const MatchExpression* rhs) {
     // First, order on indices.
     if (lhsValue != rhsValue) {
         // This relies on kNoIndex being larger than every other possible index.
-        return lhsValue < rhsValue;
+        return lhsValue < rhsValue ? -1 : 1;
     }
 
     // Next, order so that if there's a GEO_NEAR it's first.
     if (MatchExpression::GEO_NEAR == lhs->matchType()) {
-        return true;
+        return -1;
     } else if (MatchExpression::GEO_NEAR == rhs->matchType()) {
-        return false;
+        return 1;
     }
 
     // Ditto text.
     if (MatchExpression::TEXT == lhs->matchType()) {
-        return true;
+        return -1;
     } else if (MatchExpression::TEXT == rhs->matchType()) {
-        return false;
+        return 1;
     }
 
     // Next, order so that the first field of a compound index appears first.
     if (lhsPos != rhsPos) {
-        return lhsPos < rhsPos;
+        return lhsPos < rhsPos ? -1 : 1;
     }
 
     // Next, order on fields.
     int cmp = lhs->path().compare(rhs->path());
     if (0 != cmp) {
-        return 0;
+        return cmp;
+    }
+
+    // Next, order on expression type.
+    if (lhs->matchType() != rhs->matchType()) {
+        return lhs->matchType() < rhs->matchType() ? -1 : 1;
+    }
+
+    // The 'lhs' and 'rhs' are equal. Break ties by comparing child nodes.
+    const size_t numChildren = std::min(lhs->numChildren(), rhs->numChildren());
+    for (size_t childIdx = 0; childIdx < numChildren; ++childIdx) {
+        int childCompare = tagComparison(lhs->getChild(childIdx), rhs->getChild(childIdx));
+        if (childCompare != 0) {
+            return childCompare;
+        }
+    }
+
+    // If all else is equal, sort whichever node has fewer children first.
+    if (lhs->numChildren() != rhs->numChildren()) {
+        return lhs->numChildren() < rhs->numChildren() ? -1 : 1;
     }
 
-    // Finally, order on expression type.
-    return lhs->matchType() < rhs->matchType();
+    return 0;
 }
 
 // Sorts the tree using its IndexTag(s). Nodes that use the same index will sort so that they are
@@ -95,7 +115,11 @@ void sortUsingTags(MatchExpression* tree) {
     }
     std::vector<MatchExpression*>* children = tree->getChildVector();
     if (nullptr != children) {
-        std::sort(children->begin(), children->end(), TagComparison);
+        std::stable_sort(children->begin(),
+                         children->end(),
+                         [](const MatchExpression* lhs, const MatchExpression* rhs) {
+                             return tagComparison(lhs, rhs) < 0;
+                         });
     }
 }
 
diff --git a/src/mongo/db/query/planner_access_test.cpp b/src/mongo/db/query/planner_access_test.cpp
new file mode 100644
index 00000000000..52df32c871e
--- /dev/null
+++ b/src/mongo/db/query/planner_access_test.cpp
@@ -0,0 +1,99 @@
+/**
+ *    Copyright (C) 2019-present MongoDB, Inc.
+ *
+ *    This program is free software: you can redistribute it and/or modify
+ *    it under the terms of the Server Side Public License, version 1,
+ *    as published by MongoDB, Inc.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    Server Side Public License for more details.
+ *
+ *    You should have received a copy of the Server Side Public License
+ *    along with this program. If not, see
+ *    <http://www.mongodb.com/licensing/server-side-public-license>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the Server Side Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#include "mongo/platform/basic.h"
+
+#include "mongo/db/matcher/matcher.h"
+#include "mongo/db/pipeline/expression_context_for_test.h"
+#include "mongo/db/query/index_tag.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+namespace {
+
+BSONObj serializeMatcher(Matcher* matcher) {
+    BSONObjBuilder builder;
+    matcher->getMatchExpression()->serialize(&builder);
+    return builder.obj();
+}
+
+TEST(PlannerAccessTest, PrepareForAccessPlanningSortsEqualNodesByTheirChildren) {
+    boost::intrusive_ptr<ExpressionContext> expCtx{new ExpressionContextForTest()};
+    Matcher matcher{fromjson("{$or: [{x: 1, b: 1}, {y: 1, a: 1}]}"), expCtx};
+    // Before sorting for access planning, the order of the tree should be as specified in the
+    // original input BSON.
+    ASSERT_BSONOBJ_EQ(serializeMatcher(&matcher),
+                      fromjson("{$or: [{$and: [{x: {$eq: 1}}, {b: {$eq: 1}}]},"
+                               "{$and: [{y: {$eq: 1}}, {a: {$eq: 1}}]}]}"));
+
+    // The two $or nodes in the match expression tree are only differentiated by their children.
+    // After sorting in the order expected by the access planner, the $or node with the "a" child
+    // should come first.
+    prepareForAccessPlanning(matcher.getMatchExpression());
+    ASSERT_BSONOBJ_EQ(serializeMatcher(&matcher),
+                      fromjson("{$or: [{$and: [{a: {$eq: 1}}, {y: {$eq: 1}}]},"
+                               "{$and: [{b: {$eq: 1}}, {x: {$eq: 1}}]}]}"));
+}
+
+TEST(PlannerAccessTest, PrepareForAccessPlanningSortsByNumberOfChildren) {
+    boost::intrusive_ptr<ExpressionContext> expCtx{new ExpressionContextForTest()};
+    Matcher matcher{fromjson("{$or: [{a: 1, c: 1, b: 1}, {b: 1, a: 1}]}"), expCtx};
+    // Before sorting for access planning, the order of the tree should be as specified in the
+    // original input BSON.
+    ASSERT_BSONOBJ_EQ(serializeMatcher(&matcher),
+                      fromjson("{$or: [{$and: [{a: {$eq: 1}}, {c: {$eq: 1}}, {b: {$eq: 1}}]},"
+                               "{$and: [{b: {$eq: 1}}, {a: {$eq: 1}}]}]}"));
+
+    // The two $or nodes in the match expression tree are only differentiated by the number of
+    // children they have. Both have {a: {$eq: 1}} and {b: {$eq: 1}} as their first children, but
+    // one has an additional child. The node with fewer children should be sorted first.
+    prepareForAccessPlanning(matcher.getMatchExpression());
+    ASSERT_BSONOBJ_EQ(serializeMatcher(&matcher),
+                      fromjson("{$or: [{$and: [{a: {$eq: 1}}, {b: {$eq: 1}}]},"
+                               "{$and: [{a: {$eq: 1}}, {b: {$eq: 1}}, {c: {$eq: 1}}]}]}"));
+}
+
+TEST(PlannerAccessTest, PrepareForAccessPlanningSortIsStable) {
+    boost::intrusive_ptr<ExpressionContext> expCtx{new ExpressionContextForTest()};
+    Matcher matcher{fromjson("{$or: [{a: 2, b: 2}, {a: 1, b: 1}]}"), expCtx};
+    BSONObj expectedSerialization = fromjson(
+        "{$or: [{$and: [{a: {$eq: 2}}, {b: {$eq: 2}}]},"
+        "{$and: [{a: {$eq: 1}}, {b: {$eq: 1}}]}]}");
+    // Before sorting for access planning, the order of the tree should be as specified in the
+    // original input BSON.
+    ASSERT_BSONOBJ_EQ(serializeMatcher(&matcher), expectedSerialization);
+
+    // Sorting for access planning should not change the order of the match expression tree. The two
+    // $or branches are considered equal, since they only differ by their constants.
+    prepareForAccessPlanning(matcher.getMatchExpression());
+    ASSERT_BSONOBJ_EQ(serializeMatcher(&matcher), expectedSerialization);
+}
+
+}  // namespace
+}  // namespace mongo