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

Open
#1,822 0 comments 0 reactions 0 assignees View on GitHub
bug
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.