2 ms·
I think it would be better still to, when seeking forward, have it examine a couple of records, then start jumping forward in powers of 2 until it has located a
by btilly 17y ago
I think it would be better still to, when seeking forward, have it examine a couple of records, then start jumping forward in powers of 2 until it has located an interval with the next value in it, which it then does a binary search on to find the right location.
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.)
- quassnoi 17y agoUnfortunately, 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).