title: Why are all the keys examined for an indexed mongos query with a sort and limit?
body: <p>I have a mongos setup with 2 shards and the following data:</p>
  
  <pre><code>for (var i = 1; i &lt;= 1000; i++) { 
      db.items.insert({item: "a", i_type: "x", i_id: i, price: i * 50});
      db.items.insert({item: "a", i_type: "y", i_id: i, price: i * 50});
      db.items.insert({item: "b", i_type: "x", i_id: i, price: i * 50});
      db.items.insert({item: "b", i_type: "y", i_id: i, price: i * 50});
  }
  db.items.createIndex({item: 1, i_type: 1, i_id: 1}, {unique: true})
  db.items.createIndex({item: 1, i_type: 1, price: 1})
  sh.enableSharding("test")
  sh.shardCollection("test.items", {item: 1, i_type: 1})
  </code></pre>
  
  <p>I run this:</p>
  
  <pre><code>db.items.find(
      {item: "a", i_type: {$in: ["x", "y"]}},
      {_id: 0, item: 1, i_type: 1}
  ).sort({price: 1}).limit(10).explain("executionStats")
  </code></pre>
  
  <p>And get the following <code>executionStats</code>:</p>
  
  <pre><code>"nReturned" : NumberInt(10), 
  "executionTimeMillis" : NumberInt(22), 
  "totalKeysExamined" : NumberInt(2000), 
  "totalDocsExamined" : NumberInt(2000), 
  "executionStages" : {
      "stage" : "SINGLE_SHARD", 
      "nReturned" : NumberInt(10), 
      "executionTimeMillis" : NumberInt(22), 
      "totalKeysExamined" : NumberInt(2000), 
      "totalDocsExamined" : NumberInt(2000), 
      "totalChildMillis" : NumberLong(21), 
      "shards" : [
          {
              "shardName" : "rs1", 
              "executionSuccess" : true, 
              "executionStages" : {
                  "stage" : "PROJECTION", 
                  "nReturned" : NumberInt(10), 
                  "executionTimeMillisEstimate" : NumberInt(0), 
                  "works" : NumberInt(2013), 
                  "advanced" : NumberInt(10), 
                  "needTime" : NumberInt(2002), 
                  "needFetch" : NumberInt(0), 
                  "saveState" : NumberInt(47), 
                  "restoreState" : NumberInt(47), 
                  "isEOF" : NumberInt(1), 
                  "invalidates" : NumberInt(0), 
                  "transformBy" : {
                      "_id" : NumberInt(0), 
                      "item" : NumberInt(1), 
                      "i_type" : NumberInt(1)
                  }, 
                  "inputStage" : {
                      "stage" : "SORT", 
                      "nReturned" : NumberInt(10), 
                      "executionTimeMillisEstimate" : NumberInt(0), 
                      "works" : NumberInt(2013), 
                      "advanced" : NumberInt(10), 
                      "needTime" : NumberInt(2001), 
                      "needFetch" : NumberInt(0), 
                      "saveState" : NumberInt(47), 
                      "restoreState" : NumberInt(47), 
                      "isEOF" : NumberInt(1), 
                      "invalidates" : NumberInt(0), 
                      "sortPattern" : {
                          "price" : NumberInt(1)
                      }, 
                      "memUsage" : NumberInt(850), 
                      "memLimit" : NumberInt(33554432), 
                      "limitAmount" : NumberInt(10), 
                      "inputStage" : {
                          "stage" : "FETCH", 
                          "nReturned" : NumberInt(2000), 
                          "executionTimeMillisEstimate" : NumberInt(0), 
                          "works" : NumberInt(2001), 
                          "advanced" : NumberInt(2000), 
                          "needTime" : NumberInt(0), 
                          "needFetch" : NumberInt(0), 
                          "saveState" : NumberInt(47), 
                          "restoreState" : NumberInt(47), 
                          "isEOF" : NumberInt(1), 
                          "invalidates" : NumberInt(0), 
                          "docsExamined" : NumberInt(2000), 
                          "alreadyHasObj" : NumberInt(0), 
                          "inputStage" : {
                              "stage" : "SHARDING_FILTER", 
                              "nReturned" : NumberInt(2000), 
                              "executionTimeMillisEstimate" : NumberInt(0), 
                              "works" : NumberInt(2001), 
                              "advanced" : NumberInt(2000), 
                              "needTime" : NumberInt(0), 
                              "needFetch" : NumberInt(0), 
                              "saveState" : NumberInt(47), 
                              "restoreState" : NumberInt(47), 
                              "isEOF" : NumberInt(1), 
                              "invalidates" : NumberInt(0), 
                              "chunkSkips" : NumberInt(0), 
                              "inputStage" : {
                                  "stage" : "IXSCAN", 
                                  "nReturned" : NumberInt(2000), 
                                  "executionTimeMillisEstimate" : NumberInt(0), 
                                  "works" : NumberInt(2001), 
                                  "advanced" : NumberInt(2000), 
                                  "needTime" : NumberInt(0), 
                                  "needFetch" : NumberInt(0), 
                                  "saveState" : NumberInt(47), 
                                  "restoreState" : NumberInt(47), 
                                  "isEOF" : NumberInt(1), 
                                  "invalidates" : NumberInt(0), 
                                  "keyPattern" : {
                                      "item" : NumberInt(1), 
                                      "i_type" : NumberInt(1), 
                                      "price" : NumberInt(1)
                                  }, 
                                  "indexName" : "item_1_i_type_1_price_1", 
                                  "isMultiKey" : false, 
                                  "direction" : "forward", 
                                  "indexBounds" : {
                                      "item" : [
                                          "[\"a\", \"a\"]"
                                      ], 
                                      "i_type" : [
                                          "[\"x\", \"x\"]", 
                                          "[\"y\", \"y\"]"
                                      ], 
                                      "price" : [
                                          "[MinKey, MaxKey]"
                                      ]
                                  }, 
                                  "keysExamined" : NumberInt(2000), 
                                  "dupsTested" : NumberInt(0), 
                                  "dupsDropped" : NumberInt(0), 
                                  "seenInvalidated" : NumberInt(0), 
                                  "matchTested" : NumberInt(0)
                              }
                          }
                      }
                  }
              }
          }
      ]
  }
  </code></pre>
  
  <p>I am struggling to understand why all the keys containing <code>{item: "a", i_type: "x"}</code> and <code>{item: "a", i_type: "y"}</code> need to be examined on the shard. The explain suggests it is using the appropriate index.</p>
  
  <p>If I run the same query on the replica set where the documents reside my <code>totalKeysExamined</code> is 10. If I remove the sort or query for a single <code>i_type</code> on mongos the <code>totalKeysExamined</code> are 10 (or 11 depending on auto-balancing). All of these query plans have an <code>executionStage</code> of <code>LIMIT</code> that is distinctly missing from the explain I have posted above. </p>
  
  <p>Depending on how the auto-balancer decides to do things the first <code>executionStage</code> in the hierarchy may be <code>SHARD_MERGE_SORT</code> instead of <code>SINGLE_SHARD</code>, but even if the query needed to fetch information from both shards I would assume only 20 keys would need to be examined (10 from each shard).</p>
  
  <p>Is this a limitation of mongos that I am running into, a situation where I need to improve my choice of shard key and indexes, or something completely different?</p>