[SERVER-18364] Ensure non-negation predicates get chosen over negation predicates for multikey index bounds construction Created: 07/May/15 Updated: 19/Sep/15 Resolved: 07/May/15 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | Querying |
| Affects Version/s: | None |
| Fix Version/s: | 2.6.10, 3.0.4, 3.1.3 |
| Type: | Improvement | Priority: | Major - P3 |
| Reporter: | David Storch | Assignee: | David Storch |
| Resolution: | Done | Votes: | 0 |
| Labels: | None | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Issue Links: |
|
||||||||||||||||
| Backwards Compatibility: | Fully Compatible | ||||||||||||||||
| Backport Completed: | |||||||||||||||||
| Sprint: | Quint Iteration 3 | ||||||||||||||||
| Participants: | |||||||||||||||||
| Description |
|
For queries with multiple predicates over a multikey field, you can't intersect the index bounds. Suppose there is a multikey index on field 'a'. The following query
would have empty index bounds if 'a' were not a multikey field. Since it is multikey, however, we either use bounds
or
The implementation currently chooses between the possible bounds by selecting one of the predicates over the indexed field. In particular, it just chooses the first predicate. The parsed query tree is always sorted according to predicate type, which means that sometimes we build multikey bounds using negation predicates rather than non-negation predicates:
The explain output above shows that we selected bounds using the $nin predicate rather than the $in. Although we don't definitively know which bounds are the most selective because the system does not keep stats/histograms describing the data, it is generally a good heuristic to choose bounds from non-negation predicates over bounds from negation predicates. (Bounds from negation predicates tend to be wider.) We should ensure that we always choose non-negation bounds over negation bounds by sorting non-negation predicates before negations in the parsed query tree. |
| Comments |
| Comment by Githook User [ 13/May/15 ] |
|
Author: {u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}Message: (cherry picked from commit 97b5712600ada8439f024f6bf446172f0fc9a7aa) |
| Comment by Githook User [ 07/May/15 ] |
|
Author: {u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}Message: Also backports a fix to the query planner unit test library in order to ensure that the unit tests (cherry picked from commit 97b5712600ada8439f024f6bf446172f0fc9a7aa) |
| Comment by Githook User [ 07/May/15 ] |
|
Author: {u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}Message: |