title: How does sorting with an index work in MongoDB?
body: <p>I'm wondering how sorting with an index actually works in MongoDB. There are a <a href="https://docs.mongodb.org/manual/reference/method/cursor.sort/#sort-and-index-use" rel="noreferrer">couple</a> <a href="https://docs.mongodb.org/manual/tutorial/sort-results-with-indexes/" rel="noreferrer">articles</a> in the MongoDB documentation, but they don't actually describe how the sort proceeds or the time complexity. Searches of SO and the interweb in general so far haven't turned up anything relevant.</p>
  
  <p>Let's assume there are <em>a</em> documents in a collection, the find() clause matches <em>b</em> documents, there's a limit of <em>c</em> documents returned, <em>a</em> >> <em>b</em> >> <em>c</em>, and <em>c</em> is some suitably large number such that the returned set cannot fit in memory - let's say 1M documents, for example.</p>
  
  <p>At the start of the operation, there exist <em>b</em> documents that needs to be sorted and a sorted tree index of size <em>a</em> for the feature the documents will be sorted by. </p>
  
  <p>I can imagine:</p>
  
  <p>A) traverse the index in order, and for each ObjectID traverse the list of <em>b</em> documents. Return matches until <em>c</em> is reached. This would be O(<em>ab</em>).</p>
  
  <p>B) as A), but build a hashset of the ObjectIDs in the <em>b</em> documents first. This is O(<em>a</em>), but takes O(<em>b</em>) memory.</p>
  
  <p>I've tried to consider sorts based on traversing the set of <em>b</em> documents, but can't seem to come up with anything faster than O(<em>b</em> log <em>b</em>), which is no better than sorting without an index.</p>
  
  <p>I assume (but maybe I'm wrong) that every sort doesn't require an index scan, so how does the sort actually work?</p>
  
  <p><strong>Update:</strong></p>
  
  <p>Kevin's answer and provided link narrow down the question a lot, but I'd like to confirm/clarify a few points:</p>
  
  <ol>
  <li>As I understand it, you cannot use different indexes for the query and the sort if you want to avoid an in-memory sort. When I read <a href="https://docs.mongodb.org/manual/tutorial/sort-results-with-indexes/" rel="noreferrer">this page</a> it appeared as though you could (or at least, it didn't specify one way or the other), but that seems to be incorrect. Essentially, the documents are sorted because they're looked up in the order of the index during the query and therefore returned in the order of the index. Right?</li>
  <li>When querying on a compound index, the the sorting index <em>must be the first index in the compound index</em>, except for indexes where the query is an equality. If not, the sort is performed in memory. Right?</li>
  <li><p>How does sorting work with <code>$in</code> or <code>$or</code> queries? For example, assume the query is</p>
  
  <p><code>{a: {$in: [4, 6, 2, 1, 3, 10]}, b: {$gt: 1, $lt: 6}}</code></p></li>
  </ol>
  
  <p>... and there's a compound index on <code>a</code> and <code>b</code> in that order. How would the sort work in the cases the sort is on <code>a</code> or <code>b</code>? <code>$or</code> is even more complicated since, as I understand it, <code>$or</code> queries are essentially split into multiple separate queries. Are <code>$or</code> queries always an in-memory sort, at least for merging the results of the separate queries?</p>