[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:
Depends
Related
is related to SERVER-12281 When choosing multikey index bounds, ... Backlog
is related to SERVER-16042 Optimise $all/$and to select smallest... Closed
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

db.t.find({a: {$lte: 0, $gte: 1}});

would have empty index bounds if 'a' were not a multikey field. Since it is multikey, however, we either use bounds

[-Infinity, 0]

or

[1, Infinity]

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:

db.t.insert({a: [1, 2, 3]});
db.t.ensureIndex({a: 1});
db.t.find({a: {$in: [1], $nin: [2]}}).explain().queryPlanner.winningPlan
{
...
			"indexBounds" : {
				"a" : [
					"[MinKey, 2.0)",
					"(2.0, MaxKey]"
				]
			}
...
}

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: SERVER-18364 ensure multikey bounds construction prefers non-negation predicates over negations

(cherry picked from commit 97b5712600ada8439f024f6bf446172f0fc9a7aa)
Branch: v3.0
https://github.com/mongodb/mongo/commit/bfb00166de25ac44b353cce3c9979391d357eb15

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: SERVER-18364 ensure multikey bounds construction prefers non-negation predicates over negations

Also backports a fix to the query planner unit test library in order to ensure that the unit tests
work correctly with this change.

(cherry picked from commit 97b5712600ada8439f024f6bf446172f0fc9a7aa)
Branch: v2.6
https://github.com/mongodb/mongo/commit/58143382b7f73c66199774e72523f4b0c53b362d

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: SERVER-18364 ensure multikey bounds construction prefers non-negation predicates over negations
Branch: master
https://github.com/mongodb/mongo/commit/97b5712600ada8439f024f6bf446172f0fc9a7aa

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