SERVER-65715 Implement querying for null for new optimizer

7 files changed, 130 insertions, 11 deletions

diff --git a/jstests/cqf/null_missing.js b/jstests/cqf/null_missing.js
new file mode 100644
index 00000000000..75b503636b8
--- /dev/null
+++ b/jstests/cqf/null_missing.js
@@ -0,0 +1,35 @@
+(function() {
+"use strict";
+
+load("jstests/libs/optimizer_utils.js");  // For checkCascadesOptimizerEnabled.
+if (!checkCascadesOptimizerEnabled(db)) {
+    jsTestLog("Skipping test because the optimizer is not enabled");
+    return;
+}
+
+const t = db.cqf_null_missing;
+t.drop();
+
+assert.commandWorked(t.insert({a: 2}));
+assert.commandWorked(t.insert({a: {b: null}}));
+assert.commandWorked(t.insert({a: {c: 1}}));
+
+// Generate enough documents for index to be preferable.
+for (let i = 0; i < 100; i++) {
+    assert.commandWorked(t.insert({a: {b: i + 10}}));
+}
+
+{
+    const res = t.explain("executionStats").aggregate([{$match: {'a.b': null}}]);
+    assert.eq(3, res.executionStats.nReturned);
+    assert.eq("PhysicalScan", res.queryPlanner.winningPlan.optimizerPlan.child.child.nodeType);
+}
+
+assert.commandWorked(t.createIndex({'a.b': 1}));
+
+{
+    const res = t.explain("executionStats").aggregate([{$match: {'a.b': null}}]);
+    assert.eq(3, res.executionStats.nReturned);
+    assert.eq("IndexScan", res.queryPlanner.winningPlan.optimizerPlan.child.leftChild.nodeType);
+}
+}());
diff --git a/src/mongo/db/exec/sbe/abt/sbe_abt_diff_test.cpp b/src/mongo/db/exec/sbe/abt/sbe_abt_diff_test.cpp
index 6f2fc6bc33c..7ea2a11720b 100644
--- a/src/mongo/db/exec/sbe/abt/sbe_abt_diff_test.cpp
+++ b/src/mongo/db/exec/sbe/abt/sbe_abt_diff_test.cpp
@@ -50,12 +50,16 @@ static bool compareResults(const std::vector<BSONObj>& expected,
     if (expected.size() != actual.size()) {
         std::cout << "Different result size: expected: " << expected.size()
                   << " vs actual: " << actual.size() << "\n";
-        if (!expected.empty()) {
-            std::cout << "First expected result: " << expected.front() << "\n";
+
+        std::cout << "Expected results:\n";
+        for (const auto& result : expected) {
+            std::cout << result << "\n";
         }
-        if (!actual.empty()) {
-            std::cout << "First actual result: " << actual.front() << "\n";
+        std::cout << "Actual results:\n";
+        for (const auto& result : actual) {
+            std::cout << result << "\n";
         }
+
         return false;
     }
 
@@ -227,6 +231,19 @@ TEST_F(NodeSBE, DiffTest) {
 
     ASSERT_TRUE(compare("[{$match: {a: {$elemMatch: {$elemMatch: {$lt: 6, $gt: 4}}}}}]",
                         {"{a: [[4, 5, 6], [5]]}", "{a: [4, 5, 6]}"}));
+
+    // "{a: [2]}" will not match on classic.
+    ASSERT_TRUE(compare("[{$match: {'a.b': {$eq: null}}}]",
+                        {"{a: 2}",
+                         "{}",
+                         "{a: []}",
+                         "{a: [{}]}",
+                         "{a: {b: null}}",
+                         "{a: {c: 1}}",
+                         "{a: {b: 2}}",
+                         "{a: [{b: null}, {b: 1}]}"}));
+
+    ASSERT_TRUE(compare("[{$match: {'a': {$eq: null}}}]", {"{a: 2}"}));
 }
 
 }  // namespace
diff --git a/src/mongo/db/pipeline/abt/match_expression_visitor.cpp b/src/mongo/db/pipeline/abt/match_expression_visitor.cpp
index 89d13a69bbc..867ed338da9 100644
--- a/src/mongo/db/pipeline/abt/match_expression_visitor.cpp
+++ b/src/mongo/db/pipeline/abt/match_expression_visitor.cpp
@@ -439,6 +439,16 @@ private:
                 break;
             }
 
+            case Operations::Eq: {
+                if (tag == sbe::value::TypeTags::Null) {
+                    // Handle null and missing semantics. Matching against null also implies
+                    // matching against missing.
+                    result = make<PathComposeA>(make<PathDefault>(Constant::boolean(true)),
+                                                std::move(result));
+                }
+                break;
+            }
+
             default:
                 break;
         }
