[SERVER-22401] Implement index bounds generation rules for path-level multikey tracking in the PlanEnumerator Created: 01/Feb/16  Updated: 29/Jun/16  Resolved: 04/Mar/16

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

Type: Task Priority: Major - P3
Reporter: David Storch Assignee: Max Hirschhorn
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
depends on SERVER-22399 Extend IndexEntry to contain path-lev... Closed
depends on SERVER-22867 Plan enumerator should convey to acce... Closed
Related
related to SERVER-23112 Update index bounds generation rules ... Closed
is related to SERVER-24786 Compound multikey index does not comp... Closed
Backwards Compatibility: Fully Compatible
Sprint: Query 10 (02/22/16), Query 11 (03/14/16)
Participants:

 Description   

The additional metadata added to the IndexEntry as part of SERVER-22399 describes what prefixes of the indexed fields cause the index to be multikey. We can use this information to get tighter bounds by assigning additional predicates to the index.

  • It is always safe to assign a predicate on path Y to the index when no prefix of the path Y causes the index to be multikey.
  • For any non-$elemMatch predicate on path X already assigned to the index, it isn't safe to assign a predicate on path Y (possibly equal to X) to the index when a shared prefix of the paths X and Y causes the index to be multikey.
  • For any $elemMatch predicate on path X already assigned to the index, it isn't safe to assign a predicate on path Y (possibly equal to X) to the index when
    • a shared prefix of the paths X and Y causes the index to be multikey and the predicates aren't joined by the same $elemMatch context, or
    • a shared prefix of the paths X and Y inside the innermost $elemMatch causes the index to be multikey.
Some examples
Can intersect bounds on "a" because it is never an array containing multiple elements.

Index: {a: 1, b: 1}
Document: {a: 5, b: [1, 2, 3]}
⇒ Multikey paths: ["b"]
Query: {a: {$gte: 0, $lt: 10}}
⇒ Bounds on "a": [0, 10)
⇒ Bounds on "b": [MinKey, MaxKey]

Can intersect bounds on "a.b" because neither it nor the "a" field are ever an array containing multiple elements.

Index: {"a.b": 1, "a.c": 1}
Document: {a: {b: 5, c: [7, 8, 9]}}
⇒ Multikey paths: ["a.c"],
Query: {"a.b": {$gte: 0, $lt: 10}, "a.c": 7}
⇒ Bounds on "a.b": [0, 10)
⇒ Bounds on "a.c": [MinKey, MaxKey]

Can compound bounds on "a.b" and "a.c" because the "a" field is never an array containing multiple elements.

Index: {"a.b": 1, "a.c": 1}
Document: {a: {b: [1, 2, 3], c: 5}
⇒ Multikey paths: ["a.b"]
⇒ Index entries: {"": 1, "": 5}, {"": 2, "": 5}, {"": 3, "": 5}
Query: {"a.b": 1, "a.c": 5}
⇒ Bounds on "a.b": [1, 1]
⇒ Bounds on "a.c": [5, 5]

Can compound bounds on "a.b.c" and "a.b.d" because the "a.b" field is never an array containing multiple elements.

Index: {"a.b.c": 1, "a.b.d": 1}
Document: {a: [{b: {c: 1}}, {b: {d: -1}}]}
⇒ Multikey paths: ["a"]
⇒ Index entries {"": 1, "": null}, {"": null, "": -1}
Query: {a: {$elemMatch: {"b.c": 1, "b.d": -1}}}
⇒ Bounds on "a.b.c": [1, 1]
⇒ Bounds on "a.b.d": [-1, -1]



 Comments   
Comment by Githook User [ 04/Mar/16 ]

Author:

{u'username': u'visemet', u'name': u'Max Hirschhorn', u'email': u'max.hirschhorn@mongodb.com'}

Message: SERVER-22401 Add new rules for assigning predicates to multikey indexes.

The metadata in the IndexEntry struct indicates what prefixes of the
indexed fields cause the index to be multikey. This information is used
to get tighter bounds by assigning additional predicates to the index.
Branch: master
https://github.com/mongodb/mongo/commit/b465c40655a665f61f34fb225ca77492e47a868f

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