SERVER-62795 Bind values for parameterized queries in SBE RuntimeEnvironment

13 files changed, 572 insertions, 100 deletions

diff --git a/src/mongo/db/SConscript b/src/mongo/db/SConscript
index 49dd3a75584..7a19ef8fcc7 100644
--- a/src/mongo/db/SConscript
+++ b/src/mongo/db/SConscript
@@ -1360,6 +1360,8 @@ env.Library(
         'pipeline/pipeline_d.cpp',
         'pipeline/plan_executor_pipeline.cpp',
         'pipeline/plan_explainer_pipeline.cpp',
+        'query/all_indices_required_checker.cpp',
+        'query/bind_input_params.cpp',
         'query/classic_stage_builder.cpp',
         'query/explain.cpp',
         'query/find.cpp',
@@ -1376,7 +1378,6 @@ env.Library(
         'query/plan_ranker.cpp',
         'query/plan_yield_policy_impl.cpp',
         'query/plan_yield_policy_sbe.cpp',
-        'query/all_indices_required_checker.cpp',
         'query/sbe_cached_solution_planner.cpp',
         'query/sbe_multi_planner.cpp',
         'query/sbe_plan_ranker.cpp',
diff --git a/src/mongo/db/matcher/expression_leaf.h b/src/mongo/db/matcher/expression_leaf.h
index 015dae13010..4359b6f1c3c 100644
--- a/src/mongo/db/matcher/expression_leaf.h
+++ b/src/mongo/db/matcher/expression_leaf.h
@@ -812,12 +812,20 @@ public:
 
     std::string name() const;
 
-    void setInputParamId(InputParamId paramId) {
-        _inputParamId = paramId;
+    void setBitPositionsParamId(InputParamId paramId) {
+        _bitPositionsParamId = paramId;
     }
 
-    boost::optional<InputParamId> getInputParamId() const {
-        return _inputParamId;
+    void setBitMaskParamId(InputParamId paramId) {
+        _bitMaskParamId = paramId;
+    }
+
+    boost::optional<InputParamId> getBitPositionsParamId() const {
+        return _bitPositionsParamId;
+    }
+
+    boost::optional<InputParamId> getBitMaskParamId() const {
+        return _bitMaskParamId;
     }
 
 private:
@@ -852,7 +860,11 @@ private:
     // Used to perform bit tests against numbers using a single bitwise operation.
     uint64_t _bitMask = 0;
 
-    boost::optional<InputParamId> _inputParamId;
+    // When this expression is parameterized, we require two parmeter markers, not one: a parameter
+    // marker for the vector of bit positions and a second for the bitmask. The runtime plan
+    // needs both values so that it can operate against either BinData or numerical inputs.
+    boost::optional<InputParamId> _bitPositionsParamId;
+    boost::optional<InputParamId> _bitMaskParamId;
 };
 
 class BitsAllSetMatchExpression : public BitTestMatchExpression {
@@ -881,8 +893,11 @@ public:
         if (getTag()) {
             bitTestMatchExpression->setTag(getTag()->clone());
         }
-        if (getInputParamId()) {
-            bitTestMatchExpression->setInputParamId(*getInputParamId());
+        if (getBitPositionsParamId()) {
+            bitTestMatchExpression->setBitPositionsParamId(*getBitPositionsParamId());
+        }
+        if (getBitMaskParamId()) {
+            bitTestMatchExpression->setBitMaskParamId(*getBitMaskParamId());
         }
         return bitTestMatchExpression;
     }
@@ -922,8 +937,11 @@ public:
         if (getTag()) {
             bitTestMatchExpression->setTag(getTag()->clone());
         }
-        if (getInputParamId()) {
-            bitTestMatchExpression->setInputParamId(*getInputParamId());
+        if (getBitPositionsParamId()) {
+            bitTestMatchExpression->setBitPositionsParamId(*getBitPositionsParamId());
+        }
+        if (getBitMaskParamId()) {
+            bitTestMatchExpression->setBitMaskParamId(*getBitMaskParamId());
         }
         return bitTestMatchExpression;
     }
@@ -963,8 +981,11 @@ public:
         if (getTag()) {
             bitTestMatchExpression->setTag(getTag()->clone());
         }
-        if (getInputParamId()) {
-            bitTestMatchExpression->setInputParamId(*getInputParamId());
+        if (getBitPositionsParamId()) {
+            bitTestMatchExpression->setBitPositionsParamId(*getBitPositionsParamId());
+        }
+        if (getBitMaskParamId()) {
+            bitTestMatchExpression->setBitMaskParamId(*getBitMaskParamId());
         }
         return bitTestMatchExpression;
     }
@@ -1004,8 +1025,11 @@ public:
         if (getTag()) {
             bitTestMatchExpression->setTag(getTag()->clone());
         }
-        if (getInputParamId()) {
-            bitTestMatchExpression->setInputParamId(*getInputParamId());
+        if (getBitPositionsParamId()) {
+            bitTestMatchExpression->setBitPositionsParamId(*getBitPositionsParamId());
+        }
+        if (getBitMaskParamId()) {
+            bitTestMatchExpression->setBitMaskParamId(*getBitMaskParamId());
         }
         return bitTestMatchExpression;
     }
diff --git a/src/mongo/db/matcher/expression_parameterization.cpp b/src/mongo/db/matcher/expression_parameterization.cpp
index de761274c8c..0434222e0ec 100644
--- a/src/mongo/db/matcher/expression_parameterization.cpp
+++ b/src/mongo/db/matcher/expression_parameterization.cpp
@@ -32,20 +32,25 @@
 #include <cmath>
 
 namespace mongo {
+void MatchExpressionParameterizationVisitor::visitBitTestExpression(BitTestMatchExpression* expr) {
+    expr->setBitPositionsParamId(_context->nextInputParamId());
+    expr->setBitMaskParamId(_context->nextInputParamId());
+}
+
 void MatchExpressionParameterizationVisitor::visit(BitsAllClearMatchExpression* expr) {
-    expr->setInputParamId(_context->nextInputParamId());
+    visitBitTestExpression(expr);
 }
 
 void MatchExpressionParameterizationVisitor::visit(BitsAllSetMatchExpression* expr) {
-    expr->setInputParamId(_context->nextInputParamId());
+    visitBitTestExpression(expr);
 }
 
 void MatchExpressionParameterizationVisitor::visit(BitsAnyClearMatchExpression* expr) {
-    expr->setInputParamId(_context->nextInputParamId());
+    visitBitTestExpression(expr);
 }
 
 void MatchExpressionParameterizationVisitor::visit(BitsAnySetMatchExpression* expr) {
-    expr->setInputParamId(_context->nextInputParamId());
+    visitBitTestExpression(expr);
 }
 
 void MatchExpressionParameterizationVisitor::visit(EqualityMatchExpression* expr) {
diff --git a/src/mongo/db/matcher/expression_parameterization.h b/src/mongo/db/matcher/expression_parameterization.h
index c88e3ab01ee..2a28c4dae6b 100644
--- a/src/mongo/db/matcher/expression_parameterization.h
+++ b/src/mongo/db/matcher/expression_parameterization.h
@@ -141,6 +141,8 @@ public:
 private:
     void visitComparisonMatchExpression(ComparisonMatchExpressionBase* expr);
 
+    void visitBitTestExpression(BitTestMatchExpression* expr);
+
     MatchExpressionParameterizationVisitorContext* _context;
 };
 
diff --git a/src/mongo/db/matcher/expression_parameterization_test.cpp b/src/mongo/db/matcher/expression_parameterization_test.cpp
index 37874a421d8..2d9624b9590 100644
--- a/src/mongo/db/matcher/expression_parameterization_test.cpp
+++ b/src/mongo/db/matcher/expression_parameterization_test.cpp
@@ -71,40 +71,40 @@ TEST(MatchExpressionParameterizationVisitor, AlwaysTrueMatchExpressionSetsNoPara
     ASSERT_EQ(0, context.inputParamIds.size());
 }
 
-TEST(MatchExpressionParameterizationVisitor, BitsAllClearMatchExpressionSetsOneParamId) {
+TEST(MatchExpressionParameterizationVisitor, BitsAllClearMatchExpressionSetsTwoParamIds) {
     std::vector<uint32_t> bitPositions;
     BitsAllClearMatchExpression expr{"a", bitPositions};
     MatchExpressionParameterizationTestVisitorContext context{};
     MatchExpressionParameterizationVisitor visitor{&context};
     expr.acceptVisitor(&visitor);
-    ASSERT_EQ(1, context.inputParamIds.size());
+    ASSERT_EQ(2, context.inputParamIds.size());
 }
 
-TEST(MatchExpressionParameterizationVisitor, BitsAllSetMatchExpressionSetsOneParamId) {
+TEST(MatchExpressionParameterizationVisitor, BitsAllSetMatchExpressionSetsTwoParamIds) {
     std::vector<uint32_t> bitPositions;
     BitsAllSetMatchExpression expr{"a", bitPositions};
     MatchExpressionParameterizationTestVisitorContext context{};
     MatchExpressionParameterizationVisitor visitor{&context};
     expr.acceptVisitor(&visitor);
-    ASSERT_EQ(1, context.inputParamIds.size());
+    ASSERT_EQ(2, context.inputParamIds.size());
 }
 
-TEST(MatchExpressionParameterizationVisitor, BitsAnyClearMatchExpressionSetsOneParamId) {
+TEST(MatchExpressionParameterizationVisitor, BitsAnyClearMatchExpressionSetsTwoParamIds) {
     std::vector<uint32_t> bitPositions{0, 1, 8};
     BitsAnyClearMatchExpression expr{"a", bitPositions};
     MatchExpressionParameterizationTestVisitorContext context{};
     MatchExpressionParameterizationVisitor visitor{&context};
     expr.acceptVisitor(&visitor);
-    ASSERT_EQ(1, context.inputParamIds.size());
+    ASSERT_EQ(2, context.inputParamIds.size());
 }
 
-TEST(MatchExpressionParameterizationVisitor, BitsAnySetMatchExpressionSetsOneParamId) {
+TEST(MatchExpressionParameterizationVisitor, BitsAnySetMatchExpressionSetsTwoParamIds) {
     std::vector<uint32_t> bitPositions{0, 1, 8};
     BitsAnySetMatchExpression expr{"a", bitPositions};
     MatchExpressionParameterizationTestVisitorContext context{};
     MatchExpressionParameterizationVisitor visitor{&context};
     expr.acceptVisitor(&visitor);
-    ASSERT_EQ(1, context.inputParamIds.size());
+    ASSERT_EQ(2, context.inputParamIds.size());
 }
 
 TEST(MatchExpressionParameterizationVisitor,
diff --git a/src/mongo/db/matcher/expression_type.h b/src/mongo/db/matcher/expression_type.h
index 889c9f8da66..3728a97fac5 100644
--- a/src/mongo/db/matcher/expression_type.h
+++ b/src/mongo/db/matcher/expression_type.h
@@ -70,17 +70,6 @@ public:
      */
     virtual StringData name() const = 0;
 
-    std::unique_ptr<MatchExpression> shallowClone() const final {
-        auto expr = std::make_unique<T>(path(), _typeSet, _errorAnnotation);
-        if (getTag()) {
-            expr->setTag(getTag()->clone());
-        }
-        if (getInputParamId()) {
-            expr->setInputParamId(*getInputParamId());
-        }
-        return expr;
-    }
-
     bool matchesSingleElement(const BSONElement& elem, MatchDetails* details = nullptr) const {
         return _typeSet.hasType(elem.type());
     }
@@ -125,14 +114,6 @@ public:
         return _typeSet;
     }
 
-    void setInputParamId(InputParamId paramId) {
-        _inputParamId = paramId;
-    }
-
-    boost::optional<InputParamId> getInputParamId() const {
-        return _inputParamId;
-    }
-
 private:
     ExpressionOptimizerFunc getOptimizer() const final {
         return [](std::unique_ptr<MatchExpression> expression) { return expression; };
@@ -140,8 +121,6 @@ private:
 
     // The set of matching types.
     MatcherTypeSet _typeSet;
-
-    boost::optional<InputParamId> _inputParamId;
 };
 
 class TypeMatchExpression final : public TypeMatchExpressionBase<TypeMatchExpression> {
@@ -161,6 +140,17 @@ public:
         return kName;
     }
 
+    std::unique_ptr<MatchExpression> shallowClone() const final {
+        auto expr = std::make_unique<TypeMatchExpression>(path(), typeSet(), _errorAnnotation);
+        if (getTag()) {
+            expr->setTag(getTag()->clone());
+        }
+        if (getInputParamId()) {
+            expr->setInputParamId(*getInputParamId());
+        }
+        return expr;
+    }
+
     void acceptVisitor(MatchExpressionMutableVisitor* visitor) final {
         visitor->visit(this);
     }
@@ -168,6 +158,17 @@ public:
     void acceptVisitor(MatchExpressionConstVisitor* visitor) const final {
         visitor->visit(this);
     }
+
+    void setInputParamId(InputParamId paramId) {
+        _inputParamId = paramId;
+    }
+
+    boost::optional<InputParamId> getInputParamId() const {
+        return _inputParamId;
+    }
+
+private:
+    boost::optional<InputParamId> _inputParamId;
 };
 
 /**
@@ -193,6 +194,15 @@ public:
         return kName;
     }
 
+    std::unique_ptr<MatchExpression> shallowClone() const final {
+        auto expr =
+            std::make_unique<InternalSchemaTypeExpression>(path(), typeSet(), _errorAnnotation);
+        if (getTag()) {
+            expr->setTag(getTag()->clone());
+        }
+        return expr;
+    }
+
     MatchCategory getCategory() const final {
         return MatchCategory::kOther;
     }
@@ -308,6 +318,15 @@ public:
         return kName;
     }
 
+    std::unique_ptr<MatchExpression> shallowClone() const final {
+        auto expr = std::make_unique<InternalSchemaBinDataEncryptedTypeExpression>(
+            path(), typeSet(), _errorAnnotation);
+        if (getTag()) {
+            expr->setTag(getTag()->clone());
+        }
+        return expr;
+    }
+
     MatchCategory getCategory() const final {
         return MatchCategory::kOther;
     }
diff --git a/src/mongo/db/query/bind_input_params.cpp b/src/mongo/db/query/bind_input_params.cpp
new file mode 100644
index 00000000000..5da6699a61e
--- /dev/null
+++ b/src/mongo/db/query/bind_input_params.cpp
@@ -0,0 +1,309 @@
+/**
+ *    Copyright (C) 2022-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/db/query/bind_input_params.h"
+
+#include "mongo/db/exec/sbe/values/bson.h"
+#include "mongo/db/exec/sbe/values/value.h"
+#include "mongo/db/matcher/expression_array.h"
+#include "mongo/db/matcher/expression_where.h"
+#include "mongo/db/query/sbe_stage_builder_filter.h"
+
+namespace mongo::input_params {
+namespace {
+
+class MatchExpressionParameterBindingVisitor final : public MatchExpressionConstVisitor {
+public:
+    MatchExpressionParameterBindingVisitor(
+        const stage_builder::InputParamToSlotMap& inputParamToSlotMap,
+        sbe::RuntimeEnvironment* runtimeEnvironment)
+        : _inputParamToSlotMap(inputParamToSlotMap), _runtimeEnvironment(runtimeEnvironment) {
+        invariant(_runtimeEnvironment);
+    }
+
+    void visit(const BitsAllClearMatchExpression* expr) final {
+        visitBitTestExpression(expr);
+    }
+    void visit(const BitsAllSetMatchExpression* expr) final {
+        visitBitTestExpression(expr);
+    }
+    void visit(const BitsAnyClearMatchExpression* expr) final {
+        visitBitTestExpression(expr);
+    }
+    void visit(const BitsAnySetMatchExpression* expr) final {
+        visitBitTestExpression(expr);
+    }
+
+    void visit(const EqualityMatchExpression* expr) final {
+        visitComparisonMatchExpression(expr);
+    }
+    void visit(const GTEMatchExpression* expr) final {
+        visitComparisonMatchExpression(expr);
+    }
+    void visit(const GTMatchExpression* expr) final {
+        visitComparisonMatchExpression(expr);
+    }
+    void visit(const LTEMatchExpression* expr) final {
+        visitComparisonMatchExpression(expr);
+    }
+    void visit(const LTMatchExpression* expr) final {
+        visitComparisonMatchExpression(expr);
+    }
+
+    void visit(const InMatchExpression* expr) final {
+        auto inputParam = expr->getInputParamId();
+        if (!inputParam) {
+            return;
+        }
+
+        // The parameterization logic upstream should not have added a parameter marker if the $in
+        // contains any regexes.
+        tassert(6279503, "Unexpected parameter marker for $in with regexes", !expr->hasRegex());
+
+        auto&& [arrSetTag, arrSetVal, hasArray, hasNull] =
+            stage_builder::convertInExpressionEqualities(expr);
+        // Auto-parameterization should not kick in if the $in's list of equalities includes either
+        // any arrays or any nulls.
+        tassert(6279504, "Should not auto-parameterize $in with an array value", !hasArray);
+        tassert(6279505, "Should not auto-parameterize $in with a null value", !hasNull);
+
+        bindParam(*inputParam, true /*owned*/, arrSetTag, arrSetVal);
+    }
+
+    void visit(const ModMatchExpression* expr) final {
+        // Either both input parameter ids should be present, or neither should.
+        auto divisorParam = expr->getDivisorInputParamId();
+        auto remainderParam = expr->getRemainderInputParamId();
+        if (!divisorParam) {
+            tassert(6279507, "$mod had remainder param but not divisor param", !remainderParam);
+            return;
+        }
+        tassert(6279508, "$mod had divisor param but not remainder param", remainderParam);
+
+        {
+            auto value = sbe::value::bitcastFrom<int64_t>(expr->getDivisor());
+            bindParam(*divisorParam, true /*owned*/, sbe::value::TypeTags::NumberInt64, value);
+        }
+
+        {
+            auto value = sbe::value::bitcastFrom<int64_t>(expr->getRemainder());
+            bindParam(*remainderParam, true /*owned*/, sbe::value::TypeTags::NumberInt64, value);
+        }
+    }
+
+    void visit(const RegexMatchExpression* expr) final {
+        auto sourceRegexParam = expr->getSourceRegexInputParamId();
+        auto compiledRegexParam = expr->getCompiledRegexInputParamId();
+        if (!sourceRegexParam) {
+            tassert(6279509, "$regex had compiled param but not source param", !compiledRegexParam);
+            return;
+        }
+        tassert(6279510, "$regex had source param but not compiled param", compiledRegexParam);
+
+        {
+            auto&& [bsonRegexTag, bsonRegexVal] =
+                sbe::value::makeNewBsonRegex(expr->getString(), expr->getFlags());
+            bindParam(*sourceRegexParam, true /*owned*/, bsonRegexTag, bsonRegexVal);
+        }
+
+        {
+            auto&& [compiledRegexTag, compiledRegexVal] =
+                sbe::value::makeNewPcreRegex(expr->getString(), expr->getFlags());
+            bindParam(*compiledRegexParam, true /*owned*/, compiledRegexTag, compiledRegexVal);
+        }
+    }
+
+    void visit(const SizeMatchExpression* expr) final {
+        auto inputParam = expr->getInputParamId();
+        if (!inputParam) {
+            return;
+        }
+
+        auto value = sbe::value::bitcastFrom<int32_t>(expr->getData());
+        bindParam(*inputParam, true /*owned*/, sbe::value::TypeTags::NumberInt32, value);
+    }
+
+    void visit(const TypeMatchExpression* expr) final {
+        auto inputParam = expr->getInputParamId();
+        if (!inputParam) {
+            return;
+        }
+
+        // The bitmask representing the set of types is a 32-bit unsigned integer. In order to avoid
+        // a 32-bit unsigned number that is larger than INT_MAX to a 32-bit signed number, we use
+        // NumberInt64 rather than NumberInt32 as the destination SBE type.
+        auto value = sbe::value::bitcastFrom<int64_t>(expr->typeSet().getBSONTypeMask());
+        tassert(6279506, "type mask cannot be negative", value >= 0);
+        bindParam(*inputParam, true /*owned*/, sbe::value::TypeTags::NumberInt64, value);
+    }
+
+    void visit(const WhereMatchExpression* expr) final {
+        auto inputParam = expr->getInputParamId();
+        if (!inputParam) {
+            return;
+        }
+
+        auto&& [typeTag, jsFunctionVal] = sbe::value::makeCopyJsFunction(expr->getPredicate());
+        bindParam(*inputParam, true /*owned*/, typeTag, jsFunctionVal);
+    }
+
+    /**
+     * These match expressions cannot contain parameter marks themselves (though their children
+     * can).
+     */
+    void visit(const AlwaysFalseMatchExpression* expr) final {}
+    void visit(const AlwaysTrueMatchExpression* expr) final {}
+    void visit(const AndMatchExpression* expr) final {}
+    void visit(const ElemMatchObjectMatchExpression* matchExpr) final {}
+    void visit(const ElemMatchValueMatchExpression* matchExpr) final {}
+    void visit(const ExistsMatchExpression* expr) final {}
+    void visit(const ExprMatchExpression* expr) final {}
+    void visit(const GeoMatchExpression* expr) final {}
+    void visit(const GeoNearMatchExpression* expr) final {}
+    void visit(const InternalBucketGeoWithinMatchExpression* expr) final {}
+    void visit(const InternalExprEqMatchExpression* expr) final {}
+    void visit(const InternalExprGTMatchExpression* expr) final {}
+    void visit(const InternalExprGTEMatchExpression* expr) final {}
+    void visit(const InternalExprLTMatchExpression* expr) final {}
+    void visit(const InternalExprLTEMatchExpression* expr) final {}
+    void visit(const InternalSchemaAllElemMatchFromIndexMatchExpression* expr) final {}
+    void visit(const InternalSchemaAllowedPropertiesMatchExpression* expr) final {}
+    void visit(const InternalSchemaBinDataEncryptedTypeExpression* expr) final {}
+    void visit(const InternalSchemaBinDataSubTypeExpression* expr) final {}
+    void visit(const InternalSchemaCondMatchExpression* expr) final {}
+    void visit(const InternalSchemaEqMatchExpression* expr) final {}
+    void visit(const InternalSchemaFmodMatchExpression* expr) final {}
+    void visit(const InternalSchemaMatchArrayIndexMatchExpression* expr) final {}
+    void visit(const InternalSchemaMaxItemsMatchExpression* expr) final {}
+    void visit(const InternalSchemaMaxLengthMatchExpression* expr) final {}
+    void visit(const InternalSchemaMaxPropertiesMatchExpression* expr) final {}
+    void visit(const InternalSchemaMinItemsMatchExpression* expr) final {}
+    void visit(const InternalSchemaMinLengthMatchExpression* expr) final {}
+    void visit(const InternalSchemaMinPropertiesMatchExpression* expr) final {}
+    void visit(const InternalSchemaObjectMatchExpression* expr) final {}
+    void visit(const InternalSchemaRootDocEqMatchExpression* expr) final {}
+    void visit(const InternalSchemaTypeExpression* expr) final {}
+    void visit(const InternalSchemaUniqueItemsMatchExpression* expr) final {}
+    void visit(const InternalSchemaXorMatchExpression* expr) final {}
+    void visit(const NorMatchExpression* expr) final {}
+    void visit(const NotMatchExpression* expr) final {}
+    void visit(const OrMatchExpression* expr) final {}
+    void visit(const TextMatchExpression* expr) final {}
+    void visit(const TextNoOpMatchExpression* expr) final {}
+    void visit(const TwoDPtInAnnulusExpression* expr) final {}
+    void visit(const WhereNoOpMatchExpression* expr) final {}
+
+private:
+    void visitComparisonMatchExpression(const ComparisonMatchExpressionBase* expr) {
+        auto inputParam = expr->getInputParamId();
+        if (!inputParam) {
+            return;
+        }
+
+        // This is an unowned value which is a view into the BSON owned by the MatchExpression. This
+        // is acceptable because the 'MatchExpression' is held by the 'CanonicalQuery', and the
+        // 'CanonicalQuery' lives for the lifetime of the query.
+        auto&& [typeTag, val] = sbe::bson::convertFrom<true>(expr->getData());
+
+        bindParam(*inputParam, false /*owned*/, typeTag, val);
+    }
+
+    void visitBitTestExpression(const BitTestMatchExpression* expr) {
+        auto bitPositionsParam = expr->getBitPositionsParamId();
+        auto bitMaskParam = expr->getBitMaskParamId();
+        if (!bitPositionsParam) {
+            tassert(6279501,
+                    "bit-test expression had bitmask param but not bit positions param",
+                    !bitMaskParam);
+            return;
+        }
+        tassert(6279502,
+                "bit-test expression had bit positions param but not bitmask param",
+                bitMaskParam);
+
+        {
+            auto&& [bitPosTag, bitPosVal] = stage_builder::convertBitTestBitPositions(expr);
+            bindParam(*bitPositionsParam, true /*owned*/, bitPosTag, bitPosVal);
+        }
+
+        {
+            auto val = sbe::value::bitcastFrom<uint64_t>(expr->getBitMask());
+            bindParam(*bitMaskParam, true /*owned*/, sbe::value::TypeTags::NumberInt64, val);
+        }
+    }
+
+    void bindParam(MatchExpression::InputParamId paramId,
+                   bool owned,
+                   sbe::value::TypeTags typeTag,
+                   sbe::value::Value value) {
+        auto it = _inputParamToSlotMap.find(paramId);
+        // The encoding of the plan cache key should ensure that if we recover a cached plan from
+        // the cached, the auto-parameterization of the query is consistent with the way that the
+        // cached plan is parameterized.
+        tassert(6279500,
+                str::stream() << "expected value in 'inputParamsToSlotsMap' for param id: "
+                              << paramId,
+                it != _inputParamToSlotMap.end());
+        auto accessor = _runtimeEnvironment->getAccessor(it->second);
+
+        accessor->reset(owned, typeTag, value);
+    }
+
+    const stage_builder::InputParamToSlotMap& _inputParamToSlotMap;
+
+    sbe::RuntimeEnvironment* const _runtimeEnvironment;
+};
+
+class MatchExpressionParameterBindingWalker {
+public:
+    MatchExpressionParameterBindingWalker(MatchExpressionParameterBindingVisitor* visitor)
+        : _visitor{visitor} {
+        invariant(_visitor);
+    }
+
+    void preVisit(const MatchExpression* expr) {
+        expr->acceptVisitor(_visitor);
+    }
+
+    void postVisit(const MatchExpression* expr) {}
+    void inVisit(long count, const MatchExpression* expr) {}
+
+private:
+    MatchExpressionParameterBindingVisitor* const _visitor;
+};
+}  // namespace
+
+void bind(const CanonicalQuery& canonicalQuery,
+          const stage_builder::InputParamToSlotMap& inputParamToSlotMap,
+          sbe::RuntimeEnvironment* runtimeEnvironment) {
+    MatchExpressionParameterBindingVisitor visitor{inputParamToSlotMap, runtimeEnvironment};
+    MatchExpressionParameterBindingWalker walker{&visitor};
+    tree_walker::walk<true, MatchExpression>(canonicalQuery.root(), &walker);
+}
+}  // namespace mongo::input_params
diff --git a/src/mongo/db/query/bind_input_params.h b/src/mongo/db/query/bind_input_params.h
new file mode 100644
index 00000000000..82092c1ab6f
--- /dev/null
+++ b/src/mongo/db/query/bind_input_params.h
@@ -0,0 +1,47 @@
+/**
+ *    Copyright (C) 2022-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.
+ */
+
+#pragma once
+
+#include "mongo/db/exec/sbe/expressions/expression.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/query/canonical_query.h"
+#include "mongo/db/query/sbe_stage_builder.h"
+
+namespace mongo::input_params {
+/**
+ * Walks the MatchExpression from the 'CanonicalQuery' looking for nodes which have an input
+ * parameter id, along with a constant associated with that parameter id. For each such match
+ * expression node, looks up the corresponding slot in the 'RuntimeEnvironment' using the
+ * 'InputParamToSlotMap' and sets the value of that slot.
+ */
+void bind(const CanonicalQuery&,
+          const stage_builder::InputParamToSlotMap&,
+          sbe::RuntimeEnvironment*);
+}  // namespace mongo::input_params
diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp
index ad496d541ba..d3566b7070e 100644
--- a/src/mongo/db/query/canonical_query.cpp
+++ b/src/mongo/db/query/canonical_query.cpp
@@ -200,7 +200,9 @@ Status CanonicalQuery::init(OperationContext* opCtx,
     auto unavailableMetadata = validStatus.getValue();
     _root = MatchExpression::normalize(std::move(root));
     if (feature_flags::gFeatureFlagSbePlanCache.isEnabledAndIgnoreFCV()) {
-        MatchExpression::parameterize(_root.get());
+        // TODO SERVER-61421: Call 'MatchExpression::parameterize()' on '_root' in order to enable
+        // auto-parameterization. This cannot be done until the SBE plan cache code is prepared to
+        // deal with auto-parameterized queries.
     }
     // The tree must always be valid after normalization.
     dassert(isValid(_root.get(), *_findCommand).isOK());
diff --git a/src/mongo/db/query/get_executor.cpp b/src/mongo/db/query/get_executor.cpp
index fcb7c87a427..7f148d2b961 100644
--- a/src/mongo/db/query/get_executor.cpp
+++ b/src/mongo/db/query/get_executor.cpp
@@ -61,6 +61,7 @@
 #include "mongo/db/index_names.h"
 #include "mongo/db/matcher/extensions_callback_noop.h"
 #include "mongo/db/matcher/extensions_callback_real.h"
+#include "mongo/db/query/bind_input_params.h"
 #include "mongo/db/query/canonical_query.h"
 #include "mongo/db/query/canonical_query_encoder.h"
 #include "mongo/db/query/classic_plan_cache.h"
@@ -1070,6 +1071,10 @@ protected:
         invariant(sbeYieldPolicy);
         sbeYieldPolicy->registerPlan(root.get());
 
+        // If the cached plan is parameterized, bind new values for the parameters into the runtime
+        // environment.
+        input_params::bind(*_cq, stageData.inputParamToSlotMap, stageData.env);
+
         auto result = makeResult();
         result->setDecisionWorks(cacheEntry->decisionWorks);
         result->emplace(std::move(cacheEntry->debugInfo),
diff --git a/src/mongo/db/query/sbe_stage_builder.h b/src/mongo/db/query/sbe_stage_builder.h
index 6c9cec76557..6ff9bf615fb 100644
--- a/src/mongo/db/query/sbe_stage_builder.h
+++ b/src/mongo/db/query/sbe_stage_builder.h
@@ -217,6 +217,8 @@ void PlanStageSlots::forEachSlot(const PlanStageReqs& reqs,
     }
 }
 
+using InputParamToSlotMap = stdx::unordered_map<MatchExpression::InputParamId, sbe::value::SlotId>;
+
 /**
  * Some auxiliary data returned by a 'SlotBasedStageBuilder' along with a PlanStage tree root, which
  * is needed to execute the PlanStage tree.
@@ -271,6 +273,20 @@ struct PlanStageData {
     // Note that 'debugInfo' is present only if this PlanStageData is recovered from the plan cache.
     std::unique_ptr<plan_cache_debug_info::DebugInfoSBE> debugInfo;
 
+    // If the query has been auto-parameterized, then the mapping from input parameter id to the
+    // id of a slot in the runtime environment is maintained here. This mapping is established
+    // during stage building and stored in the cache. When a cached plan is used for a subsequent
+    // query, this mapping is used to set the new constant value associated with each input
+    // parameter id in the runtime environment.
+    //
+    // For example, imagine an auto-parameterized query {a: <p1>, b: <p2>} is present in the SBE
+    // plan cache. Also present in the cache is this mapping:
+    //    p1 -> s3
+    //    p2 -> s4
+    //
+    // A new query {a: 5, b: 6} runs. Using this mapping, we set a value of 5 in s3 and 6 in s4.
+    InputParamToSlotMap inputParamToSlotMap;
+
 private:
     // This copy function copies data from 'other' but will not create a copy of its
     // RuntimeEnvironment and CompileCtx.
diff --git a/src/mongo/db/query/sbe_stage_builder_filter.cpp b/src/mongo/db/query/sbe_stage_builder_filter.cpp
index 01bb3ccd8eb..76efab7a7c0 100644
--- a/src/mongo/db/query/sbe_stage_builder_filter.cpp
+++ b/src/mongo/db/query/sbe_stage_builder_filter.cpp
@@ -46,7 +46,6 @@
 #include "mongo/db/matcher/expression_expr.h"
 #include "mongo/db/matcher/expression_geo.h"
 #include "mongo/db/matcher/expression_internal_expr_comparison.h"
-#include "mongo/db/matcher/expression_leaf.h"
 #include "mongo/db/matcher/expression_text.h"
 #include "mongo/db/matcher/expression_text_noop.h"
 #include "mongo/db/matcher/expression_tree.h"
@@ -834,25 +833,7 @@ void generateBitTest(MatchExpressionVisitorContext* context,
                      const sbe::BitTestBehavior& bitOp) {
     auto makePredicate = [expr, bitOp](sbe::value::SlotId inputSlot,
                                        EvalStage inputStage) -> EvalExprStagePair {
-        auto bitPositions = expr->getBitPositions();
-
-        // Build an array set of bit positions for the bitmask, and remove duplicates in the
-        // bitPositions vector since duplicates aren't handled in the match expression parser by
-        // checking if an item has already been seen.
-        auto [bitPosTag, bitPosVal] = sbe::value::makeNewArray();
-        auto arr = sbe::value::getArrayView(bitPosVal);
-        if (bitPositions.size()) {
-            arr->reserve(bitPositions.size());
-
-            std::set<uint32_t> seenBits;
-            for (size_t index = 0; index < bitPositions.size(); ++index) {
-                auto currentBit = bitPositions[index];
-                if (auto result = seenBits.insert(currentBit); result.second) {
-                    arr->push_back(sbe::value::TypeTags::NumberInt64,
-                                   sbe::value::bitcastFrom<int64_t>(currentBit));
-                }
-            }
-        }
+        auto [bitPosTag, bitPosVal] = convertBitTestBitPositions(expr);
 
         // An EExpression for the BinData and position list for the binary case of
         // BitTestMatchExpressions. This function will be applied to values carrying BinData
@@ -1435,43 +1416,18 @@ public:
     void visit(const GeoNearMatchExpression* expr) final {}
 
     void visit(const InMatchExpression* expr) final {
-        auto equalities = expr->getEqualities();
-
-        // Build an ArraySet for testing membership of the field in the equalities vector of the
-        // InMatchExpression.
-        auto [arrSetTag, arrSetVal] = sbe::value::makeNewArraySet();
+        auto&& [arrSetTag, arrSetVal, hasArray, hasNull] = convertInExpressionEqualities(expr);
         sbe::value::ValueGuard arrSetGuard{arrSetTag, arrSetVal};
 
-        auto arrSet = sbe::value::getArraySetView(arrSetVal);
-
-        auto hasArray = false;
-        auto hasNull = false;
-        if (equalities.size()) {
-            arrSet->reserve(equalities.size());
-            for (auto&& equality : equalities) {
-                auto [tagView, valView] =
-                    sbe::bson::convertFrom<true>(equality.rawdata(),
-                                                 equality.rawdata() + equality.size(),
-                                                 equality.fieldNameSize() - 1);
-
-                hasNull |= tagView == sbe::value::TypeTags::Null;
-                hasArray |= sbe::value::isArray(tagView);
-
-                // An ArraySet assumes ownership of it's values so we have to make a copy here.
-                auto [tag, val] = sbe::value::copyValue(tagView, valView);
-                arrSet->push_back(tag, val);
-            }
-        }
-
         const auto traversalMode = hasArray ? LeafTraversalMode::kArrayAndItsElements
                                             : LeafTraversalMode::kArrayElementsOnly;
 
         // If the InMatchExpression doesn't carry any regex patterns, we can just check if the value
         // in bound to the inputSlot is a member of the equalities set.
         if (expr->getRegexes().size() == 0) {
-            auto makePredicate = [&, arrSetTag = arrSetTag, arrSetVal = arrSetVal](
-                                     sbe::value::SlotId inputSlot,
-                                     EvalStage inputStage) -> EvalExprStagePair {
+            auto makePredicate =
+                [&, arrSetTag = arrSetTag, arrSetVal = arrSetVal, hasNull = hasNull](
+                    sbe::value::SlotId inputSlot, EvalStage inputStage) -> EvalExprStagePair {
                 // We have to match nulls and undefined if a 'null' is present in equalities.
                 auto inputExpr = !hasNull
                     ? makeVariable(inputSlot)
@@ -1497,6 +1453,7 @@ public:
             // exhaust the equalities 'isMember' check, and then if no match is found it executes
             // the regex-only traversal stage.
             auto& regexes = expr->getRegexes();
+            auto& equalities = expr->getEqualities();
 
             auto [arrTag, arrVal] = sbe::value::makeNewArray();
             sbe::value::ValueGuard arrGuard{arrTag, arrVal};
@@ -1513,9 +1470,13 @@ public:
                 }
             }
 
-            auto makePredicate =
-                [&, arrSetTag = arrSetTag, arrSetVal = arrSetVal, arrTag = arrTag, arrVal = arrVal](
-                    sbe::value::SlotId inputSlot, EvalStage inputStage) -> EvalExprStagePair {
+            auto makePredicate = [&,
+                                  arrSetTag = arrSetTag,
+                                  arrSetVal = arrSetVal,
+                                  arrTag = arrTag,
+                                  arrVal = arrVal,
+                                  hasNull = hasNull](sbe::value::SlotId inputSlot,
+                                                     EvalStage inputStage) -> EvalExprStagePair {
                 auto regexArraySlot{_context->state.slotId()};
                 auto regexInputSlot{_context->state.slotId()};
                 auto regexOutputSlot{_context->state.slotId()};
@@ -1976,4 +1937,64 @@ EvalStage generateIndexFilter(StageBuilderState& state,
     tassert(5273411, "Index filter must not track a matching element index", !resultSlot);
     return std::move(resultStage);
 }
+
+std::tuple<sbe::value::TypeTags, sbe::value::Value, bool, bool> convertInExpressionEqualities(
+    const InMatchExpression* expr) {
+    auto& equalities = expr->getEqualities();
+    auto [arrSetTag, arrSetVal] = sbe::value::makeNewArraySet();
+    sbe::value::ValueGuard arrSetGuard{arrSetTag, arrSetVal};
+
+    auto arrSet = sbe::value::getArraySetView(arrSetVal);
+
+    auto hasArray = false;
+    auto hasNull = false;
+    if (equalities.size()) {
+        arrSet->reserve(equalities.size());
+        for (auto&& equality : equalities) {
+            auto [tagView, valView] =
+                sbe::bson::convertFrom<true>(equality.rawdata(),
+                                             equality.rawdata() + equality.size(),
+                                             equality.fieldNameSize() - 1);
+
+            hasNull |= tagView == sbe::value::TypeTags::Null;
+            hasArray |= sbe::value::isArray(tagView);
+
+            // An ArraySet assumes ownership of it's values so we have to make a copy here.
+            auto [tag, val] = sbe::value::copyValue(tagView, valView);
+            arrSet->push_back(tag, val);
+        }
+    }
+
+    arrSetGuard.reset();
+    return {arrSetTag, arrSetVal, hasArray, hasNull};
+}
+
+std::pair<sbe::value::TypeTags, sbe::value::Value> convertBitTestBitPositions(
+    const BitTestMatchExpression* expr) {
+    auto bitPositions = expr->getBitPositions();
+
+    // Build an array set of bit positions for the bitmask, and remove duplicates in the
+    // bitPositions vector since duplicates aren't handled in the match expression parser by
+    // checking if an item has already been seen.
+    auto [bitPosTag, bitPosVal] = sbe::value::makeNewArray();
+    sbe::value::ValueGuard arrGuard{bitPosTag, bitPosVal};
+
+    auto arr = sbe::value::getArrayView(bitPosVal);
+    if (bitPositions.size()) {
+        arr->reserve(bitPositions.size());
+
+        std::set<uint32_t> seenBits;
+        for (size_t index = 0; index < bitPositions.size(); ++index) {
+            auto currentBit = bitPositions[index];
+            if (auto result = seenBits.insert(currentBit); result.second) {
+                arr->push_back(sbe::value::TypeTags::NumberInt64,
+                               sbe::value::bitcastFrom<int64_t>(currentBit));
+            }
+        }
+    }
+
+    arrGuard.reset();
+    return {bitPosTag, bitPosVal};
+}
+
 }  // namespace mongo::stage_builder
diff --git a/src/mongo/db/query/sbe_stage_builder_filter.h b/src/mongo/db/query/sbe_stage_builder_filter.h
index 4157adf2628..c160fea42c5 100644
--- a/src/mongo/db/query/sbe_stage_builder_filter.h
+++ b/src/mongo/db/query/sbe_stage_builder_filter.h
@@ -33,6 +33,7 @@
 #include "mongo/db/exec/sbe/stages/stages.h"
 #include "mongo/db/exec/sbe/values/value.h"
 #include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_leaf.h"
 #include "mongo/db/query/sbe_stage_builder_eval_frame.h"
 #include "mongo/db/query/sbe_stage_builder_helpers.h"
 
@@ -75,4 +76,24 @@ EvalStage generateIndexFilter(StageBuilderState& state,
                               sbe::value::SlotVector keySlots,
                               std::vector<std::string> keyFields,
                               PlanNodeId planNodeId);
+
+/**
+ * Converts the list of equalities inside the given $in expression ('expr') into an SBE array, which
+ * is returned as a (typeTag, value) pair. The caller owns the resulting value.
+ *
+ * The returned tuple also includes two booleans, in this order:
+ *  - 'hasArray': True if at least one of the values inside the $in equality list is an array.
+ *  - 'hasNull': True if at least one of the values inside the $in equality list is a literal null
+ * value.
+ */
+std::tuple<sbe::value::TypeTags, sbe::value::Value, bool, bool> convertInExpressionEqualities(
+    const InMatchExpression* expr);
+
+/**
+ * Converts the list of bit positions inside of any of the bit-test match expressions
+ * ($bitsAllClear, $bitsAllSet, $bitsAnyClear, and $bitsAnySet) to an SBE array, returned as a
+ * (typeTag, value) pair. The caller owns the resulting value.
+ */
+std::pair<sbe::value::TypeTags, sbe::value::Value> convertBitTestBitPositions(
+    const BitTestMatchExpression* expr);
 }  // namespace mongo::stage_builder