[SERVER-53930] AND_SORTED IX_SCAN plans should take advantage of ability to seek by recordid in indexes Created: 20/Jan/21  Updated: 06/Dec/22

Status: Backlog
Project: Core Server
Component/s: Querying
Affects Version/s: None
Fix Version/s: None

Type: Bug Priority: Major - P3
Reporter: Mathias Stearn Assignee: Backlog - Query Optimization
Resolution: Unresolved Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
related to SERVER-53927 Support AND_SORTED plans using wildca... Backlog
Assigned Teams:
Query Optimization
Operating System: ALL
Steps To Reproduce:

> 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.

Participants:

 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.


Generated at Thu Feb 08 05:32:13 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.