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

Improve negation-related tree normalization during query canonicalization

    • Type: Icon: Improvement Improvement
    • Resolution: Unresolved
    • Priority: Icon: Minor - P4 Minor - P4
    • None
    • Affects Version/s: 2.5.5
    • Component/s: Querying
    • Query Optimization
    • Fully Compatible

      There are two cases that could be improved:

      1) We do not remove negations of negations. Example:

      > t.drop()
      > t.ensureIndex({a: 1})
      > t.find({a: {$not: {$not: {$gt: 1}}}})
      

      This query parses to the match expression below:

      $not
          $not
              a $gt 1.0
      

      Since this has a negation of something that is not bounds-generating (more precisely, another negation), this query will not use the index. If instead the CanonicalQuery::normalizeTree function rewrote this tree to simply "a $gt 1.0", then it would do an index scan over (1, Infinity] rather than a collection scan.

      In 2.4.8, a double-negation is not allowed at all:

      > t.find({a: {$not: {$not: {$gt: 1}}}})
      error: { "$err" : "invalid use of $not", "code" : 13034 }
      

      Another option is for canonicalization to return an error if it finds a double negation.

      2) Tree normalization does not pass through $elemMatch. Example:

      > t.ensureIndex({a: 1})
      > t.find({a: {$elemMatch: {b: {$not: {$gt: 1}}}}})
      

      This parses to the match expression shown below:

      a $elemMatch (obj)
          $not
              $and
                  b $gt 1.0
      

      Since normalization does not pass through the $elemMatch, we do not end up removing the single-child $and as we would elsewhere. In other words, the canonicalized tree should be

      a $elemMatch (obj)
          $not
               b $gt 1.0
      

            Assignee:
            backlog-query-optimization [DO NOT USE] Backlog - Query Optimization
            Reporter:
            david.storch@mongodb.com David Storch
            Votes:
            0 Vote for this issue
            Watchers:
            7 Start watching this issue

              Created:
              Updated: