circagraph
Sign inSign up

openchronology/timeline-app on GitHub

The OpenChronology repository on GitHub, mirrored by och-import-github: issues and pull requests as durations (ongoing while open), what happened to them as moments, plus releases, milestones, commits and branches. The Branches view shows the most recently active branches each in a track of its own.

Source: https://github.com/openchronology/timeline-app

3,131 moments · 2026-10-05 CE 20:21:49 UTC – 2026-11-16 CE 12:10:45 UTC · by @athan · @athan

#35 Viewport queries scale with timeline size because of collapsed-duration summaries

–

  • github
  • github/openchronology/timeline-app
  • github/openchronology/timeline-app#35
  • issue
  • state:closed

## Problem Viewport (overview) queries on desktop `.och` files grow linearly with timeline size, even for a small window: | SQLite viewport (`npm run bench`) | 1k | 10k | 100k | |---|--:|--:|--:| | Whole timeline | 16 ms | 104 ms | 966 ms | | 1% of the timeline | 5 ms | 48 ms | 432 ms | PostgreSQL is better (99 ms / 49 ms at 100k) but has the same shape. ## Where the time goes (SQLite, 100k moments, 10k durations) Profiled per component of `Snapshot::query("overview")`: | Component | Whole timeline | 1% window | |---|--:|--:| | Moment groups (`points` rational index) | 4.7 ms | 2.8 ms | | Duration bands (`duration_window`) | 18 ms | 10 ms | | Relationship arcs (`edge_window`) | 23 ms | 17 ms | | **Collapsed-duration summaries (`duration_summaries`)** | **932 ms** | **393 ms** | The summaries visit **11,840 nodes for 10,000 durations** in the whole-timeline view, and **5,966** for a 1% window. Each visit is one SQL round trip from Rust, about 77 µs. Two things make the walk linear in the timeline's size: 1. **Pruning by end instead of start.** The walk skips a subtree only when every duration in it ends before the window (`max_time < lower`). Long durations push `max_time` past the window for almost every subtree to its left, so a 1% window still walks most of the tree. But a summarized duration is shorter than the threshold T. If it intersects the window, it must **start** in `[lower − T, upper]`. 2. **Long durations block whole-subtree consumption.** A subtree is folded into the current summary in one step only when *every* duration in it collapses (`max_extent = q_sub(:lower,:t) AND first <= :upper AND q_cmp(extent,:t) = 0 ORDER BY first LIMIT 1) UNION ALL SELECT (SELECT first FROM duration_intervals WHERE first >= q_add(a,:t) AND first <= :upper AND q_cmp(extent,:t) = 0 ORDER BY first LIMIT 1) FROM anchors WHERE a IS NOT NULL) SELECT a, max(last), count(*), ... -- per anchor, over first in [a, a + t) ``` A prototype against the 100k benchmark timeline returned **identical groups** (same count, first and last for every group) to the current walk: | Collapsed-duration summaries, 100k | Current walk | Set-based prototype | |---|--:|--:| | Whole timeline (42 groups) | 932 ms | **27 ms** | | 1% window (21 groups) | 393 ms | **0.7 ms** | **Cost:** one statement per query. Row scans are proportional to the durations starting in `[lower − T, upper]`, and steps to the number of groups, which the viewport's minimum threshold (span/1024) bounds at about 1,000. The tree's subtree summaries are not used. The index costs one B-tree entry per duration, which incremental saves maintain row by row. ### 2. All backends: prune by start range The summary walk can skip any subtree whose starts all fall outside `[lower − T, upper]`: `max_first ≤ lower − T` or `min_time > upper`. This makes narrow windows local in the browser and in PostgreSQL witho… https://github.com/openchronology/timeline-app/issues/35

Related

Open #35 Viewport queries scale with timeline size because of collapsed-duration summaries in the timeline

#35 Viewport queries scale with timeline size because of…