diff --git a/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp b/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp
index b4a52153736..ee2bd9268a5 100644
--- a/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp
+++ b/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp
@@ -603,9 +603,9 @@ static void addElemMatchAndSargableNode(const ABT& node, ABT sargableNode, Rewri
     ctx.addNode(newNode, false /*substitute*/, true /*addExistingNodeWithNewChild*/);
 }
 
-void convertFilterToSargableNode(ABT::reference_type node,
-                                 const FilterNode& filterNode,
-                                 RewriteContext& ctx) {
+static void convertFilterToSargableNode(ABT::reference_type node,
+                                        const FilterNode& filterNode,
+                                        RewriteContext& ctx) {
     using namespace properties;
 
     const LogicalProps& props = ctx.getAboveLogicalProps();
diff --git a/src/mongo/db/query/optimizer/rewrites/path_lower.cpp b/src/mongo/db/query/optimizer/rewrites/path_lower.cpp
index c5eb294c6c8..fe149a0a608 100644
--- a/src/mongo/db/query/optimizer/rewrites/path_lower.cpp
+++ b/src/mongo/db/query/optimizer/rewrites/path_lower.cpp
@@ -244,7 +244,15 @@ void EvalFilterLowering::transport(ABT& n, const PathLambda&, ABT& lam) {
 }
 
 void EvalFilterLowering::transport(ABT& n, const PathDefault&, ABT& c) {
-    uasserted(6624135, "cannot lower default in filter");
+    const std::string& name = _prefixId.getNextId("valDefault");
+
+    n = make<LambdaAbstraction>(
+        name,
+        make<If>(make<FunctionCall>("exists", makeSeq(make<Variable>(name))),
+                 Constant::boolean(false),
+                 std::exchange(c, make<Blackhole>())));
+
+    _changed = true;
 }
 
 void EvalFilterLowering::transport(ABT& n, const PathCompare& cmp, ABT& c) {
diff --git a/src/mongo/db/query/optimizer/syntax/expr.h b/src/mongo/db/query/optimizer/syntax/expr.h
index 217fbac9e8e..93a80a76d6e 100644
--- a/src/mongo/db/query/optimizer/syntax/expr.h
+++ b/src/mongo/db/query/optimizer/syntax/expr.h
@@ -86,6 +86,10 @@ public:
         return _tag == sbe::value::TypeTags::Nothing;
     }
 
+    bool isNull() const {
+        return _tag == sbe::value::TypeTags::Null;
+    }
+
     bool isObject() const {
         return _tag == sbe::value::TypeTags::Object;
     }
diff --git a/src/mongo/db/query/optimizer/utils/utils.cpp b/src/mongo/db/query/optimizer/utils/utils.cpp
index 9b4f581a1fc..a4e54e8665f 100644
--- a/src/mongo/db/query/optimizer/utils/utils.cpp
+++ b/src/mongo/db/query/optimizer/utils/utils.cpp
@@ -485,6 +485,22 @@ public:
                                          const PathComposeA& pathComposeA,
                                          PartialSchemaReqConversion leftResult,
                                          PartialSchemaReqConversion rightResult) {
+        const auto& path1 = pathComposeA.getPath1();
+        const auto& path2 = pathComposeA.getPath2();
+        const auto& eqNull = make<PathCompare>(Operations::Eq, Constant::null());
+        const auto& pathDefault = make<PathDefault>(Constant::boolean(true));
+
+        if ((path1 == eqNull && path2 == pathDefault) ||
+            (path1 == pathDefault && path2 == eqNull)) {
+            // In order to create null bound, we need to query for Nothing or Null.
+
+            auto intervalExpr = IntervalReqExpr::makeSingularDNF(IntervalRequirement{
+                {true /*inclusive*/, Constant::null()}, {true /*inclusive*/, Constant::null()}});
+            return {PartialSchemaRequirements{
+                {PartialSchemaKey{},
+                 PartialSchemaRequirement{"" /*boundProjectionName*/, std::move(intervalExpr)}}}};
+        }
+
         return handleComposition(
             false /*isMultiplicative*/, std::move(leftResult), std::move(rightResult));
     }
@@ -596,6 +612,14 @@ public:
         return {PartialSchemaRequirements{{{}, {}}}};
     }
 
