Re:Things SQL needs: MERGE JOIN that would seek
by quassnoi on Wednesday May 12, 2010 @04:47PM
(#1342216)
Unfortunately, with a B+Tree index, you cannot jump in powers of 2 (well, you can but only within one page). To find a record with a given offset you'd need to traverse the whole linked list of the leaf-level pages, and that's what MERGE JOIN does by default.
However, this solution would be nice if you had a sorted recordset which allows efficient positional seek (for instance, a materialized result of the previous operation which required sorting).
This is at most a factor of 2 less efficient than a binary search, it is fast when the sequential reads are fast, and it doesn't rely on statistics telling the whole story. (For instance the size discrepancy could be explained by a small number of large gaps. This strategy would quickly jump the gaps while still getting fast sequential read behavior elsewhere.)