[SERVER-53927] Support AND_SORTED plans using wildcard 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
is related to SERVER-53930 AND_SORTED IX_SCAN plans should take ... Backlog
is related to SERVER-36521 Prevent allPaths indexes from generat... Closed
Assigned Teams:
Query Optimization
Operating System: ALL
Steps To Reproduce:

> db.foo.ensureIndex({'$**': 1})
{
        "createdCollectionAutomatically" : false,
        "numIndexesBefore" : 1,
        "numIndexesAfter" : 2,
        "ok" : 1
}
> db.foo.find({a:1, b:1}).explain()
{
        "queryPlanner" : {
                "plannerVersion" : 1,
                "namespace" : "test.foo",
                "indexFilterSet" : false,
                "parsedQuery" : {
                        "$and" : [
                                {
                                        "a" : {
                                                "$eq" : 1
                                        }
                                },
                                {
                                        "b" : {
                                                "$eq" : 1
                                        }
                                }
                        ]
                },
                "queryHash" : "43CAB4C5",
                "planCacheKey" : "CEC1F6AF",
                "winningPlan" : {
                        "stage" : "FETCH",
                        "filter" : {
                                "b" : {
                                        "$eq" : 1
                                }
                        },
                        "inputStage" : {
                                "stage" : "IXSCAN",
                                "keyPattern" : {
                                        "$_path" : 1,
                                        "a" : 1
                                },
                                "indexName" : "$**_1",
                                "isMultiKey" : false,
                                "multiKeyPaths" : {
                                        "$_path" : [ ],
                                        "a" : [ ]
                                },
                                "isUnique" : false,
                                "isSparse" : false,
                                "isPartial" : false,
                                "indexVersion" : 2,
                                "direction" : "forward",
                                "indexBounds" : {
                                        "$_path" : [
                                                "[\"a\", \"a\"]"
                                        ],
                                        "a" : [
                                                "[1.0, 1.0]"
                                        ]
                                }
                        }
                },
                "rejectedPlans" : [
                        {
                                "stage" : "FETCH",
                                "filter" : {
                                        "a" : {
                                                "$eq" : 1
                                        }
                                },
                                "inputStage" : {
                                        "stage" : "IXSCAN",
                                        "keyPattern" : {
                                                "$_path" : 1,
                                                "b" : 1
                                        },
                                        "indexName" : "$**_1",
                                        "isMultiKey" : false,
                                        "multiKeyPaths" : {
                                                "$_path" : [ ],
                                                "b" : [ ]
                                        },
                                        "isUnique" : false,
                                        "isSparse" : false,
                                        "isPartial" : false,
                                        "indexVersion" : 2,
                                        "direction" : "forward",
                                        "indexBounds" : {
                                                "$_path" : [
                                                        "[\"b\", \"b\"]"
                                                ],
                                                "b" : [
                                                        "[1.0, 1.0]"
                                                ]
                                        }
                                }
                        }
                ]
        },
        "serverInfo" : {
                "host" : "silversurfer-wsl",
                "port" : 27017,
                "version" : "4.4.3",
                "gitVersion" : "913d6b62acfbb344dde1b116f4161360acd8fd13"
        },
        "ok" : 1
}

Compare that to:

> db.foo.ensureIndex({a: 1})
{
        "createdCollectionAutomatically" : true,
        "numIndexesBefore" : 1,
        "numIndexesAfter" : 2,
        "ok" : 1
}
> db.foo.ensureIndex({b: 1})
{
        "createdCollectionAutomatically" : false,
        "numIndexesBefore" : 2,
        "numIndexesAfter" : 3,
        "ok" : 1
}
> db.foo.find({a:1, b:1}).explain()
{
        "queryPlanner" : {
                "plannerVersion" : 1,
                "namespace" : "test.foo",
                "indexFilterSet" : false,
                "parsedQuery" : {
                        "$and" : [
                                {
                                        "a" : {
                                                "$eq" : 1
                                        }
                                },
                                {
                                        "b" : {
                                                "$eq" : 1
                                        }
                                }
                        ]
                },
                "queryHash" : "43CAB4C5",
                "planCacheKey" : "CEC1F6AF",
                "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]"
                                                                ]
                                                        }
                                                }
                                        ]
                                }
                        }
                ]
        },
        "serverInfo" : {
                "host" : "silversurfer-wsl",
                "port" : 27017,
                "version" : "4.4.3",
                "gitVersion" : "913d6b62acfbb344dde1b116f4161360acd8fd13"
        },
        "ok" : 1
}

Sprint: Query Optimization 2021-03-08
Participants:

 Description   

Ideally wildcard indexes should be usable anywhere an infinite number of {a:1}, {b:1}, etc indexes would be. But right now a query like {a:1, b:1} will use AND_SORTED of two IX_SCANs, but it won't try to use the equivalent plan if you have a wildcard index



 Comments   
Comment by Mathias Stearn [ 11/Mar/21 ]

I think it is much harder to know when AND_HASH is profitable since it is always a blocking stage, so I'd be hesitant to lump them together for consideration. At least for exact-match (maybe less so for range or prefix match), I would expect AND_SORTED to be better. And it should be significantly better if we do SERVER-53930.

Comment by James Wahlin [ 10/Mar/21 ]

I did some more digging and we suspect that support for AND_SORTED under wildcard indexes dropped to cut project scope and because in practice it is rare for us to choose these plans. I think we should take another look at both AND_HASH and AND_SORTED once we have a new optimizer, which may be able to make better use of them.

Comment by James Wahlin [ 05/Mar/21 ]

The decision to ban AND_SORTED and AND_HASH plans for wildcard indexes was intentional with work done under SERVER-36521. I need to do a little more digging to remember why we made the decision to do this. Unfortunately the review mentions a discussion in Slack

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