Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-18364

Ensure non-negation predicates get chosen over negation predicates for multikey index bounds construction

    • Type: Icon: Improvement Improvement
    • Resolution: Done
    • Priority: Icon: Major - P3 Major - P3
    • 2.6.10, 3.0.4, 3.1.3
    • Affects Version/s: None
    • Component/s: Querying
    • Labels:
    • Fully Compatible
    • Quint Iteration 3

      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]


      [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.

            david.storch@mongodb.com David Storch
            david.storch@mongodb.com David Storch
            0 Vote for this issue
            6 Start watching this issue