Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-36393

Contained $or pushdown optimization can cause internalQueryEnumerationMaxOrSolutions to be exceeded

XMLWordPrintableJSON

    • Query Optimization
    • ALL
    • Hide 
      (function() {
    "use strict";

    db.c.drop();
    db.c.createIndex({a: 1, c: 1});
    db.c.createIndex({b: 1, c: 1});
    db.c.createIndex({c: 1, b: 1});

    let explain = db.c.find({a: 1, $or: [{b: 1, c: 1}, {b: 2, c: 2}, {b: 3, c: 3}, {b: 4, c: 4}]})
                      .explain("allPlansExecution");
    let allPlansExec = explain.executionStats.allPlansExecution;

    // The number of candidate plans here is constrained by
    // internalQueryEnumerationMaxOrSolutions=10.
    // There are 10 OR plans generated, and one plan which indexes just the "a:1" predicate.
    assert.eq(11, allPlansExec.length);

    assert.commandWorked(
        db.adminCommand({setParameter: 1, internalQueryEnumerationMaxOrSolutions: 100}));
    explain = db.c.find({a: 1, $or: [{b: 1, c: 1}, {b: 2, c: 2}, {b: 3, c: 3}, {b: 4, c: 4}]})
                  .explain("allPlansExecution");
    allPlansExec = explain.executionStats.allPlansExecution;

    // After increasing internalQueryEnumerationMaxOrSolutions, there are many more possible plans
    // generated. With a real data set, one of the inhibited plans may be the best one!
    //
    // Note that we still run up against the limit of 64 total plans. The size of the plan space for
    // this query is roughly 3 ^ 4 = 81.
    assert.eq(64, allPlansExec.length);
}());
      Show
      (function() { "use strict" ; db.c.drop(); db.c.createIndex({a: 1, c: 1}); db.c.createIndex({b: 1, c: 1}); db.c.createIndex({c: 1, b: 1}); let explain = db.c.find({a: 1, $or: [{b: 1, c: 1}, {b: 2, c: 2}, {b: 3, c: 3}, {b: 4, c: 4}]}) .explain( "allPlansExecution" ); let allPlansExec = explain.executionStats.allPlansExecution; // The number of candidate plans here is constrained by // internalQueryEnumerationMaxOrSolutions=10. // There are 10 OR plans generated, and one plan which indexes just the "a:1" predicate. assert .eq(11, allPlansExec.length); assert .commandWorked( db.adminCommand({setParameter: 1, internalQueryEnumerationMaxOrSolutions: 100})); explain = db.c.find({a: 1, $or: [{b: 1, c: 1}, {b: 2, c: 2}, {b: 3, c: 3}, {b: 4, c: 4}]}) .explain( "allPlansExecution" ); allPlansExec = explain.executionStats.allPlansExecution; // After increasing internalQueryEnumerationMaxOrSolutions, there are many more possible plans // generated. With a real data set, one of the inhibited plans may be the best one! // // Note that we still run up against the limit of 64 total plans. The size of the plan space for // this query is roughly 3 ^ 4 = 81. assert .eq(64, allPlansExec.length); }());
    • Query 2020-08-10

      For version 3.6, SERVER-13732 added an optimization for contained $or queries which causes the query planner to generate more efficient plans. This optimization can also cause additional indexed $or plans to be considered in 3.6 which were not considered in older versions of the MongoDB server. As an example, consider the query

      find({a: 1, $or: [{b: 2, c: 2}, {b: 3, c: 3}]})

      Suppose that the collection has indices {a: 1, c: 1} and {b: 1, c: 1}. Prior to 3.6, the query planner would generate two plans:

      • An IXSCAN on {a: 1, c: 1} with bounds {a: [[1, 1]], c: [["MinKey", "MaxKey"]]}
      • An OR plan with two IXSCANS on {b: 1, c: 1}.

      With contained $or pushdown, the predicate "a:1" can be pushed into both branches of the $or. This allows the planner to additionally consider an OR plan with two IXSCANS on {a: 1, c: 1}, one with bounds {a: [[1, 1]], c: [[2, 2]]} and the other with bounds {a: [[1, 1]], c: [[3, 3]]}.

      Typically, generating these extra plans has the benefit of allowing queries to be answered with tighter index bounds. However, in order to manage the potential combinatorial explosion of indexed OR plans, the planner imposes a limit on the number of plans generated for a particular $or node in the input query. This limit is configurable at startup and at runtime via the setParameter internalQueryEnumerationMaxOrSolutions, which has a default value of 10. The additional plans considered due to $or pushdown can cause the total number of plans to exceed internalQueryEnumerationMaxOrSolutions. This can inhibit generation of the best plan, thus causing a query to select a suboptimal indexed $or plan.

            Assignee:
            backlog-query-optimization [DO NOT USE] Backlog - Query Optimization
            Reporter:
            david.storch@mongodb.com David Storch
            Votes:
            5 Vote for this issue
            Watchers:
            40 Start watching this issue

              Created:
              Updated: