Data Processing Algorithms Complexity & Trade-off Analysis

The reasoning

The mechanism: hash each item, use the first `p` bits to choose a register, and record in that register the longest run of leading zeros seen in the rest of the hash. A long run is unlikely, so seeing one implies many distinct values passed through. The harmonic mean across registers, scaled by a bias constant, gives the estimate.

The properties that matter operationally. Memory is fixed at `2^p` registers and is completely independent of cardinality — the same 16 KB counts a thousand items or a billion. Error is `1.04/sqrt(m)`, so it improves as the square root of memory: four times the memory halves the error. And it is *mergeable* — combine two sketches by taking the per-register maximum — which is what lets it be computed per node, per partition or per day and then combined without re-reading anything.

The measurements beside this are the answer to 'how wrong': at precision 16 the estimate of one million distinct is 1,000,010, an error of 0.00%, against a predicted standard error of 0.41%. At precision 10 — one kilobyte — it is 0.03% against a predicted 3.25%. Note that the measured errors are inside the predicted band rather than equal to it: the prediction is a standard error, so any single measurement is a draw from a distribution, and quoting one lucky run as 'the accuracy' is the mistake to avoid.

Mergeability is the property worth emphasising, because it is what makes the sketch structurally better and not merely smaller. Exact distinct counts cannot be combined — you cannot add two nodes' counts without double-counting shared users — so exact `COUNT(DISTINCT)` requires shipping values. Sketches turn a shuffle-heavy operation into one that distributes in constant space, and daily sketches can be rolled up into a monthly figure that never required the month's data.

The reasoning

The structure: `d` rows of `w` counters, each row with its own hash. To add a key, increment one counter per row. To estimate, take the *minimum* across the rows — because every counter the key touched includes its true count plus whatever else collided there, so the smallest is the least contaminated. Hence never below the truth, and usually above it.

The error is additive rather than proportional, which is the whole point. The measured run over two million events in 10,240 counters shows the top key estimated at 200,337 against a true 200,000 — 0.2% — and a tail key estimated at 165 against a true 10, which is sixteen times too high. Same absolute error of a few hundred, utterly different relative error.

So the sketch is fit for questions about the head and unfit for questions about the tail. Heavy hitters, top-k, 'is this key hot' — fine. 'How many times did this rare key appear' — meaningless. And a question people get wrong: you cannot use it to find keys that appear *exactly once*, because the overestimate makes rare keys look common.

Sizing: width controls the error and depth controls the confidence — formally the error is bounded by `e/w` times the total count with probability `1 - e^-d`. Practically, depth of four or five is plenty and width is the dial you turn. It is mergeable like HyperLogLog, by summing the tables, which again is what makes it usable distributed. And the alternative worth naming is Space-Saving, which is designed specifically for heavy hitters and gives tighter guarantees for that narrower question.

The reasoning

The argument: item `i` (zero-based, beyond the first k) enters with probability `k/(i+1)`. Once in, it survives step `j` with probability `1 - 1/(j+1)`, because a new item is selected with probability `k/(j+1)` and evicts a specific slot with probability `1/k`. Multiplying the survival terms from `i+1` to `n-1` telescopes, and the product with the entry probability is exactly `k/n` for every `i`.

The measurement is the part worth doing, because the argument is easy to believe and easy to get subtly wrong in code. Two hundred thousand trials over twenty items with a reservoir of five: item 0 kept 50,173 times, item 19 kept 50,297, expected 50,000, largest deviation under 1%. The first and last items — the pair everyone expects to differ — agree.

The bug the measurement catches is the off-by-one: drawing `randrange(i)` instead of `randrange(i + 1)` makes early items over-represented. The output still looks like a plausible sample, so no test that inspects a single run will find it, and only the frequency distribution over many trials shows it.

The trade being made: one pass, `k` items of memory, no advance knowledge of `n`, and a genuinely uniform sample. What you give up is any control over *which* items — you cannot ask for a stratified or consistent-by-key sample, which is what hash-based sampling gives instead. Knowing that the two techniques answer different questions, and that reservoirs merge across shards with appropriate weighting, is the full answer.

The reasoning

The measured table shows the curve: at four bits per key the rate is 14.7%, at eight it is 2.2%, at twelve 0.3%, at sixteen 0.05%. Each additional four bits divides the rate by roughly seven. Memory is linear and accuracy is exponential, which is an unusually favourable shape and the reason Bloom filters are used so widely.

Consequently the decision is not a fine balance. Going from four bits to eight is dramatic and costs 50 KB per hundred thousand keys; going from twelve to sixteen improves a rate that is already negligible. The sweet spot is wherever the false-positive *cost* stops mattering, and for most uses — skipping a remote lookup, pre-filtering a join — that is around 1%, or ten bits per key.

The number of hashes matters less than people expect, and the optimum is `(m/n)·ln2` — about 5.5 for eight bits per key. Being off by one costs little; being far off costs a lot, since too few hashes underuses the bits and too many saturates them.

What actually decides the sizing is the cost asymmetry. A false positive costs one wasted lookup; the filter saves you all the true negatives. So if the lookup is a remote call, a 1% rate means 1% of the calls you would otherwise have made — a hundredfold reduction — and paying for 0.1% buys you very little more. The failure to plan for is exceeding the `n` you sized for: the rate degrades silently as the filter fills, so a filter built for a hundred million keys and fed three hundred million is far worse than its stated rate and nothing will tell you.

The reasoning

The wrong framing is 'how big is the error'. One percent on a dashboard trend is invisible; one percent on a payout is fraud. The question is what the number is *for*, and specifically what changes if it is wrong by the error bound.

Approximation is fine for: trend and monitoring, capacity planning, top-k and heavy hitters, anomaly detection, anything read as a shape rather than a value, and any intermediate used to decide whether to do the expensive exact computation. In all of these a 1% error changes no decision anyone takes.

Approximation is not acceptable for: money, anything a regulator counts, anything that must tie out against another system, and anything a user sees about their own data — a customer who counts their own eleven orders will not accept eleven-point-one. That last category is underrated and is where approximation most often causes trouble, because the individual scale is where relative error is worst.

The middle ground worth proposing rather than choosing a side: serve the approximate answer for latency and reconcile against an exact computation on a slower cadence, with the discrepancy monitored. That is the same fast-path-plus-correction shape as the late-data design, and it gets you a fast dashboard and a number that is provably close.

Two caveats to close on. Approximations compound — a sketch feeding a sketch has error nobody has bounded — so the boundary should be as close to the consumer as possible. And an approximate number must be *labelled*, because the real failure is not the 1%, it is that six months later someone builds a billing process on a figure nobody told them was estimated.

The reasoning

The measured table makes it concrete. Each pass reads all two terabytes and writes all two terabytes, so a pass costs four. At one, four and sixteen gigabytes the sort takes three passes — twelve terabytes moved. At sixty-four and two hundred and fifty-six it takes two — eight. Between the steps, extra memory changes the run size and not the number of merge rounds, so it buys nothing at all.

That has a direct budgeting consequence. Asking for more memory is only worth it if you can compute that it crosses a step — otherwise you are paying for a resource that will not change the runtime, which is a very common and entirely invisible waste.

Fan-in is usually the better lever, because it is the base of the logarithm. Doubling fan-in has the same effect on pass count as squaring the memory. Its limit is buffer size per open run: too high a fan-in means tiny reads and the disk stops being sequential, so there is an optimum rather than a maximum.

The general shape is worth carrying beyond sorting. Many data-processing costs are stepped rather than continuous — number of passes, number of shuffle stages, whether a hash table fits in cache, whether a broadcast is chosen. When someone reports that doubling a resource did nothing, a step function is usually why, and the useful question is which threshold they are between rather than how much more to add.

The reasoning

The row-store arithmetic: an index lookup gives you row locations, and fetching each is a random access. A full scan reads sequentially, which on any storage medium is dramatically cheaper per byte. So the index wins when it eliminates enough rows to offset the random-access penalty, and the crossover is typically a few percent to twenty percent depending on the medium and whether the index is covering. A covering index — one containing every column the query needs — avoids the row fetches entirely and changes the calculation completely.

Analytical columnar systems mostly do not offer that choice, and the reason is worth stating: they are designed for queries that touch large fractions of a table, where an index would lose by definition. What replaces it is pruning by *layout* — partitioning, min/max statistics per row group, and clustering — which skips data in large contiguous units rather than locating individual rows.

That changes the design lever. In a row store you add an index and the layout is unchanged. In a warehouse you change the layout — partition by the column you filter on, sort by the column you range-scan — and every query benefits or does not depending on whether it matches. You can be sorted on one thing, so it is a choice about which query shape to privilege rather than something you can add for each query.

The costs on both sides: indexes must be maintained on every write and consume storage, which is why a table with many indexes is slow to load. Clustering must be maintained too, and decays as data is appended, which is what compaction and re-clustering exist for. Neither is free, and 'add an index' as a reflex is how an ingest pipeline becomes the bottleneck.

The reasoning

The framing: compression trades CPU for bytes. Whether that is a win depends entirely on which of the two you are short of. On a system reading from object storage over a network, bytes are the constraint and a heavier codec genuinely makes queries faster despite doing more CPU work. On a system with data in page cache and a CPU-heavy query, decompression competes with the work and light compression wins.

The asymmetry that decides most real cases is that compression happens once and decompression happens on every read. So a slow, high-ratio codec at write time is often correct — you pay once for a saving realised thousands of times. Zstd is popular precisely because its decompression is fast across levels, so you can raise the level for a better ratio without paying for it on every read; gzip is the opposite, and is why it has fallen out of favour despite decent ratios.

Splittability matters as much as ratio, and is easy to forget: a single gzip file cannot be split, so it is read by one task no matter how large. Snappy and zstd within a columnar format are block-compressed and remain splittable, which is why format-level compression beats compressing the whole file.

And the encodings come first. The measurements in Mechanics show run-length collapsing a sorted column to nothing while a general codec on the same data does far less — the ratio comes mostly from the encoding and the sort order, with the codec applied on top. So the sequence is: choose the sort order, let the encodings work, then pick a codec that decompresses cheaply. Choosing a heavy codec to compensate for an unsorted table is paying CPU forever for something a sort would have given free.

The reasoning

The concrete case is sort-based versus hash-based aggregation. Hashing is `O(n)` and touches memory randomly; once the table exceeds last-level cache, most probes are main-memory accesses at a hundred nanoseconds and prefetching cannot help because the pattern is random by design. Sorting is `O(n log n)` and is almost entirely sequential, so it runs near memory bandwidth. At real sizes the log factor is around thirty and the per-access penalty is around a hundred, so the asymptotically worse algorithm wins.

The same reasoning explains why engines radix-partition before building hash tables — an extra `O(n)` pass, deliberately added, to make every subsequent table fit in cache. Adding work to reduce total time only makes sense once you are counting cache misses rather than operations.

The generalisation: in data processing the units that matter are bytes moved and where they are moved from. Sequential versus random, cache versus memory versus disk versus network — those span six orders of magnitude, and complexity analysis treats them all as one operation. That is why 'reads less data' beats 'does fewer operations' as a heuristic almost every time.

Which is not an argument for ignoring complexity. It correctly predicts what happens when the data grows tenfold, and a genuinely quadratic algorithm will lose eventually no matter how good its constants. The right posture is to use asymptotics to rule out the disasters and measurement to choose among the survivors — and to be suspicious of any performance claim, including your own, that has not been measured on realistic sizes.

The reasoning

The two terms. Overhead is `checkpoint_cost / interval` as a fraction of runtime. Expected rework is about half the interval, multiplied by the probability of a failure in that window. Minimising their sum gives an interval that grows with checkpoint cost and shrinks with failure rate — the same square-root-ish shape as many batching problems.

In practice you rarely compute it exactly; you bound it. Aim for checkpoint overhead of a few percent, and check that half an interval of rework is acceptable against the deadline. Those two constraints usually pin the interval within a small range without any calculus.

The failure rate is the term people ignore and it varies enormously. On spot or preemptible instances, interruptions are frequent and the interval should be short — the rework term dominates. On stable dedicated hardware, failures are rare and long intervals are fine. Running the same configuration on both is how a job that was well-tuned becomes badly tuned by being moved.

Two interactions. Checkpoint cost is proportional to state size, so as state grows the optimum interval lengthens — and if state is growing without bound, the checkpoint problem is a symptom rather than the thing to tune. And incremental checkpointing changes the arithmetic entirely by making the cost proportional to what changed rather than to total state, which usually means you can checkpoint far more often than before, so it is worth revisiting the interval after enabling it rather than leaving it where it was.

The reasoning

A mergeable summary means `f(A ∪ B)` can be computed from `f(A)` and `f(B)` without revisiting the data. HyperLogLog merges by taking per-register maxima; Count-Min by summing tables; t-digest by combining centroids. Exact distinct counts have no such operation — you cannot combine two counts without knowing the overlap, which is why you must ship the values.

Distributed, that is the difference between a shuffle of every value and a shuffle of a handful of fixed-size sketches. `COUNT(DISTINCT)` across a cluster moves data proportional to cardinality; the sketch version moves 16 KB per partition regardless. That is an architectural change, not a memory optimisation.

Across time it is arguably more valuable. Store a daily sketch and you can answer monthly, quarterly or arbitrary-range distinct counts by merging the stored sketches — never re-reading the underlying events. Exact daily counts cannot be added into a monthly count at all, because a user active on twenty days would be counted twenty times. That single property is why sketches appear in analytics platforms far more than the memory argument alone would justify.

The caveat that makes it honest: merging composes error, though for these structures it composes well — merged HyperLogLog sketches have the same relative error as one built over the union, which is a genuinely strong property and not true of every summary. What does not merge safely is a sketch feeding another approximation, where nobody has bounded the combined error, so the rule is to keep approximations to one layer and as close to the consumer as you can.

The reasoning

The exact answer requires ordering: the p95 is the value at position 0.95n in sorted order, so exactly it needs a sort or the full multiset. That is fine for a million values and not for a billion per node per minute.

The trap worth naming explicitly because it is committed constantly: averaging percentiles is meaningless. The mean of ten nodes' p95 values is not the global p95, and it is not an approximation of it either — it can be arbitrarily far off depending on how load is distributed. Any dashboard aggregating pre-computed per-instance percentiles is showing a number with no defined meaning.

Quantile sketches solve it. t-digest keeps clusters of values with higher resolution at the tails — deliberately, because p99 is what people care about and p50 is easy — and merges by combining centroids. KLL and the older Greenwald-Khanna give formal error bounds on rank rather than t-digest's empirical accuracy. All are mergeable, which is what makes per-node computation plus a combine correct rather than approximate-in-an-undefined-way.

The trade: error is in the *rank* rather than the value, so a t-digest p99 is really 'a value somewhere between the p98.9 and p99.1', which for latency monitoring is entirely adequate. Where it is not adequate is a hard SLA threshold with money attached, and there the answer is the same as elsewhere — serve the sketch for monitoring and compute exactly on a slower cadence for the number that is an obligation.

The reasoning

The question to ask is what decision this data drives and how quickly someone acts on it. A weekly planning meeting does not benefit from minute-level freshness. A fraud check does. Most dashboards people ask to be real-time are looked at twice a day, and the honest conversation is about that rather than about the pipeline.

The cost curve is not smooth. Nightly is one batch job. Hourly is twenty-four times the runs, and each still amortises fixed startup over real work. Every minute usually means the batch model stops working entirely — startup overhead dominates, and you move to streaming, which is a different system with state, watermarks, checkpoints and an on-call burden. That transition is a step change in operational cost, not an increment.

The intermediate options worth proposing, because they often satisfy the requirement at a fraction of the cost. Incremental batch at fifteen-minute intervals gets you most of the way with batch's simplicity. A lambda-style split — a fast approximate view plus a nightly exact recompute — gives freshness where it matters and correctness where it matters. And serving a fresh partial answer for today plus exact history is often exactly what the dashboard needed.

