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

AND_SORTED IX_SCAN plans should take advantage of ability to seek by recordid in indexes

    XMLWordPrintableJSON

Details

    • Icon: Bug Bug
    • Resolution: Unresolved
    • Icon: Major - P3 Major - P3
    • None
    • None
    • Querying
    • None
    • Query Optimization
    • ALL
    • Hide

      > for (var i = 0; i < 1000; i++) {let ops = db.foo.initializeUnorderedBulkOp(); for (var j = 0; j < 1000; j++) ops.insert({a:i, b:j}); ops.execute(); }
      > db.foo.ensureIndex({a:1})
      > db.foo.ensureIndex({b:1})
      > db.foo.find({a:1, b:1}).explain(true)
      {
              "queryPlanner" : {
                      "plannerVersion" : 1,
                      "namespace" : "test.foo",
                      "indexFilterSet" : false,
                      "parsedQuery" : {
                              "$and" : [
                                      {
                                              "a" : {
                                                      "$eq" : 1
                                              }
                                      },
                                      {
                                              "b" : {
                                                      "$eq" : 1
                                              }
                                      }
                              ]
                      },
                      "winningPlan" : {
                              "stage" : "FETCH",
                              "filter" : {
                                      "b" : {
                                              "$eq" : 1
                                      }
                              },
                              "inputStage" : {
                                      "stage" : "IXSCAN",
                                      "keyPattern" : {
                                              "a" : 1
                                      },
                                      "indexName" : "a_1",
                                      "isMultiKey" : false,
                                      "multiKeyPaths" : {
                                              "a" : [ ]
                                      },
                                      "isUnique" : false,
                                      "isSparse" : false,
                                      "isPartial" : false,
                                      "indexVersion" : 2,
                                      "direction" : "forward",
                                      "indexBounds" : {
                                              "a" : [
                                                      "[1.0, 1.0]"
                                              ]
                                      }
                              }
                      },
                      "rejectedPlans" : [
                              {
                                      "stage" : "FETCH",
                                      "filter" : {
                                              "a" : {
                                                      "$eq" : 1
                                              }
                                      },
                                      "inputStage" : {
                                              "stage" : "IXSCAN",
                                              "keyPattern" : {
                                                      "b" : 1
                                              },
                                              "indexName" : "b_1",
                                              "isMultiKey" : false,
                                              "multiKeyPaths" : {
                                                      "b" : [ ]
                                              },
                                              "isUnique" : false,
                                              "isSparse" : false,
                                              "isPartial" : false,
                                              "indexVersion" : 2,
                                              "direction" : "forward",
                                              "indexBounds" : {
                                                      "b" : [
                                                              "[1.0, 1.0]"
                                                      ]
                                              }
                                      }
                              },
                              {
                                      "stage" : "FETCH",
                                      "filter" : {
                                              "$and" : [
                                                      {
                                                              "a" : {
                                                                      "$eq" : 1
                                                              }
                                                      },
                                                      {
                                                              "b" : {
                                                                      "$eq" : 1
                                                              }
                                                      }
                                              ]
                                      },
                                      "inputStage" : {
                                              "stage" : "AND_SORTED",
                                              "inputStages" : [
                                                      {
                                                              "stage" : "IXSCAN",
                                                              "keyPattern" : {
                                                                      "a" : 1
                                                              },
                                                              "indexName" : "a_1",
                                                              "isMultiKey" : false,
                                                              "multiKeyPaths" : {
                                                                      "a" : [ ]
                                                              },
                                                              "isUnique" : false,
                                                              "isSparse" : false,
                                                              "isPartial" : false,
                                                              "indexVersion" : 2,
                                                              "direction" : "forward",
                                                              "indexBounds" : {
                                                                      "a" : [
                                                                              "[1.0, 1.0]"
                                                                      ]
                                                              }
                                                      },
                                                      {
                                                              "stage" : "IXSCAN",
                                                              "keyPattern" : {
                                                                      "b" : 1
                                                              },
                                                              "indexName" : "b_1",
                                                              "isMultiKey" : false,
                                                              "multiKeyPaths" : {
                                                                      "b" : [ ]
                                                              },
                                                              "isUnique" : false,
                                                              "isSparse" : false,
                                                              "isPartial" : false,
                                                              "indexVersion" : 2,
                                                              "direction" : "forward",
                                                              "indexBounds" : {
                                                                      "b" : [
                                                                              "[1.0, 1.0]"
                                                                      ]
                                                              }
                                                      }
                                              ]
                                      }
                              }
                      ]
              },
              "executionStats" : {
                      "executionSuccess" : true,
                      "nReturned" : 1,
                      "executionTimeMillis" : 6,
                      "totalKeysExamined" : 1000,
                      "totalDocsExamined" : 1000,
                      "executionStages" : {
                              "stage" : "FETCH",
                              "filter" : {
                                      "b" : {
                                              "$eq" : 1
                                      }
                              },
                              "nReturned" : 1,
                              "executionTimeMillisEstimate" : 0,
                              "works" : 1002,
                              "advanced" : 1,
                              "needTime" : 999,
                              "needYield" : 0,
                              "saveState" : 3,
                              "restoreState" : 3,
                              "isEOF" : 1,
                              "docsExamined" : 1000,
                              "alreadyHasObj" : 0,
                              "inputStage" : {
                                      "stage" : "IXSCAN",
                                      "nReturned" : 1000,
                                      "executionTimeMillisEstimate" : 0,
                                      "works" : 1001,
                                      "advanced" : 1000,
                                      "needTime" : 0,
                                      "needYield" : 0,
                                      "saveState" : 3,
                                      "restoreState" : 3,
                                      "isEOF" : 1,
                                      "keyPattern" : {
                                              "a" : 1
                                      },
                                      "indexName" : "a_1",
                                      "isMultiKey" : false,
                                      "multiKeyPaths" : {
                                              "a" : [ ]
                                      },
                                      "isUnique" : false,
                                      "isSparse" : false,
                                      "isPartial" : false,
                                      "indexVersion" : 2,
                                      "direction" : "forward",
                                      "indexBounds" : {
                                              "a" : [
                                                      "[1.0, 1.0]"
                                              ]
                                      },
                                      "keysExamined" : 1000,
                                      "seeks" : 1,
                                      "dupsTested" : 0,
                                      "dupsDropped" : 0
                              }
                      },
                      "allPlansExecution" : [
                              {
                                      "nReturned" : 1,
                                      "executionTimeMillisEstimate" : 0,
                                      "totalKeysExamined" : 1000,
                                      "totalDocsExamined" : 1000,
                                      "executionStages" : {
                                              "stage" : "FETCH",
                                              "filter" : {
                                                      "b" : {
                                                              "$eq" : 1
                                                      }
                                              },
                                              "nReturned" : 1,
                                              "executionTimeMillisEstimate" : 0,
                                              "works" : 1001,
                                              "advanced" : 1,
                                              "needTime" : 999,
                                              "needYield" : 0,
                                              "saveState" : 3,
                                              "restoreState" : 3,
                                              "isEOF" : 1,
                                              "docsExamined" : 1000,
                                              "alreadyHasObj" : 0,
                                              "inputStage" : {
                                                      "stage" : "IXSCAN",
                                                      "nReturned" : 1000,
                                                      "executionTimeMillisEstimate" : 0,
                                                      "works" : 1001,
                                                      "advanced" : 1000,
                                                      "needTime" : 0,
                                                      "needYield" : 0,
                                                      "saveState" : 3,
                                                      "restoreState" : 3,
                                                      "isEOF" : 1,
                                                      "keyPattern" : {
                                                              "a" : 1
                                                      },
                                                      "indexName" : "a_1",
                                                      "isMultiKey" : false,
                                                      "multiKeyPaths" : {
                                                              "a" : [ ]
                                                      },
                                                      "isUnique" : false,
                                                      "isSparse" : false,
                                                      "isPartial" : false,
                                                      "indexVersion" : 2,
                                                      "direction" : "forward",
                                                      "indexBounds" : {
                                                              "a" : [
                                                                      "[1.0, 1.0]"
                                                              ]
                                                      },
                                                      "keysExamined" : 1000,
                                                      "seeks" : 1,
                                                      "dupsTested" : 0,
                                                      "dupsDropped" : 0
                                              }
                                      }
                              },
                              {
                                      "nReturned" : 1,
                                      "executionTimeMillisEstimate" : 0,
                                      "totalKeysExamined" : 1000,
                                      "totalDocsExamined" : 1000,
                                      "executionStages" : {
                                              "stage" : "FETCH",
                                              "filter" : {
                                                      "a" : {
                                                              "$eq" : 1
                                                      }
                                              },
                                              "nReturned" : 1,
                                              "executionTimeMillisEstimate" : 0,
                                              "works" : 1001,
                                              "advanced" : 1,
                                              "needTime" : 999,
                                              "needYield" : 0,
                                              "saveState" : 3,
                                              "restoreState" : 3,
                                              "isEOF" : 1,
                                              "docsExamined" : 1000,
                                              "alreadyHasObj" : 0,
                                              "inputStage" : {
                                                      "stage" : "IXSCAN",
                                                      "nReturned" : 1000,
                                                      "executionTimeMillisEstimate" : 0,
                                                      "works" : 1001,
                                                      "advanced" : 1000,
                                                      "needTime" : 0,
                                                      "needYield" : 0,
                                                      "saveState" : 3,
                                                      "restoreState" : 3,
                                                      "isEOF" : 1,
                                                      "keyPattern" : {
                                                              "b" : 1
                                                      },
                                                      "indexName" : "b_1",
                                                      "isMultiKey" : false,
                                                      "multiKeyPaths" : {
                                                              "b" : [ ]
                                                      },
                                                      "isUnique" : false,
                                                      "isSparse" : false,
                                                      "isPartial" : false,
                                                      "indexVersion" : 2,
                                                      "direction" : "forward",
                                                      "indexBounds" : {
                                                              "b" : [
                                                                      "[1.0, 1.0]"
                                                              ]
                                                      },
                                                      "keysExamined" : 1000,
                                                      "seeks" : 1,
                                                      "dupsTested" : 0,
                                                      "dupsDropped" : 0
                                              }
                                      }
                              },
                              {
                                      "nReturned" : 1,
                                      "executionTimeMillisEstimate" : 0,
                                      "totalKeysExamined" : 1001,
                                      "totalDocsExamined" : 1,
                                      "executionStages" : {
                                              "stage" : "FETCH",
                                              "filter" : {
                                                      "$and" : [
                                                              {
                                                                      "a" : {
                                                                              "$eq" : 1
                                                                      }
                                                              },
                                                              {
                                                                      "b" : {
                                                                              "$eq" : 1
                                                                      }
                                                              }
                                                      ]
                                              },
                                              "nReturned" : 1,
                                              "executionTimeMillisEstimate" : 0,
                                              "works" : 1001,
                                              "advanced" : 1,
                                              "needTime" : 1000,
                                              "needYield" : 0,
                                              "saveState" : 3,
                                              "restoreState" : 3,
                                              "isEOF" : 0,
                                              "docsExamined" : 1,
                                              "alreadyHasObj" : 0,
                                              "inputStage" : {
                                                      "stage" : "AND_SORTED",
                                                      "nReturned" : 1,
                                                      "executionTimeMillisEstimate" : 0,
                                                      "works" : 1001,
                                                      "advanced" : 1,
                                                      "needTime" : 1000,
                                                      "needYield" : 0,
                                                      "saveState" : 3,
                                                      "restoreState" : 3,
                                                      "isEOF" : 0,
                                                      "failedAnd_0" : 2,
                                                      "failedAnd_1" : 0,
                                                      "inputStages" : [
                                                              {
                                                                      "stage" : "IXSCAN",
                                                                      "nReturned" : 998,
                                                                      "executionTimeMillisEstimate" : 0,
                                                                      "works" : 998,
                                                                      "advanced" : 998,
                                                                      "needTime" : 0,
                                                                      "needYield" : 0,
                                                                      "saveState" : 3,
                                                                      "restoreState" : 3,
                                                                      "isEOF" : 0,
                                                                      "keyPattern" : {
                                                                              "a" : 1
                                                                      },
                                                                      "indexName" : "a_1",
                                                                      "isMultiKey" : false,
                                                                      "multiKeyPaths" : {
                                                                              "a" : [ ]
                                                                      },
                                                                      "isUnique" : false,
                                                                      "isSparse" : false,
                                                                      "isPartial" : false,
                                                                      "indexVersion" : 2,
                                                                      "direction" : "forward",
                                                                      "indexBounds" : {
                                                                              "a" : [
                                                                                      "[1.0, 1.0]"
                                                                              ]
                                                                      },
                                                                      "keysExamined" : 998,
                                                                      "seeks" : 1,
                                                                      "dupsTested" : 0,
                                                                      "dupsDropped" : 0
                                                              },
                                                              {
                                                                      "stage" : "IXSCAN",
                                                                      "nReturned" : 3,
                                                                      "executionTimeMillisEstimate" : 0,
                                                                      "works" : 3,
                                                                      "advanced" : 3,
                                                                      "needTime" : 0,
                                                                      "needYield" : 0,
                                                                      "saveState" : 3,
                                                                      "restoreState" : 3,
                                                                      "isEOF" : 0,
                                                                      "keyPattern" : {
                                                                              "b" : 1
                                                                      },
                                                                      "indexName" : "b_1",
                                                                      "isMultiKey" : false,
                                                                      "multiKeyPaths" : {
                                                                              "b" : [ ]
                                                                      },
                                                                      "isUnique" : false,
                                                                      "isSparse" : false,
                                                                      "isPartial" : false,
                                                                      "indexVersion" : 2,
                                                                      "direction" : "forward",
                                                                      "indexBounds" : {
                                                                              "b" : [
                                                                                      "[1.0, 1.0]"
                                                                              ]
                                                                      },
                                                                      "keysExamined" : 3,
                                                                      "seeks" : 1,
                                                                      "dupsTested" : 0,
                                                                      "dupsDropped" : 0
                                                              }
                                                      ]
                                              }
                                      }
                              }
                      ]
              },
              "serverInfo" : {
                      "host" : "silversurfer-wsl",
                      "port" : 27017,
                      "version" : "4.4.3",
                      "gitVersion" : "913d6b62acfbb344dde1b116f4161360acd8fd13"
              },
              "ok" : 1
      }
      

      The AND_SORTED plan should examine 2 or 3 keys, not 1001.

      Show
      > for (var i = 0; i < 1000; i++) {let ops = db.foo.initializeUnorderedBulkOp(); for (var j = 0; j < 1000; j++) ops.insert({a:i, b:j}); ops.execute(); } > db.foo.ensureIndex({a:1}) > db.foo.ensureIndex({b:1}) > db.foo.find({a:1, b:1}).explain(true) { "queryPlanner" : { "plannerVersion" : 1, "namespace" : "test.foo", "indexFilterSet" : false, "parsedQuery" : { "$and" : [ { "a" : { "$eq" : 1 } }, { "b" : { "$eq" : 1 } } ] }, "winningPlan" : { "stage" : "FETCH", "filter" : { "b" : { "$eq" : 1 } }, "inputStage" : { "stage" : "IXSCAN", "keyPattern" : { "a" : 1 }, "indexName" : "a_1", "isMultiKey" : false, "multiKeyPaths" : { "a" : [ ] }, "isUnique" : false, "isSparse" : false, "isPartial" : false, "indexVersion" : 2, "direction" : "forward", "indexBounds" : { "a" : [ "[1.0, 1.0]" ] } } }, "rejectedPlans" : [ { "stage" : "FETCH", "filter" : { "a" : { "$eq" : 1 } }, "inputStage" : { "stage" : "IXSCAN", "keyPattern" : { "b" : 1 }, "indexName" : "b_1", "isMultiKey" : false, "multiKeyPaths" : { "b" : [ ] }, "isUnique" : false, "isSparse" : false, "isPartial" : false, "indexVersion" : 2, "direction" : "forward", "indexBounds" : { "b" : [ "[1.0, 1.0]" ] } } }, { "stage" : "FETCH", "filter" : { "$and" : [ { "a" : { "$eq" : 1 } }, { "b" : { "$eq" : 1 } } ] }, "inputStage" : { "stage" : "AND_SORTED", "inputStages" : [ { "stage" : "IXSCAN", "keyPattern" : { "a" : 1 }, "indexName" : "a_1", "isMultiKey" : false, "multiKeyPaths" : { "a" : [ ] }, "isUnique" : false, "isSparse" : false, "isPartial" : false, "indexVersion" : 2, "direction" : "forward", "indexBounds" : { "a" : [ "[1.0, 1.0]" ] } }, { "stage" : "IXSCAN", "keyPattern" : { "b" : 1 }, "indexName" : "b_1", "isMultiKey" : false, "multiKeyPaths" : { "b" : [ ] }, "isUnique" : false, "isSparse" : false, "isPartial" : false, "indexVersion" : 2, "direction" : "forward", "indexBounds" : { "b" : [ "[1.0, 1.0]" ] } } ] } } ] }, "executionStats" : { "executionSuccess" : true, "nReturned" : 1, "executionTimeMillis" : 6, "totalKeysExamined" : 1000, "totalDocsExamined" : 1000, "executionStages" : { "stage" : "FETCH", "filter" : { "b" : { "$eq" : 1 } }, "nReturned" : 1, "executionTimeMillisEstimate" : 0, "works" : 1002, "advanced" : 1, "needTime" : 999, "needYield" : 0, "saveState" : 3, "restoreState" : 3, "isEOF" : 1, "docsExamined" : 1000, "alreadyHasObj" : 0, "inputStage" : { "stage" : "IXSCAN", "nReturned" : 1000, "executionTimeMillisEstimate" : 0, "works" : 1001, "advanced" : 1000, "needTime" : 0, "needYield" : 0, "saveState" : 3, "restoreState" : 3, "isEOF" : 1, "keyPattern" : { "a" : 1 }, "indexName" : "a_1", "isMultiKey" : false, "multiKeyPaths" : { "a" : [ ] }, "isUnique" : false, "isSparse" : false, "isPartial" : false, "indexVersion" : 2, "direction" : "forward", "indexBounds" : { "a" : [ "[1.0, 1.0]" ] }, "keysExamined" : 1000, "seeks" : 1, "dupsTested" : 0, "dupsDropped" : 0 } }, "allPlansExecution" : [ { "nReturned" : 1, "executionTimeMillisEstimate" : 0, "totalKeysExamined" : 1000, "totalDocsExamined" : 1000, "executionStages" : { "stage" : "FETCH", "filter" : { "b" : { "$eq" : 1 } }, "nReturned" : 1, "executionTimeMillisEstimate" : 0, "works" : 1001, "advanced" : 1, "needTime" : 999, "needYield" : 0, "saveState" : 3, "restoreState" : 3, "isEOF" : 1, "docsExamined" : 1000, "alreadyHasObj" : 0, "inputStage" : { "stage" : "IXSCAN", "nReturned" : 1000, "executionTimeMillisEstimate" : 0, "works" : 1001, "advanced" : 1000, "needTime" : 0, "needYield" : 0, "saveState" : 3, "restoreState" : 3, "isEOF" : 1, "keyPattern" : { "a" : 1 }, "indexName" : "a_1", "isMultiKey" : false, "multiKeyPaths" : { "a" : [ ] }, "isUnique" : false, "isSparse" : false, "isPartial" : false, "indexVersion" : 2, "direction" : "forward", "indexBounds" : { "a" : [ "[1.0, 1.0]" ] }, "keysExamined" : 1000, "seeks" : 1, "dupsTested" : 0, "dupsDropped" : 0 } } }, { "nReturned" : 1, "executionTimeMillisEstimate" : 0, "totalKeysExamined" : 1000, "totalDocsExamined" : 1000, "executionStages" : { "stage" : "FETCH", "filter" : { "a" : { "$eq" : 1 } }, "nReturned" : 1, "executionTimeMillisEstimate" : 0, "works" : 1001, "advanced" : 1, "needTime" : 999, "needYield" : 0, "saveState" : 3, "restoreState" : 3, "isEOF" : 1, "docsExamined" : 1000, "alreadyHasObj" : 0, "inputStage" : { "stage" : "IXSCAN", "nReturned" : 1000, "executionTimeMillisEstimate" : 0, "works" : 1001, "advanced" : 1000, "needTime" : 0, "needYield" : 0, "saveState" : 3, "restoreState" : 3, "isEOF" : 1, "keyPattern" : { "b" : 1 }, "indexName" : "b_1", "isMultiKey" : false, "multiKeyPaths" : { "b" : [ ] }, "isUnique" : false, "isSparse" : false, "isPartial" : false, "indexVersion" : 2, "direction" : "forward", "indexBounds" : { "b" : [ "[1.0, 1.0]" ] }, "keysExamined" : 1000, "seeks" : 1, "dupsTested" : 0, "dupsDropped" : 0 } } }, { "nReturned" : 1, "executionTimeMillisEstimate" : 0, "totalKeysExamined" : 1001, "totalDocsExamined" : 1, "executionStages" : { "stage" : "FETCH", "filter" : { "$and" : [ { "a" : { "$eq" : 1 } }, { "b" : { "$eq" : 1 } } ] }, "nReturned" : 1, "executionTimeMillisEstimate" : 0, "works" : 1001, "advanced" : 1, "needTime" : 1000, "needYield" : 0, "saveState" : 3, "restoreState" : 3, "isEOF" : 0, "docsExamined" : 1, "alreadyHasObj" : 0, "inputStage" : { "stage" : "AND_SORTED", "nReturned" : 1, "executionTimeMillisEstimate" : 0, "works" : 1001, "advanced" : 1, "needTime" : 1000, "needYield" : 0, "saveState" : 3, "restoreState" : 3, "isEOF" : 0, "failedAnd_0" : 2, "failedAnd_1" : 0, "inputStages" : [ { "stage" : "IXSCAN", "nReturned" : 998, "executionTimeMillisEstimate" : 0, "works" : 998, "advanced" : 998, "needTime" : 0, "needYield" : 0, "saveState" : 3, "restoreState" : 3, "isEOF" : 0, "keyPattern" : { "a" : 1 }, "indexName" : "a_1", "isMultiKey" : false, "multiKeyPaths" : { "a" : [ ] }, "isUnique" : false, "isSparse" : false, "isPartial" : false, "indexVersion" : 2, "direction" : "forward", "indexBounds" : { "a" : [ "[1.0, 1.0]" ] }, "keysExamined" : 998, "seeks" : 1, "dupsTested" : 0, "dupsDropped" : 0 }, { "stage" : "IXSCAN", "nReturned" : 3, "executionTimeMillisEstimate" : 0, "works" : 3, "advanced" : 3, "needTime" : 0, "needYield" : 0, "saveState" : 3, "restoreState" : 3, "isEOF" : 0, "keyPattern" : { "b" : 1 }, "indexName" : "b_1", "isMultiKey" : false, "multiKeyPaths" : { "b" : [ ] }, "isUnique" : false, "isSparse" : false, "isPartial" : false, "indexVersion" : 2, "direction" : "forward", "indexBounds" : { "b" : [ "[1.0, 1.0]" ] }, "keysExamined" : 3, "seeks" : 1, "dupsTested" : 0, "dupsDropped" : 0 } ] } } } ] }, "serverInfo" : { "host" : "silversurfer-wsl", "port" : 27017, "version" : "4.4.3", "gitVersion" : "913d6b62acfbb344dde1b116f4161360acd8fd13" }, "ok" : 1 } The AND_SORTED plan should examine 2 or 3 keys, not 1001.

    Description

      Since our indexes are logically sorted sets of (key1, key2, ..., rowid) tuples that support seeking to any position, there is room for significant speedup by having AND_SORTED IX_SCAN plans seek in each index based on the lowest possible record id that could match given what other indexes have said. For example if the A index says that the next record id is 1000, we should seek the B index to skip to the next entry with a matching value that is >= 1000, since anything lower is guaranteed not to match. If B then says that 2000 is next, we should go back to A (or on to C if there are more indexes) and ask for >=2000, and keep going on like that until all indexes say the same rowid. This has the advantage of both significantly reducing the number of index entries we need to look at, as well as automatically taking advantage of the more selective index without needing to keep stats or use a fancy plan ranker.

      Once we do this, it will be unconditionally better than the single IX_SCAN + fetch plans, so we should stop generating those plans and just always use AND_SORTED. At least for multi-field point queries. If any fields are range queries, it may be more nuanced.

      Attachments

        Activity

          People

            backlog-query-optimization Backlog - Query Optimization
            mathias@mongodb.com Mathias Stearn
            Votes:
            0 Vote for this issue
            Watchers:
            9 Start watching this issue

            Dates

              Created:
              Updated: