How OpenChronology was built

#33 · Save PostgreSQL timelines incrementally with persistent AVL indexes

2026-10-09T05:18:40Z CE

• timeline-app
• pull request

Part of #32: the PostgreSQL half. SQLite follows in a separate PR, as agreed. ## Results (`npm run bench`, local, means) | Save one moment (create/update/delete) | 1k | 10k | 100k | |---|--:|--:|--:| | PostgreSQL before | 180 ms | 1.6 s | 18.5 s | | **PostgreSQL now** | **4.4 ms** | **5.0 ms** | **4.6 ms** | At 100k moments, 300 consecutive saves measured p50 5.7 ms, p90 6.7 ms and p99 15 ms. The exception is the periodic full history snapshot described below, which takes about 2 s at that size. | PostgreSQL viewport, whole timeline | 1k | 10k | 100k | |---|--:|--:|--:| | before | 61 ms | 95 ms | 331 ms | | now | 7.0 ms | 21 ms | 99 ms | Reads are unchanged or faster (one moment: 5.4 ms → 0.7 ms at 100k). ## What changed - **Moments have their own rows** (`oc_moments`). Tree nodes hold one distinct time, its moment IDs and subtree summaries. A metadata-only edit updates one moment row and one search row, and writes **no tree rows**; the test checks this through row versions. - **The moment, duration and arc trees are persistent AVL trees** with stable node IDs and a height column (`server/avl.mjs`). An insert or delete loads the paths it needs in one query, rewrites only the nodes on them (plus rotations), and recomputes summaries from children. The SQL traversal functions were unchanged apart from root lookups and reading moments by key. Overview results don't depend on the tree's shape. - **Incremental patch application** (`server/incremental.mjs`) has the same semantics as `applyPatch` plus a rebuild: - durations anchored to moved or deleted moments move or keep their last time; - relationships cascade when an entity is deleted, and the last change to each link wins; - arcs of moved entities are placed again; - search rows change per entity; - the 200,000 limits are enforced from subtree counts. - **Large patches fall back to a full rebuild.** Patches larger than an eighth of the timeline, plugin changes, whole-document saves, merges, syncs and forks still rebuild the index. - **Delta revisions.** A save records its patch against the previous head. A full snapshot is written every 1,000 saves, or once patches outweigh the document. `revisionDocument` replays the chain in a single pass, and browser forks use it. Storage accounting charges patch bytes. - **Catalogue text is refreshed after the save commits**, as you chose: - It is built in the database (`oc_event_text`), with the expensive part outside any lock, and is rewritten only when it changes. - Saves in quick succession share one rebuild, and large timelines wait longer between rebuilds. - A stale flag survives restarts; the platform catches up on start. - Separation views of older revisions are pruned at the same time. ## Other fixes found along the way - **Overviews scanned every timeline's interval rows.** The band and arc recursive queries joined child nodes on `p.timeline_id`, not the timeline parameter, so each tree level hash-scanned every timeline's `oc_duration_nodes` and `oc_edge_nodes`. This partly answers your earlier question: viewport cost did depend on the rest of the database. - **Updates rewrote the catalogue index.** Setting `title` or `updated_at` on every save recomputed the catalogue `tsvector` (up to 1 MB) and forced a non-HOT update that inserted the whole vector into the GIN index. Saves now set those columns only when they change. `updated_at` advances at most once a minute while someone is editing, and `oc_timelines` uses `fillfactor=50`. - **`access()` no longer reads `event_text`/`search_document`** (about 1 MB each at 100k). - **Whole-timeline reads** (snapshot, export, fork) use an ordered scan of `oc_moments`: 0.2 s, compared with 2 s for the tree walk at 100k. - **Batch lookups use one primary-key probe per key.** They're robust to stale statistics on freshly imported timelines, which had produced full-timeline scans. ## Migration `npm run migrate`: - moves moments out of old nodes in SQL; - rebuilds every timeline's indexes once (`ind…

Open #33 · Save PostgreSQL timelines incrementally with persistent AVL indexes in the timeline