How OpenChronology was built

#36 · Make viewport queries scale with what is shown, not the timeline

2026-10-09T11:14:42Z CE

• timeline-app
• pull request

Fixes #35. ## Results (`npm run bench`, means at 100,000 moments) | Viewport | SQLite before → now | PostgreSQL before → now | In-memory before → now | |---|--:|--:|--:| | Whole timeline | 945 ms → **31 ms** | 99 ms → 101 ms | 310 → 292 ms (p50 50 ms) | | 1% of the timeline | 430 ms → **14 ms** | 49 ms → **12 ms** | 34 ms → **8.4 ms** | The acceptance targets are met: SQLite under 50 ms for the whole timeline and under 15 ms for a 1% window. Saves are unchanged: SQLite 2.1–2.6 ms, PostgreSQL 4.8–5.3 ms, flat from 1k to 100k. ## Changes 1. **SQLite summaries, set-based** (`duration_summaries`). - One recursive statement over a new index on `duration_intervals(first)`. - Each cluster's anchor is the first collapsed start at or after the previous anchor plus the threshold; count, latest end and the single band are aggregated per anchor. - Cost follows the durations starting in `[lower − T, upper]` and the number of clusters. At 100k: 932 ms → 15 ms whole, 393 ms → 0.6 ms for a 1% window. 2. **Start-range pruning on every backend.** A collapsed duration that reaches the window starts after `lower − T`, so the walk skips subtrees whose starts all fall at or before that. This is one added check in each of `durationSummaries` (browser), `oc_duration_overview` (PostgreSQL), and the generated view variant. 3. **SQLite bands and arcs.** The old recursive query found every match before `LIMIT 257` applied: 3,847 bands at whole-timeline zoom, with `LIMIT 1` still taking 17 ms. The new walk goes through the tree in start order using SQLite's ordered recursion queue and stops at the 257th match: 18–24 ms → 3–4 ms. - As agreed, results now come back in **start order** (as the browser lists them), so a band's row (`i % 3`) can differ from before. - Past 256 bands, the first 257 in start order are shown. The old subset depended on the query plan and on node IDs, which change with every save. ## Old-versus-new equivalence tests Each optimized method is compared with the previous implementation, which is kept verbatim (in tests or behind `#[cfg(test)]`): | Test | Previous method kept | Coverage | |---|---|---| | `summary_equivalence_tests::set_based_summaries_match_the_tree_walk` (Rust) | `duration_summaries_walk` (the old SQLite tree walk) | 504 windows over 12 random timelines, more than 1,000 clusters; identical `first`, `last`, count and band | | `test/summaries-equivalence.test.mjs` | `previousSummaries` (the old browser traversal, copied) | 1,000 windows over 20 random trees, more than 2,000 clusters; `deepEqual` | | `test/summaries-equivalence-postgres.mjs` (added to CI) | `pg_temp.oc_duration_overview_previous` (the old function, copied) | 320 windows over 8 timelines, more than 2,000 clusters; identical rows | | `summary_equivalence_tests::band_and_arc_windows_match_the_recursive_query` (Rust) | `interval_window_query` (the old recursive query) | 504 band and arc windows on dense timelines, more than 20 of them truncated | - In the band and arc test, results must equal a brute-force scan of every interval in (start, ID) order, truncation included. When the old query wasn't truncated, its rows must also be the same set. - The random data covers: - coincident starts and grid times; - negative times and rationals with huge components; - durations anchored to moments and long durations mixed with short ones; - window edges and thresholds taken from stored starts, ends and extents. - Later rounds reshape the trees through incremental saves first. - Each suite was checked against a deliberate bug: - an off-by-one cluster boundary in the SQLite summaries; - pruning without `− T` in the browser and in PostgreSQL; - removing the ordered queue in the band and arc walk. All three suites fail on their bug. - Existing tests also pass: the brute-force `native_summaries_match_a_brute_force_reference`, the PostgreSQL summary/duration/view suites, 180 JS unit tests and 23 native tests. ## Not included PostgreSQL's whole-timeline view is unchanged (101…

Open #36 · Make viewport queries scale with what is shown, not the timeline in the timeline