numKeysEstimate ignores overshoots for index skip scans

ExportXMLWordPrintableJSON

    • Type: Improvement
    • Resolution: Unresolved
    • Priority: Critical - P2
    • None
    • Affects Version/s: None
    • Component/s: None
    • Query Optimization
    • None
    • None
    • None
    • None
    • None
    • None
    • None

      For index skip scans, the number of matching keys in the sample is not an accurate estimator for the number of keys the index scan will examine during execution, as it ignores overshoots.

      Eg:

      const COLL_SIZE = 100;
const coll = db.num_keys_estimate_inaccurate;
coll.drop();
coll.insertOne({a: 0, b: 0});
for (let i = 0; i < COLL_SIZE; i++) {
    coll.insertOne({a: i, b: 1});
}
coll.createIndex({a: 1, b: 1});
db.adminCommand({setParameter: 1, featureFlagCostBasedRanker: true, internalQueryPlanRanker: "costBased", internalQueryCBRCEMode: "samplingCE", internalQuerySamplingBySequentialScan: true, internalSamplingSizeOverride: COLL_SIZE+1});
const res = coll.explain("executionStats").find({a: {$gte: 0}, b: 0}).hint({a: 1, b: 1}).finish();

function findIx(n) { if (!n) return null; if (n.stage === "IXSCAN") return n; return findIx(n.inputStage); }
const ix = findIx(res.executionStats.executionStages);
printjson({numKeysEstimate: ix.numKeysEstimate, keysExamined: ix.keysExamined});
printjson({ce: ix.cardinalityEstimate, nReturned: res.executionStats.nReturned});

      Prints:

       

      {
  numKeysEstimate: 1,
  keysExamined: 101
}
{
  ce: 1,
  nReturned: 1
}

      So the outCE estimation is accurate, but numKeysEstimate is underestimated by 100x (the size of the collection in this example). That is because there is one matching key in the sample, but during execution the index scan has to try seeking to all {a: ..., b: 0}, all resulting in an overshoot except the first. Thus it really examines all the keys.

       

      Discovered while examining plan quality regressions during SERVER-134637.

            Assignee:
            Unassigned
            Reporter:
            Kartal Kaan Bozdogan
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

              Created:
              Updated: