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

Plan enumerator doesn't enumerate all possibilities for a nested $or

    • Type: Icon: Bug Bug
    • Resolution: Done
    • Priority: Icon: Minor - P4 Minor - P4
    • 2.6.5, 2.7.6
    • Affects Version/s: 2.6.0-rc1, 2.6.4, 2.7.5
    • Component/s: Querying
    • None
    • ALL

      Say you have indices {a: 1} and {b: 1} and the following query:

      db.coll.find({c: 1, $or: [{$and: [{a: 1}, {b: 1}]}, {a: 1}]});
      

      Only one plan is generated for this query:

      KEEP_MUTATIONS
      ---filter:
              $and
                  $or
                      $and
                          a == 1.0
                          b == 1.0
                      a == 1.0
                  c == 1.0
      ---fetched = 1
      ---sortedByDiskLoc = 0
      ---getSort = []
      ---Child:
      ------FETCH
      ---------filter:
                      c == 1.0
      ---------fetched = 1
      ---------sortedByDiskLoc = 0
      ---------getSort = []
      ---------Child:
      ------------OR
      ---------------fetched = 0
      ---------------sortedByDiskLoc = 0
      ---------------getSort = []
      ---------------Child 0:
      ------------------FETCH
      ---------------------filter:
                                      b == 1.0
      ---------------------fetched = 1
      ---------------------sortedByDiskLoc = 1
      ---------------------getSort = [{ a: 1 }, ]
      ---------------------Child:
      ------------------------IXSCAN
      ---------------------------keyPattern = { a: 1.0 }
      ---------------------------direction = 1
      ---------------------------bounds = field #0['a']: [1.0, 1.0]
      ---------------------------fetched = 0
      ---------------------------sortedByDiskLoc = 1
      ---------------------------getSort = [{ a: 1 }, ]
      
      ---------------Child 1:
      ------------------IXSCAN
      ---------------------keyPattern = { a: 1.0 }
      ---------------------direction = 1
      ---------------------bounds = field #0['a']: [1.0, 1.0]
      ---------------------fetched = 0
      ---------------------sortedByDiskLoc = 1
      ---------------------getSort = [{ a: 1 }, ]
      

      However, there are additional plans that have not been enumerated. For example, the first child of the OR stage above could use index {b: 1}. It does not get enumerated because of how we step through the memo (see https://github.com/mongodb/mongo/blob/20a22bdf907a0e2cd60b79f242a7375d84a3ab6a/src/mongo/db/query/plan_enumerator.cpp#L1033). The outer $and only has one "top-level" choice, and we don't consider that there are multiple enumeration choices for the nested $and.

            Assignee:
            david.storch@mongodb.com David Storch
            Reporter:
            david.storch@mongodb.com David Storch
            Votes:
            0 Vote for this issue
            Watchers:
            7 Start watching this issue

              Created:
              Updated:
              Resolved: