How OpenChronology was built

#81 · Keep duration summaries fast beyond float8's range

2026-10-11T16:54:50Z CE

• timeline-app
• pull request

Closes #54: *do summary views still work for values outside of the floating point range?* ## Answer **Correctness: yes, and it already was.** Every summary path compares times exactly: - **Browser and desktop:** moment groups, duration summaries, coalescing and expansion use exact `Q` arithmetic in the browser and in the desktop store (exact SQLite index). - **Postgres:** moment groups and duration summaries use exact `mpq` comparisons. - **Screen positions:** these are computed as `(time - left) / span` relative to the view, so they work at any magnitude. **Performance: no, and this PR fixes it.** PostgreSQL duration summaries range-scan an index on each start rounded to `float8`, then recheck the exact values. `float8` saturates, so every start beyond ±1.8e308 (or below ~1e-308) got the same key (`±Infinity` or `0`). Each summary group then read all of those durations, so cost grew with durations × groups, toward the 30 s statement timeout. ## Changes 1. **Start key `oc_qkey(first_time)`:** `±((2^40 + e)·10^30 + m)` as one `numeric`, where `e` is the decimal exponent and `m` the first 30 significant digits (truncated). - **Order:** truncation never reverses the order of two starts, so key-range scans plus the exact recheck stay correct. - **No saturation:** the exponent never overflows. The key for 10^10000 is 14 bytes; the `mpq` itself is 4 KB, too large for a B-tree index entry. - **Plans:** a single column keeps the planner's estimates and ordered index scans the same as before. - **Migration:** drops `first_approx` and adds `first_key` on `oc_duration_nodes` and `oc_view_duration_nodes`. On an upgrade test, 100,000 rows migrated in 5 s with no ordering inversions. 2. **Starts that share a key are grouped in one pass.** Starts that agree in their first 30 significant digits share a key. `oc_duration_overview` now finds the next key holding a collapsed start, reads that block once in exact order, forms its groups in memory, and extends the block's last group into later keys with one count. A tied block costs one read per view instead of one per group. The block is sorted by each start's offset from the bound, divided by the threshold, as `float8` (monotone, with exact comparisons only to break ties). The next-key search skips blocks already grouped. Bitmap scans are off in this function, because PostgreSQL can't estimate the exact `mpq` filters and otherwise read whole key ranges to find the first match. ## Measurements 20,000 short durations, minimum of 3 runs, 200 groups (full range) / 201 groups (1% window): | starts | main (float8) | key only (1) | key + block pass (1+2) | |---|---|---|---| | 0 … 20,000, step 1 | 107 / 59 ms | 97 / 65 ms | 114 / 69 ms | | epoch seconds, step 1 ns | 244 / 147 ms | 225 / 86 ms | 292 / 147 ms | | **10^400 …, step 10^398** | **5,717 / 4,174 ms** | 143 / 80 ms | 172 / 80 ms | | **10^-400 …, step 10^-402** | **7,783 / 5,510 ms** | 163 / 84 ms | 146 / 82 ms | | **10^400 + k (clustered)** | **6,868 / 4,949 ms** | 6,641 / 4,151 ms | 176 / 56 ms | | **10^1200 offset, 10^-1100 step** | **355,519 / 293,524 ms** | – | 1,951 / 638 ms | The "key only" column comes from an earlier run on the same machine, without the 10^1200 case. The last row is the browser tests' extreme case. On `main` it exceeds the server's 30 s statement timeout, so that view fails. Its remaining cost is reading and exactly filtering every short duration in the view, each start a 2,300-digit number. The pre-#35 tree walk, which uses stored subtree totals, does that case in 287 ms, but it is 2.8× slower once every tenth duration is long, so this PR keeps the set-based query. ## Tests - `test/summaries-equivalence-postgres.mjs`: - **Key-order oracle:** checks that the key never sorts against the exact order, and that values differing within 30 digits get distinct keys. It covers powers of ten from 10^-10000 to 10^10000 and their neighbours, both signs, long fractions, and random times. Breaking the exponent correction in `oc_qkey…

Open #81 · Keep duration summaries fast beyond float8's range in the timeline