Skip to content

Query Performance as a Sorting Problem — Research Spike

Date: 2026-07-22 Method: deep-research harness — 5 search angles, 20 sources fetched, 86 claims extracted, 25 adversarially verified (3-vote refute-to-kill). 24 confirmed, 1 refuted, 0 unverified. Question: How to make PhonoLex's constraint-based lexical/phonological search fast on Cloudflare Workers + D1, reframed as a sorting/ranking problem rather than top-N retrieval, with the hard requirement that no matching word is ever unreachable due to result limits. Feeds: docs/superpowers/specs/2026-07-22-query-performance-audit-design.md (§3–§4); PHON-203.

Verdict

Reframing as "rank the whole matching set and page through it, never truncate" maps cleanly onto proven D1/edge-SQLite patterns. The single highest-leverage change is keyset (seek) pagination over a deterministic total order (rank, id) — O(1) in page depth, insert/delete immune, and every matching row reachable by paging forward. Speed comes from precomputed rank/sort-key columns + composite indexes ordered by the leftmost-prefix rule. Full reachability is a policy choice (never set a total cap), not an engine limit. Most of the win is query-and-index shape; keyset + indexing is query-only, precomputed rank columns + generated/expression indexes need a schema + reseed.

Verified findings (confidence, vote, sources)

  1. Keyset/seek pagination — not OFFSET/LIMIT — satisfies "sorting not retrieval, never truncate." A WHERE clause carries the last-seen sort value to index-seek the next page, over a deterministic total order made by appending a unique monotonic tiebreaker (id) to ORDER BY. (high; unanimous 3-0). Sources: codestudy.net (SQLite paging), medium/@annxsa (keyset+filters+sort), stacksync.com. Corroborated: Markus Winand (use-the-index-luke.com), GitLab, Cybertec, jOOQ, Vlad Mihalcea.

  2. OFFSET/LIMIT degrades O(n) with depth in SQLite (scans + discards all rows before the offset); keyset is depth-independent and immune to concurrent inserts/deletes (which shift OFFSET positions → silent skips/dupes). Directional deep-page figures (Postgres self-benchmarks, treat as magnitudes): OFFSET page 1 = 468µs vs page 50k = 87ms; a 5s→500ms case on million-row sets. (high; 3-0 except the benchmark figure 2-1). Sources: codestudy.net, stacksync.com, caduh.com.

  3. D1 composite indexes need leftmost-prefix ordering. "Queries only use the index if they specify all the columns, or a subset provided all columns to the left are also in the query." So put equality-filter columns first, sort/rank column last. Skip-scan is a narrow exception, never applied on a freshly-seeded (un-ANALYZEd) DB. (high; 3-0). Source: developers.cloudflare.com/d1/best-practices/use-indexes.

  4. Full reachability is a policy choice, not an engine limit. Typesense limit_hits defaults to no limit (page the whole ordered set; only per_page ≤250 bounds page size; no max page number). Meilisearch maxTotalHits (default 1000) is a hard ceiling — "not possible to see the 1001st result," offsets past it return empty. → Meet "no word unreachable" by never configuring such a cap. (high; 3-0). Sources: typesense.org, meilisearch.com.

  5. Design UI around forward cursor paging, not "page N of M." Meilisearch itself recommends Previous/Next because "calculating the exhaustive number of documents matching a query is resource-intensive" and worsens as the cap grows — matching keyset's forward-only nature. (high; 3-0). Source: meilisearch.com.

  6. Precompute-and-index expensive generation (e.g. contrastive minimal-pair enumeration) rather than per-query. PhonoLex already materializes the 642K pairs table correctly; the fix is to add rank/sort-key columns + composite indexes and keyset-page, not enumerate per query. (medium; inference from claims 3–5). Sources: cloudflare d1 indexes, typesense, meilisearch.

  7. D1 read replication is real but Sessions-API-only, and cuts proximity — not query cost. "To use read replication you must use the D1 Sessions API, otherwise all queries execute only on the primary." Static replicas in every D1 region at no extra cost; auto-routed; sequential consistency via x-d1-bookmark. Addresses the ~0.15s network floor, NOT the 0.8–3.7s execution cost; requires a Worker code change. (high; 3-0). Sources: cloudflare d1 read-replication docs + beta blog + storage-options.

  8. KV as a cache for precomputed pages: hot reads <5ms (third-party p50 ~2.6ms), orders of magnitude below D1's seconds; even cold KV (30–200ms) beats D1. Hot-path only under eventual consistency; goes stale on reseed → suits popular/stable pages, not arbitrary deep cursors. (high; 3-0). Source: cloudflare.com/products/kv.

  9. SQLite-in-Durable-Objects: synchronous in-thread reads, no per-query network round-trip → N+1 / many-simple-queries performs like a single join (relevant to the chunked word-enrichment). But it does NOT eliminate the ~0.15s floor for a Worker calling into a DO (that stronger claim was REFUTED 0-3). Effort-heavy option with single-writer/geo-pinning tradeoffs. (high; 3-0, with the over-claim refuted). Sources: cloudflare sqlite-in-DO blog, storage-options.

  10. Recommended architecture (synthesis, medium): precompute stable rank/sort-key columns per surface; composite covering indexes (equality-filter cols then rank col) on words/pairs/norm/corpus tables; replace OFFSET/LIMIT with keyset over (rank, id); never set a total-reachability cap; cache popular first pages in KV; adopt the Sessions API for global proximity. Migration split: keyset + adding indexes = query-only/DDL (no reseed); precomputed rank columns + generated/expression indexes = schema change + D1 reseed.

