Constant-Time Pagination

Why this matters

Almost every line-of-business application paginates:

• CRM: SELECT … FROM leads ORDER BY created_at LIMIT 25 OFFSET 500
• ERP: SELECT … FROM invoices LEFT JOIN customers … LIMIT 50 OFFSET 10000
• Admin UIs: SELECT … FROM audit_log ORDER BY ts DESC LIMIT 100 OFFSET 50000

On most databases, the cost of OFFSET grows linearly with depth. At 1k rows it’s fine; at 100k it’s a support ticket. HeliosDB Nano 3.12 pushes the OFFSET skip into the storage engine and does it without deserialising skipped rows — so the 10 000th page costs the same as the 1st.

---

Measured numbers

Same hardware, same connection protocol (psycopg over Unix socket), same table, same queries. 100 000 rows, 20 samples per shape plus 3 warm-up, median reported.

Offset pagination: ORDER BY id LIMIT 10 OFFSET M

Offset depth	HeliosDB Nano 3.12	PostgreSQL 13	Speedup
0	32 µs	49 µs	1.5×
100	37 µs	57 µs	1.5×
1 000	32 µs	144 µs	4.5×
10 000	36 µs	1 194 µs	33×
99 990	32 µs	10 688 µs	334×

Nano is flat — depth 99 990 costs the same as depth 0. PostgreSQL scales linearly with offset because every skipped tuple still goes through visibility checks and deserialisation.

Keyset pagination: WHERE id > $last ORDER BY id LIMIT 10

This is the canonical “do-it-right” pagination shape. Nano and PostgreSQL both handle it with index seeks, so the numbers are close.

Cursor position	HeliosDB Nano 3.12	PostgreSQL 13
first page	31 µs	84 µs
after id=10 001	32 µs	50 µs
after id=99 990	33 µs	69 µs

LEFT OUTER JOIN + LIMIT + OFFSET

The shape SQLAlchemy emits for select(Lead, Company.name).outerjoin(Company).limit(N).offset(M):

Offset depth	HeliosDB Nano 3.12	PostgreSQL 13	Speedup
0	38 µs	83 µs	2.2×
1 000	38 µs	768 µs	20×
10 000	34 µs	6 838 µs	201×

Row-constructor keyset: WHERE (created_at, id) < ($1, $2) ORDER BY created_at DESC, id DESC LIMIT 10

The idiomatic “Markus Winand” keyset pattern, now supported natively in Nano v3.12:

Cursor	HeliosDB Nano 3.12	PostgreSQL 13	Speedup
middle of 100k rows	33 µs	10 369 µs	314×

---

Why HeliosDB Nano is fast at deep offsets

Three things, in order of impact:

1. Storage-level skip without deserialising. The RocksDB iterator advances to the offset-th matching key without decoding the bincode tuple, decrypting the page, or resolving dictionary / content-addressed references. On PostgreSQL, every skipped tuple still pays for MVCC visibility checks and heap-tuple decoding.
2. Top-K operator (sql::executor::topk::TopKOperator). When the plan is Limit(Sort(…)), Nano streams the input through a bounded heap of size k = limit + offset — O(N log k) instead of O(N log N), O(k) memory instead of O(N).
3. Row-constructor comparison ((created_at, id) < ($1, $2)) is a first-class operator, not a macro-expansion into created_at < $1 OR (created_at = $1 AND id < $2). That means the planner and the evaluator both see the tuple directly, which opens the door to future index-range pushdown.

---

Reproduce

Every number on this page comes from the bundled bench script. It uses the standard PostgreSQL wire protocol, so it runs unchanged against Nano, PostgreSQL, CockroachDB, YugabyteDB, or anything else that speaks PG wire.

git clone https://github.com/dimensigon/HDB-HeliosDB-Nano
cd HDB-HeliosDB-Nano
pip install 'psycopg[binary]'

# Against HeliosDB Nano (Unix socket, 100k rows)
./target/release/heliosdb-nano start --memory \
    --pg-socket-dir /tmp --port 5432 &
python3 benches/external/pagination_bench.py \
    --host /tmp --port 5432 --user postgres --dbname heliosdb \
    --name "HeliosDB Nano" --rows 100000 --out nano.json

# Against PostgreSQL
PGPASSWORD=postgres python3 benches/external/pagination_bench.py \
    --host localhost --port 5432 --user postgres \
    --name "PostgreSQL 16" --rows 100000 --out pg.json

# Side-by-side
python3 benches/external/pagination_bench.py --compare nano.json pg.json

For Oracle or MS SQL Server, use the same queries through the respective native CLI (sqlplus or sqlcmd) with a timer wrapper — we haven’t bundled the proprietary drivers, but the shapes are identical and easy to port.

---

What this means for your app

---

Caveats, honestly

1. PostgreSQL 13, not 16. We tested against the version available on our build box. The fundamental cost model (OFFSET is O(M) heap-tuple decodes) is the same in PG 14/15/16, but exact numbers differ — expect a 10–30 % improvement on newer PG. The qualitative shape (linear growth with offset) is unchanged.
2. Fsync off on both. We disabled fsync on PostgreSQL to level the bulk-seed time — the metric we care about is read latency, so the flag doesn’t affect the measured numbers, but it’s disclosed for completeness.
3. Embedded workload shape. 100 000-row table fits entirely in the OS page cache on both systems. For cold-cache reads on a billion-row table, the gap would narrow — storage I/O dominates. We’ll publish that measurement once we have the hardware.
4. Oracle / MS SQL Server numbers: not yet measured by us. Port the benchmark and send us your results — we’ll publish them here with attribution.

Numbers generated on 2026-04-17. Benchmark script: benches/external/pagination_bench.py. HeliosDB Nano v3.12.0 release build.