[SERVER-12769] Queries that scan an entire index to provide a sort should be covered when possible Created: 18/Feb/14  Updated: 06/Dec/22

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

Type: Improvement Priority: Minor - P4
Reporter: David Storch Assignee: Backlog - Query Optimization
Resolution: Unresolved Votes: 0
Labels: former-quick-wins, tpcc
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Duplicate
is duplicated by SERVER-20433 Unexpected non-covered query in 3.0 a... Closed
Related
is related to SERVER-45011 Index used for whole IXSCAN plan is d... Closed
Assigned Teams:
Query Optimization
Backwards Compatibility: Fully Compatible
Participants:

 Description   

This ticket is the same as the TODO here: https://github.com/mongodb/mongo/blob/e5e4a2427b869e40f1a1e6f65dc5e3fd11f451ac/src/mongo/db/query/planner_access.cpp#L1126.

Currently, when we try to perform an indexed sort by scanning the whole index from MinKey to MaxKey, we always add a FETCH as the parent of the index scan. The FETCH is usually necessary, but may not be if the query is covered by the index.

Example:

> t = db.t
> t.drop()
true
> t.ensureIndex({a: 1, b: 1})
> t.find({b: {$gte: 0}}, {_id: 0, b: 1}).sort({a: 1})

The indexed solution for this example is a scan over the entire index {a: 1, b: 1}, followed by a FETCH, followed by a PROJ:

PROJ
---proj = { _id: 0.0, b: 1.0 }
---fetched = 1
---sortedByDiskLoc = 0
---getSort = []
Child:
------FETCH
---------filter:
                b $gte 0.0 First: notFirst: full path:
---------fetched = 1
---------sortedByDiskLoc = 0
---------getSort = [{ a: 1 }, { a: 1, b: 1 }, ]
---------Child:
------------IXSCAN
---------------keyPattern = { a: 1.0, b: 1.0 }
---------------direction = 1
---------------bounds = field #0['a']: [MinKey, MaxKey], field #1['b']: [MinKey, MaxKey]
---------------fetched = 0
---------------fetched = 0
---------------sortedByDiskLoc = 0
---------------getSort = [{ a: 1 }, { a: 1, b: 1 }, ]

Since the value of "b" is provided by the index, the FETCH is unnecessary---in other words, this should execute as a covered query.



 Comments   
Comment by Asya Kamsky [ 21/Sep/22 ]

This just came up again in this example:

