Problem

CardinalityEstimator::estimateIndexSeeks() estimates the number of seeks of an index scan as the number of intervals of the last non-open field times the NDV of the preceding fields, where the NDV is computed on the sample documents that satisfy the bounds of those fields (estimateNDV / estimateNDVMultiKey). With the default sample (375 documents) the bounds often match only a handful of sample documents, and the resulting NDV is close to the collection size (and above it for multikey fields). The seek estimate is then off by up to four orders of magnitude, independently of the (correct or clamped) key estimate.

The cost model charges 1134.71 ns per seek and 435.55 ns per key, so a seek estimate in the hundreds of thousands dominates the cost of the index scan and CBR rejects the plan, even when it examines the fewest keys.

Examples

Dataset: the plan_stability dataset (100,000 documents), run with the settings of query_golden_cbr_sampling (samplingCE, strides sampling, default sample size).

1. Pipeline 226 in plan_stability_pipelines.js

{$match: {$nor: [{k_compound: {$gte: 15}}, {a_compound: {$all: [11, 5, 7, 12]}}],
          a_compound: {$elemMatch: {$exists: true, $in: [11, 6, 15]}},
          d_idx: {$exists: true}}},
{$sort: {c_idx: -1, d_idx: -1, z_idx: -1}}, {$project: {_id: 0, z_idx: 1}}

The plan on index {k_compound: 1, a_compound: 1} has bounds k_compound: [MinKey, 15), (inf, MaxKey] and a_compound: [6, 6], [11, 11], [15, 15].

• Estimated seeks: 300,000 (100,000 x 3 intervals). Actual: 15 distinct values of k_compound x 3 = 45.
• Estimated cost 340.4 against 1.18 for the plan on k_compound_1. CBR picks the latter: 3001 keys+docs examined against 476 for the rejected plan (259 keys).

2. Pipeline 18 in plan_stability_pipelines2.js (an $or with several conjuncts and a sort)
The plan on index {field31_list_idx: -1, field7_str_idx: -1} has bounds field31_list_idx: [[], []], [undefined, undefined] and field7_str_idx: ["MUU", ""].

• Estimated seeks: 143,200. Estimate with a full-collection sample: 1. Actual: 2.
• Estimated cost 162.5 against 59.5 for the plan on field7_str_idx_1_field20_Timestamp_idx_-1_field6_mixed_idx_-1, which CBR picks: 49,219 keys+docs examined against 113 for the rejected plan (57 keys).

The formula is correct when its input is

Raising the sample size (internalSamplingSizeOverride) with everything else unchanged:

With a sample large enough that the NDV input is accurate, the existing formula produces the true seek counts and the plan with the least work wins in both queries. The defect is therefore in the NDV input when few sample documents satisfy the bounds. We have not yet traced where in estimateNDV / estimateNDVMultiKey the extrapolation goes wrong.

Relation to the zero-CE clamp

The key estimate and the seek estimate are computed independently, and both depend on how many sample documents survive the bounds. The key estimate uses the full bounds and is clamped to 1 when no sample document matches (the "zero-CE" case). The NDV uses only the leading fields, so a few documents can still survive, and the extrapolated NDV is large. The two can therefore disagree: in example 1 the scan is estimated at 1 key (clamped) and 300,000 seeks. The clamp does not change the seek estimate; it changes the cost only through the key term, by about 0.1 ms in example 1 (computed from the cost formula, not measured).

Relation to SERVER-136561

SERVER-136561 describes a bias of the seek formula itself, with exact inputs (100-document collections). This ticket is about the NDV input to the formula. The upper bound proposed in SERVER-136561 (k_0 + NDV(f_0|B_0)*k_1 + ...) would not fix this problem, because the NDV terms in it are the inflated ones (about 300,000 for example 1).

Bound on the seek estimate based on executor invariant

seeks <= keysExamined + 1 holds for every IXSCAN. IndexScan performs one initial seek in initIndexScan(), and every further seek is triggered by IndexBoundsChecker::checkKey() returning MUST_ADVANCE for a key that was already counted in keysExamined (index_scan.cpp, the NEED_SEEK state is set only in that branch). A seek that lands at EOF ends the scan. The number of intervals does not enter this bound. We verified it on all 59 single-index scans of the two example queries (executed via hint); the two scans discussed above meet the tighter form seeks <= 1 + keysExamined - nReturned with equality.

Since inCE of an IXSCAN estimates keysExamined, the estimator should satisfy indexSeekCE <= inCE + 1. Example 1 violates it by five orders of magnitude (inCE = 0 before clamping, indexSeekCE = 300,000).

Possible directions (not validated)

• Cap the seek estimate at inCE + 1, using the unclamped inCE. In example 1 this reduces the seek estimate from 300,000 to 1 (actual: 45) and the plan wins. The cap makes the seek term inherit an underestimated inCE, which is a milder failure than today's: the key term and the seek term then agree, so the plan is misjudged by the key estimate alone. The tighter form 1 + inCE - outCE is not recommended as a cap, because the difference of two sample estimates can go negative.
• Replace the NDV extrapolation for small filtered samples with an estimator that is bounded by the estimated number of qualifying keys.
• Increase the default sample size. This is not a fix: it only moves the threshold and increases sampling cost.

Acceptance criteria

• Pipelines 226 and 18 above choose the plans with 476 and 113 keys+docs at the default sample size.
• The samplingCE plan_stability goldens show no query regressing by more than 1.2x on keys+docs. The ticket should list any query that changes.

Reproduction

1. buildscripts/resmoke.py run --suites=query_golden_cbr_sampling --pauseAfterPopulate jstests/query_golden/plan_stability.js (use plan_stability2.js for example 2); wait for "Pausing indefinitely".
2. Connect to port 20000, database test. Set internalQueryPlannerEnableSortIndexIntersection: true, internalQuerySamplingBySequentialScan: false and internalQuerySamplingByStrides: true, as runPlanStabilityPipelines() does.
3. Run the pipeline from the pipeline list with index 226 (or 18) as explain with executionStats. Read indexSeekEstimate, numKeysEstimate and costEstimate of the IXSCAN nodes of the rejected plans in queryPlanner.rejectedPlans.
4. Repeat after {db.adminCommand( \{setParameter: 1, internalSamplingSizeOverride: 100000}

   )}.