bug(fts): limit/offset pagination skips and repeats equal-score results (Node 0.38/0.39 preview)

[mick-net]

Description

Full-text search with limit/offset can repeat some rows and omit others on an unchanged dataset when many rows have equal BM25 scores. This affects flat, indexed and mixed storage. Sorting each returned page cannot restore candidates already discarded inside top-K selection.

Related implementation: #7846. I found that PR after testing a small local repair against Lance 9.0.0. This report supplies an independent Node reproduction and requests community review. We have not built or tested #7846's branch.

Observed results

The synthetic fixture has 180 scalar-text documents, two relevance levels, and multiple fragments. A single query with limit 200 returns all 180 rows. Paging by 10 returns 180 rows in total, but both published Node packages (0.38.0 and 0.39.0-beta.6) produced these counts with FTS formats 1 and 3:

Storage	Unique rows of 180	Missing	Repeated
Flat	128	52	52
Fully indexed	91	89	89
Mixed indexed/appended	105	75	75

Page sizes 7 and 65 also lose rows. All 36 layout/page-size combinations across these versions and formats reproduce missing/repeated rows. Incidental ordering can vary; omitted membership is the important failure. The reproduction completes every page before reporting failure and checks that search does not write the dataset.

Experimental repair for review

The attached patch targets Lance v9.0.0 at 7653c20, used with the LanceDB v0.33.0 Node binding at 01df4f72c05168d53a4dd326c9448b0379e3d2e6. It was developed with Codex and tested locally. It is an investigation artifact, not a patch against current main or a production-ready native release.

1. Compare score descending, then real row ID ascending in collectors and partition/segment merges.
2. For default-factor WAND and positive finite cutoffs, use the next lower representable f32 value for strict pruning checks so exact ties remain eligible. Keep the actual score in the shared threshold.
3. Resolve real IDs before local selection; posting IDs can order differently after remapping.
4. Apply the same sort before flat/mixed and compound top-K truncation.
5. In this older source, use the propagated params.limit for MultiMatch so offsets and nested unlimited queries work. Our separate MultiMatch/nested-offset regression already passes on published 0.38.0 and 0.39.0-beta.6.

The local patched binding passes all nine standalone layout/page-size scenarios with all 180 rows returned once. Four raw-native tests pass in both FTS formats 1 and 2; the same four fail on stock/source-built unpatched 0.33. We also ran 85 Rust WAND tests and downstream incremental, old-index and Electron search regressions. These results do not establish correctness for every query shape or current-main index format.

Known tradeoff: this small patch eagerly loads real IDs for contributing partitions. Source inspection estimates about 36 MB per million contributing documents when cached columns and reverse lookup coexist; this is not measured at that scale. Small development-build probes showed peak RSS 348.1 -> 350.9 MiB, with less than 1% index-time/disk variation. These unoptimized results are not release-performance evidence. No index-writing format change is in the patch. Cross-platform optimized builds and signed packaged verification are not done.

The bounded deferred-candidate/retry approach in #7846 appears preferable for avoiding unconditional ID loads. We have not compared its performance.

Review questions

• Does the reproduction match the intended pagination contract, and is fix(fts): deterministic top-k tiebreak for tied scores #7846 the right place to converge the repair?
• Are the real-ID tie rule and inclusive WAND boundary sufficient for exact default-BM25 retrieval across partitions, remaps and mixed index coverage?
• What additional correctness or memory/performance checks should gate adoption? Our patch retains previous non-default WAND-factor and nonpositive/nonfinite custom-score behavior.

Attachments

The reproduction and experimental patch use only synthetic data and upstream engine code. Remove the final .txt extension before running/applying them.

documentbot-fts-pagination-repro.cjs.txt
documentbot-lance-9.0.0-ordering.patch.txt

Steps to reproduce

1. Install @lancedb/lancedb@0.38.0 in an isolated folder (repeat with 0.39.0-beta.6).
2. Download the attached documentbot-fts-pagination-repro.cjs.txt and rename it to repro.cjs in that folder.
3. Unset NAPI_RS_NATIVE_LIBRARY_PATH so the stock published binding is used.
4. Run:

LANCE_FTS_FORMAT_VERSION=1 node repro.cjs "$PWD/node_modules/@lancedb/lancedb"
LANCE_FTS_FORMAT_VERSION=3 node repro.cjs "$PWD/node_modules/@lancedb/lancedb"

The script creates and removes only its own synthetic temporary datasets. It reports missing, duplicate and order-mismatch counts for flat/indexed/mixed storage and page sizes 7/10/65, and exits nonzero on a failure.

Expected behavior

On a fixed dataset version, pages should preserve descending relevance and enumerate every matching row exactly once. A consistent secondary key, such as ascending real row ID/address, must apply before every top-K pruning/merge boundary. The 180-row fixture should yield 180 unique rows, zero omissions, and zero duplicates for every page size.

Lance version

Published Node @lancedb/lancedb 0.38.0 and 0.39.0-beta.6; experimental repair targets Lance 9.0.0 / LanceDB 0.33.0

Language binding

Other / not sure

Environment

macOS arm64; Node v22.22.0; local temporary filesystem; synthetic scalar text; stock bindings for reproduction; FTS formats 1 and 3

Logs / traceback

Representative output from the standalone probe (published 0.38.0 and 0.39.0-beta.6, FTS formats 1 and 3):

{"layout":"indexed","pageSize":10,"returned":180,"unique":91,"missing":89,"duplicate":89}

Local patched 0.33 binding, same fixture/page size:
{"layout":"indexed","pageSize":10,"returned":180,"unique":180,"missing":0,"duplicate":0,"orderMismatches":0}

The attached script emits the complete matrix as JSON.