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

Support explode for sort optimization when there is a FETCH after OR

    • Type: Icon: Improvement Improvement
    • Resolution: Unresolved
    • Priority: Icon: Major - P3 Major - P3
    • None
    • Affects Version/s: None
    • Component/s: None
    • Query Optimization

      Consider the query

      db.test.explain().find({
          $or: [
              {a: {$in: [3, 7]}},
              {b: {$in: [4, 6]}}
          ],
          {d: {$exists: false}}
      }).sort({c: 1}));
      

      And indexes

      {a: 1, c: 1} {b: 1, c: 1}

      The ideal plan for this query should include 4 index scans with point bounds for a or b, such that they each provide a sort on c and a SORT_MERGE.

      However to explode the index scans for sort and end up with a plan that contains a blocking sort
      SORT - - FETCH - OR - 2x IXSCAN:

          winningPlan: {
            stage: 'SORT',
            <..>
            inputStage: {
              stage: 'FETCH',
              filter: { e: { '$not': { '$exists': true } } },
              inputStage: {
                stage: 'OR',
                inputStages: [
                  {
                    stage: 'IXSCAN',
                    keyPattern: { a: 1, c: 1 },
                    <..>
                    indexBounds: { a: [ '[3, 3]', '[7, 7]' ], c: [ '[MinKey, MaxKey]' ] }
                  },
                  {
                    stage: 'IXSCAN',
                    keyPattern: { b: 1, c: 1 },
                    <..>
                    indexBounds: { b: [ '[4, 4]', '[6, 6]' ], c: [ '[MinKey, MaxKey]' ] }
                  }
                ]
              }
            }
      

      But if we remove predicate on d, everything works as expected: sort_merge and 4 ixscans.

        winningPlan: {
            stage: 'SUBPLAN',
            inputStage: {
              stage: 'FETCH',
              inputStage: {
                stage: 'SORT_MERGE',
                inputStages: [
                  {
                    stage: 'IXSCAN',
                    keyPattern: { a: 1, c: 1 },
                    indexName: 'a_1_c_1',
                    <..>
                    indexBounds: { a: [ '[3, 3]' ], c: [ '[MinKey, MaxKey]' ] }
                  },
                  {
                    stage: 'IXSCAN',
                    keyPattern: { a: 1, c: 1 },
                    <..>
                    indexBounds: { a: [ '[7, 7]' ], c: [ '[MinKey, MaxKey]' ] }
                  },
                  {
                    stage: 'IXSCAN',
                    keyPattern: { b: 1, c: 1 },
                    <..>
                    indexBounds: { b: [ '[4, 4]' ], c: [ '[MinKey, MaxKey]' ] }
                  },
                  {
                    stage: 'IXSCAN',
                    keyPattern: { b: 1, c: 1 },
                    <..>
                    indexBounds: { b: [ '[6, 6]' ], c: [ '[MinKey, MaxKey]' ] }
                  }
                ]
              }
            }
      

      I suspect this code to be the reason: https://github.com/mongodb/mongo/blob/5cf319032320a6c3aca95eeccf59d1ec65a2e910/src/mongo/db/query/planner_analysis.cpp#L201

      When we traverse the query solution to check for explode for sort, we only go down through SHARDING_FILTER, OR and FETCH, but only if FETCH has a single IXSCAN child.

      However in this case we have FETCH before the OR, so we fail this check and don't proceed with the traversal.

            Assignee:
            Unassigned Unassigned
            Reporter:
            ivan.fefer@mongodb.com Ivan Fefer
            Votes:
            0 Vote for this issue
            Watchers:
            6 Start watching this issue

              Created:
              Updated: