HarperFast / HarperFast/harper
SQL two-sided primary-key range full-scans instead of range-seeking (O(table) not O(window)) — confirmed on legacy AND sql-engine-v2
- Dominant language
- JavaScript
- Stars
- 89
- Forks
- 10
- Avg merge
- 2d 6h
- Merged PRs (30d)
- 200
Description
## Summary
A SQL query with a two-sided primary-key range predicate (`WHERE id >= a AND id < b`, or `BETWEEN`) reads **O(total-table)** instead of **O(window)** — even though the underlying store range-seeks that same PK trivially. Confirmed on both the legacy AlaSQL-based engine and the in-progress `sql-engine-v2` rewrite (forced `HARPER_SQL_ENGINE=new`), so this isn't fixed by the ongoing cutover.
Correctness is unaffected — this is a pure performance defect, but a severe one for SQL users doing keyset/range pagination or time-id-range scans on large tables.
## Reproduction
Fixed table with a numeric PK. Seed a small fixed PK window (`id ∈ [0, 500)`, 500 rows) once, then grow the table by appending only *higher* ids (20k → 60k → 180k, 9× growth). At every scale, the window itself never changes — same 500 rows should be returned by `WHERE id >= 0 AND id < 500`.
3-path bare-PK-range benchmark (ms/iter, all correctly returning exactly 500 rows):
| N | SQL | ops `search_by_conditions` (between) | direct `primaryStore.getRange` |
|---|---|---|---|
| 20,000 | 55–65ms | 6–8ms | 2–2.5ms |
| 60,000 | 169–207ms | 6–12ms | 1.8–2.7ms |
| 180,000 | 530–638ms | 5.6–24ms | 1.4–1.6ms |
| **growth (9× table)** | **~8.5–9.9×** | **flat (~1×)** | **flat (~0.6×)** |
SQL scales almost linearly with total table size; the ops-API path and a direct storage range read both stay flat for the identical bounded window — proving the PK is cheaply range-seekable and only the SQL path fails to exploit it.
**Verified on `sql-engine-v2` too** (branch HEAD `e8ed30a46`): default `auto` mode shows the same ~9.65× growth; forcing `HARPER_SQL_ENGINE=new` (no legacy fallback) still serves the query correctly but at ~8.48× growth — so the new engine doesn't fuse two-sided PK bounds into a single range-seek either.
Repro test: `integrationTests/qa-scratch/qa558-sql-planner-overscan.test.ts` (harper `182971ad1`).
(Side note found while probing: SQL `EXPLAIN SELECT ...` is unsupported — returns HTTP 500 `"unsupported SQL type explain"` — so there's no query-plan visibility from SQL itself; the resource engine's `search({explain:true})` is the only plan-inspection path.)
## Root cause
`dataLayer/SQLSearch.ts`:
- `_conditionsToFetchAttributeValues` (~L218) splits a two-sided PK predicate into two *independent* single-sided comparators instead of fusing them into one bounded range.
- `_getFetchAttributeValues` (~L549) then issues one range read **per bound** and unions the results — so `id >= a` alone (`resources/search.ts` `ge` → `start=a, end=undefined`) streams from `a` to the end of the table, filtering in memory, before the union/intersection ever narrows it back down.
By contrast, the ops-API `between` path (also in `resources/search.ts`) sets **both** `start` and `end` up front, producing a single bounded `getRange` call — which is why it stays flat. `SQLSearch` never uses the two-bound fusion that `Table.ts`'s `prepareConditions` relies on for the ops path.
## Impact
Any SQL query with a two-sided PK range on a large table pays O(table) latency regardless of how narrow the requested window is — a real footgun for SQL-based keyset pagination, time-id-range scans, or any bounded scan over a big table. Workaround: use the ops/resource API (`search_by_conditions` with a `between` condition) or a direct `getRange`, which are both correctly bounded.
## Suggested fix
Fuse two-sided PK-range predicates (both `>=`/`>` and `<`/`<=` on the same attribute) into a single bounded range read before issuing the storage query, the same way the ops path's `prepareConditions` does — in both `SQLSearch.ts` (legacy) and wherever `sql-engine-v2`'s planner resolves PK-range predicates to a storage read.
---
*Found by exploratory QA (qa-explorer). Severity: medium — perf-only, both storage engines correct underneath, but a real regression for large-table SQL range queries. Verified NOT fixed by sql-engine-v2 as of e8ed30a46.*
Contributor guide
Research direction
Start with dataLayer/SQLSearch.ts, especially _conditionsToFetchAttributeValues and _getFetchAttributeValues, then compare their behavior with resources/search.ts and Table.ts's prepareConditions. Run integrationTests/qa-scratch/qa558-sql-planner-overscan.test.ts in both legacy and HARPER_SQL_ENGINE=new modes; done means bounded primary-key ranges use one storage range read and no longer scale with total table size.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- javascript, sql
- Domain
- databases, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Clearly specified
- Newbie friendliness
- 52/100