The costs beyond compute that decide it in practice: streaming systems need people who can debug them at 3am, and correctness is harder because late data must be handled explicitly rather than by tomorrow's rerun. I would push back on a real-time requirement until someone names the decision that depends on the difference — and if they can, build it, because then it is worth the money.

The reasoning

The reframing first: raw data is what every derived table can be rebuilt from. Delete it and every downstream table becomes the only copy of its own logic's output — so a transformation bug discovered in six months is unfixable for the period beyond retention, and a new metric can only be computed from the day you thought of it.

So the retention decision is really 'how far back must we be able to reprocess'. That is usually driven by how long a bug can plausibly go unnoticed — which for a rarely-checked metric is months — plus any regulatory obligation, plus the cost of losing the ability to answer new questions retroactively.

The cost side is less alarming than it sounds, and the tiering is the answer rather than deletion. Raw events compress extremely well, and cold object storage is very cheap. A common shape is hot storage for recent data, cold for the older tail, and deletion only where a regulation requires it — which usually means retention is bounded by policy rather than by cost.

Two related decisions. Deletion obligations under privacy regulation cut the other way and are non-negotiable, so retention has a legal ceiling as well as an operational floor. And the derived tables should be treated as disposable rather than precious: if raw is retained and the transformations are in version control, a derived table is a cache. Teams that back up derived tables and delete raw have it exactly backwards, and it is worth saying so.

The reasoning

Measure first and expect concentration: in every pipeline I have looked at, a handful of jobs are most of the bill. Per-stage runtime and bytes scanned, attributed back to specific tables, turns 'the pipeline is expensive' into 'these four models are 70% of it', and the conversation becomes tractable.

Then the levers, roughly in order of return. **Read less** — partition and cluster so pruning works, project only needed columns, filter before joining and before shuffling. This is almost always the biggest single win because it compounds through every downstream stage. **Recompute less** — incremental instead of full rebuild where the aggregate decomposes, and stop rebuilding tables nobody reads. **Store less hot** — tier cold data, compact small files, and re-examine anything held in an expensive tier for convenience.

Then the shape of the spend: idle capacity is the quiet one. A fleet sized for the 9am peak is idle sixteen hours a day, and staggering schedules plus autoscaling can be a large saving without touching any pipeline. And a surprising fraction of the bill is often CI or ad-hoc queries rather than production, which nobody attributes.

What I would not trade: correctness, obviously; reproducibility, because a cheaper pipeline whose numbers cannot be re-derived costs more the first time they are questioned; recoverability, meaning idempotence and retention, because giving those up saves money until the incident that costs more than a year of the savings; and the tests and reconciliation checks, which are usually a rounding error in cost and the only reason anyone would notice if a cost optimisation broke something.

The one to be explicit about is approximation. Replacing exact aggregates with sketches is often a large saving and it changes what the numbers mean — so it is a decision for whoever owns the number, and it needs the result labelled as estimated. A cost optimisation that quietly makes the figures approximate is not an optimisation, it is a change of contract.

The reasoning

Write both costs with the memory term visible, because that is the one that decides it. Hash: one pass over `n` rows, a table holding `g` entries. Sort: `n log n` comparisons and constant running state. The measured run shows the difference starkly — 500,000 rows over 183,206 groups gives a hash table of 183,206 entries against a sort whose running state is one group.

So the crossover is not about `n` at all. It is about whether `g` fits. Low cardinality means hash wins comfortably; as `g` approaches `n` the hash table approaches the size of the input, and grouping by a near-unique key is the worst case for hashing and the case where sorting is both cheaper and possible.

Then the discontinuity: when the table does not fit, hash aggregation does not degrade gracefully, it spills — partitioning to disk and reprocessing, which is a full write and read plus the risk of a partition that is still too large. That is why a plan that was fine at last year's cardinality falls off a cliff rather than sloping, and why the cost model has to include the spill branch rather than just the two clean cases.

