Details
-
Bug
-
Resolution: Unresolved
-
Major - P3
-
None
-
None
-
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.