Multikey Index Bounds

The bounds of an index scan define the portions of an index to search during a query. When multiple predicates over an index exist, MongoDB will attempt to combine the bounds for these predicates, by either intersection or compounding, in order to produce a scan with smaller bounds.

Intersect Bounds for Multikey Index

Bounds intersection refers to a logical conjunction (i.e. AND) of multiple bounds. For instance, given two bounds [ [ 3, Infinity ] ] and [ [ -Infinity, 6 ] ], the intersection of the bounds results in [ [ 3, 6 ] ].

Given an indexed array field, consider a query that specifies multiple predicates on the array and can use a multikey index. MongoDB can intersect multikey index bounds if an $elemMatch joins the predicates.

For example, a collection survey contains documents with a field item and an array field ratings:

{ _id: 1, item: "ABC", ratings: [ 2, 9 ] }
{ _id: 2, item: "XYZ", ratings: [ 4, 3 ] }

Create a multikey index on the ratings array:

db.survey.createIndex( { ratings: 1 } )

The following query uses $elemMatch to require that the array contains at least one single element that matches both conditions:

db.survey.find( { ratings : { $elemMatch: { $gte: 3, $lte: 6 } } } )

Taking the predicates separately:

  • the bounds for the greater than or equal to 3 predicate (i.e. $gte: 3) are [ [ 3, Infinity ] ];
  • the bounds for the less than or equal to 6 predicate (i.e. $lte: 6) are [ [ -Infinity, 6 ] ].

Because the query uses $elemMatch to join these predicates, MongoDB can intersect the bounds to:

ratings: [ [ 3, 6 ] ]

If the query does not join the conditions on the array field with $elemMatch, MongoDB cannot intersect the multikey index bounds. Consider the following query:

db.survey.find( { ratings : { $gte: 3, $lte: 6 } } )

The query searches the ratings array for at least one element greater than or equal to 3 and at least one element less than or equal to 6. Because a single element does not need to meet both criteria, MongoDB does not intersect the bounds and uses either [ [ 3, Infinity ] ] or [ [ -Infinity, 6 ] ]. MongoDB makes no guarantee as to which of these two bounds it chooses.

Compound Bounds for Multikey Index

Compounding bounds refers to using bounds for multiple keys of compound index. For instance, given a compound index { a: 1, b: 1 } with bounds on field a of [ [ 3, Infinity ] ] and bounds on field b of [ [ -Infinity, 6 ] ], compounding the bounds results in the use of both bounds:

{ a: [ [ 3, Infinity ] ], b: [ [ -Infinity, 6 ] ] }

If MongoDB cannot compound the two bounds, MongoDB always constrains the index scan by the bound on its leading field, in this case, a: [ [ 3, Infinity ] ].

Compound Index on an Array Field

Consider a compound multikey index; i.e. a compound index where one of the indexed fields is an array. For example, a collection survey contains documents with a field item and an array field ratings:

{ _id: 1, item: "ABC", ratings: [ 2, 9 ] }
{ _id: 2, item: "XYZ", ratings: [ 4, 3 ] }

Create a compound index on the item field and the ratings field:

db.survey.createIndex( { item: 1, ratings: 1 } )

The following query specifies a condition on both keys of the index:

db.survey.find( { item: "XYZ", ratings: { $gte: 3 } } )

Taking the predicates separately:

  • the bounds for the item: "XYZ" predicate are [ [ "XYZ", "XYZ" ] ];
  • the bounds for the ratings: { $gte: 3 } predicate are [ [ 3, Infinity ] ].

MongoDB can compound the two bounds to use the combined bounds of:

{ item: [ [ "XYZ", "XYZ" ] ], ratings: [ [ 3, Infinity ] ] }

Range Queries on a Scalar Indexed Field (WiredTiger)

Changed in version 3.4: For the WiredTiger and In-Memory storage engines only,

Starting in MongoDB 3.4, for multikey indexes created using MongoDB 3.4 or later, MongoDB keeps track of which indexed field or fields cause an index to be a multikey index. Tracking this information allows the MongoDB query engine to use tighter index bounds.

The aforementioned compound index is on the scalar field [1] item and the array field ratings:

db.survey.createIndex( { item: 1, ratings: 1 } )

For the WiredTiger and the In-Memory storage engines, if a query operation specifies multiple predicates on the indexed scalar field(s) of a compound multikey index created in MongoDB 3.4 or later, MongoDB will intersect the bounds for the field.

For example, the following operation specifies a range query on the scalar field as well as a range query on the array field:

db.survey.find( {
   item: { $gte: "L", $lte: "Z"}, ratings : { $elemMatch: { $gte: 3, $lte: 6 } }
} )

MongoDB will intersect the bounds for item to [ [ "L", "Z" ] ] and ratings to [[3.0, 6.0]] to use the combined bounds of:

"item" : [ [ "L", "Z" ] ], "ratings" : [ [3.0, 6.0] ]

For another example, consider where the scalar fields belong to a nested document. For instance, a collection survey contains the following documents:

{ _id: 1, item: { name: "ABC", manufactured: 2016 }, ratings: [ 2, 9 ] }
{ _id: 2, item: { name: "XYZ", manufactured: 2013 },  ratings: [ 4, 3 ]