[SERVER-8743] add the ability for a query to match multiple arbitrary ranges within a single index Created: 26/Feb/13  Updated: 14/Apr/16  Resolved: 26/Jan/15

Status: Closed
Project: Core Server
Component/s: Index Maintenance, Querying
Affects Version/s: None
Fix Version/s: None

Type: Improvement Priority: Major - P3
Reporter: Aaron Staple Assignee: David Storch
Resolution: Duplicate Votes: 1
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Duplicate
duplicates SERVER-12594 subtrees of and/or can reduce to ixscans Backlog
is duplicated by SERVER-6200 some $or queries not optimized properly Closed
Backwards Compatibility: Fully Compatible
Participants:

 Description   

Right now it's easy to specify a query that will scan a range on an index:

index { a:1 }
query { a:{ $gte:5, $lte:10 } }

or a set of points on an index:

index { a:1 }
query { a:{ $in:[ 1, 2 ] } }

Using a regular expression it is also possible to specify certain combinations of ranges on an index:

index { a:1 }
query { a:{ $in:[ /^x/, /^y/ ] } }

This ticket represents functionality for easily specifying more than one arbitrary range on a single index, scanned efficiently by the query optimizer. For example on

index { a:1 }:
 
1) query { $or:[ { a:{ $gte:5, $lte:10 } }, { a:{ $gte:100 } } ] }
2) query { a:{ $in:[ { $gte:5, $lte:10 }, { $gte:100 } ] } }
 

Example 1 is not currently optimized to work as a single index scan because $or is only implemented to support more general cases where or clauses may use different indexes.

Example 2 is not an allowed query currently.



 Comments   
Comment by David Storch [ 26/Jan/15 ]

The new query planner added in version 2.6 plans the example $or query by constructing a plan that is an OR of two index scans:

> t.drop()
true
> t.ensureIndex({a: 1})
{
	"createdCollectionAutomatically" : true,
	"numIndexesBefore" : 1,
	"numIndexesAfter" : 2,
	"ok" : 1
}
> t.find({$or: [{a: {$gte: 5, $lte: 10}}, {a: {$gte: 100}}]}).explain()
{
	"queryPlanner" : {
		"plannerVersion" : 1,
		"namespace" : "test.t",
		"indexFilterSet" : false,
		"parsedQuery" : {
			"$or" : [
				{
					"$and" : [
						{
							"a" : {
								"$lte" : 10
							}
						},
						{
							"a" : {
								"$gte" : 5
							}
						}
					]
				},
				{
					"a" : {
						"$gte" : 100
					}
				}
			]
		},
		"winningPlan" : {
			"stage" : "SUBPLAN",
			"inputStage" : {
				"stage" : "FETCH",
				"inputStage" : {
					"stage" : "OR",
					"inputStages" : [
						{
							"stage" : "IXSCAN",
							"keyPattern" : {
								"a" : 1
							},
							"indexName" : "a_1",
							"isMultiKey" : false,
							"direction" : "forward",
							"indexBounds" : {
								"a" : [
									"[5.0, 10.0]"
								]
							}
						},
						{
							"stage" : "IXSCAN",
							"keyPattern" : {
								"a" : 1
							},
							"indexName" : "a_1",
							"isMultiKey" : false,
							"direction" : "forward",
							"indexBounds" : {
								"a" : [
									"[100.0, inf.0]"
								]
							}
						}
					]
				}
			}
		},
		"rejectedPlans" : [ ]
	},
	"serverInfo" : {
		"host" : "dstorch-desktop",
		"port" : 27017,
		"version" : "3.1.0-pre-",
		"gitVersion" : "d8628625507b7a6927f21b1f1f91d68201fe4030"
	},
	"ok" : 1
}

The planner could collapse this into a single index scan with the following index bounds:

{a: [[5, 10], [100, Infinity]]}

An improvement request for this kind of collapsing of plans into a single index scan stage is already being tracked by SERVER-12594. Resolving as a duplicate of SERVER-12594.

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