SERVER-23138 make CanonicalQuery normalize $nor with one child to a NOT expression

3 files changed, 56 insertions, 4 deletions

diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp
index 9bbb5a169dc..00f8721a11d 100644
--- a/src/mongo/db/query/canonical_query.cpp
+++ b/src/mongo/db/query/canonical_query.cpp
@@ -268,11 +268,8 @@ bool CanonicalQuery::isSimpleIdQuery(const BSONObj& query) {
 
 // static
 MatchExpression* CanonicalQuery::normalizeTree(MatchExpression* root) {
-    // root->isLogical() is true now.  We care about AND, OR, and NOT. NOR currently scares us.
     if (MatchExpression::AND == root->matchType() || MatchExpression::OR == root->matchType()) {
-        // We could have AND of AND of AND.  Make sure we clean up our children before merging
-        // them.
-        // UNITTEST 11738048
+        // We could have AND of AND of AND.  Make sure we clean up our children before merging them.
         for (size_t i = 0; i < root->getChildVector()->size(); ++i) {
             (*root->getChildVector())[i] = normalizeTree(root->getChild(i));
         }
@@ -309,6 +306,27 @@ MatchExpression* CanonicalQuery::normalizeTree(MatchExpression* root) {
             delete root;
             return ret;
         }
+    } else if (MatchExpression::NOR == root->matchType()) {
+        // First clean up children.
+        for (size_t i = 0; i < root->getChildVector()->size(); ++i) {
+            (*root->getChildVector())[i] = normalizeTree(root->getChild(i));
+        }
+
+        // NOR of one thing is NOT of the thing.
+        if (1 == root->numChildren()) {
+            // Detach the child and assume ownership.
+            std::unique_ptr<MatchExpression> child(root->getChild(0));
+            root->getChildVector()->clear();
+
+            // Delete the root when this goes out of scope.
+            std::unique_ptr<NorMatchExpression> ownedRoot(static_cast<NorMatchExpression*>(root));
+
+            // Make a NOT to be the new root and transfer ownership of the child to it.
+            auto newRoot = stdx::make_unique<NotMatchExpression>();
+            newRoot->init(child.release());
+
+            return newRoot.release();
+        }
     } else if (MatchExpression::NOT == root->matchType()) {
         // Normalize the rest of the tree hanging off this NOT node.
         NotMatchExpression* nme = static_cast<NotMatchExpression*>(root);
diff --git a/src/mongo/db/query/canonical_query_test.cpp b/src/mongo/db/query/canonical_query_test.cpp
index 59b192aa89f..9c95d347a08 100644
--- a/src/mongo/db/query/canonical_query_test.cpp
+++ b/src/mongo/db/query/canonical_query_test.cpp
@@ -670,5 +670,27 @@ TEST(CanonicalQueryTest, SettingCollatorUpdatesCollatorAndMatchExpression) {
     ASSERT_EQUALS(inExpr->getCollator(), cq->getCollator());
 }
 
+TEST(CanonicalQueryTest, NorWithOneChildNormalizedToNot) {
+    unique_ptr<CanonicalQuery> cq(canonicalize("{$nor: [{a: 1}]}"));
+    auto root = cq->root();
+    ASSERT_EQ(MatchExpression::NOT, root->matchType());
+    ASSERT_EQ(1U, root->numChildren());
+    ASSERT_EQ(MatchExpression::EQ, root->getChild(0)->matchType());
+}
+
+TEST(CanonicalQueryTest, NorWithTwoChildrenNotNormalized) {
+    unique_ptr<CanonicalQuery> cq(canonicalize("{$nor: [{a: 1}, {b: 1}]}"));
+    auto root = cq->root();
+    ASSERT_EQ(MatchExpression::NOR, root->matchType());
+}
+
+TEST(CanonicalQueryTest, NorWithOneChildNormalizedAfterNormalizingChild) {
+    unique_ptr<CanonicalQuery> cq(canonicalize("{$nor: [{$or: [{a: 1}]}]}"));
+    auto root = cq->root();
+    ASSERT_EQ(MatchExpression::NOT, root->matchType());
+    ASSERT_EQ(1U, root->numChildren());
+    ASSERT_EQ(MatchExpression::EQ, root->getChild(0)->matchType());
+}
+
 }  // namespace
 }  // namespace mongo
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index a3e4477a568..4fc0145d0dc 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -4236,4 +4236,16 @@ TEST_F(QueryPlannerTest, NToReturnHackWithSingleBatch) {
         "{cscan: {dir:1, filter: {}}}}}}}");
 }
 
+TEST_F(QueryPlannerTest, NorWithSingleChildCanUseIndexAfterComplementingBounds) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+
+    addIndex(BSON("a" << 1));
+    runQuery(fromjson("{$nor: [{a: {$lt: 3}}]}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {filter: null, node: {ixscan: {pattern: {a: 1}, bounds:"
+        "{a: [['MinKey', -Infinity, true, false], [3, 'MaxKey', true, true]]}}}}}");
+}
+
 }  // namespace