#32 Make saves incremental: cost proportional to the change, not the timeline
–
- github
- github/openchronology/timeline-app
- github/openchronology/timeline-app#32
- issue
- state:closed
## Problem The benchmarks from #27 show that saving one moment costs time proportional to the **whole timeline's** size on both persistent backends: | Save one moment (create/update/delete) | 1k | 10k | 100k | |---|--:|--:|--:| | PostgreSQL | 180 ms | 1.6 s | 18.5 s | | SQLite (desktop) | 12 ms | 97 ms | 1.2 s | | In-memory (browser) | 0.1 ms | 0.1 ms | 0.2 ms | At 100k moments, server-side editing is not interactive. The in-memory index already does O(log n) updates with a persistent augmented AVL tree from `rational-ordered-map`, so this cost comes from how the persistent stores save, not from the data model. The cost is per timeline. Saving a 1k timeline took 187 ms alone and 179 ms with two 100k timelines in the same database; every statement in the save path is scoped by `timeline_id`. ## Where the time goes (PostgreSQL, one title update at 10k moments, 1.82 s) `PostgresStore.save` turns every sparse patch into a full document replacement: | Step | Time | |---|--:| | `branchDocument`: read every moment, duration and relationship back out | ~290 ms | | JS: apply the patch, re-validate the whole document, rebuild all trees and search text | ~580 ms | | Delete and re-insert every `oc_entity_search` row | ~300 ms | | Delete and re-insert every `oc_nodes` row | ~200 ms | | Rewrite `oc_duration_nodes`, `oc_edge_nodes` and `oc_relationships` | ~90 ms | | Update `oc_timelines` (whole-timeline `event_text`) | ~100 ms | | Store a full JSON snapshot in `oc_snapshots` for the revision | ~150 ms | Revision history also stores a **full copy of the document per save** (about 1.7 MB per save at 10k moments), so storage grows by the timeline's size on every edit. ### Why the time tree can't be updated in place `server/tree.mjs` (`indexedNodes`) builds a **static, perfectly balanced augmented binary search tree** from the sorted distinct times. It is not a B-tree. Node IDs are in-order positions (`mid + 1`), so inserting or deleting one distinct time shifts the ID of every later node, and the only way to update it is to rebuild it. Each node also carries its moments' full metadata (`oc_nodes.events` jsonb), so even a title edit changes a node row. The duration and arc interval trees (`durationTree` / `edgeTree`) are static in the same way. SQLite keeps moments in their own `events` table (SQLite's native B-tree on time), but `save_patch` stages a full copy of the file, and `duration_intervals` uses positional `ord`. ## Proposal 1. **Separate entities from the index.** Store moments (and durations) in their own rows keyed by `(timeline_id, id)`, with time and metadata. Tree nodes reference times and counts, not metadata; overview samples are looked up by ID. Then: - a **metadata-only edit** (time unchanged) updates one entity row and that entity's search row, and touches no tree node; - a **time change** is a delete plus an insert in the tree. 2. **Make the persisted time tree self-balancing, with stable node IDs.** Store an augmented AVL tree in rows, matching the client's `RationalMap` so summaries agree. A red-black tree, or a B+-tree with augmented counts per page (fewer rows per path), would also work. The essential change is from a positional, rebuilt-from-scratch tree to one where insert and delete rewrite only the O(log n) nodes on the path, plus rotations, updating `first`/`last`/`count`/`distinct` on the way up. The existing `oc_overview_v2` traversal over cached subtree summaries keeps working. 3. **Apply the same approach to the interval trees.** Durations and arcs need an augmented interval tree with O(log n) insert and delete, e.g. a balanced tree keyed by start, with max end and the short-span summaries per subtree. 4. **Apply patches without materializing the document.** Validate only the changed entities and their references (relationship endpoints, anchored duration endpoints). Update `oc_entity_search` and `oc_relationships` row by row. Maintain `event_text` and `storage_bytes` incrementally, or derive ……
Related
Open #32 Make saves incremental: cost proportional to the change, not the timeline in the timeline