[SERVER-45011] Index used for whole IXSCAN plan is determined by index creation order Created: 06/Dec/19  Updated: 29/Oct/23  Resolved: 03/Jan/20

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

Type: Bug Priority: Major - P3
Reporter: Ian Boros Assignee: James Wahlin
Resolution: Fixed Votes: 0
Labels: greenerbuild, qopt-team
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
related to SERVER-12769 Queries that scan an entire index to ... Backlog
Backwards Compatibility: Fully Compatible
Operating System: ALL
Participants:
Linked BF Score: 23

 Description   

The following query is eligible for a whole IXSCAN solution on any index prefixed by "a":

db.c.find({}, {"b": 1, _id: 0}).sort({a: 1}).explain()

However, because we "break" in this block as soon as any index which provides the sort is available, we miss out on covered plans. That is, we only consider the "first" whole IXSCAN solution we see.

So, for example if I were to run:

> db.c.drop()
> db.c.createIndex({a: 1})
> db.c.createIndex({a: 1, b: 1})
> db.c.find({}, {"b": 1, _id: 0}).sort({a: 1}).explain()
...

We would get a non-covered plan, because the "a" index comes first in the list of indexes in the catalog.

But switch the order we create the indexes in:

> db.c.drop()
> db.c.createIndex({a: 1, b: 1})
> db.c.createIndex({a: 1})
> db.c.find({}, {"b": 1, _id: 0}).sort({a: 1}).explain()
...

And now we have a covered plan because the "a, b" index came first when looking for a whole IXSCAN solution.

Note that this is a separate issue from SERVER-12769, which is a problem when using a whole IXSCAN solution and the filter is non-empty. This ticket is relevant for cases where the filter is empty.

Ideas to fix this:
-Delete that "break" statement (and the similar one for reverse index scans). This will cause both plans to go through the multi planner and plan ranker. Since both plans will have the same output/work ratio, the covered one will be chosen by the plan ranker.
-If we want the planner to only ever generate one whole IXSCAN solution, we can have it generate all of the possible ones and then see if any are covered, picking that one. This would save work of multi planning (which is basically useless for this case, since there's no filter and all of the indexes are equally selective) but add yet another special code path to the planner.



 Comments   
Comment by Chris Harris [ 01/Feb/20 ]

I had a backlogged TODO item from last year to investigate why the rejectedPlans array of .explain() output was empty when an index was used to sort but there were also other indexes present that could do the same.  I had observed that the plan depended on index creation order and I was suspecting that we might indeed be breaking out of a loop early.  But I wasn't able to find such logic looking at master and we appeared to be looping on fullIndexList so I was thoroughly confused.  Then I decided to check previous versions of query_planner.cpp... You can imagine what a pleasant surprise it was to discover the old break statements and the fact that they had very recently been removed via this ticket!

 

Just swinging by to say thanks to ian.boros for filing and to james.wahlin for resolving!

Comment by Githook User [ 03/Jan/20 ]

Author:

{'name': 'James Wahlin', 'email': 'james.wahlin@mongodb.com', 'username': 'jameswahlin'}

Message: SERVER-45011 Index used for whole IXSCAN plan is determined by index creation order
Branch: master
https://github.com/mongodb/mongo/commit/0faebb0f323afbfed89bb3d82f5c432ae6ec5232

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