HarperFast / HarperFast/rocksdb-js
Optional: bound exactStart absent-timestamp lookups with a suffix-minimum index
- Dominant language
- C++
- Stars
- 21
- Forks
- 2
- Avg merge
- 2d 9h
- Merged PRs (30d)
- 36
Description
## Summary
`TransactionLog.prototype.query({ start, exactStart: true })` has **no upper bound** on its
forward scan. When the requested `start` timestamp is **absent** from the log, the iterator
scans from the computed start position all the way to **end-of-log** (continuing across log
files) before returning `done`, even though it can never match. On a large or multi-segment
log this turns a point lookup into an O(n) scan (multi-millisecond).
This is a **missing capability, not a correctness bug** — results are always correct. Filing as
a tracked, optional enhancement.
## Background — why the current index can't bound it
`findPositionByTimestamp` (`src/binding/transaction_log/transaction_log_file.cpp`) builds a
**running-maxima** index: it records an entry only when its timestamp exceeds the current max,
then answers with `lower_bound(t)`. That gives a correct, tight **lower bound to START a scan**
— "before the returned position, no entry has timestamp ≥ t" — which is exactly what
`query()`/`next()` relies on, in both normal and `exactStart` modes. It does **not** provide any
*upper* bound, so the scan has no stop condition and runs to EOF.
Position-derived stop heuristics (e.g. "stop at the next maxima position", "stop at
`nextUp(start)`") are **not safe**: on an out-of-order log a present `=== start` entry can sit
physically *after* such a position, so those bounds produce false negatives and break the
existing `should query an out-of-order transaction log` and
`keeps every committed entry findable … (#1148)` (HarperFast/harper#1148) tests.
## Proposed option — a suffix-minimum ("min remaining timestamp") structure
Maintain, alongside the maxima index, the minimum timestamp over the *remaining* (suffix)
entries. A forward scan can then **terminate as soon as `min(remaining) > start`** — at that
point no `=== start` entry can remain. (The same stop generalizes range queries: a `[start,
end)` scan can stop once `min(remaining) >= end`.)
- **(a) Correctness under arbitrary disorder:** safe. The stop is value-based, not
position-based, so an out-of-order match always keeps `min(remaining) <= start` until it is
read — no false negatives. Keeps the out-of-order and #1148 tests green (for a present `t`,
at `t`'s position `min(remaining) <= t`, so it cannot stop early).
- **(b) Tightness:** tight for mostly-increasing logs (the min sits near the front, so
`suffix-min` rises immediately past `start`). **Adversarial worst case:** a single small
timestamp near the *tail* keeps `suffix-min` low until that entry, forcing a near-full scan.
So it bounds the worst case but does not eliminate it.
- **(c) Maintenance — amortized O(1):** store the suffix-minimum **breakpoints** (positions ≤
everything after them) as a **monotonic stack** keyed by increasing timestamp → position,
folded into the existing lazy forward-indexing loop:
```
while (stack.top().ts >= ts) stack.pop(); // no longer suffix-minima
stack.push({ts, pos}); // ts is a suffix-min (nothing after it yet)
```
A new global-min pops the stack and pushes one entry — O(k) for that step, total pops ≤ total
pushes ⇒ **amortized O(1)** per indexed entry. Stop lookup is `upper_bound(start)` on the
stack ⇒ O(log n). (Per-position suffix-min arrays would be O(n)/append — avoid those. A
min-segment-tree is an alternative but strictly more code for no asymptotic win here.)
- **(d) Memory:** suffix-min size ≈ #right-to-left minima; for mostly-increasing analytics logs
that's ≈ O(n), roughly **doubling** the (already-O(n)) maxima index. Negligible for
decreasing/short logs.
## Recommendation
Track, don't pre-build. The motivating hot caller (an audit-dedup exact lookup) is being
removed upstream by a separate change, after which this is a **large-log-only, low-frequency**
residual cost. Build the suffix-min stop only if profiling still shows hot absent-key
`exactStart` lookups after that lands.
A bounded-disorder-window alternative (scan a fixed `W` past the natural stop) is cheaper but
only correct if maximum reordering is an *enforced* invariant — it is not today
(`txn.setTimestamp` accepts any value), so it would reintroduce the false-negative class above.
_Filed from an investigation into the maxima-vs-suffix index semantics; the function docstring
fix is a separate, already-open PR. Analysis generated with assistance from Claude (Opus 4.8)._
Contributor guide
Research direction
Start in src/binding/transaction_log/transaction_log_file.cpp, reading findPositionByTimestamp and the query()/next() scan path. Review the out-of-order transaction-log tests and the #1148 findability test before considering the proposed suffix-minimum structure. Done means profiling confirms the optimization is still needed and any bound preserves correct absent and present exactStart lookups.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp, node.js
- Domain
- backend, databases, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100