Exactness vs. approximation
Where you meet it: sketches, sampling, ANN.
What it is
One more mechanism deserves its own place. Sampling (TABLESAMPLE, block sampling, approximate query processing) is a deliberate data-reduction step. It is the only mechanism in this article that reduces data without preserving the exact answer. That makes it the natural home of the trade between exactness and approximation, and a clean contrast with everything else here. Bloom filters are approximate too, but their error only costs extra reads, never a wrong answer. A sample's error appears in the answer itself. A dashboard that shows "about 1.2 million" can use it; a financial close cannot.
From Query Planning & Optimization › Late materialization, sampling
Sliding window counter. The practical compromise. Interpolate between the previous and the current fixed window according to how much of the current window has elapsed. It uses O(1) memory, is approximately correct, and has no boundary spike. This is a trade of exactness for approximation, and it is almost always the right trade: nobody needs a rate limit to be exact to the single request.
From Data Movement › Rate limiting and pacing
Where it appears
In 14 mechanisms. Each says what the mechanism is about, then how this trade-off shows up there, in its own words.
- Data Movement
How do records cross between two systems that have independent rates, independent availability and independent lifetimes, and what are you willing to lose when the assumption underneath the crossing breaks?
This is a trade of exactness for approximation, and it is almost always the right trade: nobody needs a rate limit to be exact to the single request.
Read it inRate limiting, throttling and pacingLoad sheddingConsistent and rendezvous hashing
- Storage: Physical Organization
What should sit next to what, given that I must decide at write time and find out at read time?
All skipping metadata can prove that a unit is irrelevant.
- Core Data Structures
How do we choose a data structure when the real cost is set by the hardware, not by Big-O?
Approximation buys space at a square-root rate: the error of an estimate from m independent observations is proportional to 1/√m.
Read it inLSM-treesBloom filtersCount-Min SketchCuckoo, XOR and ribbon filtersHyperLogLog, Theta and KMVSpending correctness: what a sketch is
- Indexing
When does a separate "where is it?" structure pay for itself, and what does it cost to keep it true?
Approximation in high-dimensional search is not an optimization.
- Query Processing
Why can one question be answered by plans whose costs differ by a factor of ten thousand, and what does each operator force the engine to do?
A sketch converts a holistic aggregate into an algebraic one.
- Query Planning & Optimization
How does a system choose a plan for a question when the facts that decide the best plan are unknown until the plan has run?
A sample's error appears in the answer itself.
Read it inLate materialization and samplingThe cost model and the cardinality estimatorStatistics
- Caching
What happens when we deliberately keep a second copy of data that no protocol forces to be correct?
When the absent set is enormous and you can tolerate a fraction of wasted lookups, take completeness and pay with false positives.
Read it inNegative caching and Bloom filters
- Time & Temporal Semantics
When am I allowed to act on data that may still be incomplete, and what do I owe the reader if I was wrong?
Emit early and accept that you may be wrong.
Read it inThe three ways out of incompleteness
- Change Data Capture & Incremental Processing
What does it cost to know what changed, and is that cheaper than not needing to know?
In one line: path-dependent models require path-complete capture; you cannot bolt Type 2 onto a polling pipeline.
- Data Quality & Validation
How do you check that data is right, when "right" is a claim about the world and not about the bytes?
The right instrument is effect size against a threshold chosen for business meaning.
Read it inStatistical checks: from predicates to estimatorsThe reconciliation ladder: detecting is cheap, locating is what costs
- Observability & Operations
What is the smallest description of a running system from which we can find a fault, fast enough to matter, at a cost we can still pay while the system is failing?
You see a lossy, delayed, aggregated projection of it.
Read it inObservation is a second machineProfiling
- Security & Privacy
How do you protect data from someone who watches your design and then chooses how to attack it?
Every authorization model is a compression scheme for that matrix.
Read it inAuthorization modelsDifferencing and differential privacyPrivacy is a bound on what an adversary learnsEncryption at rest and envelope encryption
- Specialized Processing Models
What do you build when a query predicate cannot be reduced to a range over an ordered key?
Scores from independently calibrated systems are commensurable only in rank, not in magnitude.
Read it inHybrid search and filtered ANN
- Measurement & Experimental Method
What would have to be true for this number to mean what I think it means?
Principle: aggregation is lossy and irreversible.
Read it inWhat kind of thing is a measurement?
Related
Made on the same pages most often.