The three cases where sort wins outright are worth having ready: the groups do not fit; the input is already sorted on the key, so the sort is free and the sweep needs no memory; and the query has an `ORDER BY` on the same key, so the sort has to happen regardless and doing it first makes the aggregation free. That last one is a genuine plan-level optimisation rather than a fallback.

The reasoning

The immediate consequences are all plan choices. A join whose small side is estimated at ten thousand rows gets a broadcast; at ten million it either dies collecting it or ships gigabytes to every node. A hash table sized for the estimate spills as soon as reality arrives. Memory grants and partition counts are set from the same number, so a thousand-fold underestimate leaves every one of them wrong in the same direction.

The compounding is what makes deep queries worse than shallow ones. A join's output estimate is derived from its inputs' estimates, so an error at the leaves propagates and multiplies. Three joins each estimated three times too small give a final estimate off by a factor of twenty-seven, and the plan for the last join — the most expensive one — is chosen from the worst number in the chain.

Which is why the errors are asymmetric in consequence. Overestimating is usually mildly wasteful: a shuffle where a broadcast would have done, more memory reserved than needed. Underestimating is catastrophic: a broadcast that OOMs, a spill, a partition count far too low. A good optimizer is deliberately conservative for that reason, and so should you be when hinting.

The fixes in order: refresh statistics, since stale stats on a growing table are the most common root cause; add multi-column statistics where supported, which directly addresses the independence assumption behind correlated predicates; materialise a problem intermediate so the next stage plans against a known size; and use adaptive execution where the engine offers it, since re-planning once real row counts are known is the only approach that fixes the compounding rather than the leaf.

The reasoning

The cost model is simple and is the thing to state first: a stage completes when its slowest task does, so the runtime is set by the largest partition rather than by the total volume. That makes the meaningful metric `largest / mean`, and it is directly measurable from task input sizes.

The measured run makes it concrete. One million rows, two hundred partitions, one key holding 30% of them: the largest partition is 303,513 rows against a mean of 5,000 — a ratio of 60.7. The cluster is effectively running at a sixtieth of its capacity for that stage, and adding nodes changes nothing because the hot partition cannot be split.

After splitting the hot key sixty-four ways with a round-robin salt, the largest partition is 17,574 against the same mean — 3.5x. Not perfect, and a seventeen-fold improvement in the stage's runtime. The residual is because sixty-four sub-keys over two hundred partitions still collide, and more salts would narrow it further at the cost of a larger combine step.

The constraint that decides whether salting is available at all: it requires a two-stage aggregation, partial results per salt then combined. Sums, counts, mins and maxes decompose that way. A median or an exact distinct count does not — you cannot combine per-salt medians — so for those the answer is a different algorithm, a sketch, or handling the hot key on a separate path entirely. Naming that limit is what distinguishes knowing the technique from knowing when it applies.

The reasoning

The trade: a full rebuild is correct by construction, since it is a pure function of its inputs and cannot drift. An incremental update is cheap and accumulates the errors its filter cannot see — late arrivals outside the window, corrections to old partitions, deletes that no timestamp reveals, a partial write that was retried.

So the answer is not to choose. Run the incremental path for daily freshness and cost, and run the full rebuild on a cadence — weekly is usually enough — as the thing that resets accumulated drift. The rebuild is the correctness mechanism, not a contingency, and budgeting for it is part of choosing incremental in the first place.

Where a full rebuild is genuinely unaffordable, replace it with reconciliation: compare per-partition summaries between the incremental output and a recomputation over a bounded recent window, and repair what disagrees. That gets you detection at a fraction of the cost, and it works even when the raw data for older periods has aged out.

The precondition for all of it is that the rebuild is *possible*: raw inputs retained long enough, and the transformation deterministic and idempotent so the rebuild produces the same answer. A pipeline that cannot be rebuilt has no correctness backstop at all, and its incremental output is the only copy of a number nobody can re-derive — which is the state to avoid rather than a cost to optimise.

The reasoning

**Membership** — 'have I seen this key?' A hash set is exact and grows with distinct keys. A Bloom filter is fixed-size, has no false negatives and some false positives, so it is right when a false positive is merely wasted work and fatal when it would cause a row to be dropped. That direction is the single most important thing to get right.

