Episode Details

This story was originally published on HackerNoon at: https://hackernoon.com/block-decomposition-how-clickhouse-prometheus-and-influxdb-rediscovered-the-same-fundamental-algo.
ClickHouse, Prometheus, and InfluxDB independently landed on the same idea: sqrt-decomposition. Here's where the model holds — and where it breaks.
Check more stories related to programming at: https://hackernoon.com/c/programming. You can also check exclusive content about #software-engineering, #software-architecture, #data-structures, #decomposition-patterns, #time-series-database, #clickhouse, #prometheus, #hackernoon-top-story, and more.

This story was written by: @ivan-fekete. Learn more about this writer by checking @ivan-fekete's about page, and for more stories, please visit hackernoon.com.

ClickHouse, Prometheus, and InfluxDB were built by different teams, in different languages, for partially different workloads — yet all three read data the same way: split the timeline into sealed blocks, keep a small summary next to each one, and answer a range query by skipping whole blocks and scanning only the partial ones at the edges. That's square-root decomposition, the structure competitive programmers reach for when trees don't fit the query pattern. The model isn't followed literally. Nobody picks B = sqrt(N), because N grows forever and recent data must stay cheap to reach; block sizes are fixed instead (8192 rows, ~120 samples, a 2-hour window) and driven by the compression algorithm rather than by asymptotics. Decomposition is also two-dimensional in practice: time is one axis, label filtering is another, handled by a separate inverted index, and real query cost lives at their intersection. And updates are appends, not random writes — the summary cost shows up as background compaction. The practical payoff: block size is the tuning knob (pruning accuracy and index size vs. compression and scan throughput), single-row reads are structurally slow because you always pay for a whole block, and range-query performance is predictable once you know which blocks get touched.