Using indexes for sorting

Working with Data
1

With index { batch: 1, dob: 1 }, following query performs 2 index seeks and performs sort merge

db.Students.find({ batch: {$in: [2001, 2004]} }).sort({ dob: -1 }).limit(10000).explain("executionStats");

winningPlan: {
      stage: 'LIMIT',
      limitAmount: 10000,
      inputStage: {
        stage: 'FETCH',
        inputStage: {
          stage: 'SORT_MERGE',
          sortPattern: { dob: 1 },
          inputStages: [
            {
              stage: 'IXSCAN',
              keyPattern: { batch: 1, dob: 1 },
              indexName: 'batch_1_dob_1',
              isMultiKey: false,
              multiKeyPaths: { batch: [], dob: [] },
              isUnique: false,
              isSparse: false,
              isPartial: false,
              indexVersion: 2,
              direction: 'forward',
              indexBounds: {
                batch: [ '[2001, 2001]' ],
                dob: [ '[MinKey, MaxKey]' ]
              }
            },
            {
              stage: 'IXSCAN',
              keyPattern: { batch: 1, dob: 1 },
              indexName: 'batch_1_dob_1',
              isMultiKey: false,
              multiKeyPaths: { batch: [], dob: [] },
              isUnique: false,
              isSparse: false,
              isPartial: false,
              indexVersion: 2,
              direction: 'forward',
              indexBounds: {
                batch: [ '[2004, 2004]' ],
                dob: [ '[MinKey, MaxKey]' ]
              }
            }
          ]
        }
      }
    }

Then why does db.Students.find().sort({ batch: 1, dob: -1 }).limit(5) query with index { batch: 1, dob: -1 } does similar thing. For each batch scan the index backwards and merge the final result.
I know that sort order in query should match index order. I want to know the reason behind this limitaiton.
Why we cannot perform backward scans with multiple index seeks ?

2

Hi Anish, let me try to understand.
db.Students.find().sort({ batch: 1, dob: -1 }).limit(5).explain("executionStats").executionStats scans the index, get the entries ordered, with 1 seek and 5 keys examined.
If you mean db.Students.find({ batch: {$in: [2001, 2004]} }).sort({ batch: 1, dob: -1 }).limit(5).explain("executionStats").executionStats this is a single scan, forward.
Can you show the query and execution plan where you see a merge?

4

Let me simplifly

I have an composite index { batch: 1, dob: 1 }.
db.Students.find().sort({ batch: 1, dob: 1 }).limit(5) uses the composite index to fetch results in sorted order

db.Students.find().sort({ batch: 1, dob: -1 }).limit(5) does not use the index. It performs blocking sort.

Why not perform index seeks for each distinct batch value in backward direction and merge the results.

5

Ok, got it. So an index on { batch: 1, dob: 1 } can be used forward with { batch: 1, dob: 1 } or backwards with { batch: -1, dob: -1 }.
For sort({ batch: 1, dob: -1 }) an index on { batch: 1, dob: -1 } can be used forward, and an index on { batch: -1, dob: 1 } can be used backwards.

Think of it as the key is the concatenation of the fields, an index on { batch: 1, dob: 1 } is like:

A A.     ^
A B.     |
B A.     |
B B.     v

From it, you can read AA<AB<BA<BB or BB>BA>AB>AA, but you cannot read AB-AA-BB-BA
The merge sort with a $in is different because it looks at multiple ranges and can read each range forwards or backwards. But without a list of value, there’s no internal pointers to go back and forth