lance-format / lance-format/lance

Finger search for btree index usage

Open
#4,648 0 comments 0 reactions 1 assignee View on GitHub

@jbapple is already working on this.

Since Sep 4, 2025.

performance
Dominant language
Rust
Stars
7.1k
Forks
852
Avg merge
3d 18h
Merged PRs (30d)
272

Description

When searching a large target table with a sorted index, if the source keys being searched for are also sorted, it is not necessary to restart every search on the target with the full range of the index as a potential target. For instance, if you were looking for ["alpha", "bravo", "charlie"] in a sorted list of strings, after finding "alpha", you know that "bravo" cannot be in any of the slots before the slot in target which "alpha" was found.

This can be accomplished by doing an exponential search starting from the target's "alpha" slot until "bravo" is exceeded, then doing a binary search between the two bounding slots. In the literature on trees, this is sometimes called "finger search". It reduces the total search cost from O(x log(y)) to O(x log(y/x)).

This could potentially require changing BTreeLookup::tree away from a BTreeMap if some combination of nth, Cursor, etc. doesn't suffice in terms of API needed for finger search.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.