You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
sqlite3BtreeTableMoveto() binary-searches every page on the way down a rowid b-tree and ignores the values of the keys it compares. Rowids are integers and are usually close to evenly spaced within a page. When the search descends from an interior page, it already knows the child's key range: the cell that points to the child holds the child's largest rowid, and the cell to its left bounds it from below.
I'd like to propose using those bounds to interpolate the first probe on each page, step outward from it until the key is bracketed, and then finish with the existing binary search. The result is the same and the file format doesn't change; it uses fewer cell reads per seek.
Why it matters
Point lookups by rowid, rowid joins, REPLACE on an INTEGER PRIMARY KEY, and the row fetch after every index lookup all go through this function. In local measurements (details in #2311):
The number of cells compared per seek drops from about 19 to 7 on dense rowids and to 10 on random 64-bit rowids.
Point lookups, range seeks and joins by rowid get 10–49% faster on ten of the eleven rowid distributions I tested. On the eleventh, a synthetic one with heavy-tailed gaps, everything stays within ±6%.
The rowid-seeking speedtest1 tests get up to 35% faster. The geomean over all 32 tests is −0.9% on a file and −4.1% in memory.
Proposal
The change is in #2311. It adds about 130 lines to btree.c, can be compiled out with -DLIBSQL_OMIT_INTERP_SEEK, and doesn't touch index b-trees.
Two design points, with my position on each (the reasoning is in the PR description):
Divergence from upstream SQLite in btree.c. I think it is worth it. The change is confined to one function that upstream has changed by 3 lines since 2022, and it can be dropped at any time without affecting anything else.
On by default or opt-in. I propose on by default with the compile-time opt-out, because results are identical and the Rust crates build the bundled amalgamation with a fixed set of flags. If you prefer opt-in, I will change it.
Activity
timohuovinen commentedon Nov 8, 2026
PR: #2311