Loading...

Type: Improvement
Resolution: Unresolved
Priority: Major - P3
Fix Version/s: None
Affects Version/s: None
Component/s: None
Labels:
None

Assigned Teams:

Query Optimization
Confidence Status:
None
Work Order:
3
Size Category:
TBD
CAR Domain/s:
None

Aha! Reference:
None
Tracking Level:
None
Risk Status:
None
Exec Notes:
None
Goal Name(s):
None
Goal Link:
None

Due to e.g. SERVER-106829 the plan enumerator can generate the following two plans together:

a stand-alone IXSCAN plan
an AND_SORTED plan where the two children are two identical IXSCANs

Due to exponential back-off the AND_SORTED plan will have a lower cost and win, causing double the index keys read when evaluating the query.

To reproduce:

1. Start the plan_stability test so that the dataset is populated:

buildscripts/resmoke.py run --installDir bazel-bin/install-dist-test/bin --suites=query_golden_classic '--mongodSetParameters={internalQueryFrameworkControl: forceClassicEngine, planRankerMode: samplingCE}' jstests/query_golden/plan_stability.js  --pauseAfterPopulate

2. Wait until the following log line:

[js_test:plan_stability] [jsTest] ----
[js_test:plan_stability] [jsTest] TestData.pauseAfterPopulate is set. Pausing indefinitely ...
[js_test:plan_stability] [jsTest] ----

3. Run the following manually:

pipeline = [{'$match': {'$and': [{'$or': [{'a_compound': {'$all': [8,
                                                                         5,
                                                                         2]}},
                                                {'a_compound': {'$nin': [5,
                                                                         14]}}]},
                                       {'k_idx': {'$ne': 17}}],
                              '$or': [{'d_noidx': {'$gt': 11}},
                                      {'$nor': [{'a_compound': {'$all': [6,
                                                                         13]}},
                                                {'a_noidx': {'$nin': [7,
                                                                      6,
                                                                      1,
                                                                      6,
                                                                      6]}},
                                                {'d_compound': {'$nin': [7,
                                                                         18]}}]},
                                      {'a_idx': {'$gte': 11}}],
                              'a_compound': {'$all': [13, 13]}}}];
db.plan_stability.aggregate(pipeline).explain().queryPlanner.winningPlan;

and you will get the following winning plan:

{
  isCached: false,
  stage: 'FETCH',
  costEstimate: 1.4775613933600216,
  cardinalityEstimate: 33.96450911617378,
  estimatesMetadata: { ceSource: 'Sampling' },
  filter: {
    '$and': [
      { a_compound: { '$eq': 13 } },
      { a_compound: { '$eq': 13 } },
      {
        '$or': [
          { '$and': [ [Object], [Object], [Object] ] },
          { a_compound: { '$not': [Object] } }
        ]
      },
      {
        '$or': [
          { '$nor': [ [Object], [Object], [Object] ] },
          { a_idx: { '$gte': 11 } },
          { d_noidx: { '$gt': 11 } }
        ]
      },
      { k_idx: { '$not': { '$eq': 17 } } }
    ]
  },
  inputStage: {
    stage: 'AND_SORTED',
    costEstimate: 1.2859183333333333,
    cardinalityEstimate: 106.31465897496435,
    estimatesMetadata: { ceSource: 'Sampling' },
    inputStages: [
      {
        stage: 'IXSCAN',
        costEstimate: 0.43457583333333333,
        cardinalityEstimate: 1041.6666666666667,
        numKeysEstimate: 1041.6666666666667,
        estimatesMetadata: { ceSource: 'Sampling' },
        keyPattern: { a_compound: 1 },
        indexName: 'a_compound_1',
        isMultiKey: true,
        multiKeyPaths: { a_compound: [ 'a_compound' ] },
        isUnique: false,
        isSparse: false,
        isPartial: false,
        indexVersion: 2,
        direction: 'forward',
        indexBounds: { a_compound: [ '[13, 13]' ] }
      },
      {
        stage: 'IXSCAN',
        costEstimate: 0.43457583333333333,
        cardinalityEstimate: 1041.6666666666667,
        numKeysEstimate: 1041.6666666666667,
        estimatesMetadata: { ceSource: 'Sampling' },
        keyPattern: { a_compound: 1 },
        indexName: 'a_compound_1',
        isMultiKey: true,
        multiKeyPaths: { a_compound: [ 'a_compound' ] },
        isUnique: false,
        isSparse: false,
        isPartial: false,
        indexVersion: 2,
        direction: 'forward',
        indexBounds: { a_compound: [ '[13, 13]' ] }
      }
    ]
  }
}

This plan will have two completely identical IXSCANS under AND_SORTED. It has a cost of 1.4775613933600216 . At the same time, the single IXSCAN plan:

nterprise test> db.plan_stability.aggregate(pipeline).explain().queryPlanner.rejectedPlans[10];
{
isCached: false,
stage: 'FETCH',
costEstimate: 2.2339512,
cardinalityEstimate: 1041.6666666666667,
estimatesMetadata:

{ ceSource: 'Sampling' }

,
filter: {
'$and': [
{
'$or': [

{ '$and': [ [Object], [Object], [Object] ] }

,
{ a_compound:

{ '$not': [Object] }

}
]
},
{
'$or': [

{ '$nor': [ [Object], [Object], [Object] ] }

,
{ a_idx:

{ '$gte': 11 }

},
{ d_noidx:

{ '$gt': 11 }

}
]
},
{ k_idx: { '$not':

{ '$eq': 17 }

} },
{ a_compound:

{ '$eq': 13 }

}
]
},
inputStage: {
stage: 'IXSCAN',
costEstimate: 0.43457583333333333,
cardinalityEstimate: 1041.6666666666667,
numKeysEstimate: 1041.6666666666667,
estimatesMetadata:

{ ceSource: 'Sampling' }

,
keyPattern:

{ a_compound: 1 }

,
indexName: 'a_compound_1',
isMultiKey: true,
multiKeyPaths:

{ a_compound: [ 'a_compound' ] }

,
isUnique: false,
isSparse: false,
isPartial: false,
indexVersion: 2,
direction: 'forward',
indexBounds:

{ a_compound: [ '[13, 13]' ] }

}
}

has a cost of 2.2339512 and thus loses.

is related to

SERVER-106829 Plan enumerator generates an AND_SORTED plan with two identical IXSCANs

Backlog

related to

SERVER-106829 Plan enumerator generates an AND_SORTED plan with two identical IXSCANs

Backlog

Details

Description

Attachments

Issue Links

Forms

Activity

People

Dates