+    PartialSchemaReqConversion transport(const ABT& n, const Constant& c) {
+        if (c.isNull()) {
+            // Cannot create bounds with just NULL.
+            return {};
+        }
+        return {n};
+    }
+
     template <typename T, typename... Ts>
     PartialSchemaReqConversion transport(const ABT& n, const T& node, Ts&&...) {
         if constexpr (std::is_base_of_v<ExpressionSyntaxSort, T>) {
@@ -1038,13 +1062,30 @@ CandidateIndexMap computeCandidateIndexMap(PrefixId& prefixId,
 
 class PartialSchemaReqLowerTransport {
 public:
+    PartialSchemaReqLowerTransport(const bool hasBoundProjName)
+        : _hasBoundProjName(hasBoundProjName) {}
+
     ABT transport(const IntervalReqExpr::Atom& node) {
         const auto& interval = node.getExpr();
         const auto& lowBound = interval.getLowBound();
         const auto& highBound = interval.getHighBound();
 
         if (interval.isEquality()) {
-            return make<PathCompare>(Operations::Eq, lowBound.getBound());
+            if (auto constPtr = lowBound.getBound().cast<Constant>()) {
+                if (constPtr->isNull()) {
+                    uassert(6624163,
+                            "Cannot lower null index bound with bound projection",
+                            !_hasBoundProjName);
+                    return make<PathComposeA>(make<PathDefault>(Constant::boolean(true)),
+                                              make<PathCompare>(Operations::Eq, Constant::null()));
+                }
+                return make<PathCompare>(Operations::Eq, lowBound.getBound());
+            } else {
+                uassert(6624164,
+                        "Cannot lower variable index bound with bound projection",
+                        !_hasBoundProjName);
+                return make<PathCompare>(Operations::Eq, lowBound.getBound());
+            }
         }
 
         ABT result = make<PathIdentity>();
@@ -1083,17 +1124,21 @@ public:
     ABT lower(const IntervalReqExpr::Node& intervals) {
         return algebra::transport<false>(intervals, *this);
     }
+
+private:
+    const bool _hasBoundProjName;
 };
 
 void lowerPartialSchemaRequirement(const PartialSchemaKey& key,
                                    const PartialSchemaRequirement& req,
                                    ABT& node,
                                    const std::function<void(const ABT& node)>& visitor) {
-    PartialSchemaReqLowerTransport transport;
+    const bool hasBoundProjName = req.hasBoundProjectionName();
+    PartialSchemaReqLowerTransport transport(hasBoundProjName);
     ABT path = transport.lower(req.getIntervals());
     const bool pathIsId = path.is<PathIdentity>();
 
-    if (req.hasBoundProjectionName()) {
+    if (hasBoundProjName) {
         node = make<EvaluationNode>(req.getBoundProjectionName(),
                                     make<EvalPath>(key._path, make<Variable>(key._projectionName)),
                                     std::move(node));