db.accounts.explain().find({ balance: { $gt: 1300 } }, { account_holder: 1, balance: 1, _id: 0}).sort({ account_holder: 1, balance: -1 })
{
  explainVersion: '1',
  queryPlanner: {
    namespace: 'test.accounts',
    indexFilterSet: false,
    parsedQuery: { balance: { '$gt': 1300 } },
    queryHash: '3833F71B',
    planCacheKey: '6BA9E76C',
    maxIndexedOrSolutionsReached: false,
    maxIndexedAndSolutionsReached: false,
    maxScansToExplodeReached: false,
    winningPlan: {
      stage: 'PROJECTION_SIMPLE',
      transformBy: { account_holder: 1, balance: 1, _id: 0 },
      inputStage: {
        stage: 'FETCH',
        filter: { balance: { '$gt': 1300 } },
        inputStage: {
          stage: 'IXSCAN',
          keyPattern: { account_holder: 1, balance: -1 },
          indexName: 'account_holder_1_balance_-1',
          isMultiKey: false,
          multiKeyPaths: { account_holder: [], balance: [] },
          isUnique: false,
          isSparse: false,
          isPartial: false,
          indexVersion: 2,
          direction: 'forward',
          indexBounds: {
            account_holder: [ '[MinKey, MaxKey]' ],
            balance: [ '[MaxKey, MinKey]' ]
          }
        }
      }
    },
 

We are already scanning the full index and can filter balance in the IXSCAN part, but we do a FETCH anyway.

Comment by Asya Kamsky [ 01/Mar/19 ]

Here is an example from related ticket that's manifestation of this issue:
Collection with index on a, b and query with equality on b and sort on a. We use the index for sort but still fetch to test "b".

db.foo.find({b: 0}, {a: 1, b: 1, _id: 0}).sort({a: 1}).explain(true)
{
	"queryPlanner" : {
		"plannerVersion" : 1,
		"namespace" : "test.foo",
		"indexFilterSet" : false,
		"parsedQuery" : {
			"b" : {
				"$eq" : 0
			}
		},
		"winningPlan" : {
			"stage" : "PROJECTION",
			"transformBy" : {
				"a" : 1,
				"b" : 1,
				"_id" : 0
			},
			"inputStage" : {
				"stage" : "FETCH",
				"filter" : {
					"b" : {
						"$eq" : 0
					}
				},
				"inputStage" : {
					"stage" : "IXSCAN",
					"keyPattern" : {
						"a" : 1,
						"b" : 1
					},
					"indexName" : "a_1_b_1",
					"isMultiKey" : false,
					"multiKeyPaths" : {
						"a" : [ ],
						"b" : [ ]
					},
					"isUnique" : false,
					"isSparse" : false,
					"isPartial" : false,
					"indexVersion" : 2,
					"direction" : "forward",
					"indexBounds" : {
						"a" : [
							"[MinKey, MaxKey]"
						],
						"b" : [
							"[MinKey, MaxKey]"
						]
					}
				}
			}
		},
		"rejectedPlans" : [ ]
	},
	"executionStats" : {
		"executionSuccess" : true,
		"nReturned" : 0,
		"executionTimeMillis" : 0,
		"totalKeysExamined" : 0,
		"totalDocsExamined" : 0,
		"executionStages" : {
			"stage" : "PROJECTION",
			"nReturned" : 0,
			"executionTimeMillisEstimate" : 0,
			"works" : 1,
			"advanced" : 0,
			"needTime" : 0,
			"needYield" : 0,
			"saveState" : 0,
			"restoreState" : 0,
			"isEOF" : 1,
			"invalidates" : 0,
			"transformBy" : {
				"a" : 1,
				"b" : 1,
				"_id" : 0
			},
			"inputStage" : {
				"stage" : "FETCH",
				"filter" : {
					"b" : {
						"$eq" : 0
					}
				},
				"nReturned" : 0,
				"executionTimeMillisEstimate" : 0,
				"works" : 1,
				"advanced" : 0,
				"needTime" : 0,
				"needYield" : 0,
				"saveState" : 0,
				"restoreState" : 0,
				"isEOF" : 1,
				"invalidates" : 0,
				"docsExamined" : 0,
				"alreadyHasObj" : 0,
				"inputStage" : {
					"stage" : "IXSCAN",
					"nReturned" : 0,
					"executionTimeMillisEstimate" : 0,
					"works" : 1,
					"advanced" : 0,
					"needTime" : 0,
					"needYield" : 0,
					"saveState" : 0,
					"restoreState" : 0,
					"isEOF" : 1,
					"invalidates" : 0,
					"keyPattern" : {
						"a" : 1,
						"b" : 1
					},
					"indexName" : "a_1_b_1",
					"isMultiKey" : false,
					"multiKeyPaths" : {
						"a" : [ ],
						"b" : [ ]
					},
					"isUnique" : false,
					"isSparse" : false,
					"isPartial" : false,
					"indexVersion" : 2,
					"direction" : "forward",
					"indexBounds" : {
						"a" : [
							"[MinKey, MaxKey]"
						],
						"b" : [
							"[MinKey, MaxKey]"
						]
					},
					"keysExamined" : 0,
					"seeks" : 1,
					"dupsTested" : 0,
					"dupsDropped" : 0,
					"seenInvalidated" : 0
				}
			}
		},
		"allPlansExecution" : [ ]
	},
	"serverInfo" : {
		"host" : "Asyas-MacBook-Pro.local",
		"port" : 27017,
		"version" : "4.0.0",
		"gitVersion" : "3b07af3d4f471ae89e8186d33bbb1d5259597d51"
	},
	"ok" : 1
}

Generated at Thu Feb 08 03:29:34 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.