diff options
Diffstat (limited to 'src/mongo/db/query/optimizer')
8 files changed, 269 insertions, 108 deletions
diff --git a/src/mongo/db/query/optimizer/cascades/implementers.cpp b/src/mongo/db/query/optimizer/cascades/implementers.cpp index b4f24715450..f32d391839e 100644 --- a/src/mongo/db/query/optimizer/cascades/implementers.cpp +++ b/src/mongo/db/query/optimizer/cascades/implementers.cpp @@ -347,6 +347,7 @@ public: // via a physical scan even in the absence of indexes. const IndexingRequirement& requirements = getPropertyConst<IndexingRequirement>(_physProps); + const CandidateIndexMap& candidateIndexMap = node.getCandidateIndexMap(); const IndexReqTarget indexReqTarget = requirements.getIndexReqTarget(); switch (indexReqTarget) { case IndexReqTarget::Complete: @@ -356,6 +357,11 @@ public: break; case IndexReqTarget::Index: + if (candidateIndexMap.empty()) { + return; + } + [[fallthrough]]; + case IndexReqTarget::Seek: if (_hints._disableIndexes == DisableIndexOptions::DisableAll) { return; @@ -438,7 +444,7 @@ public: // Consider all candidate indexes, and check if they satisfy the collation and // distribution requirements. - for (const auto& [indexDefName, candidateIndexEntry] : node.getCandidateIndexMap()) { + for (const auto& [indexDefName, candidateIndexEntry] : candidateIndexMap) { const auto& indexDef = scanDef.getIndexDefs().at(indexDefName); if (!indexDef.getPartialReqMap().empty() && (_hints._disableIndexes == DisableIndexOptions::DisablePartialOnly || diff --git a/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp b/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp index 7a499b0ec18..e8d4603e0f4 100644 --- a/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp +++ b/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp @@ -79,11 +79,13 @@ LogicalRewriter::RewriteSet LogicalRewriter::_substitutionSet = { LogicalRewriter::LogicalRewriter(Memo& memo, PrefixId& prefixId, const RewriteSet rewriteSet, + const QueryHints& hints, const bool useHeuristicCE) : _activeRewriteSet(std::move(rewriteSet)), _groupsPending(), _memo(memo), _prefixId(prefixId), + _hints(hints), _useHeuristicCE(useHeuristicCE) { initializeRewrites(); @@ -182,6 +184,10 @@ public: return _rewriter._prefixId; } + const QueryHints& getHints() const { + return _rewriter._hints; + } + auto& getIndexFieldPrefixMap() const { return _rewriter._indexFieldPrefixMap; } @@ -567,8 +573,12 @@ static boost::optional<ABT> mergeSargableNodes( const ScanDefinition& scanDef = ctx.getMetadata()._scanDefs.at(indexingAvailability.getScanDefName()); - auto candidateIndexMap = computeCandidateIndexMap( - ctx.getPrefixId(), scanProjName, mergedReqs, scanDef, hasEmptyInterval); + auto candidateIndexMap = computeCandidateIndexMap(ctx.getPrefixId(), + scanProjName, + mergedReqs, + scanDef, + ctx.getHints()._fastIndexNullHandling, + hasEmptyInterval); if (hasEmptyInterval) { return createEmptyValueScanNode(ctx); } @@ -700,8 +710,12 @@ static void convertFilterToSargableNode(ABT::reference_type node, return; } - auto candidateIndexMap = computeCandidateIndexMap( - ctx.getPrefixId(), scanProjName, conversion->_reqMap, scanDef, hasEmptyInterval); + auto candidateIndexMap = computeCandidateIndexMap(ctx.getPrefixId(), + scanProjName, + conversion->_reqMap, + scanDef, + ctx.getHints()._fastIndexNullHandling, + hasEmptyInterval); if (hasEmptyInterval) { addEmptyValueScanNode(ctx); @@ -880,8 +894,12 @@ struct SubstituteConvert<EvaluationNode> { } bool hasEmptyInterval = false; - auto candidateIndexMap = computeCandidateIndexMap( - ctx.getPrefixId(), scanProjName, conversion->_reqMap, scanDef, hasEmptyInterval); + auto candidateIndexMap = computeCandidateIndexMap(ctx.getPrefixId(), + scanProjName, + conversion->_reqMap, + scanDef, + ctx.getHints()._fastIndexNullHandling, + hasEmptyInterval); if (hasEmptyInterval) { addEmptyValueScanNode(ctx); @@ -957,6 +975,30 @@ struct ExploreConvert<SargableNode> { const bool indexFieldMapHasScanDef = indexFieldPrefixMapIt != indexFieldPrefixMap.cend(); const auto& reqMap = sargableNode.getReqMap(); + + const bool fastIndexNullHandling = ctx.getHints()._fastIndexNullHandling; + std::vector<bool> isFullyOpen; + std::vector<bool> maybeHasNullAndBinds; + { + // Pre-compute if a requirement's interval is fully open. + isFullyOpen.reserve(reqMap.size()); + for (const auto& [key, req] : reqMap) { + isFullyOpen.push_back(isIntervalReqFullyOpenDNF(req.getIntervals())); + } + + if (!fastIndexNullHandling && !isIndex) { + // Pre-compute if needed if a requirement's interval may contain nulls, and also has + // an output binding. + maybeHasNullAndBinds.reserve(reqMap.size()); + for (const auto& [key, req] : reqMap) { + maybeHasNullAndBinds.push_back(req.hasBoundProjectionName() && + checkMaybeHasNull(req.getIntervals())); + } + } + } + + // We iterate over the possible ways to split N predicates into 2^N subsets, one goes to the + // left, and the other to the right side. const size_t reqSize = reqMap.size(); const size_t highMask = isIndex ? (1ull << (reqSize - 1)) : (1ull << reqSize); for (size_t mask = 1; mask < highMask; mask++) { @@ -968,21 +1010,43 @@ struct ExploreConvert<SargableNode> { size_t index = 0; for (const auto& [key, req] : reqMap) { - const bool fullyOpenInterval = isIntervalReqFullyOpenDNF(req.getIntervals()); + const bool fullyOpenInterval = isFullyOpen.at(index); if (((1ull << index) & mask) != 0) { - leftReqs.emplace(key, req); - - if (!fullyOpenInterval) { - hasLeftIntervals = true; + bool addedToLeft = false; + if (fastIndexNullHandling || isIndex) { + leftReqs.emplace(key, req); + addedToLeft = true; + } else if (maybeHasNullAndBinds.at(index)) { + // We cannot return index values if our interval can possibly contain Null. + // Instead, we remove the output binding for the left side, and return the + // value from the right (seek) side. + if (!fullyOpenInterval) { + leftReqs.emplace(key, PartialSchemaRequirement{"", req.getIntervals()}); + addedToLeft = true; + } + rightReqs.emplace( + key, + PartialSchemaRequirement{req.getBoundProjectionName(), + IntervalReqExpr::makeSingularDNF()}); + } else { + leftReqs.emplace(key, req); + addedToLeft = true; } - if (indexFieldMapHasScanDef) { - if (auto pathPtr = key._path.cast<PathGet>(); pathPtr != nullptr && - indexFieldPrefixMapIt->second.count(pathPtr->name()) == 0) { - // We have found a left requirement which cannot be covered with an - // index. - hasFieldCoverage = false; - break; + + if (addedToLeft) { + if (!fullyOpenInterval) { + hasLeftIntervals = true; + } + + if (indexFieldMapHasScanDef) { + if (auto pathPtr = key._path.cast<PathGet>(); pathPtr != nullptr && + indexFieldPrefixMapIt->second.count(pathPtr->name()) == 0) { + // We have found a left requirement which cannot be covered with an + // index. + hasFieldCoverage = false; + break; + } } } } else { @@ -995,6 +1059,12 @@ struct ExploreConvert<SargableNode> { index++; } + if (leftReqs.empty()) { + // Can happen if we have intervals containing null. + invariant(!fastIndexNullHandling && !isIndex); + continue; + } + if (isIndex && (!hasLeftIntervals || !hasRightIntervals)) { // Reject. Must have at least one proper interval on either side. continue; @@ -1005,16 +1075,24 @@ struct ExploreConvert<SargableNode> { } bool hasEmptyLeftInterval = false; - auto leftCandidateIndexMap = computeCandidateIndexMap( - ctx.getPrefixId(), scanProjectionName, leftReqs, scanDef, hasEmptyLeftInterval); + auto leftCandidateIndexMap = computeCandidateIndexMap(ctx.getPrefixId(), + scanProjectionName, + leftReqs, + scanDef, + fastIndexNullHandling, + hasEmptyLeftInterval); if (isIndex && leftCandidateIndexMap.empty()) { // Reject rewrite. continue; } bool hasEmptyRightInterval = false; - auto rightCandidateIndexMap = computeCandidateIndexMap( - ctx.getPrefixId(), scanProjectionName, rightReqs, scanDef, hasEmptyRightInterval); + auto rightCandidateIndexMap = computeCandidateIndexMap(ctx.getPrefixId(), + scanProjectionName, + rightReqs, + scanDef, + fastIndexNullHandling, + hasEmptyRightInterval); if (isIndex && rightCandidateIndexMap.empty()) { // With empty candidate map, reject only if we cannot implement as Seek. continue; diff --git a/src/mongo/db/query/optimizer/cascades/logical_rewriter.h b/src/mongo/db/query/optimizer/cascades/logical_rewriter.h index 197d9c24771..97684ec992d 100644 --- a/src/mongo/db/query/optimizer/cascades/logical_rewriter.h +++ b/src/mongo/db/query/optimizer/cascades/logical_rewriter.h @@ -58,7 +58,11 @@ public: */ using RewriteSet = opt::unordered_map<LogicalRewriteType, double>; - LogicalRewriter(Memo& memo, PrefixId& prefixId, RewriteSet rewriteSet, bool useHeuristicCE); + LogicalRewriter(Memo& memo, + PrefixId& prefixId, + RewriteSet rewriteSet, + const QueryHints& hints, + bool useHeuristicCE); LogicalRewriter() = delete; LogicalRewriter(const LogicalRewriter& other) = delete; @@ -117,6 +121,7 @@ private: // We don't own those: Memo& _memo; PrefixId& _prefixId; + const QueryHints& _hints; RewriteFnMap _rewriteMap; diff --git a/src/mongo/db/query/optimizer/defs.h b/src/mongo/db/query/optimizer/defs.h index 863521b3a03..15dce7fc94f 100644 --- a/src/mongo/db/query/optimizer/defs.h +++ b/src/mongo/db/query/optimizer/defs.h @@ -252,6 +252,10 @@ struct QueryHints { // Disable Cascades branch-and-bound strategy, and fully evaluate all plans. Used in conjunction // with keeping rejected plans. bool _disableBranchAndBound = false; + + // Controls if we prefer to cover queries which may return nulls with indexes, even though we + // may not distinguish between null and missing. Alternatively we always fetch (slower). + bool _fastIndexNullHandling = false; }; } // namespace mongo::optimizer diff --git a/src/mongo/db/query/optimizer/opt_phase_manager.cpp b/src/mongo/db/query/optimizer/opt_phase_manager.cpp index 6b79345ba0b..17e38eecad4 100644 --- a/src/mongo/db/query/optimizer/opt_phase_manager.cpp +++ b/src/mongo/db/query/optimizer/opt_phase_manager.cpp @@ -144,11 +144,9 @@ bool OptPhaseManager::runMemoLogicalRewrite(const OptPhase phase, } _memo.clear(); - logicalRewriter = std::make_unique<LogicalRewriter>( - _memo, - _prefixId, - rewriteSet, - phase == OptPhase::MemoSubstitutionPhase /* useHeuristicCE */); + const bool useHeuristicCE = phase == OptPhase::MemoSubstitutionPhase; + logicalRewriter = + std::make_unique<LogicalRewriter>(_memo, _prefixId, rewriteSet, _hints, useHeuristicCE); rootGroupId = logicalRewriter->addRootNode(input); if (runStandalone) { diff --git a/src/mongo/db/query/optimizer/physical_rewriter_optimizer_test.cpp b/src/mongo/db/query/optimizer/physical_rewriter_optimizer_test.cpp index 098ef8632d3..176063563aa 100644 --- a/src/mongo/db/query/optimizer/physical_rewriter_optimizer_test.cpp +++ b/src/mongo/db/query/optimizer/physical_rewriter_optimizer_test.cpp @@ -1203,13 +1203,14 @@ TEST(PhysRewriter, FilterIndexing4) { hints.emplace(PartialSchemaKey{"root", make<PathGet>("d", make<PathIdentity>())}, kDefaultSelectivity); + // Make sure the intervals do not contain Null. ABT evalNode = make<EvaluationNode>( "pa", make<EvalPath>(make<PathGet>("a", make<PathIdentity>()), make<Variable>("root")), std::move(scanNode)); ABT filterANode = make<FilterNode>( - make<EvalFilter>(make<PathTraverse>(make<PathCompare>(Operations::Lt, Constant::int64(1)), + make<EvalFilter>(make<PathTraverse>(make<PathCompare>(Operations::Gt, Constant::int64(1)), PathTraverse::kSingleLevel), make<Variable>("pa")), std::move(evalNode)); @@ -1217,7 +1218,7 @@ TEST(PhysRewriter, FilterIndexing4) { ABT filterBNode = make<FilterNode>( make<EvalFilter>( make<PathGet>("b", - make<PathTraverse>(make<PathCompare>(Operations::Lt, Constant::int64(1)), + make<PathTraverse>(make<PathCompare>(Operations::Gt, Constant::int64(1)), PathTraverse::kSingleLevel)), make<Variable>("root")), std::move(filterANode)); @@ -1225,7 +1226,7 @@ TEST(PhysRewriter, FilterIndexing4) { ABT filterCNode = make<FilterNode>( make<EvalFilter>( make<PathGet>("c", - make<PathTraverse>(make<PathCompare>(Operations::Lt, Constant::int64(1)), + make<PathTraverse>(make<PathCompare>(Operations::Gt, Constant::int64(1)), PathTraverse::kSingleLevel)), make<Variable>("root")), std::move(filterBNode)); @@ -1233,7 +1234,7 @@ TEST(PhysRewriter, FilterIndexing4) { ABT filterDNode = make<FilterNode>( make<EvalFilter>( make<PathGet>("d", - make<PathTraverse>(make<PathCompare>(Operations::Lt, Constant::int64(1)), + make<PathTraverse>(make<PathCompare>(Operations::Gt, Constant::int64(1)), PathTraverse::kSingleLevel)), make<Variable>("root")), std::move(filterCNode)); @@ -1279,21 +1280,21 @@ TEST(PhysRewriter, FilterIndexing4) { "Filter []\n" "| EvalFilter []\n" "| | Variable [evalTemp_8]\n" - "| PathCompare [Lt]\n" + "| PathCompare [Gt]\n" "| Const [1]\n" "Filter []\n" "| EvalFilter []\n" "| | Variable [evalTemp_7]\n" - "| PathCompare [Lt]\n" + "| PathCompare [Gt]\n" "| Const [1]\n" "Filter []\n" "| EvalFilter []\n" "| | Variable [evalTemp_6]\n" - "| PathCompare [Lt]\n" + "| PathCompare [Gt]\n" "| Const [1]\n" "IndexScan [{'<indexKey> 0': pa, '<indexKey> 1': evalTemp_6, '<indexKey> 2': evalTemp_7, " - "'<indexKey> 3': evalTemp_8}, scanDefName: c1, indexDefName: index1, interval: {[Const " - "[minKey], Const [1]), [Const [minKey], Const [maxKey]], [Const [minKey], Const [maxKey]], " + "'<indexKey> 3': evalTemp_8}, scanDefName: c1, indexDefName: index1, interval: {(Const " + "[1], Const [maxKey]], [Const [minKey], Const [maxKey]], [Const [minKey], Const [maxKey]], " "[Const [minKey], Const [maxKey]]}]\n" " BindBlock:\n" " [evalTemp_6]\n" @@ -1842,42 +1843,67 @@ TEST(PhysRewriter, CoveredScan) { using namespace properties; PrefixId prefixId; + PartialSchemaSelHints hints; + hints.emplace(PartialSchemaKey{"root", make<PathGet>("a", make<PathIdentity>())}, 0.01); + ABT scanNode = make<ScanNode>("root", "c1"); - ABT evalNode1 = make<EvaluationNode>( + ABT evalNode = make<EvaluationNode>( "pa", make<EvalPath>(make<PathGet>("a", make<PathIdentity>()), make<Variable>("root")), std::move(scanNode)); + ABT filterNode = + make<FilterNode>(make<EvalFilter>(make<PathCompare>(Operations::Lt, Constant::int32(1)), + make<Variable>("pa")), + std::move(evalNode)); + ABT rootNode = - make<RootNode>(ProjectionRequirement{ProjectionNameVector{"pa"}}, std::move(evalNode1)); + make<RootNode>(ProjectionRequirement{ProjectionNameVector{"pa"}}, std::move(filterNode)); OptPhaseManager phaseManager( {OptPhaseManager::OptPhase::MemoSubstitutionPhase, OptPhaseManager::OptPhase::MemoExplorationPhase, OptPhaseManager::OptPhase::MemoImplementationPhase}, prefixId, + false /*requireRID*/, {{{"c1", ScanDefinition{ {}, {{"index1", makeIndexDefinition("a", CollationOp::Ascending, false /*isMultiKey*/)}}}}}}, + std::make_unique<HintedCE>(std::move(hints)), + std::make_unique<DefaultCosting>(), {true /*debugMode*/, 2 /*debugLevel*/, DebugInfo::kIterationLimitForTests}); ABT optimized = std::move(rootNode); ASSERT_TRUE(phaseManager.optimize(optimized)); - ASSERT_EQ(4, phaseManager.getMemo().getStats()._physPlanExplorationCount); + ASSERT_EQ(5, phaseManager.getMemo().getStats()._physPlanExplorationCount); + // Since we do not optimize with fast null handling, we need to split the predicate between the + // index scan and fetch in order to handle null. ASSERT_EXPLAIN_V2( "Root []\n" "| | projections: \n" "| | pa\n" "| RefBlock: \n" "| Variable [pa]\n" - "IndexScan [{'<indexKey> 0': pa}, scanDefName: c1, indexDefName: index1, interval: {[Const " - "[minKey], Const [maxKey]]}]\n" + "BinaryJoin [joinType: Inner, {rid_0}]\n" + "| | Const [true]\n" + "| LimitSkip []\n" + "| | limitSkip:\n" + "| | limit: 1\n" + "| | skip: 0\n" + "| Seek [ridProjection: rid_0, {'a': pa}, c1]\n" + "| | BindBlock:\n" + "| | [pa]\n" + "| | Source []\n" + "| RefBlock: \n" + "| Variable [rid_0]\n" + "IndexScan [{'<rid>': rid_0}, scanDefName: c1, indexDefName: index1, interval: {[Const " + "[minKey], Const [1])}]\n" " BindBlock:\n" - " [pa]\n" + " [rid_0]\n" " Source []\n", optimized); } @@ -2082,9 +2108,11 @@ TEST(PhysRewriter, EvalIndexing2) { {true /*debugMode*/, 2 /*debugLevel*/, DebugInfo::kIterationLimitForTests}); ABT optimized = rootNode; + phaseManager.getHints()._fastIndexNullHandling = true; ASSERT_TRUE(phaseManager.optimize(optimized)); ASSERT_BETWEEN(10, 20, phaseManager.getMemo().getStats()._physPlanExplorationCount); + // Verify collation is subsumed into the index scan. ASSERT_EXPLAIN_V2( "Root []\n" "| | projections: \n" @@ -2566,62 +2594,35 @@ TEST(PhysRewriter, CompoundIndex3) { ABT optimized = rootNode; ASSERT_TRUE(phaseManager.optimize(optimized)); - ASSERT_BETWEEN(70, 130, phaseManager.getMemo().getStats()._physPlanExplorationCount); + ASSERT_BETWEEN(40, 60, phaseManager.getMemo().getStats()._physPlanExplorationCount); // Demonstrate we have a merge join because we have point predicates. - ASSERT_EXPLAIN_V2( - "Root []\n" - "| | projections: \n" - "| | root\n" - "| RefBlock: \n" - "| Variable [root]\n" - "Collation []\n" - "| | collation: \n" - "| | pa: Ascending\n" - "| | pb: Ascending\n" - "| RefBlock: \n" - "| Variable [pa]\n" - "| Variable [pb]\n" - "BinaryJoin [joinType: Inner, {rid_0}]\n" - "| | Const [true]\n" - "| LimitSkip []\n" - "| | limitSkip:\n" - "| | limit: 1\n" - "| | skip: 0\n" - "| Seek [ridProjection: rid_0, {'<root>': root, 'a': pa, 'b': pb}, c1]\n" - "| | BindBlock:\n" - "| | [pa]\n" - "| | Source []\n" - "| | [pb]\n" - "| | Source []\n" - "| | [root]\n" - "| | Source []\n" - "| RefBlock: \n" - "| Variable [rid_0]\n" - "MergeJoin []\n" - "| | | Condition\n" - "| | | rid_0 = rid_1\n" - "| | Collation\n" - "| | Ascending\n" - "| Union []\n" - "| | BindBlock:\n" - "| | [rid_1]\n" - "| | Source []\n" - "| Evaluation []\n" - "| | BindBlock:\n" - "| | [rid_1]\n" - "| | Variable [rid_0]\n" - "| IndexScan [{'<rid>': rid_0}, scanDefName: c1, indexDefName: index2, interval: {[Const " - "[2], Const [2]], [Const [4], Const [4]]}]\n" - "| BindBlock:\n" - "| [rid_0]\n" - "| Source []\n" - "IndexScan [{'<rid>': rid_0}, scanDefName: c1, indexDefName: index1, interval: {[Const " - "[1], Const [1]], [Const [3], Const [3]]}]\n" - " BindBlock:\n" - " [rid_0]\n" - " Source []\n", - optimized); + const BSONObj& explainRoot = ExplainGenerator::explainBSONObj(optimized); + ASSERT_BSON_PATH("\"Collation\"", explainRoot, "child.nodeType"); + ASSERT_BSON_PATH("\"pa\"", explainRoot, "child.collation.0.projectionName"); + ASSERT_BSON_PATH("\"pb\"", explainRoot, "child.collation.1.projectionName"); + ASSERT_BSON_PATH("\"BinaryJoin\"", explainRoot, "child.child.nodeType"); + ASSERT_BSON_PATH("\"Seek\"", explainRoot, "child.child.rightChild.child.nodeType"); + ASSERT_BSON_PATH("\"MergeJoin\"", explainRoot, "child.child.leftChild.nodeType"); + + const BSONObj& explainIndex1 = + dotted_path_support::extractElementAtPath( + explainRoot, "child.child.leftChild.rightChild.children.0.child") + .Obj(); + ASSERT_BSON_PATH("\"IndexScan\"", explainIndex1, "nodeType"); + ASSERT_BSON_PATH("2", explainIndex1, "interval.0.lowBound.bound.value"); + ASSERT_BSON_PATH("2", explainIndex1, "interval.0.highBound.bound.value"); + ASSERT_BSON_PATH("4", explainIndex1, "interval.1.lowBound.bound.value"); + ASSERT_BSON_PATH("4", explainIndex1, "interval.1.highBound.bound.value"); + + const BSONObj& explainIndex2 = + dotted_path_support::extractElementAtPath(explainRoot, "child.child.leftChild.leftChild") + .Obj(); + ASSERT_BSON_PATH("\"IndexScan\"", explainIndex2, "nodeType"); + ASSERT_BSON_PATH("1", explainIndex2, "interval.0.lowBound.bound.value"); + ASSERT_BSON_PATH("1", explainIndex2, "interval.0.highBound.bound.value"); + ASSERT_BSON_PATH("3", explainIndex2, "interval.1.lowBound.bound.value"); + ASSERT_BSON_PATH("3", explainIndex2, "interval.1.highBound.bound.value"); } TEST(PhysRewriter, CompoundIndex4Negative) { @@ -2891,7 +2892,7 @@ TEST(PhysRewriter, IndexBoundsIntersect2) { ABT optimized = rootNode; ASSERT_TRUE(phaseManager.optimize(optimized)); - ASSERT_EQ(6, phaseManager.getMemo().getStats()._physPlanExplorationCount); + ASSERT_EQ(4, phaseManager.getMemo().getStats()._physPlanExplorationCount); // Demonstrate we can intersect the bounds here because composition does not contain // traverse. @@ -3176,6 +3177,7 @@ TEST(PhysRewriter, IndexResidualReq1) { {true /*debugMode*/, 2 /*debugLevel*/, DebugInfo::kIterationLimitForTests}); ABT optimized = rootNode; + phaseManager.getHints()._fastIndexNullHandling = true; ASSERT_TRUE(phaseManager.optimize(optimized)); ASSERT_BETWEEN(25, 45, phaseManager.getMemo().getStats()._physPlanExplorationCount); diff --git a/src/mongo/db/query/optimizer/utils/utils.cpp b/src/mongo/db/query/optimizer/utils/utils.cpp index f08f3262ca6..1893840a40a 100644 --- a/src/mongo/db/query/optimizer/utils/utils.cpp +++ b/src/mongo/db/query/optimizer/utils/utils.cpp @@ -32,6 +32,7 @@ #include "mongo/db/query/optimizer/index_bounds.h" #include "mongo/db/query/optimizer/metadata.h" #include "mongo/db/query/optimizer/reference_tracker.h" +#include "mongo/db/query/optimizer/rewrites/const_eval.h" #include "mongo/db/query/optimizer/syntax/path.h" #include "mongo/db/query/optimizer/utils/interval_utils.h" #include "mongo/db/storage/storage_parameters_gen.h" @@ -1011,10 +1012,24 @@ CandidateIndexMap computeCandidateIndexMap(PrefixId& prefixId, const ProjectionName& scanProjectionName, const PartialSchemaRequirements& reqMap, const ScanDefinition& scanDef, + const bool fastNullHandling, bool& hasEmptyInterval) { CandidateIndexMap result; hasEmptyInterval = false; + // Contains one instance for each unmatched key. + PartialSchemaKeySet unsatisfiedKeysInitial; + for (const auto& [key, req] : reqMap) { + unsatisfiedKeysInitial.insert(key); + + if (!fastNullHandling && req.hasBoundProjectionName() && + checkMaybeHasNull(req.getIntervals())) { + // We cannot use indexes to return values for fields if we have an interval with null + // bounds. + return {}; + } + } + for (const auto& [indexDefName, indexDef] : scanDef.getIndexDefs()) { FieldProjectionMap indexProjectionMap; auto intervals = MultiKeyIntervalReqExpr::makeSingularDNF(); // Singular empty interval. @@ -1023,12 +1038,7 @@ CandidateIndexMap computeCandidateIndexMap(PrefixId& prefixId, ResidualKeyMap residualKeyMap; opt::unordered_set<size_t> fieldsToCollate; size_t intervalPrefixSize = 0; - - // Contains one instance for each unmatched key. - PartialSchemaKeySet unsatisfiedKeys; - for (const auto& [key, req] : reqMap) { - unsatisfiedKeys.insert(key); - } + PartialSchemaKeySet unsatisfiedKeys = unsatisfiedKeysInitial; // True if the paths from partial schema requirements form a strict prefix of the index // collation. @@ -1163,6 +1173,60 @@ CandidateIndexMap computeCandidateIndexMap(PrefixId& prefixId, return result; } +/** + * Transport that checks if we have a primitive interval which may contain null. + */ +class PartialSchemaReqMayContainNullTransport { +public: + bool transport(const IntervalReqExpr::Atom& node) { + const auto& interval = node.getExpr(); + + if (const auto& lowBound = interval.getLowBound(); + foldFn(make<BinaryOp>(lowBound.isInclusive() ? Operations::Gt : Operations::Gte, + lowBound.getBound(), + Constant::null())) == Constant::boolean(true)) { + // Lower bound is strictly larger than null, or equal to null but not inclusive. + return false; + } + if (const auto& highBound = interval.getHighBound(); + foldFn(make<BinaryOp>(highBound.isInclusive() ? Operations::Lt : Operations::Lte, + highBound.getBound(), + Constant::null())) == Constant::boolean(true)) { + // Upper bound is strictly smaller than null, or equal to null but not inclusive. + return false; + } + + return true; + } + + bool transport(const IntervalReqExpr::Conjunction& node, std::vector<bool> childResults) { + return std::all_of( + childResults.cbegin(), childResults.cend(), [](const bool v) { return v; }); + } + + bool transport(const IntervalReqExpr::Disjunction& node, std::vector<bool> childResults) { + return std::any_of( + childResults.cbegin(), childResults.cend(), [](const bool v) { return v; }); + } + + bool check(const IntervalReqExpr::Node& intervals) { + return algebra::transport<false>(intervals, *this); + } + +private: + ABT foldFn(ABT expr) { + // Performs constant folding. + VariableEnvironment env = VariableEnvironment::build(expr); + ConstEval instance(env); + instance.optimize(expr); + return expr; + }; +}; + +bool checkMaybeHasNull(const IntervalReqExpr::Node& intervals) { + return PartialSchemaReqMayContainNullTransport{}.check(intervals); +} + class PartialSchemaReqLowerTransport { public: PartialSchemaReqLowerTransport(const bool hasBoundProjName) @@ -1176,9 +1240,6 @@ public: if (interval.isEquality()) { 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())); } diff --git a/src/mongo/db/query/optimizer/utils/utils.h b/src/mongo/db/query/optimizer/utils/utils.h index 1cf7f20d3f0..09a18cc8817 100644 --- a/src/mongo/db/query/optimizer/utils/utils.h +++ b/src/mongo/db/query/optimizer/utils/utils.h @@ -222,9 +222,16 @@ CandidateIndexMap computeCandidateIndexMap(PrefixId& prefixId, const ProjectionName& scanProjectionName, const PartialSchemaRequirements& reqMap, const ScanDefinition& scanDef, + bool fastNullHandling, bool& hasEmptyInterval); /** + * Checks if we have an interval tree which has at least one atomic interval which may include Null + * as an endpoint. + */ +bool checkMaybeHasNull(const IntervalReqExpr::Node& intervals); + +/** * Used to lower a Sargable node to a subtree consisting of functionally equivalent Filter and Eval * nodes. */ |