Refuted (killed by adversarial verification)

  • ✗ "SQLite-in-Durable-Objects eliminates the ~0.15s network floor that D1 pays" — 0-3. A Worker still reaches a DO over the network; DOs add single-writer + geographic-pinning tradeoffs. Treat SQLite-in-DO as an effort-heavy option for the N+1 enrichment, not a drop-in speedup.

Open questions (what the research explicitly cannot answer)

  1. Latency breakdown: what fraction of the 0.8–3.7s is D1 query-execution vs the N+1 word-enrichment round-trips vs the ~0.15s floor? The right fix (indexes vs join/denormalize vs Sessions API vs SQLite-in-DO) depends on this → needs EXPLAIN QUERY PLAN + timing decomposition (spec §3.2).
  2. Index budget: for the ~160 norm columns across 4 tables, how many composite (filter, rank) indexes cover the real constraint combinations without bloating write/reseed time or hitting D1's index/storage limits?
  3. Phoneme filter shape: can phonemes_str LIKE '|ɹ|%' be reshaped into an index-usable form (precomputed position column / generated column / FTS5) — in-place expression index or reseed?
  4. Computed-rank keyset (the real wrinkle): does keyset stay sound when the ranking key is query-time-computed (sentence retrieval ranks by per-query match_count)? If the sort key isn't materialized per row, the seek predicate isn't expressible → may force a precomputed global rank or a bounded-window fallback.

Caveats

  • Keyset-vs-OFFSET perf claims lean partly on blog sources, but the behavior is textbook consensus (Winand, GitLab, Cybertec, jOOQ) → high confidence despite weak citations.
  • The deep-page numbers are single-vendor Postgres self-benchmarks (the only 2-1 split) — directional, not D1/edge-SQLite measurements; trust magnitudes, not exact figures.
  • D1 read replication is a 2025 open-beta feature; the Sessions API is a code change, and it reduces proximity latency, not execution cost.
  • Faceted-engine reachability caps are current-version behaviors (older GitHub complaints reference pre-2022 defaults).
  • KV <5ms is hot-path only under eventual consistency; stale on reseed.
  • The concrete PhonoLex column-level mapping is synthesized inference, not benchmarked on this codebase — validate with the harness (§3.1) and EXPLAIN (§3.2).

Primary sources

  • Cloudflare D1 — Use indexes: https://developers.cloudflare.com/d1/best-practices/use-indexes/
  • Cloudflare D1 — Read replication: https://developers.cloudflare.com/d1/best-practices/read-replication/ ; beta blog: https://blog.cloudflare.com/d1-read-replication-beta/
  • Cloudflare — SQLite in Durable Objects: https://blog.cloudflare.com/sqlite-in-durable-objects/
  • Cloudflare — Storage options: https://developers.cloudflare.com/workers/platform/storage-options/ ; KV: https://www.cloudflare.com/products/kv/
  • Typesense search API (limit_hits): https://typesense.org/docs/30.2/api/search.html
  • Meilisearch pagination (maxTotalHits): https://meilisearch.com/docs/guides/front_end/pagination
  • Keyset/SQLite paging: https://www.codestudy.net/blog/efficient-paging-in-sqlite-with-millions-of-records/ ; https://www.stacksync.com/blog/keyset-cursors-postgres-pagination-fast-accurate-scalable ; https://kenwagatsuma.com/blog/blog-pagination-cloudflare-d1