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.

        1. repro.js
          0.6 kB
          Ivan Fefer

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

              Created:
              Updated: