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

#81 Keep duration summaries fast beyond float8's range

–

  • github
  • github/openchronology/timeline-app
  • github/openchronology/timeline-app#81
  • pull request
  • state:merged

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 expon……

Related

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

#81 Keep duration summaries fast beyond float8's range