Skip to content

Faster rowid seeks: interpolation search inside table b-tree pages #2310

Open

Description

@timohuovinen

What

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):

  1. 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.
  2. 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

  1. timohuovinen commented on Nov 8, 2026

    @timohuovinen
    Author

    PR: #2311

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions