-
Type:
Bug
-
Resolution: Won't Do
-
Priority:
Minor - P4
-
None
-
Affects Version/s: None
-
Component/s: None
-
None
-
Query Execution
-
ALL
-
None
-
None
-
None
-
None
-
None
-
None
-
None
Summary
CardinalityEstimator::propagateLimit (src/mongo/db/query/compiler/optimizer/cost_based_ranker/cardinality_estimator.cpp) splits a limit between the children of OR, AND_HASH, AND_SORTED and SORT_MERGE in proportion to their cardinality estimates, and passes a FETCH's limit on to its child. Both use CardinalityEstimate::toCount(), which floors:
propagateLimit(child.get(), (limitFraction * childCE).toCount()); // OR / AND / SORT_MERGE children propagateToChildren((limitFraction * inCE).toCount()); // FETCH child
Any child whose proportional share is below one row is therefore given a limit of 0. That sets its output estimate to 0 and scales the index scan beneath it down to 0 keys, so the whole subtree is costed as essentially free.
Impact
- Small limits over $or: with LIMIT 1 (e.g. findOne()), an OR estimated at 1,000 rows with children estimated at 600 and 400 gives shares of 0.6 and 0.4. Both become 0 and the OR plan costs almost nothing, while a competing single-index plan under the same limit is costed realistically.
- Near-empty branches: an OR branch whose filter matches almost nothing (e.g. an index scan on a common value with a residual filter on a rare combination, as produced by $all on multikey fields) is estimated at about one row. Its share of the limit floors to 0 and its scan is costed as free, although in reality it must scan every key before it can produce its row.
- Under sampling CE on master this is partly masked: sampled estimates are either 0, which propagateLimit skips, or multiples of collectionSize / sampleSize. Histogram and heuristic estimates can be fractional and hit it more easily. SERVER-139137 raises some zero sampling estimates to about one row, which exposes it.
Example (simple plan stability dataset, costBased + samplingCE, with SERVER-139137)
[{$match: {$and: [{a_compound: {$exists: true}}, {$or: [{a_compound: {$all: [6, 5]}}, {z_compound: {$nin: [8, 13]}}]}]}}, {$limit: 220}]
The OR (estimate ~221) gets limit 220, so the branch IXSCAN a_compound [6, 6] (~9,600 keys) + FETCH filter a_compound == 5 (estimate 1) gets floor(220/221 * 1) = 0. The OR plan is costed at 0.54 vs. 0.85 for the full a_compound scan under the limit, and wins: 12,832 keys+docs examined vs. 442 with the full scan.
Proposed fix
Round child limit shares up rather than down: a child expected to produce a fraction of a row must still run until it produces one row or is exhausted. Rounding the two call sites above up with std::ceil restores the cheaper plan in the example. A prototype passes cost_based_ranker_test, join_ordering_test, and all 138 jstests in jstests/noPassthroughWithMongod/query/cbr and .../plan_ranking.
Note that a proportional split is itself a heuristic, since OR executes its children sequentially. Rounding up only prevents fractional shares from making subtrees free.
Suggested testing
- A cardinality_estimator_test case: LIMIT 1 (and a near-empty branch case) over an OR of two index scans; assert the child scans keep non-zero estimates and that the OR plan is not costed below a comparable single-index plan.
- Regenerate and review the CBR plan stability goldens in all CE modes (query_golden_cbr_sampling, query_golden_cbr_histogram, query_golden_cbr_automatic_cost_choice, query_golden_cbr_automatic_no_multiplanning_results, query_golden_join_optimization_plan_stability), since limit propagation applies to every CE mode.
- related to
-
SERVER-139137 Estimate NDVs within samples to handle zero CE cases on equality predicates
-
- In Progress
-