title: mongodb 4.2 sort by id slow with compound index
body: <p>I have docs in the fasion</p>
  
  <pre><code>{
    _id: ...,
    p: [
         {
           k: 'stringvalue',
           v: 'stringvalue'
         },
         ...
       ]
  }
  </code></pre>
  
  <p><code>_id</code> is provided to drivers as a sequence number of insertion, e.g. <code>...0001</code>, <code>....0002</code>, etc.</p>
  
  <p>That works extermely well for find queries, now I have added sort condition and added <code>_id</code> field to the compound index (see below).
  That works extermely bad around x100 slower, what could be the reason? The server has plenty of RAM.</p>
  
  <pre><code>db.getCollection('mycoll').find({ p: { '$elemMatch': { k: 'd', v: { '$gt': '2019-10-16T08:01:39.741' } } } }).sort({_id: 1}).explain()
  {
          "queryPlanner" : {
                  "plannerVersion" : 1,
                  "namespace" : "mydb.mycoll",
                  "indexFilterSet" : false,
                  "parsedQuery" : {
                          "p" : {
                                  "$elemMatch" : {
                                          "$and" : [
                                                  {
                                                          "k" : {
                                                                  "$eq" : "d"
                                                          }
                                                  },
                                                  {
                                                          "v" : {
                                                                  "$gt" : "2019-10-16T08:01:39.741"
                                                          }
                                                  }
                                          ]
                                  }
                          }
                  },
                  "queryHash" : "E28632C1",
                  "planCacheKey" : "E28632C1",
                  "winningPlan" : {
                          "stage" : "SORT",
                          "sortPattern" : {
                                  "_id" : 1
                          },
                          "inputStage" : {
                                  "stage" : "SORT_KEY_GENERATOR",
                                  "inputStage" : {
                                          "stage" : "FETCH",
                                          "filter" : {
                                                  "p" : {
                                                          "$elemMatch" : {
                                                                  "$and" : [
                                                                          {
                                                                                  "k" : {
                                                                                          "$eq" : "d"
                                                                                  }
                                                                          },
                                                                          {
                                                                                  "v" : {
                                                                                          "$gt" : "2019-10-16T08:01:39.741"
                                                                                  }
                                                                          }
                                                                  ]
                                                          }
                                                  }
                                          },
                                          "inputStage" : {
                                                  "stage" : "IXSCAN",
                                                  "keyPattern" : {
                                                          "p.k" : 1,
                                                          "p.v" : 1,
                                                          "_id" : 1
                                                  },
                                                  "indexName" : "p.k_1_p.v_1__id_1",
                                                  "isMultiKey" : true,
                                                  "multiKeyPaths" : {
                                                          "p.k" : [
                                                                  "p"
                                                          ],
                                                          "p.v" : [
                                                                  "p"
                                                          ],
                                                          "_id" : [ ]
                                                  },
                                                  "isUnique" : false,
                                                  "isSparse" : false,
                                                  "isPartial" : false,
                                                  "indexVersion" : 2,
                                                  "direction" : "forward",
                                                  "indexBounds" : {
                                                          "p.k" : [
                                                                  "[\"d\", \"d\"]"
                                                          ],
                                                          "p.v" : [
                                                                  "(\"2019-10-16T08:01:39.741\", {})"
                                                          ],
                                                          "_id" : [
                                                                  "[MinKey, MaxKey]"
                                                          ]
                                                  }
                                          }
                                  }
                          }
                  },
                  "rejectedPlans" : [
                          {
                                  "stage" : "FETCH",
                                  "filter" : {
                                          "p" : {
                                                  "$elemMatch" : {
                                                          "$and" : [
                                                                  {
                                                                          "k" : {
                                                                                  "$eq" : "d"
                                                                          }
                                                                  },
                                                                  {
                                                                          "v" : {
                                                                                  "$gt" : "2019-10-16T08:01:39.741"
                                                                          }
                                                                  }
                                                          ]
                                                  }
                                          }
                                  },
                                  "inputStage" : {
                                          "stage" : "IXSCAN",
                                          "keyPattern" : {
                                                  "_id" : 1
                                          },
                                          "indexName" : "_id_",
                                          "isMultiKey" : false,
                                          "multiKeyPaths" : {
                                                  "_id" : [ ]
                                          },
                                          "isUnique" : true,
                                          "isSparse" : false,
                                          "isPartial" : false,
                                          "indexVersion" : 2,
                                          "direction" : "forward",
                                          "indexBounds" : {
                                                  "_id" : [
                                                          "[MinKey, MaxKey]"
                                                  ]
                                          }
                                  }
                          }
                  ]
          },
          "serverInfo" : {
                  "host" : "dev-10-178-3-247",
                  "port" : 27017,
                  "version" : "4.2.0",
                  "gitVersion" : "a4b751dcf51dd249c5865812b390cfd1c0129c30"
          },
          "ok" : 1
  }
  </code></pre>
  
  <pre><code>&gt; db.getCollection('mycoll').getIndexes()
  [
          {
                  "v" : 2,
                  "key" : {
                          "_id" : 1
                  },
                  "name" : "_id_",
                  "ns" : "mydb.mycoll"
          },
          {
                  "v" : 2,
                  "key" : {
                          "p.k" : 1,
                          "p.v" : 1,
                          "_id" : 1
                  },
                  "name" : "p.k_1_p.v_1__id_1",
                  "ns" : "mydb.mycoll"
          }
  ]
  </code></pre>
  
  <pre><code>{
  "executionStats" : {
    "executionSuccess" : true,
    "nReturned" : 1015268,
    "executionTimeMillis" : 77032,
    "totalKeysExamined" : 3122749,
    "totalDocsExamined" : 3122749,
    "executionStages" : {
            "stage" : "FETCH",
            "filter" : {
                    "p" : {
                            "$elemMatch" : {
                                    "$and" : [
                                            {
                                                    "k" : {
                                                            "$eq" : "d"
                                                    }
                                            },
                                            {
                                                    "v" : {
                                                            "$gt" : "2019-10-16T08:01:39.741"
                                                    }
                                            }
                                    ]
                            }
                    }
            },
            "nReturned" : 1015268,
            "executionTimeMillisEstimate" : 16092,
            "works" : 3122750,
            "advanced" : 1015268,
            "needTime" : 2107481,
            "needYield" : 0,
            "saveState" : 24469,
            "restoreState" : 24469,
            "isEOF" : 1,
            "docsExamined" : 3122749,
            "alreadyHasObj" : 0,
            "inputStage" : {
                    "stage" : "IXSCAN",
                    "nReturned" : 3122749,
                    "executionTimeMillisEstimate" : 492,
                    "works" : 3122750,
                    "advanced" : 3122749,
                    "needTime" : 0,
                    "needYield" : 0,
                    "saveState" : 24469,
                    "restoreState" : 24469,
                    "isEOF" : 1,
                    "keyPattern" : {
                            "_id" : 1
                    },
                    "indexName" : "_id_",
                    "isMultiKey" : false,
                    "multiKeyPaths" : {
                            "_id" : [ ]
                    },
                    "isUnique" : true,
                    "isSparse" : false,
                    "isPartial" : false,
                    "indexVersion" : 2,
                    "direction" : "forward",
                    "indexBounds" : {
                            "_id" : [
                                    "[MinKey, MaxKey]"
                            ]
                    },
                    "keysExamined" : 3122749,
                    "seeks" : 1,
                    "dupsTested" : 0,
                    "dupsDropped" : 0
            }
    },
    "allPlansExecution" : [
            {
                    "nReturned" : 0,
                    "executionTimeMillisEstimate" : 85,
                    "totalKeysExamined" : 9298,
                    "totalDocsExamined" : 9298,
                    "executionStages" : {
                            "stage" : "SORT",
                            "nReturned" : 0,
                            "executionTimeMillisEstimate" : 85,
                            "works" : 9300,
                            "advanced" : 0,
                            "needTime" : 9299,
                            "needYield" : 0,
                            "saveState" : 7391,
                            "restoreState" : 7391,
                            "isEOF" : 0,
                            "sortPattern" : {
                                    "_id" : 1
                            },
                            "memUsage" : 33559558,
                            "memLimit" : 33554432,
                            "inputStage" : {
                                    "stage" : "SORT_KEY_GENERATOR",
                                    "nReturned" : 9298,
                                    "executionTimeMillisEstimate" : 71,
                                    "works" : 9299,
                                    "advanced" : 9298,
                                    "needTime" : 1,
                                    "needYield" : 0,
                                    "saveState" : 7391,
                                    "restoreState" : 7391,
                                    "isEOF" : 0,
                                    "inputStage" : {
                                            "stage" : "FETCH",
                                            "filter" : {
                                                    "p" : {
                                                            "$elemMatch" : {
                                                                    "$and" : [
                                                                            {
                                                                                    "k" : {
                                                                                            "$eq" : "d"
                                                                                    }
                                                                            },
                                                                            {
                                                                                    "v" : {
                                                                                            "$gt" : "2019-10-16T08:01:39.741"
                                                                                    }
                                                                            }
                                                                    ]
                                                            }
                                                    }
                                            },
                                            "nReturned" : 9298,
                                            "executionTimeMillisEstimate" : 58,
                                            "works" : 9298,
                                            "advanced" : 9298,
                                            "needTime" : 0,
                                            "needYield" : 0,
                                            "saveState" : 7391,
                                            "restoreState" : 7391,
                                            "isEOF" : 0,
                                            "docsExamined" : 9298,
                                            "alreadyHasObj" : 0,
                                            "inputStage" : {
                                                    "stage" : "IXSCAN",
                                                    "nReturned" : 9298,
                                                    "executionTimeMillisEstimate" : 0,
                                                    "works" : 9298,
                                                    "advanced" : 9298,
                                                    "needTime" : 0,
                                                    "needYield" : 0,
                                                    "saveState" : 7391,
                                                    "restoreState" : 7391,
                                                    "isEOF" : 0,
                                                    "keyPattern" : {
                                                            "p.k" : 1,
                                                            "p.v" : 1,
                                                            "_id" : 1
                                                    },
                                                    "indexName" : "p.k_1_p.v_1__id_1",
                                                    "isMultiKey" : true,
                                                    "multiKeyPaths" : {
                                                            "p.k" : [
                                                                    "p"
                                                            ],
                                                            "p.v" : [
                                                                    "p"
                                                            ],
                                                            "_id" : [ ]
                                                    },
                                                    "isUnique" : false,
                                                    "isSparse" : false,
                                                    "isPartial" : false,
                                                    "indexVersion" : 2,
                                                    "direction" : "forward",
                                                    "indexBounds" : {
                                                            "p.k" : [
                                                                    "[\"d\", \"d\"]"
                                                            ],
                                                            "p.v" : [
                                                                    "(\"2019-10-16T08:01:39.741\", {})"
                                                            ],
                                                            "_id" : [
                                                                    "[MinKey, MaxKey]"
                                                            ]
                                                    },
                                                    "keysExamined" : 9298,
                                                    "seeks" : 1,
                                                    "dupsTested" : 9298,
                                                    "dupsDropped" : 0
                                            }
                                    }
                            }
                    }
            },
            {
                    "nReturned" : 0,
                    "executionTimeMillisEstimate" : 85,
                    "totalKeysExamined" : 9298,
                    "totalDocsExamined" : 9298,
                    "executionStages" : {
                            "stage" : "SORT",
                            "nReturned" : 0,
                            "executionTimeMillisEstimate" : 85,
                            "works" : 9301,
                            "advanced" : 0,
                            "needTime" : 9299,
                            "needYield" : 0,
                            "saveState" : 24469,
                            "restoreState" : 24469,
                            "isEOF" : 0,
                            "sortPattern" : {
                                    "_id" : 1
                            },
                            "memUsage" : 33559558,
                            "memLimit" : 33554432,
                            "inputStage" : {
                                    "stage" : "SORT_KEY_GENERATOR",
                                    "nReturned" : 9298,
                                    "executionTimeMillisEstimate" : 71,
                                    "works" : 9299,
                                    "advanced" : 9298,
                                    "needTime" : 1,
                                    "needYield" : 0,
                                    "saveState" : 24469,
                                    "restoreState" : 24469,
                                    "isEOF" : 0,
                                    "inputStage" : {
                                            "stage" : "FETCH",
                                            "filter" : {
                                                    "p" : {
                                                            "$elemMatch" : {
                                                                    "$and" : [
                                                                            {
                                                                                    "k" : {
                                                                                            "$eq" : "d"
                                                                                    }
                                                                            },
                                                                            {
                                                                                    "v" : {
                                                                                            "$gt" : "2019-10-16T08:01:39.741"
                                                                                    }
                                                                            }
                                                                    ]
                                                            }
                                                    }
                                            },
                                            "nReturned" : 9298,
                                            "executionTimeMillisEstimate" : 58,
                                            "works" : 9298,
                                            "advanced" : 9298,
                                            "needTime" : 0,
                                            "needYield" : 0,
                                            "saveState" : 24469,
                                            "restoreState" : 24469,
                                            "isEOF" : 0,
                                            "docsExamined" : 9298,
                                            "alreadyHasObj" : 0,
                                            "inputStage" : {
                                                    "stage" : "IXSCAN",
                                                    "nReturned" : 9298,
                                                    "executionTimeMillisEstimate" : 0,
                                                    "works" : 9298,
                                                    "advanced" : 9298,
                                                    "needTime" : 0,
                                                    "needYield" : 0,
                                                    "saveState" : 24469,
                                                    "restoreState" : 24469,
                                                    "isEOF" : 0,
                                                    "keyPattern" : {
                                                            "p.k" : 1,
                                                            "p.v" : 1,
                                                            "_id" : 1
                                                    },
                                                    "indexName" : "p.k_1_p.v_1__id_1",
                                                    "isMultiKey" : true,
                                                    "multiKeyPaths" : {
                                                            "p.k" : [
                                                                    "p"
                                                            ],
                                                            "p.v" : [
                                                                    "p"
                                                            ],
                                                            "_id" : [ ]
                                                    },
                                                    "isUnique" : false,
                                                    "isSparse" : false,
                                                    "isPartial" : false,
                                                    "indexVersion" : 2,
                                                    "direction" : "forward",
                                                    "indexBounds" : {
                                                            "p.k" : [
                                                                    "[\"d\", \"d\"]"
                                                            ],
                                                            "p.v" : [
                                                                    "(\"2019-10-16T08:01:39.741\", {})"
                                                            ],
                                                            "_id" : [
                                                                    "[MinKey, MaxKey]"
                                                            ]
                                                    },
                                                    "keysExamined" : 9298,
                                                    "seeks" : 1,
                                                    "dupsTested" : 9298,
                                                    "dupsDropped" : 0
                                            }
                                    }
                            }
                    }
            }
    ]
  },
  "ok" : 1
  }
  </code></pre>