Glossary

113 terms, in the sense this mechanism uses them. The platform glossary has every term across all mechanisms.

Accumulator: The small running value kept per group during aggregation (for example a running sum).
Aggregation: Replacing many observations with fewer numbers (a mean, a percentile). Lossy and irreversible.Combining many rows into fewer: SUM, COUNT, AVG. Aggregation loses detail. You cannot get the individual rows back from the total.
Algebraic aggregate: An aggregate (SUM, COUNT, MIN, MAX) whose state is O(1) per group and can be combined partially.
Amplification: Extra bytes read, written or stored compared with what was logically needed.If you ask for 200 bytes and the system must move 4,096 bytes, the amplification is about 20. Read amplification means extra bytes read. Write amplification means extra bytes written. Space amplification means extra bytes stored. It is the hidden cost behind most slow systems.
Anti-join: A join that keeps left rows with no match on the right.
As-of join: A join that, for each left row at time t, picks the right row with the greatest time at or before t.A join that, for each event at time t, picks the most recent value of another table that was valid at or before t.
Bag semantics: SQL's model: collections where duplicates are kept unless removed explicitly.
Band merge join: A merge join for range predicates, walking sorted inputs with a moving window.
Block nested loop: A nested loop join that reads R in memory-sized chunks and scans S once per chunk.
Blocking: An operator that must collect its input before producing any output, such as a sort; also called a pipeline breaker, because rows stop flowing through the plan there.1 other meaning →A streaming operator handles each row and passes it on at once, holding almost nothing. A blocking operator must collect input before it can produce output (a sort, for example). A blocking operator is also called a pipeline breaker, because the flow of rows through the plan stops there.
Bloom filter: A bit array and k hash functions answering "definitely not present" or "probably present"A tiny structure that answers "is this key in the set?" with either "definitely not" or "probably yes". It never misses a real member, but sometimes says "probably yes" for a key that is not there (a false positive). It needs about 10 bits per key.
Broadcast join: A join that copies the small side to every executor so the large side does not move.
Bucketed table: A table stored pre-divided into buckets by the hash of a key, so equal keys are co-located.
Build side / probe side: The input put into the hash table / the input streamed through it.
Cardinality: Number of rows an operator produces.2 other meanings →The cardinality of an operator is the number of rows it produces. The selectivity of a condition is the fraction of rows that pass it. Example: a table has 1,000,000 rows and city = 'Pune' matches 20,000 of them. The selectivity is 20,000 / 1,000,000 = 0.02 (2%), and the cardinality of the filter output is 20,000.
Clustered table: A table stored sorted by a key.
Co-partitioned tables: Tables stored pre-partitioned on the same key so a join needs no network.
Combiner: A step that aggregates messages per destination before they are sent, as partial aggregation does.
Count-Min Sketch: A d × w table of counters that estimates item frequencies with overestimation proportional to total stream size.
Cuckoo filter: A membership filter storing fingerprints in a cuckoo hash table; supports deletion.
Decorrelation: Rewriting a correlated subquery into a join.
Delta: In recursive evaluation, the rows that were new in the previous round.1 other meaning →
Digest: A short fixed-width fingerprint (hash) of a row or key, used for dedup.
Distributive aggregate: An aggregate (SUM, COUNT, MIN, MAX) whose partial results combine directly.
Dot product of frequency vectors: The equijoin output size: the sum over keys of f_R(v) times f_S(v).
Enforcer: An operator (sort, shuffle, hash build, dedup) inserted to give an input a property the next operator requires.
Equivalence class: The set of different plans that give identical results.2 other meanings →
Executor: A worker process that runs part of a distributed query.A distributed engine splits a table into partitions, each processed by one executor (worker). We write P for the number of executors. Shuffle means redistributing rows over the network so that rows with the same key land on the same executor. Shuffles are expensive because every row may travel.
External sort: A sort of data larger than memory: write sorted runs to disk, then merge them.
Fan-in: The number of runs or partitions handled at once; F = M/B.1 other meaning →
Fixpoint iteration: Repeating a step until no new rows appear.
Grace hash join: A hash join that partitions both inputs to disk and joins partition pairs.
Group (algebra): A monoid in which every change can be undone (an inverse exists); needed to support deletions incrementally.
Grouping equality: Two-valued equality that treats NULLs as equal; used by GROUP BY and DISTINCT.
Grouping sets / rollup / cube: Several groupings computed in one query; cube over d columns gives 2^d.
Hash table: A structure that finds a key in roughly constant time by computing a number (the hash) from the key and jumping to that slot. Fast to build and to probe (look up). It keeps no useful order.
Heap: A tree-shaped structure that keeps only the minimum (or maximum) in place.2 other meanings →
Heavy hitter: The most frequent keys; structures such as Space-Saving track only the top k.
Holistic aggregate: An aggregate (MEDIAN, exact COUNT DISTINCT) with no bounded intermediate state.
Hot key: A key with far more rows than average.One key that receives far more traffic than others (a famous artist's tickets, one celebrity's profile). Traffic to keys is often Zipf-distributed: a few keys take most of the load.
Hybrid hash join: A hash join that keeps one partition in memory while spilling the rest.
HyperLogLog: A distinct-count sketch that keeps the longest leading-zero run per bucket; error 1.04/√m.
Incremental aggregation: Updating an aggregate with combine(state, delta) instead of recomputing it.
Indexed nested loop: A join that probes an existing index for each row of R.
Interesting order: An ordering supplied by an index that lets the plan skip a sort.
Invertible aggregate: An aggregate whose effect can be undone (SUM), allowing O(1) sliding frames.
Join: Combining rows of two tables where a condition holds, such as attaching each order to its customer. An equijoin matches on equality; a range join uses <, > or BETWEEN.Combining rows of two tables where a condition holds. orders JOIN customers ON orders.customer_id = customers.customer_id attaches each order to its customer. In this mechanism we call the two inputs R and S, with sizes |R| and |S|. An equijoin uses =. A join that uses <, > or BETWEEN is a range or inequality join.
Kahan / Neumaier summation: Compensated summation that carries a correction term to reduce floating-point rounding error.
Key expansion: The growth in size when a value (especially collated text) is encoded as a normalized sort key.
Keyset pagination: Paging by "everything after this key" instead of by count.
KLL: A mergeable quantile sketch with proven rank error.
Lateral / correlated subquery: A subquery that depends on a value from the outer row.
Load factor (α): The fraction of hash table slots in use.
Loser tree (tournament tree): A merge structure needing one comparison per level when the winner is replaced.
Mark join (null-aware anti-join): A join returning three outcomes per probe (matched, unmatched, unmatched with NULLs present), needed for NOT IN.
memcmp: Byte-by-byte, unsigned, lexicographic comparison of two memory regions.
Memory versus disk: The constraint that an operator may use only M bytes of memory; data that does not fit spills to disk, read and written in blocks, and each extra pass over it costs a full read and write.An operator may use only a limited amount of memory, which we call M. If its data does not fit, it spills: it writes pieces to disk and reads them back later. This is much slower. Disk is read and written in blocks of size B (a few megabytes). A "pass" over the data means reading it all once, and usually writing it once.
Monoid: An associative operation with an identity element (no inverse required).
Monotonic: Only increases; never goes backward.
Monotonic deque: A double-ended queue that keeps only non-dominated candidates for a sliding maximum.
NDV: Number of distinct values of a column; sizes hash aggregation memory.
Negative oracle: Using a Bloom filter only for the answer "definitely not present", with an exact check for "maybe".
Normalized key: A byte-string encoding of a sort key whose memcmp order equals the semantic order.
Null: A present field that has no value.In SQL, NULL means "unknown". A condition can be TRUE, FALSE or UNKNOWN. NULL = NULL is UNKNOWN, not TRUE. A WHERE clause keeps only rows where the condition is TRUE. This small fact causes many of the corner cases here.
Null-supplying side: The side of an outer join whose missing matches are padded with NULLs.
Optimizer: The database part that chooses a query plan using statistics and declared facts.The part of a database that chooses how to run a query. It uses statistics (row counts, distinct counts, min and max) and declared facts (such as "this column is unique") to choose a fast plan.
Out-of-core: Working with data larger than memory by using disk.
Outer join: A join that keeps all rows of one or both sides, padding missing matches with NULLs.
P: The number of executors (workers) a distributed engine runs, each processing one partition of the data at a time.A distributed engine splits a table into partitions, each processed by one executor (worker). We write P for the number of executors. Shuffle means redistributing rows over the network so that rows with the same key land on the same executor. Shuffles are expensive because every row may travel.
Partial aggregation: Aggregating rows locally before a shuffle; its state is a cache and can be dropped at any time.
Partition: One piece of a data set; each key belongs to exactly one. Partitions are the unit of parallel work and of placement, each kept as several replicas on different nodes.3 other meanings →A node is one machine (or one process) in the cluster. A replica is one copy of a piece of data. A partition (also called a shard) is one piece of the data set; each key belongs to exactly one partition. If you have 64 partitions and 3 replicas of each, the cluster holds 64 × 3 = 192 partition-replicas.
Pipeline breaker: An operator (sort, hash build) that consumes all its input before it produces output.Most operators can pass a row on as soon as they have processed it (a filter does this). Some must read all of their input before they can output anything. A sort cannot output its first row until it has seen every row. The build side of a hash join must see all its rows before probing starts. Such an operator is a pipeline breaker. A pipeline is a chain of operators that pass rows straight through, and a stage is the stretch of the plan between two breakers.
Pivot / unpivot: Turn column values into columns / turn columns into rows.
Plan: The tree of steps the optimizer chooses to compute a query's result, such as: scan orders, filter by date, join customers, sum by region. The SQL says what; the plan says how.A SQL query says what result you want, not how to get it. The optimizer (also called the planner) is the part of the database that decides how. Its output is a plan: a tree of steps. For example: scan table orders, filter by date, join with customers, sum by region.
Point mass: A single key that occurs more than N/P times; no partitioning can balance it.
Prefix rule: A sort on (a, b) also provides an order on (a).
Pure function: A function whose output depends only on its input and that has no side effects.
Radix sort: A sort that distributes records by key bytes, with no comparisons, in O(N·k).
Range partitioning: Sending each record to the node that owns its key range; makes a global merge a concatenation.
Range partitioning with replication: Splitting the value domain into buckets and copying intervals into every bucket they overlap.
Reduction factor: N/(P·G): average rows per group per partition; the benefit of partial aggregation.
Replacement selection: A heap-based run generation method giving runs of average length 2M; now mostly obsolete.
Requires / provides: The input properties an operator needs / the output properties it delivers.
Row: A table has rows (one record each, such as one scan event) and columns (one attribute each, such as weight_g). A table with n columns has n values in each row.
Run: A sorted block of data written to disk during an external sort.1 other meaning →
Salting: Adding a random suffix to a hot key so it splits into k sub-keys.
Segmented sort: Sorting within each group of an input that is already sorted on a prefix of the requirement.
Selectivity: Fraction of rows that pass a condition.The cardinality of an operator is the number of rows it produces. The selectivity of a condition is the fraction of rows that pass it. Example: a table has 1,000,000 rows and city = 'Pune' matches 20,000 of them. The selectivity is 20,000 / 1,000,000 = 0.02 (2%), and the cardinality of the filter output is 20,000.
Semi-join: A join that keeps left rows having at least one match on the right.
Semi-naive evaluation: Recursive evaluation that joins only the previous round's new rows.
Shuffle: Moving rows between stages so that data is partitioned by a different key.Two stages of a parallel query often need the data grouped by different keys. The shuffle moves every row from the machine that produced it to the machine that needs it. It is the most expensive data movement in a distributed engine.
Sideways information passing (runtime filter): Sending a summary of build-side keys to the probe-side scan to drop rows early.
Sketch (HyperLogLog): A small summary of a data set that answers one kind of question approximately.A quantile is a percentile: the value below which a given fraction of data falls (the median is the 50% quantile). A sketch is a small, fixed-size summary of a huge dataset that answers one kind of question approximately: for example a t-digest or KLL sketch answers quantile questions, HyperLogLog counts distinct values, and Space-Saving finds the most frequent values. A sketch is built in a single pass and uses bounded memory.
Skew: A task or partition much bigger than its peers.2 other meanings →A column is skewed when some values are far more common than others. In a Zipf distribution, the most common value is about twice as common as the second, three times as common as the third, and so on. Web data, names, products and customers are often Zipf-like. A key is hot when it has far more rows than average.
Skew splitting: Detecting oversized partitions at run time and splitting them while broadcasting the other side.
Snapshot: A frozen consistent view of the database at one moment.1 other meaning →A lock makes other transactions wait while you use a row. A snapshot is a frozen, consistent view of the database as it was at one moment; with it, readers do not need locks, because they read old versions while writers create new ones. This second idea is called MVCC (multi-version concurrency control): the database keeps several versions of each row. Both are mechanisms. This mechanism is about the promises they are used to keep.
Sort-merge join: A join that sorts both inputs on the key and walks them together.
Sorting: Putting rows in key order costs O(n log n) comparisons. Sorted data has a useful property: equal keys sit next to each other.
Space-Saving: A heavy-hitter algorithm that evicts the minimum counter and adopts its count plus one.
Spill: Writing operator state to disk and continuing with a different algorithm, instead of failing.A hash join matches rows of two tables by building an in-memory hash table from the smaller side (the build side) and looking up each row of the other side. A sort orders rows. Both need memory proportional to their input. When there is not enough memory, a good engine writes some of its working data to temporary files on disk and reads it back later. This is called spilling. Part 5 explains it fully; Part 1 only names it.
Splitters: The key values that divide key space into ranges in range partitioning.
Streaming: An operator that handles each row and passes it on at once, holding almost nothing, as opposed to a blocking operator that must collect its input first.1 other meaning →A streaming operator handles each row and passes it on at once, holding almost nothing. A blocking operator must collect input before it can produce output (a sort, for example). A blocking operator is also called a pipeline breaker, because the flow of rows through the plan stops there.
Streaming operator: An operator that handles each row and passes it on with O(1) state.
t-digest: A quantile sketch with small clusters near the extremes, giving good tail accuracy without proofs.
Table: Rows of records with named columns. Keys identify rows, and foreign keys link a row to a row in another table.A table has rows (one record each) and columns (one named field each). A primary key is a column (or set of columns) that identifies one row. A foreign key (FK) is a column that holds the primary key of a row in another table. A join matches rows of two tables by key. Example: order_lines.product_id is a foreign key to products.product_id.
Three-valued logic: Logic with TRUE, FALSE and UNKNOWN; comparing with NULL gives UNKNOWN.In SQL, NULL means "unknown". A condition can be TRUE, FALSE or UNKNOWN. NULL = NULL is UNKNOWN, not TRUE. A WHERE clause keeps only rows where the condition is TRUE. This small fact causes many of the corner cases here.
Top-N: ORDER BY ... LIMIT k, done with a size-k heap.
Two-phase aggregation: Partial aggregation, a shuffle of partials by group key, then a final merge.
UDF: User-defined function; opaque to the optimizer.
Watermark: Declared non-decreasing lower bound on the event times of future arrivals.1 other meaning →Every event carries a timestamp of when it happened (event time), which differs from when the job sees it (processing time). Events arrive late and out of order: a phone with no signal sends its events 5 minutes after they happened. A watermark is a marker flowing through the stream that says "no event with a timestamp earlier than T should arrive any more." It is the job's best guess of how complete the input is. When the watermark passes the end of a time period, the job may treat that period as complete. Watermarks are a guess, and late events can still violate them. The rules of when it is correct to emit a result (event time versus processing time, how late is too late) are a topic of their own. In this mechanism we need only the idea above. We study the machinery that holds data until the watermark allows an answer.
Window function: A function computed per row over a related set of rows without collapsing them.
Zipf: A skewed distribution in which the most common value is about twice as common as the second, three times as common as the third, and so on. Web traffic, names, products and customers often follow it.A column is skewed when some values are far more common than others. In a Zipf distribution, the most common value is about twice as common as the second, three times as common as the third, and so on. Web data, names, products and customers are often Zipf-like. A key is hot when it has far more rows than average.
Zipf distribution: A distribution where the r-th most common value has frequency about 1/r of the top one.In many workloads a few items are requested very often and most items are requested rarely. Zipf's law says the item of popularity rank i (rank 1 is the most popular) is requested with frequency proportional to i^(−α). The number α (alpha) is the popularity exponent. A larger α means a steeper concentration on the top items.