How OpenChronology was built

#34 · Save desktop SQLite timelines incrementally and in place

2026-10-09T05:55:26Z CE

• timeline-app
• pull request
• packages

Fixes #32 (the SQLite half; PostgreSQL landed in #33). ## Results (`cargo bench --bench backends`, saving to the open file as the desktop app does) | Save one moment (create/update/delete) | 1k | 10k | 100k | |---|--:|--:|--:| | SQLite before | 12.7 ms | 105 ms | 1.24 s | | **SQLite now** | **2.1 ms** | **2.3 ms** | **2.6 ms** | Reads are unchanged. ## What changed **Interval trees** (`native-store/src/intervals.rs`) - Durations and relationship arcs are now persistent AVL trees. - An interval row and its node share a stable ID (`ord`); nodes gain a `height`, and roots live in `interval_roots`. - Inserts and removals rewrite only the nodes on their path, plus rotations, and recompute the summaries the window and summary queries prune with. Removing a node with two children moves the successor's interval row into it. - A full balanced build, as used by `save()` and older files, is a valid AVL tree, so incremental saves continue from it. - The readers take the root from `interval_roots` instead of computing the midpoint of the row count. **Patch application** (`apply` in `workspace.rs`) - Moment changes keep the per-time updates to the `points` index. - The full rebuilds of both interval indexes are replaced by per-interval updates: - changed durations, and durations anchored to moved or deleted moments (new `durations_start_moment`/`_end_moment` indexes), are placed again; - links of deleted entities are removed; - the patch's link changes apply with the last change winning, and links to missing entities are dropped, as the rebuild did; - arcs of touched links, including links of moved entities, are removed and placed again. **No copies on save** - Each file records its index layout and a save token (`index_layout`). - When the save target holds exactly the baseline's saved state (same token, valid timeline, no triggers), the patch applies in one transaction to the file, then to the baseline in place. - If the file transaction fails, nothing changes. - If the baseline step fails afterwards, a fresh baseline is opened from the saved file. - Otherwise (Save As, or the first save of a file from an older version, whose indexes get rebuilt on open) the old path runs once: a patched copy of the baseline is backed up over the target. - After an in-place save, the old baseline handle sees the new state. The desktop app already discards it and rejects queries carrying an old generation; the affected test now asserts this. - Files saved with the current layout open without rebuilding their indexes. ## Testing - New `random_sparse_saves_match_a_model_and_a_rebuild`: 80 random patches saved in place. They cover moves onto shared times, deletions with anchored durations, duration edits and deletions, and link adds and removes. - After every step, the file and the baseline must equal a model of the document. That includes durations pinned to deleted moments' last times and links dropped with their entities. The test asserts every save went in place. - Every 10 steps, both interval trees in both copies are checked (AVL balance, key order, every recomputed summary, root, no orphans), and the overview (four thresholds), duration pages, event pages and search must equal a snapshot rebuilt from the saved document. - I checked the test catches a deliberately broken subtree count. - All 21 native-store tests, `cargo fmt` and clippy (no new warnings), the desktop crate's check and tests, `test/files.mjs` (SQLite conversion over HTTP) and the JS unit tests pass. Not in scope: SQLite viewport queries still grow with the number of summaries drawn (about 1 s for the whole-timeline view at 100k), as before this change.

Open #34 · Save desktop SQLite timelines incrementally and in place in the timeline