#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
- #36 Make viewport queries scale with what is shown, not the timeline
- #37 Compute PostgreSQL duration summaries set-based over a start index
- #65 Log file importer with pluggable formats and metadata mapping
- #81 Keep duration summaries fast beyond float8's range
- #83 Summarize PostgreSQL durations from subtree totals, batching mixed subtrees