**Cardinality** — 'how many distinct?' A set is exact and expensive; HyperLogLog is fixed-size, mergeable and about 1% wrong. Use the sketch unless the count is an obligation.

**Frequency** — 'how many times this key?' A counter map is exact and grows with distinct keys; Count-Min is fixed-size, never underestimates, and is accurate for the head and meaningless for the tail.

**Top-k** — 'which are the biggest?' A heap of size k over exact counts when the counts fit, and Count-Min or Space-Saving over the counts when they do not.

The decision procedure I would state: name the question first, check whether the exact structure fits — it usually does, and reaching for a sketch when a hash map would have worked is over-engineering — and only then choose the approximation whose error direction is harmless for your use. Then write down what the error means for the number being served, because the structure choice is a contract with whoever reads the output and nobody but you will know it was made.

The reasoning

**Fixed window.** One counter per key per minute, reset on the boundary. O(1) memory, trivially correct to implement, and it has a real flaw: 100 requests at 10:00:59 and 100 more at 10:01:00 both pass, so a client can send 200 requests in one second. The limit says 100 per minute and the system tolerates 200 in two adjacent instants.

**Sliding window log.** Keep the timestamp of every request in the window; on each arrival, evict anything older than 60 seconds and count what remains. **Exact** — no boundary artifact at all. The cost is memory proportional to the allowed rate per key, so a 100/minute limit across a million keys is up to a hundred million timestamps, which is why this one rarely survives contact with scale.

**Sliding window counter.** Keep the current window's count and the previous window's, and estimate as `current + previous × (fraction of the previous window still in range)`. O(1) memory, no hard boundary artifact, and it is an approximation — it assumes the previous window's requests were spread evenly, so it can be slightly wrong in either direction on very bursty traffic. This is the trade almost every production limiter takes, and it is worth naming as an approximation rather than presenting it as exact.

**Token bucket is the fourth answer** and it is often the better one: a bucket refilled at a steady rate, each request taking a token. O(1) memory, and it allows a *controlled* burst up to the bucket size, which is usually what you actually want — a client should be able to send ten requests at once after being idle. If the requirement is "smooth the rate but tolerate short bursts", token bucket expresses that directly where the window designs only approximate it.

**What decides it in practice:** whether the limit must be exact (log), whether memory per key is constrained (counter or bucket), and whether a burst after idle time is desirable (bucket) or forbidden (log). And in a distributed setting all four need shared state, at which point the per-node approximation error usually dominates the choice of algorithm.

The reasoning

**Why subtraction is impossible.** An HLL register stores the maximum leading-zero count seen for the hashes landing in that bucket. Union is easy — take the elementwise maximum of two sketches, which is why HLLs merge so cleanly. Subtraction is not the inverse of a maximum: if you remove the element that set a register to 7, the correct new value is whatever the second-highest was, and the sketch never recorded it. The information is gone by construction.

**So you do not subtract, you re-merge.** Build one sketch per day. A 30-day rolling count is the union of the last 30 daily sketches, computed at query time. Merging 30 sketches is cheap — elementwise max over a fixed-size array — and it is exact with respect to the union, with only the usual HLL estimation error on the result.

**The costs are honest and small.** Storage is one sketch per day per dimension you slice by, which is a few kilobytes each. Query cost is 30 merges instead of one lookup. In exchange any window is available — 7 days, 30 days, this month against last — from the same daily sketches, with no precomputation per window. That flexibility is usually worth more than the merge cost.

**Where it stops working:** sub-daily granularity multiplies the sketch count, so hourly windows over a year is 8,760 sketches per dimension. And if the window has to slide continuously rather than by whole days, the daily grain is too coarse and you need finer sketches or a different structure — a sliding HLL with per-bucket timestamps, which exists and is considerably more complex.

**The general lesson worth stating:** sketches are mergeable, not invertible. That is true of Count-Min Sketch too, and it is the property that decides how you have to structure the precomputation — you build at the finest grain you will ever need and merge upward, never the reverse.