Glossary

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

Actor model: A design where each actor owns private state and one mailbox, processes one message at a time, and talks to others only by messages.
Adaptive compilation: Starting a query in an interpreter, compiling in the background, and switching when the compiled code is ready.
Adaptive partition splitting: After the producing stage, assigning several consumer tasks to byte ranges of one oversized partition.
All-to-all exchange: A shuffle where each of M producers sends to each of R consumers: M × R connections.
Associative: An operation where grouping does not matter, such as sum or max; it allows partial results to be combined.An operation is associative if grouping does not matter: (a + b) + c = a + (b + c). Sum, count, min and max are associative. This means you can add up pieces separately and then add the partial sums. Average and median are not associative in this plain form.
Backpressure: A signal from a consumer, based on its actual state, that makes the producer slow down.If a slow step cannot keep up, it tells the step before it to slow down, and that step tells the one before it, until the source stops reading. We study this in Part 8.
Barrier: A point where all workers must arrive before any may continue.1 other meaning →
Batch-at-a-time: Passing many tuples (for example 1,024) across an operator boundary in one call.
Binding time: The moment when the structure of the work is fixed: query start (compiled) or each tuple (interpreted)
Boundary: The handoff between two operators; it has a fixed cost per call.1 other meaning →
Bounded queue: A queue with a maximum length that rejects new work when full, turning waiting into a fast error.
Branch misprediction: A modern CPU guesses which way an if will go and keeps working. A wrong guess costs 15 to 20 cycles. Code with unpredictable ifs is slow.
Break-even volume: The number of tuples above which a setup cost (such as compilation) pays for itself: setup cost ÷ per-tuple saving.
Broadcast: Sending the whole (small) input to every consumer, which avoids shuffling the other side.
BSP (Bulk Synchronous Parallel): Computation in rounds (supersteps): compute, exchange messages, wait at a global barrier.
Bushy plan: Join tree where joins can take other joins as inputs.
Bytes per connection: Total shuffle bytes ÷ (M × R); compared with the substrate's minimum efficient transfer.
Cache: A small, fast memory between the CPU and main memory that holds recently used data in 64-byte lines. A miss, when the data is not there, costs about 100 ns, hundreds of CPU cycles.1 other meaning →A cache is a small, fast memory between the CPU and main memory. L1 is the smallest and fastest (about 32 KB per core). Data moves in blocks of 64 bytes called cache lines. A cache miss (the needed data is not in cache) costs about 100 ns, which is hundreds of CPU cycles.
Cache line: The 64-byte block the CPU moves between RAM and cache.Memory (RAM) is fast but small and loses its content when power is off. Storage (SSD, disk) is slower but large and permanent. Hardware never moves single bytes. It moves fixed-size blocks:
Coefficient of variation (c): Standard deviation divided by the mean; a measure of relative spread.
Cold start: The billed time to start a machine, runtime and caches before useful work.
Commit arbitration: One designated atomic act that decides which of several attempts' output counts.
Compiled execution: Generating code for one specific query so that the operator structure is resolved at compile time.
Control flow: Which party decides when the next unit of work moves.
Core: One execution unit of a CPU, which runs one thread at a time. A distributed engine runs many tasks, each one piece of a plan on one partition of the data, in parallel across cores and machines.A core is one execution unit of a CPU. A thread is a sequence of instructions that the operating system schedules onto a core. A partition is a slice of the data (for example, all rows whose key hashes to number 7). A task is "run this piece of the plan on this partition". A distributed engine runs many tasks in parallel on many cores and machines.
Credit-based flow control: A scheme where the consumer gives the producer credits for the buffers it can accept.
Critical path (span, T∞): The longest chain of dependent tasks in a DAG; the lower bound of makespan.
Data parallelism: The same operator running on disjoint partitions of the input.
Data-centric compilation: Compiling a pipeline so that each tuple is pushed through as many operators as possible before a pipeline breaker.
Dataflow / DAG execution: A plan held as a graph of stages by a scheduler, with materialized or streamed edges.
Decomposable operator: An operator that can be computed as partition, compute locally, merge; it is gated by associativity.
Degree of parallelism (DOP): The number of workers or tasks running one stage at the same time.
Dependency idleness: Time a unit waits for its producer.
Deque (work-stealing): A double-ended queue owned by one worker; the owner uses one end and thieves take from the other.
Dispatch cost: The fixed cost of starting a task: scheduler round trip, serialization, process start.
Dynamic scheduling: Assigning each task when a worker becomes free, using observations.
E[max] / E[mean]: The ratio of the expected slowest task to the average task; about 1 + c·√(2 ln n) for light tails.
Elastic parallelism: Changing the number of workers as load or data size changes.
Exchange operator: A plan node that repartitions data between stages; the only node that knows parallelism exists.
Exclusion idleness: Time a unit waits for a shared resource such as a lock or a hash table.
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.
Failure rate: If a machine task fails at rate λ per task-hour, then running n tasks for T hours each gives an expected n × T × λ failures.
Fixed cost: A cost paid once per operation regardless of its size, such as a call, a task launch or a compilation.
Flow control: The ability of a consumer to refuse or slow down incoming work.
Function call: Jumping to a function and returning, a few CPU cycles. A virtual (indirect) call goes through a table of addresses, so the CPU often mispredicts it and the compiler cannot inline it, which makes it costly in hot loops.Calling a function costs a few CPU cycles (the CPU saves where it was, jumps, and returns). A virtual call (also called an indirect call) jumps through a table of function addresses, because the target is not known until the program runs. The CPU often cannot predict where it will land, and the compiler cannot merge the called code into the caller (inlining). Both facts make virtual calls costly.
Granularity is the floor on adaptivity: No mechanism can correct an imbalance smaller than the unit it schedules.
Hash aggregate: An aggregation that keeps one running total per group key in a hash table, updating it as each row arrives.A hash table finds a value by key in about one step. A hash join loads one input (the build side) into a hash table and looks up each row of the other input (the probe side). A hash aggregate keeps one running total per group key in a hash table.
Hash join: Join that builds an in-memory hash table from one input and probes it with the other.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.
Hash shuffle: A shuffle where each producer writes one file per consumer, giving M × R files.
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.
Heavy-hitter separation: Detecting hot keys with a sketch and sending them down a broadcast path while the rest use normal hashing.
Imbalance idleness: Time a unit waits for a slower peer at a barrier or join point.
Incast: Synchronized many-to-one traffic that overflows a switch buffer and causes timeouts.
Indirect (virtual) call: A call whose target is looked up at run time; hard to predict and to inline.
Inlining: Merging the body of a called function into its caller, which allows further optimization.
Inter-operator parallelism: Parallelism across operators: pipeline plus task parallelism.
Interpreted execution: A generic operator reads the plan at run time and handles any query.
Intra-operator parallelism: Parallelism inside one operator, by partitioning its input.
Iterator model (Volcano): Pull-based execution where each operator has open/next/close and returns one tuple per next call.
L1 cache: The smallest and fastest per-core cache, about 32 KB.
Latency: Time one operation takes from request to response.Throughput is work finished per second. Latency is how long one operation takes. Little's Law links them to the number of operations in progress: L = λ × W, where λ is the arrival rate (per second), W is the average time one operation spends in the system, and L is how many are inside the system at the same time. Example: 1,000 requests per second, each taking 20 ms (0.02 s), means 1,000 × 0.02 = 20 requests in flight at any moment. This is an identity, not a design choice.
Little's Law: L = λW: average items in a system = arrival rate × average time in the system.Throughput is work finished per second. Latency is how long one operation takes. Little's Law links them to the number of operations in progress: L = λ × W, where λ is the arrival rate (per second), W is the average time one operation spends in the system, and L is how many are inside the system at the same time. Example: 1,000 requests per second, each taking 20 ms (0.02 s), means 1,000 × 0.02 = 20 requests in flight at any moment. This is an identity, not a design choice.
Mailbox: The queue of incoming messages of an actor.
Map-output tracker: A registry mapping each shuffle partition to its locations and offsets.
Map-side combine: Partial aggregation on the producer before data is shuffled.
Materialized edge: A stage output that is written out and can be read again, so a consumer task can be retried.
Maximum: If many tasks must all finish before the next step can start, the step takes as long as the slowest task. The slowest of many is usually much worse than the typical one. The slowest tasks are called stragglers.
Memory-level parallelism: Having many cache misses outstanding at once so their waiting times overlap.
Minimum efficient transfer (b_min): The transfer size at which a storage substrate delivers about half its peak bandwidth.
Morsel: A small chunk of input (10⁴ to 10⁵ tuples) that one thread processes through a whole pipeline.
Morsel-driven parallelism: One permanent thread per core taking morsels from a queue, so the thread owns the plan.
MPP (massively parallel processing): An engine design that streams rows between parallel stages and restarts a whole query on failure.
n × T × λ: Expected failures per attempt: tasks × duration × failure rate per task-hour.
Object storage: A cloud service holding named objects fetched by HTTP, replaced whole, never edited.A cloud service where each file ("object") has a name and is fetched with an HTTP request. A request costs 20-100 ms before the first byte arrives, and the provider charges a small fee per request. You cannot change a few bytes inside an object. You replace the whole object.
Operator: One step of a query plan: scan, filter, project, join, aggregate. Rows flow from the scans at the bottom of the plan to the final operator at the top.A SQL query is turned into a plan: a tree or graph of steps. Each step is an operator: scan (read a table), filter (keep rows that match a condition), project (compute columns), join (combine two tables), aggregate (sum, count, group). A tuple is one row as seen by an operator. Data flows from the scanning operators at the bottom to the final operator at the top.
Over-partitioning: Using many more partitions than workers so that adding a worker only means handing out more partitions.
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.
Partition function: The rule that assigns a row to a consumer (hash, range, round-robin)
Pipeline: A chain of operators that pass tuples straight through without waiting for all input.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.
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.
Pipeline parallelism: Different operators working on different data at the same time.
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.
Pull-based execution: The consumer asks the producer for the next tuple.
Push-based execution: The producer runs the loop and calls the consumer for each tuple.
Push-based shuffle: A shuffle where producers send blocks to a service that merges them per partition.
Range partitioning: Sending each record to the node that owns its key range; makes a global merge a concatenation.
Request pricing: Cloud object stores (such as Amazon S3) hold files called objects and answer HTTP requests. Each request has a time floor (tens of milliseconds) and a price (roughly $5 per million write requests), however small the object is.
Reservoir sampling: A one-pass uniform random sample of k items from a stream of unknown length.
Resumable operator: An operator that can be suspended after each tuple and continue later; it needs its state in an object, not in registers.
Round-robin partitioning: Dealing rows to consumers in turn; balanced but without key co-location.
Salting: Adding a random suffix to a hot key so it splits into k sub-keys.
Selection vector: A list of the positions in a batch that passed a filter.
Serverless: Running each task as a short-lived function started by the platform, with no direct worker-to-worker network.
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.
Shuffle file consolidation: Letting tasks on one executor append to shared per-partition files, so files number E × R.
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.
Sort shuffle: A shuffle where each producer writes one file plus an index of R offsets, using a counting pass by partition id.
Speculative execution: Launching a duplicate of a slow-looking task and taking whichever attempt finishes first.
Spill amplification: The number of times shuffle bytes are written during map-side spill and merge: 1 + ⌈log_k(S_task/B)⌉.
Stage: The stretch of a plan between two pipeline breakers.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.
Static scheduling: Assigning tasks to workers before execution, using estimates.
Straggler: A task much slower than its peers.
Superstep: One round of a BSP computation.
Tail (a log): The slowest requests, such as those above p99.p50 is the median latency, p99 is the latency that 99% of requests beat. The slowest requests are the tail. When one request needs answers from many servers (a fan-out) it must wait for the slowest one. With 100 servers that each have a 1% chance of being slow, the chance that at least one is slow is 1 − 0.99¹⁰⁰ = 63%. So the user-facing tail is much worse than any single server's tail.
Task: One step of a workflow.A workflow (also pipeline or DAG run) is a set of steps that must happen in a certain order. A task is one step: "run this SQL", "start this Spark job", "call this API". The orchestrator does not do the work itself. It tells another system to do it.
Task parallelism: Independent subtrees of a plan running concurrently.
The queue formula: For one server with random arrivals, response time ≈ S / (1 − ρ), where S is the time of one job alone and ρ the utilization: 2S at half load, 10S at 90%, 100S at 99%.Utilization ρ is the fraction of time a server (a core, a disk, a queue worker) is busy. Near full load, waiting time explodes: response time is about S / (1 − ρ), where S is the time of one job alone. At ρ = 0.5 it is 2S; at ρ = 0.9 it is 10S; at ρ = 0.99 it is 100S.
Thread: A sequence of instructions the operating system schedules onto a CPU core. Threads of one process share its memory.A core is one execution unit of a CPU. A thread is a sequence of instructions that the operating system schedules onto a core. A partition is a slice of the data (for example, all rows whose key hashes to number 7). A task is "run this piece of the plan on this partition". A distributed engine runs many tasks in parallel on many cores and machines.
Throughput: Work completed per unit of time.Throughput is work finished per second. Latency is how long one operation takes. Little's Law links them to the number of operations in progress: L = λ × W, where λ is the arrival rate (per second), W is the average time one operation spends in the system, and L is how many are inside the system at the same time. Example: 1,000 requests per second, each taking 20 ms (0.02 s), means 1,000 × 0.02 = 20 requests in flight at any moment. This is an identity, not a design choice.
Tiering: Starting with a cheap method and switching to an expensive faster one once the work is known to be large.1 other meaning →
Tree-structured exchange: An exchange with intermediate combining levels; legal only for associative reductions.
Tuple: One row as seen by an operator.A SQL query is turned into a plan: a tree or graph of steps. Each step is an operator: scan (read a table), filter (keep rows that match a condition), project (compute columns), join (combine two tables), aggregate (sum, count, group). A tuple is one row as seen by an operator. Data flows from the scanning operators at the bottom to the final operator at the top.
Tuple-at-a-time: Passing a single tuple across each operator boundary.
Uniformity assumption: The assumption, built into partitioners, that keys spread evenly.
Utilization (ρ): The fraction of time a resource is busy.Utilization (ρ, "rho") is the fraction of time a server is busy. For random arrivals, average response time grows like S ÷ (1 − ρ), where S is the service time: 2×S at 50%, 5×S at 80%, 10×S at 90%, 100×S at 99%. Queues are caused by variability meeting load, and the curve has a wall at 100%. The last few percent of utilization cost more than the first eighty.
Vectorized execution: Processing batches of values per function call.
Virtual call: A call through a table of function addresses, because the target is known only at run time. The CPU often mispredicts it and the compiler cannot inline it, so it is costly in hot loops.Calling a function costs a few CPU cycles (the CPU saves where it was, jumps, and returns). A virtual call (also called an indirect call) jumps through a table of function addresses, because the target is not known until the program runs. The CPU often cannot predict where it will land, and the compiler cannot merge the called code into the caller (inlining). Both facts make virtual calls costly.
Width ceiling: The largest useful shuffle width, M = R ≤ √(S/b_min)
Work and idleness (the reframe): The view that elapsed time = work ÷ the capacity actually kept busy.
Work stealing: Idle workers take tasks from a randomly chosen busy worker's queue.
Work-span bound: T_p ≥ max(T₁/p, T∞)
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.