The algebra decides
What can be skipped, pushed down, parallelized, merged or precomputed is determined by the algebra of the function, not the layout of the data.
What it is
The general form reaches well beyond search: what can be skipped, pushed down, parallelized, merged or precomputed is determined by the algebra of the function, not the layout of the data. Block-max skipping requires a decomposable score with per-term bounds. Partial aggregation (computing sums on each shard and then adding them) requires associativity (the grouping of operations does not change the result). Predicate pushdown requires the predicate to be expressible in the remote system's dialect. Proximity scoring has none of these properties and therefore gets none of the optimizations. The same question later decides which time-series aggregates can be rolled up.
From Specialized Processing Models › Scoring
Look at the third check. It is the same algebraic property that decided incremental maintainability for views, doing completely different work. One property, two mechanisms: the algebra decides both whether you can maintain an entry and whether you can reuse it. It is the best argument for asking about the algebra first for any declared derivation, before storage, refresh schedule or indexing. It also shows why sketches and combiners (map-side partial aggregation) are the same idea in three places.
From Caching › Semantic caching
When operations have the right algebra (commutative, idempotent, associative), coordination becomes optional. The work moves from designing a protocol to reformulating the operation.
From Transactions & Concurrency Control › Commutativity
Where it appears
In 17 mechanisms. Each says what the mechanism is about, then how this principle 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?
Converting deltas into full state at the source is usually cheaper than preserving order from end to end.
Read it inMessage keys and key-based orderingTwo kinds of skew: different problems, different fixes
- Persistence & Durability
When a system says "yes, your data is safe", what exactly has it promised, and what did it have to do to keep that promise?
This is a monotonic version counter used to make a non-repeatable operation safe to retry.
Read it inWrite-ahead logging (redo)
- Core Data Structures
How do we choose a data structure when the real cost is set by the hardware, not by Big-O?
Discard what is dominated on every dimension that matters is the cheapest form of state reduction, and it costs no accuracy at all.
Read it inMonotonic queues and sliding windowsCount-Min SketchSpending correctness: what a sketch isWhat probabilistic structures forbid
- Transactions & Concurrency Control
What happens when many users change the same data at the same time, and how do we keep the result correct?
When operations have the right algebra (commutative, idempotent, associative), coordination becomes optional.
Read it inCommutativity: removing the conflict
- Consistency & Isolation Models
When many users, many objects and many copies exist at once, which histories does the system promise never to show, and who writes the code for the histories it does show?
It is the closure of that requirement: this is the right-algebra rule in its purest form.
Read it inEventual consistency, convergence and CRDTsCALM: when coordination is necessaryHighly available transactions and invariant confluenceRead Committed and the lost update
- 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?
The aggregate's algebra chooses its spill strategy, not only its parallelization strategy.
Read it inThe output does not grow with the inputPartial, two-phase and incremental aggregationJoins, aggregates and windows: what each forces
- 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?
Because a conjunct can be moved independently, and a disjunct cannot.
Read it inQuery normalizationView expansion and materialized-view rewriting
- Memory & Resource Management
Who is allowed to hold how much memory, for how long, and what happens to the work when the answer is less than it asked for?
This is a recurring idea: the right algebra makes spill unnecessary.
- Caching
What happens when we deliberately keep a second copy of data that no protocol forces to be correct?
For a view, the consequence is a design rule: the view must store the monoid element, not the final projection.
Read it inMaterialized views: a cache whose admission was declared
- Distributed Systems Coordination
Who is allowed to decide, and how does everyone else learn the decision without asking?
A program has a coordination-free distributed implementation if and only if it is monotonic: no later fact can retract an earlier conclusion.
Read it inCoordination avoidance
- Fault Tolerance & Delivery Semantics
What is the cheapest thing that can be safely done twice?
The right algebra removes the need to coordinate.
Read it inIdempotency: the three sourcesAnti-entropy, read repair and hinted handoff
- 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?
This is the same trick as CRDTs (replicated data types, built so that updates can arrive in any order and still give the same result): make the operation tolerate disorder instead of paying to remove it.
Read it inOut-of-order handling and bufferingTriggers and accumulation mode
- Streaming
What does it cost to remember, when the input never ends?
It works only for associative and commutative aggregates (sum, count, max), adds a shuffle and a latency stage, and does nothing at all for joins, pattern matching, or anything that depends on order.
Read it inKeyed state, operator state and the indivisible keyWindows are retention rules in time
- Change Data Capture & Incremental Processing
What does it cost to know what changed, and is that cheaper than not needing to know?
Principle: incrementality requires an inverse.
Read it inIncremental view maintenanceChange event envelopes and retraction
- Data Modeling
What does one row mean, who is allowed to change that answer, and what breaks downstream when they do?
> This is arithmetic, not a modeling convention.
Read it inAdditivity comes first
- Security & Privacy
How do you protect data from someone who watches your design and then chooses how to attack it?
Allow-only policies compose; explicit deny does not.
Read it inViews, grants and privilege inheritanceK-anonymity and its successors
- Specialized Processing Models
What do you build when a query predicate cannot be reduced to a range over an ordered key?
The score of a document is a sum of independent per-term contributions, each with a computable maximum.
Read it inScoring and top-k skippingDownsampling, rollups and retention tiersThe ANN families and their build cost
Related
Made on the same pages most often.