// Contains helpers for checking, based on the explain output, properties of a // plan. For instance, there are helpers for checking whether a plan is a collection // scan or whether the plan is covered (index only). import {assertArrayEq, documentEq} from "jstests/aggregation/extras/utils.js"; import {runWithParamsAllNonConfigNodes} from "jstests/noPassthrough/libs/server_parameter_helpers.js"; import {isPlanCosted} from "jstests/libs/query/cbr_utils.js"; /** * Returns query planner part of explain for every node in the explain report. */ export function getQueryPlanners(explain) { return getAllNodeExplains(explain).flatMap((nodeExplain) => { // When the shards are present in 'queryPlanner.winningPlan', then the 'nodeExplain' itself // represents the shard's 'queryPlanner'. const isQueryPlanner = nodeExplain.hasOwnProperty("winningPlan"); if (isQueryPlanner) { return [nodeExplain]; } // Otherwise, the planner outputs will be nested deeper under a 'queryPlanner' field. return getNestedProperties(nodeExplain, "queryPlanner"); }); } /** * Utility to return the 'queryPlanner' section of 'explain'. The input is the root of the explain * output. */ export function getQueryPlanner(explain) { explain = getSingleNodeExplain(explain); if ("queryPlanner" in explain) { const qp = explain.queryPlanner; // Sharded case. if ("winningPlan" in qp && "shards" in qp.winningPlan) { return qp.winningPlan.shards[0]; } return qp; } assert(explain.hasOwnProperty("stages"), explain); const stage = explain.stages[0]; const cursorStage = stage.$cursor || stage.$geoNearCursor; assert(cursorStage, explain); assert(cursorStage.hasOwnProperty("queryPlanner"), explain); return cursorStage.queryPlanner; } /** * Help function to extract shards from explain in sharded environment. Returns null for * non-sharded plans. */ export function getShardsFromExplain(explain) { if ( explain.hasOwnProperty("queryPlanner") && explain.queryPlanner.hasOwnProperty("winningPlan") ) { return explain.queryPlanner.winningPlan.shards; } return null; } /** * Extracts and returns an array of explain outputs for every shard in a sharded cluster; returns * the original explain output in case of a single replica set. */ export function getAllNodeExplains(explain) { let shardsExplain = []; // If 'splitPipeline' is defined, there could be explains for each shard in the 'mergerPart' of // the 'splitPipeline', e.g. $unionWith. if (explain.splitPipeline) { const splitPipelineShards = getNestedProperties(explain.splitPipeline, "shards"); shardsExplain.push(...splitPipelineShards.flatMap(Object.values)); } if (explain.shards) { shardsExplain.push(...Object.values(explain.shards)); } // NOTE: When shards explain is present in the 'queryPlanner.winningPlan' the shard explains are // placed in the array and therefore there is no need to call Object.values() on each element. const shards = getShardsFromExplain(explain); if (shards) { assert(Array.isArray(shards), shards); shardsExplain.push(...shards); } if (shardsExplain.length > 0) { return shardsExplain; } return [explain]; } /** * Returns the output from a single shard if 'explain' was obtained from an unsharded collection; * returns 'explain' as is otherwise. */ export function getSingleNodeExplain(explain) { if ("shards" in explain) { const shards = explain.shards; const shardNames = Object.keys(shards); // There should only be one shard given that this function assumes that 'explain' was // obtained from an unsharded collection. assert.eq(shardNames.length, 1, explain); return shards[shardNames[0]]; } return explain; } /** * Returns true if this 'queryPlanner' section is in the V3 explain shape, where every candidate * plan lives in a unified "plans" array (winner first) instead of the legacy * winningPlan/rejectedPlans pair. */ export function isV3QueryPlanner(queryPlanner) { return queryPlanner.hasOwnProperty("plans") && !queryPlanner.hasOwnProperty("winningPlan"); } /** * Presents one V3 "plans" array entry in the legacy plan shape this library's accessors consume: * the plan's stage tree, with the plan-level fields (isCached, multiPlanEstimateStats, ...) kept * on the root - the place the legacy winningPlan/rejectedPlans entries carry them. * * When the winner carries "executedPlanStages" (a pipeline pushed down to SBE after ranking), that * tree is used instead of the ranked "planStages". */ function v3PlanToLegacyShape(planEntry) { const {planStages, executedPlanStages, ...planLevelFields} = planEntry; return Object.assign(planLevelFields, executedPlanStages ?? planStages); } /** * Returns the rejected plans of one 'queryPlanner' section (not the whole explain; use * getRejectedPlans() for that), handling both the legacy and the V3 section shape. */ function getRejectedPlansFromQueryPlanner(queryPlanner) { return isV3QueryPlanner(queryPlanner) ? queryPlanner.plans.slice(1).map(v3PlanToLegacyShape) : queryPlanner.rejectedPlans; } /** * Returns the winning plan from the corresponding sub-node of classic/SBE explain output. Takes * into account that the plan may or may not have agg stages. * For sharded collections, this may return the top-level "winningPlan" which contains the shards. * To ensure getting the winning plan for a specific shard, provide as input the specific explain * for that shard i.e, explain.queryPlanner.winningPlan.shards[shardNames[0]]. */ export function getWinningPlanFromExplain(explain, isSBEPlan = false) { let getWinningSBEPlan = (queryPlanner) => isV3QueryPlanner(queryPlanner) ? queryPlanner.plans[0].slotBasedPlan : queryPlanner.winningPlan.slotBasedPlan; // In the V3 shape the winner is the first entry of the unified "plans" array. Otherwise, the // 'queryPlan' format is used when the SBE engine is turned on. If this field is present, // it will hold a serialized winning plan, otherwise it will be stored in the 'winningPlan' // field itself. let getWinningPlan = (queryPlanner) => { if (isV3QueryPlanner(queryPlanner)) { return v3PlanToLegacyShape(queryPlanner.plans[0]); } return queryPlanner.winningPlan.hasOwnProperty("queryPlan") ? queryPlanner.winningPlan.queryPlan : queryPlanner.winningPlan; }; if ("shards" in explain) { for (const shardName in explain.shards) { let queryPlanner = getQueryPlanner(explain.shards[shardName]); return isSBEPlan ? getWinningSBEPlan(queryPlanner) : getWinningPlan(queryPlanner); } } if (explain.hasOwnProperty("pipeline")) { const pipeline = explain.pipeline; // Pipeline stages' explain output come in two shapes: // 1. When in single node, as a single object array // 2. When in sharded, as an object. if (pipeline.constructor === Array) { return getWinningPlanFromExplain(pipeline[0].$cursor, isSBEPlan); } else { return getWinningPlanFromExplain(pipeline, isSBEPlan); } } let queryPlanner = explain; if (explain.hasOwnProperty("queryPlanner") || explain.hasOwnProperty("stages")) { queryPlanner = getQueryPlanner(explain); } return isSBEPlan ? getWinningSBEPlan(queryPlanner) : getWinningPlan(queryPlanner); } /** * The ranker that produced the winning plan. * kCostBased - the cost-based ranker (CBR) ranked the plan (it carries a cost estimate). * kMultiPlanning - the multi-planner (MP) ranked the plan (no cost estimate). This includes the * case where CBR was engaged but could not cost the plans and fell back to MP. * kSinglePlan - no ranking was needed because there was a single candidate plan. * kCachedPlan - no ranking was needed because the plan came from the plan cache. * kExpress - no ranking was needed because the plan was produced by the express path. */ export const ChosenRanker = { kMultiPlanning: "multiPlanning", kCostBased: "costBased", kSinglePlan: "singlePlan", kCachedPlan: "cachedPlan", kExpress: "express", }; /** * The reason a particular ranker was chosen for a query, as reported by the V3 explain * queryPlanner.rankerChoice.reason field. These values mirror the C++ PlanRankerReason enum * (src/mongo/db/query/plan_ranking/plan_ranker_reason.h) byte for byte. Not all reasons apply to * every plan ranker or CE strategy. * TODO SERVER-115714: add enum value kSmallCollection: "smallCollection" */ export const PlanRankerReason = { kSinglePlan: "singlePlan", kCBRFeatureFlagDisabled: "cbrFeatureFlagDisabled", kQueryPlanRankerKnob: "queryPlanRankerKnob", kCBRInestimableNode: "cbrInestimableNode", kHistogramCEInternalColl: "histogramCEInternalColl", kMpEarlyExit: "mpEarlyExit", kMpFoundResult: "mpFoundResult", kNoMultiplanningResults: "noMultiplanningResults", kInestimableMP: "inestimableMP", kMpCheaperThanCbr: "mpCheaperThanCbr", kCbrCheaperThanMp: "cbrCheaperThanMp", }; export function getRankerChoice(explain) { const queryPlanner = getQueryPlanner(explain); const rankerChoice = queryPlanner.rankerChoice; assert(rankerChoice, "missing queryPlanner.rankerChoice", {explain}); return rankerChoice; } /** * Asserts that the winning plan in 'explain' was produced by 'chosenRanker'. * * Optionally takes 'reason', which is validated against 'PlanRankerReason' and, for V3 explain * output, asserted against queryPlanner.rankerChoice.reason. Legacy explain output does not * surface the reason, so there it is validated only. */ export function assertChosenRanker(explain, chosenRanker, reason = undefined) { assert(Object.values(ChosenRanker).includes(chosenRanker), "Unknown chosenRanker", { chosenRanker, }); if (reason !== undefined) { assert(Object.values(PlanRankerReason).includes(reason), "Unknown reason", {reason}); } const queryPlanner = getQueryPlanner(explain); if (isV3QueryPlanner(queryPlanner)) { assert(queryPlanner.hasOwnProperty("rankerChoice"), "Expected rankerChoice in V3 explain", { queryPlanner, }); const rankerChoice = queryPlanner.rankerChoice; assert( rankerChoice.hasOwnProperty("chosenRanker"), "Expected chosenRanker in rankerChoice", {rankerChoice}, ); assert( rankerChoice.chosenRanker === chosenRanker, 'Unexpected chosenRanker in rankerChoice, expected: "' + chosenRanker + '", got: "' + rankerChoice.chosenRanker + '"', {rankerChoice}, ); if (reason !== undefined) { assert(rankerChoice.hasOwnProperty("reason"), "Expected reason in rankerChoice", { rankerChoice, }); assert( rankerChoice.reason === reason, 'Unexpected reason in rankerChoice, expected: "' + reason + '", got: "' + rankerChoice.reason + '"', {rankerChoice}, ); } return; } const winningPlan = getWinningPlanFromExplain(explain); const isCosted = isPlanCosted(winningPlan); switch (chosenRanker) { case ChosenRanker.kCostBased: assert(isCosted, "Expected CBR to have costed the winning plan", { chosenRanker, reason, winningPlan, }); break; case ChosenRanker.kMultiPlanning: assert(!isCosted, "Expected the winning plan to not be costed", { chosenRanker, reason, winningPlan, }); break; case ChosenRanker.kSinglePlan: case ChosenRanker.kCachedPlan: assert(getRejectedPlans(explain).length === 0, "Expected no rejected plans", {explain}); break; } } /** * Returns the V3 per-plan array of 'explain', asserting it is present. The winning (or sole) plan is * always the first entry; the rest follow in the deciding ranker's order. */ export function getV3Plans(explain) { const queryPlanner = getQueryPlanner(explain); const plans = queryPlanner.plans; assert(Array.isArray(plans), "missing queryPlanner.plans", {explain}); assert.gte(plans.length, 1, "plans must hold at least the winning plan", {explain}); return plans; } /** * The values that legitimately differ between two explain invocations of the same query on the same * data: planning and trial timing, and yield bookkeeping. Everything else is expected to be * reproducible, so keeping this list short and named is what gives a deep explain comparison its * teeth - resist adding to it. * */ const kRunVaryingExplainFields = new Set([ "optimizationTimeMillis", "optimizationTimeMicros", "executionTimeMillisEstimate", "executionTimeMicros", "executionTimeNanos", "saveState", "restoreState", "needYield", ]); /** * Returns a deep copy of 'value' with every run-varying field (see 'kRunVaryingExplainFields') * replaced by the placeholder string "", so that two explain outputs for the same query * can be compared for deep equality. * * Field *presence* is never normalized: a normalized field is still present, so a field appearing or * disappearing between the two outputs still fails the comparison. Recurses through both objects and * arrays; scalars pass through unchanged. */ export function normalizeRunVarying(value) { if (Array.isArray(value)) { return value.map(normalizeRunVarying); } if (typeof value === "object" && value !== null) { const out = {}; for (const key of Object.keys(value)) { out[key] = kRunVaryingExplainFields.has(key) ? "" : normalizeRunVarying(value[key]); } return out; } return value; } /** * How a candidate plan's multi-planner trial period ended. * kEof - the plan exhausted its results before any trial bound could stop it. * kFullBatch - the plan buffered the trial's target number of results, without hitting EOF. * kExhaustedBudget - the plan met no early-exit condition and used up the per-plan work budget. * kTrialEndedEarly - the plan met no early-exit condition, but another plan did and ended the * trial period for everyone, so this plan was stopped short with budget left. * kFailed - the plan's trial ended by failing recoverably (e.g. a blocking sort over its * memory limit with disk use disallowed). Such a plan is ranked out but still * appears among the rejected plans, with partial counters and no score. */ export const MultiPlannerStopCondition = { kEof: "EOF", kFullBatch: "fullBatch", kExhaustedBudget: "exhaustedBudget", kTrialEndedEarly: "trialEndedEarly", kFailed: "failed", }; /** * Asserts that 'plan', one entry of a V3 explain's queryPlanner.plans[], ran a multi-planning trial * that ended with the 'expected' condition, one of 'MultiPlannerStopCondition'. A plan that ran a * trial carries at least one of the plan-level subobjects 'multiPlanEstimateStats' / * 'multiPlanFinalizeStats'. A plan that never ran a trial fails here: under strict cost-based * ranking (the queryPlanRanker knob) no plan runs one, and neither does a single plan. In the * mixed modes every candidate runs at least the capped trial, so every candidate passes. * * 'phase' names the subobject whose stopCondition to check: * - "multiPlanEstimateStats": how the capped trial phase of the mixed rankers ended. A later * trial may have ended differently; this is the capped phase's own value. * - "multiPlanFinalizeStats": how the trial that this subobject reports ended. It reports one of * three trials, whichever the plan ran: * (1) the capped trial resumed with the remaining budget, after the cost-based ranker could * not decide (e.g. an inestimable plan): every surviving plan carries both subobjects; * (2) pure multiplanning's single uncapped trial: no capped phase ran, so this is the plan's * only subobject; * (3) the finishing-up trial of the plan the cost-based ranker chose, which collects the works * the plan cache needs: only the winner carries this subobject, next to its estimate one. * - "final": the stop condition of the last phase the plan ran, i.e. of the last subobject * present. Use it when the caller does not care which phases the plan ran. */ export function assertStopCondition(plan, expected, phase) { assert(Object.values(MultiPlannerStopCondition).includes(expected), "Unknown stop condition", { expected, }); const presentGroups = ["multiPlanEstimateStats", "multiPlanFinalizeStats"].filter((name) => plan.hasOwnProperty(name), ); assert.gte(presentGroups.length, 1, "expected a plan that ran a multi-planning trial", {plan}); if (phase === "final") { phase = presentGroups[presentGroups.length - 1]; } else { assert( ["multiPlanEstimateStats", "multiPlanFinalizeStats"].includes(phase), "Unknown trial phase subobject", {phase}, ); assert(plan.hasOwnProperty(phase), "expected the plan to have run the phase", { plan, phase, }); } assert.eq(plan[phase].stopCondition, expected, {plan, phase}); } /** * Returns an element of explain output which represents a rejected candidate plan. */ export function getRejectedPlan(rejectedPlan) { // The 'queryPlan' format is used when the SBE engine is turned on. If this field is present, // it will hold a serialized winning plan, otherwise it will be stored in the 'rejectedPlan' // element itself. return rejectedPlan.hasOwnProperty("queryPlan") ? rejectedPlan.queryPlan : rejectedPlan; } /** * Returns a sub-element of the 'cachedPlan' explain output which represents a query plan. */ export function getCachedPlan(cachedPlan) { // The 'queryPlan' format is used when the SBE engine is turned on. If this field is present, it // will hold a serialized cached plan, otherwise it will be stored in the 'cachedPlan' field // itself. return cachedPlan.hasOwnProperty("queryPlan") ? cachedPlan.queryPlan : cachedPlan; } function isPlainObject(value) { return value && typeof value == "object" && value.constructor === Object; } export const kExplainChildFieldNames = [ "inputStage", "inputStages", "thenStage", "elseStage", "outerStage", "stages", "innerStage", "child", "leftChild", "rightChild", ]; /** * Removes unwanted/variable fields from the explain plan without altering the tree structure, * and if flatten is set to true, turns the tree structure into an array (useful for plans where every node has one child). */ export function normalizePlan(plan, flatten = true) { let results = []; if (!isPlainObject(plan)) { return results; } // Expand this array if you find new fields which are inconsistent across different test runs. // The last three are the V3 explain shape's per-node statistics grouping and plan-level // fields, which carry the same run-varying content as the legacy estimate fields above. const ignoreFields = [ "isCached", "indexVersion", "planNodeId", "cardinalityEstimate", "costEstimate", "estimatesMetadata", "statistics", "multiPlanEstimateStats", "multiPlanFinalizeStats", "solutionHashUnstable", ]; // Iterates over the plan while ignoring the `ignoreFields`, to create flattened stages whenever // `kExplainChildFieldNames` are encountered. ignoreFields.forEach((field) => delete plan[field]); const stack = [["root", {...plan}]]; while (stack.length > 0) { const [name, next] = stack.pop(); ignoreFields.forEach((field) => delete next[field]); for (const childField of kExplainChildFieldNames) { if (childField in next) { const child = next[childField]; if (flatten) delete next[childField]; if (Array.isArray(child)) { for (let i = 0; i < child.length; i++) { stack.push([childField, child[i]]); } } else { stack.push([childField, child]); } } } if (flatten) { results.push(next); } else if (name == "root" && !flatten) { results = plan; } } return results; } /** * Returns an object containing the winning plan and an array of rejected plans for the given * queryPlanner. Each of those plans is returned in its flattened form. */ export function formatQueryPlanner(queryPlanner, shouldFlatten = true) { let winningPlan = normalizePlan(getWinningPlanFromExplain(queryPlanner), shouldFlatten); let rejectedPlans = getRejectedPlansFromQueryPlanner(queryPlanner)?.map((plan) => normalizePlan(plan, shouldFlatten), ) ?? []; return {winningPlan, rejectedPlans}; } /** * Formats the given pipeline, which must be an array of stage objects. Returns an array of * formatted stages. It excludes fields which might differ in the explain across multiple executions * of the same query. */ export function formatPipeline(pipeline, shouldFlatten = true) { const results = []; // Pipeline must be an array of objects if (!pipeline || !Array.isArray(pipeline) || !pipeline.every(isPlainObject)) { return results; } // Expand this array if you find new fields which are inconsistent across different test runs. const ignoreFields = ["lsid"]; for (const stage of pipeline) { const keys = Object.keys(stage).filter((key) => key.startsWith("$")); if (keys.length !== 1) { throw Error("This is not a stage: " + tojson(stage)); } const stageName = keys[0]; if (stageName == "$cursor") { const queryPlanner = stage[stageName].queryPlanner; results.push({[stageName]: formatQueryPlanner(queryPlanner, shouldFlatten)}); } else { const stageCopy = {...stage[stageName]}; ignoreFields.forEach((field) => delete stageCopy[field]); // Don't keep any fields that are on the same level as the stage name results.push({[stageName]: stageCopy}); } } return results; } /** * Helper function to only add `field` to `dest` if it is present in `src`. A lambda can be passed * to transform the field value when it is added to `dest`. */ function addIfPresent(field, src, dest, lambda = (i) => i) { if (src && dest && field in src) { dest[field] = lambda(src[field]); } } /** * If queryPlanner contains an array of shards, this returns both the merger part and shards * part. Both are flattened. */ function invertShards(queryPlanner, shouldFlatten = true) { const winningPlan = queryPlanner.winningPlan; const shards = winningPlan.shards; if (!Array.isArray(shards)) { throw Error("Expected shards field to be array, got: " + tojson(shards)); } const topStage = {...winningPlan}; delete topStage.shards; const res = {mergerPart: normalizePlan(topStage, shouldFlatten), shardsPart: {}}; shards.forEach( (shard) => (res.shardsPart[shard.shardName] = formatQueryPlanner(shard, shouldFlatten)), ); return res; } /** * Help function to exclude fields from explain. */ function excludeFields(obj, fields) { if (Array.isArray(obj)) { // Process each element in the array. return obj.map((item) => excludeFields(item, fields)); } else if (obj !== null && typeof obj === "object") { const newObj = {}; for (const key of Object.keys(obj)) { if (!fields.includes(key)) { newObj[key] = excludeFields(obj[key], fields); } } return newObj; } return obj; } /** * Returns a formatted version of the explain, excluding fields which might differ in the explain * across multiple executions of the same query (e.g. caching information or UUIDs). */ export function formatExplainRoot(explain, shouldFlatten = true, fieldsToExclude = []) { let res = {}; if (!isPlainObject(explain)) { return res; } const formatExplainPipeline = (pipeline) => { return formatPipeline(pipeline, shouldFlatten); }; addIfPresent("mergeType", explain, res); if ("splitPipeline" in explain) { addIfPresent("mergerPart", explain.splitPipeline, res, formatExplainPipeline); addIfPresent("shardsPart", explain.splitPipeline, res, formatExplainPipeline); } if ("shards" in explain) { for (const [shardName, shardExplain] of Object.entries(explain["shards"])) { res[shardName] = "queryPlanner" in shardExplain ? formatQueryPlanner(shardExplain.queryPlanner, shouldFlatten) : formatExplainPipeline(shardExplain.stages); } } else if ( "queryPlanner" in explain && "winningPlan" in explain.queryPlanner && "shards" in explain.queryPlanner.winningPlan ) { res = {...res, ...invertShards(explain.queryPlanner, shouldFlatten)}; } else if ("queryPlanner" in explain) { res = {...res, ...formatQueryPlanner(explain.queryPlanner, shouldFlatten)}; } else if ("stages" in explain) { res.stages = formatExplainPipeline(explain.stages); } addIfPresent("queryShapeHash", explain, res); if (fieldsToExclude.length > 0) { return excludeFields(res, fieldsToExclude); } return res; } /** * Traverses a explain plan to find all occurrences of a specified stage. * * This function recursively navigates through the 'root' document, which should be * the output of an explain command (or any of its subdocuments). It * identifies and collects all plan stages that match the provided 'stage' name. * The function supports explain outputs from both aggregation pipelines and * query commands (e.g. find, count, etc..). * * @param {object} root The explain plan document or a subdocument thereof. * @param {string|null} stage The name of the stage to search for (e.g., 'IXSCAN', 'COLLSCAN'). * If 'null', the function returns all stages found in the 'root' document. * @returns {Array} A list of objects, where each object represents a stage * matching the 'stage' argument. Returns an empty array * if no matching stages are found or if the plan is empty. */ export function getPlanStages(root, stage) { let results = []; if (root.stage === stage || stage === undefined || root.nodeType === stage) { results.push(root); } if ("inputStage" in root) { results = results.concat(getPlanStages(root.inputStage, stage)); } if ("inputStages" in root) { for (let i = 0; i < root.inputStages.length; i++) { results = results.concat(getPlanStages(root.inputStages[i], stage)); } } if ("queryPlanner" in root) { results = results.concat( getPlanStages(getWinningPlanFromExplain(root.queryPlanner), stage), ); } if ("thenStage" in root) { results = results.concat(getPlanStages(root.thenStage, stage)); } if ("elseStage" in root) { results = results.concat(getPlanStages(root.elseStage, stage)); } if ("outerStage" in root) { results = results.concat(getPlanStages(root.outerStage, stage)); } if ("innerStage" in root) { results = results.concat(getPlanStages(root.innerStage, stage)); } if ("queryPlan" in root) { results = results.concat(getPlanStages(root.queryPlan, stage)); } if ("child" in root) { results = results.concat(getPlanStages(root.child, stage)); } if ("leftChild" in root) { results = results.concat(getPlanStages(root.leftChild, stage)); } if ("rightChild" in root) { results = results.concat(getPlanStages(root.rightChild, stage)); } if ("shards" in root) { if (Array.isArray(root.shards)) { results = root.shards.reduce( (res, shard) => res.concat( getPlanStages( shard.hasOwnProperty("winningPlan") ? getWinningPlanFromExplain(shard) : shard.executionStages, stage, ), ), results, ); } else { const shards = Object.keys(root.shards); results = shards.reduce( (res, shard) => res.concat(getPlanStages(root.shards[shard], stage)), results, ); } } if ("stages" in root) { results = results.concat(getAggPlanStages(root, stage)); } return results; } /** * Given the root stage of explain's JSON representation of a query plan ('root'), returns a list of * all the stages in 'root'. */ export function getAllPlanStages(root) { return getPlanStages(root); } /** * Given a stage of explain's JSON representation of a query plan, returns its immediate child * stages, in order. * * Use this instead of reading '.inputStage' directly: the legacy node shape nests a single child as * the 'inputStage' subdocument and multiple children as the 'inputStages' array, while the V3 node * shape always uses the array. Reading '.inputStage' therefore silently yields undefined on a V3 * plan (queryPlanner.plans[]), even though the V3 executionStats section keeps the legacy nesting. */ export function getChildStages(node) { if (node.hasOwnProperty("inputStages")) { return node.inputStages; } return node.hasOwnProperty("inputStage") ? [node.inputStage] : []; } /** * Given a stage of explain's JSON representation of a query plan, returns its only child stage, * asserting that it has exactly one. The node-shape-independent form of reading '.inputStage'; see * getChildStages(). */ export function getSingleChildStage(node) { const children = getChildStages(node); assert.eq(children.length, 1, "expected a stage with exactly one child", {node}); return children[0]; } /** * Given the root stage of explain's JSON representation of a query plan ('root'), returns the * subdocument with its stage as 'stage'. Returns null if the plan does not have such a stage. * Asserts that no more than one stage is a match. */ export function getPlanStage(root, stage) { assert(stage, "Stage was not defined in getPlanStage."); let planStageList = getPlanStages(root, stage); if (planStageList.length === 0) { return null; } else { assert( planStageList.length === 1, "getPlanStage expects to find 0 or 1 matching stages. planStageList: " + tojson(planStageList), ); return planStageList[0]; } } /** * Returns the set of rejected plans from the given replset or sharded explain output. */ export function getRejectedPlans(root) { if (root.hasOwnProperty("queryPlanner")) { if (isV3QueryPlanner(root.queryPlanner)) { return getRejectedPlansFromQueryPlanner(root.queryPlanner); } if (root.queryPlanner.winningPlan.hasOwnProperty("shards")) { const rejectedPlans = []; for (let shard of root.queryPlanner.winningPlan.shards) { for (let rejectedPlan of shard.rejectedPlans) { rejectedPlans.push(Object.assign({shardName: shard.shardName}, rejectedPlan)); } } return rejectedPlans; } return root.queryPlanner.rejectedPlans; } else if ("shards" in root) { for (const shardName in root.shards) { return getRejectedPlans(root.shards[shardName]); } } else { const firstStage = root.stages[0]; const cursorStage = firstStage && (firstStage.$cursor || firstStage.$geoNearCursor); assert(cursorStage, "expected a leading cursor stage", {root}); return getRejectedPlans(cursorStage); } } /** * Given the root stage of explain's JSON representation of a query plan ('root'), returns true if * the query planner reports at least one rejected alternative plan, and false otherwise. */ export function hasRejectedPlans(root) { function sectionHasRejectedPlans(explainSection) { if (isV3QueryPlanner(explainSection)) { // The V3 "plans" array holds the winner first, then the rejected plans. return explainSection.plans.length > 1; } assert(explainSection.hasOwnProperty("rejectedPlans"), tojson(explainSection)); return explainSection.rejectedPlans.length !== 0; } function cursorStageHasRejectedPlans(cursorStage) { assert(cursorStage.hasOwnProperty("$cursor"), tojson(cursorStage)); assert(cursorStage.$cursor.hasOwnProperty("queryPlanner"), tojson(cursorStage)); return sectionHasRejectedPlans(cursorStage.$cursor.queryPlanner); } if (root.hasOwnProperty("shards")) { // This is a sharded agg explain. Recursively check whether any of the shards has rejected // plans. const shardExplains = []; for (const shard in root.shards) { shardExplains.push(root.shards[shard]); } return shardExplains.some(hasRejectedPlans); } else if (root.hasOwnProperty("stages")) { // This is an agg explain. const cursorStages = getAggPlanStages(root, "$cursor"); return ( cursorStages.find((cursorStage) => cursorStageHasRejectedPlans(cursorStage)) !== undefined ); } else { // This is some sort of query explain. assert(root.hasOwnProperty("queryPlanner"), tojson(root)); if (isV3QueryPlanner(root.queryPlanner)) { return sectionHasRejectedPlans(root.queryPlanner); } assert(root.queryPlanner.hasOwnProperty("winningPlan"), tojson(root)); if (!root.queryPlanner.winningPlan.hasOwnProperty("shards")) { // This is an unsharded explain. return sectionHasRejectedPlans(root.queryPlanner); } // This is a sharded explain. Each entry in the shards array contains a 'winningPlan' and // 'rejectedPlans'. return ( root.queryPlanner.winningPlan.shards.find((shard) => sectionHasRejectedPlans(shard)) !== undefined ); } } /** * Returns an array of execution stages from the given replset or sharded explain output. */ export function getExecutionStages(root) { if ( root.hasOwnProperty("executionStats") && root.executionStats.executionStages.hasOwnProperty("shards") ) { const executionStages = []; for (let shard of root.executionStats.executionStages.shards) { executionStages.push( Object.assign( {shardName: shard.shardName, executionSuccess: shard.executionSuccess}, shard.executionStages, ), ); } return executionStages; } if (root.hasOwnProperty("shards")) { const executionStages = []; for (const shard in root.shards) { executionStages.push(root.shards[shard].executionStats.executionStages); } return executionStages; } return [root.executionStats.executionStages]; } /** * Returns an array of "executionStats" from the given replset or sharded explain output. */ export function getExecutionStats(root) { if (root.hasOwnProperty("shards")) { return Object.values(root.shards).map((shardExplain) => shardExplain.executionStats); } // If the root does not have executionStats but has stages, it is likely a classic pipeline // with a leading cursor stage. if (!root.hasOwnProperty("executionStats") && Array.isArray(root.stages)) { const firstStage = root.stages[0]; const cursorStage = firstStage && (firstStage.$cursor || firstStage.$geoNearCursor); assert(cursorStage, root); assert(cursorStage.hasOwnProperty("executionStats"), root); return [cursorStage.executionStats]; } assert(root.hasOwnProperty("executionStats"), root); if ( root.executionStats.hasOwnProperty("executionStages") && root.executionStats.executionStages.hasOwnProperty("shards") ) { return root.executionStats.executionStages.shards; } return [root.executionStats]; } /** * Extract the high-level stable fields from the root. These include fields such as "stage", * "nReturned", and "totalDocsExamined" that should remain the same across runs. Unstable * measurement fields such as "executionTimeMillis" and "totalChildMillis" are excluded, as are more * detailed fields. */ export function extractStableExecutionFieldsSummary(root) { if (!root) return undefined; const stableKeys = [ "stage", "nCounted", "nReturned", "limitAmount", "skipAmount", "isEOF", "totalDocsExamined", "totalKeysExamined", ]; const stable = {}; for (const key of stableKeys) { if (key in root) { stable[key] = root[key]; } } const input = extractStableExecutionFieldsSummary(root.inputStage); if (input) { stable.inputStage = input; } return stable; } /** * Get high-level stable fields from the executionStats section of explain from the root * executionStages field and any nested executionStages objects. */ export function getStableExecutionStats(explain) { const execStats = explain.executionStats; const topLevel = execStats.executionStages; const stableFields = extractStableExecutionFieldsSummary(topLevel); if (topLevel.shards) { const sortedShards = [...topLevel.shards].sort((a, b) => a.shardName.localeCompare(b.shardName), ); stableFields.shards = sortedShards.map((shard) => ({ nReturned: shard.nReturned, totalDocsExamined: shard.totalDocsExamined, totalKeysExamined: shard.totalKeysExamined, executionStages: extractStableExecutionFieldsSummary(shard.executionStages), })); } return [{executionStages: stableFields}]; } /** * Returns the winningPlan.queryPlan of each shard in the explain in a list. */ export function getShardQueryPlans(root) { let result = []; if (root.hasOwnProperty("shards")) { for (let shardName of Object.keys(root.shards)) { let shard = root.shards[shardName]; result.push(shard.queryPlanner.winningPlan.queryPlan); } } else { for (let shard of root.queryPlanner.winningPlan.shards) { result.push(shard.winningPlan.queryPlan); } } return result; } /** * Returns an array of strings representing the "planSummary" values found in the input explain. * Assumes the given input is the root of an explain. * * The helper supports sharded and unsharded explain. */ export function getPlanSummaries(root) { let res = []; // Queries that use the find system have top-level queryPlanner and winningPlan fields. If it's // a sharded query, the shards have their own winningPlan fields to look at. if ("queryPlanner" in root && "winningPlan" in root.queryPlanner) { const wp = root.queryPlanner.winningPlan; if ("shards" in wp) { for (let shard of wp.shards) { res.push(shard.winningPlan.planSummary); } } else { res.push(wp.planSummary); } } // Queries that use the agg system either have a top-level stages field or a top-level shards // field. getQueryPlanner pulls the queryPlanner out of the stages/cursor subfields. if ("stages" in root) { res.push(getQueryPlanner(root).winningPlan.planSummary); } if ("shards" in root) { for (let shardName of Object.keys(root.shards)) { let shard = root.shards[shardName]; res.push(getQueryPlanner(shard).winningPlan.planSummary); } } return res.filter((elem) => elem !== undefined); } /** * Given the root stage of agg explain's JSON representation of a query plan ('root'), returns all * subdocuments whose stage is 'stage'. This can either be an agg stage name like "$cursor" or * "$sort", or a query stage name like "IXSCAN" or "SORT". * * If 'useQueryPlannerSection' is set to 'true', the 'queryPlanner' section of the explain output * will be used to lookup the given 'stage', even if 'executionStats' section is available. * * Returns an empty array if the plan does not have the requested stage. Asserts that agg explain * structure matches expected format. */ export function getAggPlanStages(root, stage, useQueryPlannerSection = false) { assert(stage, "Stage was not defined in getAggPlanStages."); let results = []; function getDocumentSources(docSourceArray) { let results = []; for (let i = 0; i < docSourceArray.length; i++) { let properties = Object.getOwnPropertyNames(docSourceArray[i]); if (properties[0] === stage) { results.push(docSourceArray[i]); } } return results; } function getStagesFromQueryLayerOutput(queryLayerOutput) { let results = []; assert(queryLayerOutput.hasOwnProperty("queryPlanner"), "missing queryPlanner section", { queryLayerOutput, }); const queryPlanner = queryLayerOutput.queryPlanner; assert( isV3QueryPlanner(queryPlanner) || queryPlanner.hasOwnProperty("winningPlan"), "missing plans or winningPlan", {queryLayerOutput}, ); // If execution stats are available, then use the execution stats tree. Otherwise use the // plan info from the "queryPlanner" section. if (queryLayerOutput.hasOwnProperty("executionStats") && !useQueryPlannerSection) { assert(queryLayerOutput.executionStats.hasOwnProperty("executionStages")); results = results.concat( getPlanStages(queryLayerOutput.executionStats.executionStages, stage), ); } else { results = results.concat(getPlanStages(getWinningPlanFromExplain(queryPlanner), stage)); } return results; } if (root.hasOwnProperty("stages")) { assert(root.stages.constructor === Array); results = results.concat(getDocumentSources(root.stages)); if (root.stages[0].hasOwnProperty("$cursor")) { results = results.concat(getStagesFromQueryLayerOutput(root.stages[0].$cursor)); } else if (root.stages[0].hasOwnProperty("$geoNearCursor")) { results = results.concat(getStagesFromQueryLayerOutput(root.stages[0].$geoNearCursor)); } } if (root.hasOwnProperty("shards")) { for (let elem in root.shards) { if (root.shards[elem].hasOwnProperty("queryPlanner")) { // The shard was able to optimize away the pipeline, which means that the format of // the explain output doesn't have the "stages" array. assert.eq(true, root.shards[elem].queryPlanner.optimizedPipeline); results = results.concat(getStagesFromQueryLayerOutput(root.shards[elem])); // Move onto the next shard. continue; } if (!root.shards[elem].hasOwnProperty("stages")) { continue; } assert(root.shards[elem].stages.constructor === Array); results = results.concat(getDocumentSources(root.shards[elem].stages)); const firstStage = root.shards[elem].stages[0]; if (firstStage.hasOwnProperty("$cursor")) { results = results.concat(getStagesFromQueryLayerOutput(firstStage.$cursor)); } else if (firstStage.hasOwnProperty("$geoNearCursor")) { results = results.concat(getStagesFromQueryLayerOutput(firstStage.$geoNearCursor)); } } } // If the agg pipeline was completely optimized away, then the agg explain output will be // formatted like the explain output for a find command. if (root.hasOwnProperty("queryPlanner")) { assert.eq(true, root.queryPlanner.optimizedPipeline); results = results.concat(getStagesFromQueryLayerOutput(root)); } return results; } /** * Given the root stage of agg explain's JSON representation of a query plan ('root'), returns the * subdocument with its stage as 'stage'. Returns null if the plan does not have such a stage. * Asserts that no more than one stage is a match. * * If 'useQueryPlannerSection' is set to 'true', the 'queryPlanner' section of the explain output * will be used to lookup the given 'stage', even if 'executionStats' section is available. */ export function getAggPlanStage(root, stage, useQueryPlannerSection = false) { assert(stage, "Stage was not defined in getAggPlanStage."); let planStageList = getAggPlanStages(root, stage, useQueryPlannerSection); if (planStageList.length === 0) { return null; } else { assert.eq( 1, planStageList.length, "getAggPlanStage expects to find 0 or 1 matching stages. planStageList: " + tojson(planStageList), ); return planStageList[0]; } } /** * Given the root stage of an explain's JSON representation of a query plan ('root'), returns the * specified stage of the plan. * * The normal getAggPlanStages() doesn't find certain stages in the sharded scenario since they * exist in the splitPipeline. **/ export function getStageFromSplitPipeline(root, stage) { function checkForStageInSubAggPipe(subAggPipe, stage) { for (let i = 0; i < subAggPipe.length; i++) { const subAggStage = subAggPipe[i]; if (subAggStage.hasOwnProperty(stage)) { return subAggStage; } } } if (root.splitPipeline != null) { // If there is only one shard, the whole pipeline will run on that shard. let subAggPipe = root.splitPipeline === null ? root.shards["shard-rs0"].stages : root.splitPipeline.mergerPart; // Check if the requested stage exists in the merger part. const stageInMergerPart = checkForStageInSubAggPipe(subAggPipe, stage); if (stageInMergerPart) { return stageInMergerPart; } // If the requested stage isn't in the merger part, it might be in the shards part. subAggPipe = root.splitPipeline.shardsPart; return checkForStageInSubAggPipe(subAggPipe, stage); } else { return getAggPlanStage(root, stage); } } export function getUnionWithStage(root) { return getStageFromSplitPipeline(root, "$unionWith"); } export function getLookupStage(root) { return getStageFromSplitPipeline(root, "$lookup"); } /** * Returns all occurrences of a stage in a sharded explain's splitPipeline, * searching both mergerPart and shardsPart. Each result is tagged with which * part it came from so callers can assert placement. * * @param {object} root Explain output (must contain splitPipeline). * @param {string} stage Stage name including '$' (e.g. "$testVectorSearch"). * @returns {Array<{part: "mergerPart"|"shardsPart", stage: object}>} */ export function getSplitPipelineStages(root, stage) { if (!root.splitPipeline) { return getAggPlanStages(root, stage); } const collect = (part) => (root.splitPipeline[part] || []) .filter((s) => s.hasOwnProperty(stage)) .map((s) => ({part, stage: s})); return [...collect("mergerPart"), ...collect("shardsPart")]; } export function countSplitPipelineStages(root, stage) { return getSplitPipelineStages(root, stage).length; } /** * Returns every occurrence of `stage` as a flat array of raw stage subdocuments, regardless of * whether the explain is a single pipeline or a sharded split (mergerPart + shardsPart) pipeline. * Unlike getSplitPipelineStages, which tags split results with their `part`, this always yields the * bare stage objects so callers that only care about the stage spec get a uniform shape. * * @param {object} explain Explain output. * @param {string} stage Stage name including '$' (e.g. "$sort"). * @returns {Array} The matching stage subdocuments. */ export function getAggStagesAcrossSplitPipeline(explain, stage) { if (explain.splitPipeline != null) { return getSplitPipelineStages(explain, stage).map(({stage}) => stage); } return getAggPlanStages(explain, stage); } /** * Given an explain node representing a $lookup stage, identify the index used in an INLJ * strategy and return its name and key pattern. * TODO: SERVER-121842 Remove the check for the presence of the indexName field once all * supported releases have featureFlagLookupWithPipelinesInSbe enabled * * @param {object} plan The explain plan node representing the $lookup stage. * @returns {object} An object exposing indexName and indexKeyPattern from the INLJ strategy. */ export function getLookupStageIndexStrategy(plan) { if (plan.hasOwnProperty("indexName")) { return { indexName: plan.indexName, indexKeyPattern: plan.indexKeyPattern, }; } else if (plan.hasOwnProperty("inputStages")) { var ixscan = getPlanStage(plan.inputStages[1], "IXSCAN"); if (ixscan) { return { indexName: ixscan.indexName, indexKeyPattern: ixscan.keyPattern, }; } } return {indexName: null, indexKeyPattern: null}; } /** * Given the root stage of agg explain's JSON representation of a query plan ('root'), returns * whether the plan has a stage called 'stage'. It could have more than one to allow for sharded * explain plans, and it can search for a query planner stage like "FETCH" or an agg stage like * "$group." */ export function aggPlanHasStage(root, stage) { return getAggPlanStages(root, stage).length > 0; } /** * Given the root stage of explain's BSON representation of a query plan ('root'), * returns true if the plan has a stage called 'stage'. */ export function planHasStage(db, root, stage) { assert(stage, "Stage was not defined in planHasStage."); return getPlanStages(root, stage).length > 0; } /** * A query is covered iff it does *not* have a FETCH stage or a COLLSCAN. * * Given the root stage of explain's BSON representation of a query plan ('root'), * returns true if the plan is index only. Otherwise returns false. */ export function isIndexOnly(db, root) { return !planHasStage(db, root, "FETCH") && !planHasStage(db, root, "COLLSCAN"); } /** * Returns true if the BSON representation of a plan rooted at 'root' is using * an index scan, and false otherwise. */ export function isIxscan(db, root) { return planHasStage(db, root, "IXSCAN"); } /** * Returns true if the BSON representation of a plan rooted at 'root' is using * a count scan scan, and false otherwise. */ export function isCountScan(db, root) { return planHasStage(db, root, "COUNT_SCAN"); } /** * Returns true if the plan is formed of a single EOF stage. False otherwise. */ export function isEofPlan(db, root) { return planHasStage(db, root, "EOF"); } /** * Returns true if the plan contains fetch stages containing '$alwaysFalse' filters, or false * otherwise. */ export function isAlwaysFalsePlan(root) { const hasAlwaysFalseFilter = (stage) => stage && stage.filter && stage.filter["$alwaysFalse"] === 1; return getPlanStages(root, "FETCH").every(hasAlwaysFalseFilter); } export function isIdhackOrExpress(db, root) { return isExpress(db, root) || isIdhack(db, root); } /** * Returns true if the BSON representation of a plan rooted at 'root' is using * the idhack fast path, and false otherwise. These can be represented either as * explicit 'IDHACK' or as 'CLUSTERED_IXSCAN' stages with equal min & max * record bounds in the case of clustered collections. */ export function isIdhack(db, root) { if (planHasStage(db, root, "IDHACK")) { return true; } if (!isClusteredIxscan(db, root)) { return false; } const stage = getPlanStages(root, "CLUSTERED_IXSCAN")[0]; if (stage.minRecord instanceof ObjectId) { return stage.minRecord.equals(stage.maxRecord); } else { if (isObject(stage.minRecord) && isObject(stage.maxRecord)) { return documentEq(stage.minRecord, stage.maxRecord); } return stage.minRecord === stage.maxRecord; } } /** * Returns true if the BSON representation of a plan rooted at 'root' is using * the EXPRESS executor, and false otherwise. */ export function isExpress(db, root) { return ( planHasStage(db, root, "EXPRESS_IXSCAN") || planHasStage(db, root, "EXPRESS_CLUSTERED_IXSCAN") || planHasStage(db, root, "EXPRESS_UPDATE") || planHasStage(db, root, "EXPRESS_DELETE") ); } /** * Returns true if the BSON representation of a plan rooted at 'root' is using * a collection scan, and false otherwise. */ export function isCollscan(db, root) { return planHasStage(db, root, "COLLSCAN"); } /** * Returns true if the BSON representation of a plan rooted at 'root' is using * a clustered Ix scan, and false otherwise. */ export function isClusteredIxscan(db, root) { return planHasStage(db, root, "CLUSTERED_IXSCAN"); } /** * Returns true if the BSON representation of a plan rooted at 'root' is using the aggregation * framework, and false otherwise. */ export function isAggregationPlan(root) { if (root.hasOwnProperty("shards")) { const shards = Object.keys(root.shards); return ( shards.reduce( (res, shard) => (res + root.shards[shard].hasOwnProperty("stages") ? 1 : 0), 0, ) > 0 ); } return root.hasOwnProperty("stages"); } /** * Returns true if the BSON representation of a plan rooted at 'root' is using just the query layer, * and false otherwise. */ export function isQueryPlan(root) { if (root.hasOwnProperty("shards")) { const shards = Object.keys(root.shards); return ( shards.reduce( (res, shard) => (res + root.shards[shard].hasOwnProperty("queryPlanner") ? 1 : 0), 0, ) > 0 ); } return root.hasOwnProperty("queryPlanner"); } /** * Returns true if every winning plan present in the explain satisfies the predicate. Returns * false otherwise. */ export function everyWinningPlan(explain, predicate) { return getQueryPlanners(explain) .map((queryPlanner) => getWinningPlanFromExplain(queryPlanner, false)) .every(predicate); } /** * Get the "chunk skips" for a single shard. Here, "chunk skips" refer to documents excluded by the * shard filter. */ export function getChunkSkipsFromShard(shardPlan, shardExecutionStages) { const shardFilterPlanStage = getPlanStage( getWinningPlanFromExplain(shardPlan), "SHARDING_FILTER", ); if (!shardFilterPlanStage) { return 0; } if (shardFilterPlanStage.hasOwnProperty("planNodeId")) { const shardFilterNodeId = shardFilterPlanStage.planNodeId; // If the query plan's shard filter has a 'planNodeId' value, we search for the // corresponding SBE filter stage and use its stats to determine how many documents were // excluded. const filters = getPlanStages(shardExecutionStages.executionStages, "filter").filter( (stage) => stage.planNodeId === shardFilterNodeId, ); return filters.reduce( (numSkips, stage) => numSkips + (stage.numTested - stage.nReturned), 0, ); } else { // Otherwise, we assume that execution used a "classic" SHARDING_FILTER stage, which // explicitly reports a "chunkSkips" value. const filters = getPlanStages(shardExecutionStages.executionStages, "SHARDING_FILTER"); return filters.reduce((numSkips, stage) => numSkips + stage.chunkSkips, 0); } } /** * Get the sum of "chunk skips" from all shards. Here, "chunk skips" refer to documents excluded by * the shard filter. */ export function getChunkSkipsFromAllShards(explainResult) { const shardPlanArray = explainResult.queryPlanner.winningPlan.shards; const shardExecutionStagesArray = explainResult.executionStats.executionStages.shards; assert.eq(shardPlanArray.length, shardExecutionStagesArray.length, explainResult); let totalChunkSkips = 0; for (let i = 0; i < shardPlanArray.length; i++) { totalChunkSkips += getChunkSkipsFromShard(shardPlanArray[i], shardExecutionStagesArray[i]); } return totalChunkSkips; } /** * Given explain output at executionStats level verbosity, for a count query, confirms that the root * stage is COUNT or RECORD_STORE_FAST_COUNT and that the result of the count is equal to * 'expectedCount'. */ export function assertExplainCount({explainResults, expectedCount}) { const execStages = explainResults.executionStats.executionStages; // If passed through mongos, then the root stage should be the mongos SINGLE_SHARD stage or // SHARD_MERGE stages, with COUNT as the root stage on each shard. If explaining directly on the // shard, then COUNT is the root stage. if ("SINGLE_SHARD" == execStages.stage || "SHARD_MERGE" == execStages.stage) { for (let shardExplain of execStages.shards) { const countStage = shardExplain.executionStages; assert( countStage.stage === "COUNT" || countStage.stage === "RECORD_STORE_FAST_COUNT", `Root stage on shard is not COUNT or RECORD_STORE_FAST_COUNT. ` + `The actual plan is: ${tojson(explainResults)}`, ); } assert.eq( execStages.nCounted, expectedCount, assert.eq(execStages.nCounted, expectedCount, "wrong count result"), ); } else { assert( execStages.stage === "COUNT" || execStages.stage === "RECORD_STORE_FAST_COUNT", `Root stage on shard is not COUNT or RECORD_STORE_FAST_COUNT. ` + `The actual plan is: ${tojson(explainResults)}`, ); assert.eq( execStages.nCounted, expectedCount, "Wrong count result. Actual: " + execStages.nCounted + "expected: " + expectedCount, ); } } /** * Verifies that a given query uses an index and is covered when used in a count command. */ export function assertCoveredQueryAndCount({collection, query, project, count}) { let explain = collection.find(query, project).explain(); assert( isIndexOnly(db, getWinningPlanFromExplain(explain.queryPlanner)), "Winning plan was not covered: " + tojson(explain.queryPlanner.winningPlan), ); // Same query as a count command should also be covered. explain = collection.explain("executionStats").find(query).count(); assert( isIndexOnly(db, getWinningPlanFromExplain(explain.queryPlanner)), "Winning plan for count was not covered: " + tojson(explain.queryPlanner.winningPlan), ); assertExplainCount({explainResults: explain, expectedCount: count}); } /** * Runs explain() operation on 'cmdObj' and verifies that all the stages in 'expectedStages' are * present exactly once in the plan returned. When 'stagesNotExpected' array is passed, also * verifies that none of those stages are present in the explain() plan. */ export function assertStagesForExplainOfCommand({coll, cmdObj, expectedStages, stagesNotExpected}) { const plan = assert.commandWorked(coll.runCommand({explain: cmdObj})); const winningPlan = getWinningPlanFromExplain(plan.queryPlanner); for (let expectedStage of expectedStages) { assert( planHasStage(coll.getDB(), winningPlan, expectedStage), "Could not find stage " + expectedStage + ". Plan: " + tojson(plan), ); } for (let stage of stagesNotExpected || []) { assert( !planHasStage(coll.getDB(), winningPlan, stage), "Found stage " + stage + " when not expected. Plan: " + tojson(plan), ); } return plan; } /** * Runs an explain command, retrying on transient NamespaceNotSharded errors that can * surface during explain for timeseries collections due to a known server bug. Non-transient errors fail immediately. * * @param {Object} dbOrColl - A DB or collection object with a runCommand method. * @param {Object} explainCmd - The full explain command object, * e.g. {explain: {delete: collName, deletes: [...]}, verbosity: "queryPlanner"}. * @returns {Object} The successful explain result. */ export function runExplainWithRoutingRetry(dbOrColl, explainCmd) { let result; assert.soon( () => { result = dbOrColl.runCommand(explainCmd); if (result.ok === 1) { return true; } // TODO SERVER-114324: NamespaceNotSharded on explain for timeseries is a known // server bug. Remove this retry once SERVER-114324 is fixed. if (result.code === ErrorCodes.NamespaceNotSharded) { return false; } assert(false, "Explain failed with unexpected error", {result}); }, () => `Explain command failed after retries: ${tojson(result)}`, ); return result; } /** * Get the 'planCacheKey' from 'explain'. */ export function getPlanCacheKeyFromExplain(explain) { return getQueryPlanners(explain) .map((qp) => { assert(qp.hasOwnProperty("planCacheKey")); return qp.planCacheKey; }) .at(0); } /** * Get the 'planCacheShapeHash' from 'object'. */ export function getPlanCacheShapeHashFromObject(object) { // TODO SERVER-93305: Remove deprecated 'queryHash' usages. const planCacheShapeHash = object.planCacheShapeHash || object.queryHash; assert.neq(planCacheShapeHash, undefined); return planCacheShapeHash; } /** * Get the 'planCacheShapeHash' from 'explain'. */ export function getPlanCacheShapeHashFromExplain(explain) { return getQueryPlanners(explain) .map(getPlanCacheShapeHashFromObject) .reduce((hash0, hash1) => { assert.eq(hash0, hash1); return hash0; }); } /** * Helper to run a explain on the given query shape and get the "planCacheKey" from the explain * result. */ export function getPlanCacheKeyFromShape({ query = {}, projection = {}, sort = {}, collation = {}, collection, db, }) { const explainRes = assert.commandWorked( collection.explain().find(query, projection).collation(collation).sort(sort).finish(), ); return getPlanCacheKeyFromExplain(explainRes); } /** * Helper to run a explain on the given pipeline and get the "planCacheKey" from the explain * result. */ export function getPlanCacheKeyFromPipeline(pipeline, collection) { const explainRes = assert.commandWorked(collection.explain().aggregate(pipeline)); return getPlanCacheKeyFromExplain(explainRes); } /** * Given the winning query plan, flatten query plan tree into a list of plan stage names. */ export function flattenQueryPlanTree(winningPlan) { let stages = []; while (winningPlan) { stages.push(winningPlan.stage); if (winningPlan.hasOwnProperty("inputStages")) winningPlan = winningPlan.inputStages[0]; else winningPlan = winningPlan.inputStage; } stages.reverse(); return stages; } /** * Assert that a command plan has no FETCH stage or if the stage is present, it has no filter. */ export function assertNoFetchFilter({coll, cmdObj}) { const plan = assert.commandWorked(coll.runCommand({explain: cmdObj})); const winningPlan = getWinningPlanFromExplain(plan.queryPlanner); const fetch = getPlanStage(winningPlan, "FETCH"); assert(fetch === null || !fetch.hasOwnProperty("filter"), "Unexpected fetch: " + tojson(fetch)); return winningPlan; } /** * Assert that a find plan has a FETCH stage with expected filter and returns a specified number of * results. */ export function assertFetchFilter({coll, predicate, expectedFilter, nReturned}) { const exp = coll.find(predicate).explain("executionStats"); const plan = getWinningPlanFromExplain(exp.queryPlanner); const fetch = getPlanStage(plan, "FETCH"); assert(fetch !== null, "Missing FETCH stage " + plan); assert( fetch.hasOwnProperty("filter"), "Expected filter in the fetch stage, got " + tojson(fetch), ); assert.eq( expectedFilter, fetch.filter, "Expected filter " + tojson(expectedFilter) + " got " + tojson(fetch.filter), ); if (nReturned !== null) { assert.eq( exp.executionStats.nReturned, nReturned, "Expected " + nReturned + " documents, got " + exp.executionStats.nReturned, ); } } /** * Recursively checks if a javascript object contains a nested property key and returns the values. */ export function getNestedProperties(object, key) { let accumulator = []; function traverse(object) { if (typeof object !== "object") { return; } for (const k in object) { if (k == key) { accumulator.push(object[k]); } traverse(object[k]); } return; } traverse(object); return accumulator; } /** * Recognizes the query engine used by the query (sbe/classic). */ export function getEngine(explain) { const sbePlans = getQueryPlanners(explain).flatMap((queryPlanner) => getNestedProperties(queryPlanner, "slotBasedPlan"), ); return sbePlans.length == 0 ? "classic" : "sbe"; } export function getWarnings(explain) { return getQueryPlanners(explain).flatMap((queryPlanner) => getNestedProperties(queryPlanner, "warning"), ); } /** * Asserts that a pipeline runs with the engine that is passed in as a parameter. */ export function assertEngine(pipeline, engine, coll) { const explain = coll.explain().aggregate(pipeline); assert.eq(getEngine(explain), engine); } /** * Returns the number of index scans in a query plan. */ export function getNumberOfIndexScans(explain) { const indexScans = getPlanStages(getWinningPlanFromExplain(explain.queryPlanner), "IXSCAN"); return indexScans.length; } /** * Returns the number of column scans in a query plan. */ export function getNumberOfColumnScans(explain) { const columnIndexScans = getPlanStages( getWinningPlanFromExplain(explain.queryPlanner), "COLUMN_SCAN", ); return columnIndexScans.length; } /* * Returns whether a query is using a multikey index. */ export function isIxscanMultikey(winningPlan) { let ixscanStage = getPlanStage(winningPlan, "IXSCAN"); return ixscanStage && ixscanStage.isMultiKey; } /** * Verify that the explain command output 'explain' shows a BATCHED_DELETE stage with an * nWouldDelete value equal to 'nWouldDelete'. */ export function checkNWouldDelete(explain, nWouldDelete) { assert.commandWorked(explain); assert("executionStats" in explain); let executionStats = explain.executionStats; assert("executionStages" in executionStats); // If passed through mongos, then BATCHED_DELETE stage(s) should be below the SHARD_WRITE // mongos stage. Otherwise the BATCHED_DELETE stage is the root stage. let execStages = executionStats.executionStages; if ("SHARD_WRITE" === execStages.stage) { let totalToBeDeletedAcrossAllShards = 0; execStages.shards.forEach(function (shardExplain) { const rootStageName = shardExplain.executionStages.stage; assert(rootStageName === "BATCHED_DELETE", tojson(execStages)); totalToBeDeletedAcrossAllShards += shardExplain.executionStages.nWouldDelete; }); assert.eq(totalToBeDeletedAcrossAllShards, nWouldDelete, explain); } else { assert(execStages.stage === "BATCHED_DELETE", explain); assert.eq(execStages.nWouldDelete, nWouldDelete, explain); } } /** * Recursively remove fields which conditionally appear in plans that may contribute to spurious * differences. Modifies the parameter in-place, no return value. */ export function canonicalizePlan(p) { delete p.planNodeId; delete p.isCached; delete p.cardinalityEstimate; delete p.costEstimate; delete p.estimatesMetadata; // The V3 explain shape's per-node statistics grouping and plan-level fields. delete p.statistics; delete p.multiPlanEstimateStats; delete p.multiPlanFinalizeStats; delete p.solutionHashUnstable; if (p.hasOwnProperty("inputStage")) { canonicalizePlan(p.inputStage); } else if (p.hasOwnProperty("inputStages")) { p.inputStages.forEach((s) => { canonicalizePlan(s); }); } } /** * Returns index of stage in a aggregation pipeline stage plan running on a single node * (will not work for sharded clusters). * 'root' is root of explain JSON. * Returns -1 if stage does not exist. */ export function getIndexOfStageOnSingleNode(root, stageName) { if (root.hasOwnProperty("stages")) { for (let i = 0; i < root.stages.length; i++) { if (root.stages[i].hasOwnProperty(stageName)) { return i; } } } return -1; } /** * Given the root of an explain, return an array of all enumerated plans. */ export function getAllPlans(explain) { return [getWinningPlanFromExplain(explain), ...getRejectedPlans(explain)]; } /** * Given the root of an explain, checks whether it has a $mergeCursors stage. */ export function hasMergeCursors(explain) { if (explain.hasOwnProperty("splitPipeline")) { if (explain.splitPipeline && explain.splitPipeline.hasOwnProperty("mergerPart")) { if ( explain.splitPipeline.mergerPart[0] && explain.splitPipeline.mergerPart[0].hasOwnProperty("$mergeCursors") ) { return true; } } } return false; } /** * Given a query, asserts that there is an entry in the plan cache for it and returns that entry. */ export function getCachedPlanForQuery(db, coll, filter) { const planCacheKey = getPlanCacheKeyFromShape({query: filter, collection: coll, db: db}); const matchingCacheEntries = coll.getPlanCache().list([{$match: {planCacheKey: planCacheKey}}]); assert.eq(matchingCacheEntries.length, 1, coll.getPlanCache().list()); return matchingCacheEntries[0]; } /** * Asserts that the plan contained in the plan cache 'entry' is an index scan plan over the index * with the given 'indexName'. * * Also verifies that the 'planCacheShapeHash' matches the provided 'expectedPlanCacheShapeHash'. */ export function assertPlanHasIxScanStage(entry, indexName, expectedPlanCacheShapeHash) { assert.eq(entry.planCacheShapeHash, expectedPlanCacheShapeHash, entry); const cachedPlan = getCachedPlan(entry.cachedPlan); assert.eq(entry.version, "1", entry); const stage = getPlanStage(cachedPlan, "IXSCAN"); assert.neq(stage, null, entry); assert.eq(indexName, stage.indexName, entry); } /** * Returns true if the plan was created by the multiplanner subplanner. In this case the plan has a SUBPLAN stage * and the rejected plans are empty, since a single plan was composed from individual branch plans. */ export function isSubplannerCompositePlan(explain) { const subplan = getPlanStage(explain, "SUBPLAN"); return subplan != null && !hasRejectedPlans(explain); } /** * Asserts that the query's optimised plan returns the same results as a collection scan. */ export function assertResultsSameAsCollscan(coll, query) { const expected = coll.find(query).hint({$natural: 1}).toArray(); assertArrayEq({actual: coll.find(query).toArray(), expected}); } /** * Forces each candidate plan to completion via forcedPlanSolutionHash and asserts every plan * returns the same results as a collection scan. Silently passes when not supported (subplanning). */ export function assertResultsSameAllPlans(coll, query) { const db = coll.getDB(); if (!db.adminCommand({getParameter: 1, internalQueryAllowForcedPlanByHash: 1}).ok) { return; } const expected = coll.find(query).hint({$natural: 1}).toArray(); runWithParamsAllNonConfigNodes(db, {internalQueryAllowForcedPlanByHash: true}, () => { const plannerExplain = assert.commandWorked( db.runCommand({ explain: {find: coll.getName(), filter: query}, verbosity: "queryPlanner", }), ); for (const plan of getAllPlans(plannerExplain)) { if (!plan.hasOwnProperty("solutionHashUnstable")) { continue; } const res = db.runCommand({ find: coll.getName(), filter: query, forcedPlanSolutionHash: plan.solutionHashUnstable, }); if ( !res.ok && [ErrorCodes.IllegalOperation, ErrorCodes.NoQueryExecutionPlans].includes(res.code) ) { return; } assert.commandWorked(res); assertArrayEq({actual: new DBCommandCursor(db, res).toArray(), expected}); } }); } /** * Asserts that a query returns the expected results, that the optimised plan matches a collscan, * and that every candidate plan results are correct. */ export function assertQueryResults(coll, query, expected, opts = {}) { assertArrayEq({actual: coll.find(query).toArray(), expected, ...opts}); assertResultsSameAsCollscan(coll, query); assertResultsSameAllPlans(coll, query); }