title: Data structure / algorithm for query: filter by A, sort by B, return N results
body: <p>Imagine that you have a large set of <code>#m</code> objects with properties <code>A</code> and <code>B</code>. What data structure can you use as index(s) (or which algorithm) to improve the performance of the following query?</p>
  
  <pre><code>find all objects where A between X and Y, order by B, return first N results;
  </code></pre>
  
  <p>That is, filter by range <code>A</code> and sort by <code>B</code>, but only return the first few results (say, 1000 at most). Insertions are very rare, so heavy preprocessing is acceptable. I'm <em>not</em> happy with the following options:</p>
  
  <ol>
  <li><p><strong>With records (or index) sorted by B</strong>: Scan the records/index in <code>B</code> order, return the first <code>N</code> where <code>A</code> matches X-Y. In the worst cases (few objects match the range X-Y, or the matches are at the end of the records/index) this becomes <code>O(m)</code>, which for large data sets of size <code>m</code> is not good enough.</p></li>
  <li><p><strong>With records (or index) sorted by A</strong>: Do a binary search until the first object is found which matches the range X-Y. Scan and create an array of references to all <code>k</code> objects which match the range. Sort the array by B, return the first <code>N</code>. That's <code>O(log m + k + k log k)</code>. If <code>k</code> is small then that's really <code>O(log m)</code>, but if <code>k</code> is large then the cost of the sort becomes even worse than the cost of the linear scan over all <code>m</code>objects.</p></li>
  <li><p><strong>Adaptative 2/1</strong>: do a binary search for the first match of the range X-Y (using an index over A); do a binary search for the last match of the range. If the range is small continue with algorithm 2; otherwise revert to algorithm 1. The problem here is the case where we revert to algorithm 1. Although we checked that "many" objects pass the filter, which is the good case for algorithm 1, this "many" is at most a constant (asymptotically the <code>O(n)</code> scan will always win over the <code>O(k log k)</code> sort). So we still have an <code>O(n)</code> algorithm for some queries.</p></li>
  </ol>
  
  <p>Is there an algorithm / data structure which allows answering this query in sublinear time?</p>
  
  <p>If not, what could be good compromises to achieve the necessary performance? For instance, if I don't guarantee returning the objects best ranking for their <code>B</code> property (recall &lt; 1.0) then I can scan only a fraction of the B index. But could I do that while bounding the results' quality somehow?</p>