Glossary

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

Access path selection: Choosing how to read a table: full scan, index scan, index-only scan or bitmap scan.
Adaptive query execution (AQE): Revising some plan decisions at a barrier, using measured sizes instead of estimates.
Aggregate decomposability: Property that a partial aggregate can be combined (SUM, COUNT yes; AVG, COUNT DISTINCT only with extra data).
Aggregate pushdown: Computing an aggregate at the source or from metadata so that fewer rows move.
Amplification of an error: If an estimate is wrong by a factor of 10 ("ten times too small"), we call that a ratio error. Ratio errors multiply. This is the core of Part 1.
Anti-join: A join that keeps left rows with no match on the right.
AST: Abstract syntax tree: the parsed form of the SQL text.
Auto-analyze: Background job that refreshes statistics when enough rows have changed.
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 →
Binding (early/late): Fixing a decision; early binding is before seeing the data, late binding is after.
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: Sending the whole (small) input to every consumer, which avoids shuffling the other side.
Bushy plan: Join tree where joins can take other joins as inputs.
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.
Cascades / Volcano (optimizer): Rule-based search framework that keeps all alternative plans in one memo.
Catalog: The service that knows which tables exist, where they are and their definitions.A catalog is the service that knows which tables exist and where they are. A metastore is the database inside (or behind) a catalog that stores table definitions, partitions and file lists. Compare it with a library card index: it tells you where each book sits and which books exist, without opening any book.
CNF: Conjunctive normal form: conditions joined by AND, each possibly containing ORs.
Compaction: Rewriting many small files into fewer larger ones.An LSM-tree (Log-Structured Merge tree) is a storage structure that never changes files in place. It collects writes in memory, writes them as sorted, immutable files, and later compacts (merges and rewrites) the files in the background to remove old versions and deleted entries. A tombstone is a marker that says "this key was deleted"; compaction removes the key and the marker. Compaction costs disk and CPU. Write amplification is the ratio of bytes the storage actually writes to bytes the application asked to write. A Bloom filter is a small structure that answers "definitely not in this file" or "maybe in this file", so reads can skip most files.
Confluence: Property that rule application order does not change the final result.
Constant folding: Computing constant expressions once at plan time instead of per row.
Containment (join assumption): Whether every result of one query is a result of another; undecidable for full SQL.
Copy-on-write: Writing a new copy of a unit and swapping a pointer instead of changing the old bytes.Two ways to handle a delete or update in immutable storage. Copy-on-write: rewrite the whole data file without the deleted rows. Merge-on-read: write a small side file (a delete vector or tombstone, a note that says "row 17 of file X is deleted") and let every reader apply it. Copy-on-write makes writes costly and reads clean. Merge-on-read makes writes cheap and every read does extra work.
Correlated subquery: Subquery that refers to a column of the outer query.
Cost model: Function that turns a plan and estimated sizes into a number used to rank plans.
Count bug: Wrong answer when a correlated COUNT subquery is turned into a left join (0 versus NULL).
CTE: Common table expression: a named sub-result written with WITH.A view is a saved query with a name; using it in another query means that query's text is pasted in. A CTE (common table expression) is a named sub-result written with WITH name AS (...). A subquery is a query inside a query. A correlated subquery refers to a column of the outer query, so it seems to run once per outer row.
Data skipping: Avoiding reads of blocks that statistics prove cannot match.
Decorrelation: Rewriting a correlated subquery into a join.
Deletion vector: A compact bitmap of dead row positions, stored beside an immutable file.
Dictionary encoding: Replacing each value by a small integer index into a table of distinct values.
DP cliff: The point (about 12-15 relations) where dynamic programming over join orders becomes impractical.
Dynamic partition pruning: Pruning partitions using values found while running the query, usually join keys.
Dynamic programming (DP): Search that builds best plans for subsets of relations from smaller subsets, solving each once.
Early / late materialization: Building full rows before filtering, or filtering first and fetching other columns afterward.
Enforcer: An operator (sort, shuffle, hash build, dedup) inserted to give an input a property the next operator requires.
Equi-depth histogram: Histogram whose buckets each hold about the same number of rows.
Equi-width histogram: Histogram whose buckets cover equal value ranges.
Equivalence class: Set of columns known to be equal; used to infer new predicates.2 other meanings →
Estimate versus actual: Before running the query the optimizer estimates the cardinality of every operator. After running, the engine knows the actual count. EXPLAIN shows the plan with estimates. EXPLAIN ANALYZE runs the query and shows estimates and actuals side by side:
Exchange (shuffle): Sending rows over the network so equal keys meet on one machine.
EXPLAIN / EXPLAIN ANALYZE: Show the plan; run the query and show estimates and actual numbers.
Extended statistics: Statistics on column groups, built to capture correlation.
Fixpoint: State in which applying the rules again changes nothing.
Footer: Metadata at the end of a file, such as a directory of offsets and statistics.
Foreign key: Constraint that every value in a column exists in a column of another table.Rules a database can enforce. A primary key says each row has a unique, non-null identifier. A unique constraint says no two rows share a value. A foreign key says a value must exist in another table (for example every orders.customer_id must exist in customers). A check constraint says a row must satisfy a predicate.
Functional dependency: One column's value determines another's.
Generic plan: A cached plan made without looking at the parameter value, based on average selectivity.
GEQO: PostgreSQL's genetic join-order search, used above geqo_threshold; nondeterministic.
Greedy search: Join-order method that repeatedly picks the best-looking next join, with no guarantee.
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.
Heap: A tree-shaped structure that keeps only the minimum (or maximum) in place.2 other meanings →
Hidden partitioning: Declaring a partition as a transform of a data column so the optimizer can map predicates to partitions.
Histogram: A metric that counts observations per bucket; can be summed across instances.
HyperLogLog: A distinct-count sketch that keeps the longest leading-zero run per bucket; error 1.04/√m.
Interesting order: An ordering supplied by an index that lets the plan skip a sort.
Interpreter / JIT compilation: Executing a plan by walking operators versus generating machine code for the plan.
Join elimination: Removing a join that constraints prove has no effect on the result.
Left-deep plan: Join tree in which each join's right input is a base table.
Logical plan: Algebraic form of the query, closed under equivalence-preserving rewrites.
Materialized view: A stored query result that the system refreshes, with its admission declared.A query result that is saved as a table and kept up to date, instead of being recomputed each time it is read.
Memo: Data structure holding groups of equivalent plans, used for search and sharing.
Merge join: A join of two sorted inputs in O(n + m) time and O(1) memory.
Merge-on-read: Writing small deltas and combining them with the base at read time.Two ways to handle a delete or update in immutable storage. Copy-on-write: rewrite the whole data file without the deleted rows. Merge-on-read: write a small side file (a delete vector or tombstone, a note that says "row 17 of file X is deleted") and let every reader apply it. Copy-on-write makes writes costly and reads clean. Merge-on-read makes writes cheap and every read does extra work.
Metadata-only answer: Answering a query from stored statistics without reading data.
Min/max statistics: The smallest and largest value of a column in a block, used to decide skipping.
NDV: Number of distinct values of a column; sizes hash aggregation memory.
Nested loop join: Join that looks up matches for each row of one input; good for few rows, bad for millions.
Nested-field pruning: Reading only one sub-field of a nested column.
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-rejection: A condition that is not TRUE for NULL, which allows an outer join to become an inner join.
Operator fusion: Merging operators into one loop, removing the boundary between them.
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.
Optimizer / planner: The component that chooses the plan for a query.
Ordinal cost: Cost that is valid only for ranking plans, not as a prediction.
Parameter sniffing: Building a cached plan for the first parameter value and reusing it for others with different row counts.
Parquet: Column-oriented file format with row groups, pages and a footer.Object storage (like Amazon S3) stores whole files called objects behind HTTP requests. Parquet is a file format that stores data column by column. A table format (such as Iceberg or Delta) records, in small metadata files called manifests, which data files make up a table. A snapshot is one exact version of the table, identified by a snapshot id. A catalog is the service that tells you the current snapshot of a table.
Partition pruning: Skipping partitions that cannot match the query's filter.A zone map stores the minimum and maximum of a column for each block of rows. If your range does not overlap a block's min/max, you skip the block without reading it. Partition pruning is the same idea at table level: a table is split into partitions by a key (for example by date), and the engine skips partitions that cannot match. Both rely on values being comparable, so that "min" and "max" mean something.
Partitioning: A big table can be split into pieces (partitions), here one per day. If a query filters on the date, the engine can skip the partitions that cannot match. This is called partition pruning.
Phase-ordered optimizer: Optimizer that runs all rewrites to a fixpoint, then plans (as opposed to unified search).
Physical plan: Plan with concrete algorithms (hash join, index scan).
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.
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.
Plan vocabulary: Plan trees are made from a few kinds of steps (called operators):
Position list / selection vector: An array of row positions that passed a filter.
Predicate pushdown: Moving a filter earlier in the plan, closer to the data.
Principle of optimality: Claim that the best plan for a set can be built from the best plans for its subsets.
Projection pushdown: Reading only the columns the query needs.
Pruning: Skipping whole partitions or files using metadata.A columnar file format (such as Parquet) stores each column of a table separately, so a query that needs 5 of 200 columns can read only those 5. Partitioning splits a table into folders (for example, one per day). Pruning (or skipping) means not reading the parts a query cannot need. Selectivity is the fraction of data a query actually needs.
Query: A request for data, in SQL a statement of what result is wanted. The optimizer decides how to compute it and turns it into a plan.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.
Residual filter: A filter the source did not apply, which the engine must still apply.
Result cache: Stored results of earlier queries, reused when the same query recurs and inputs have not changed.
Row group: A block of rows (for example 128 MB) that is the unit of independent metadata and rewrite.
Runtime filter: A filter built during execution (from join keys) and applied to a scan.
Sampling: Keeping only a fraction of events.1 other meaning →
Sargable: In the form column op constant, so it can reach an index or partition filter.
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.
Semantic caching: Reusing a cached result for a different but contained query by applying a residual filter.
Semi-join: A join that keeps left rows having at least one match on the right.
Snapshot id / version token: A value that changes whenever a table's data changes, allowing a cheap freshness check.
Star schema: A fact table surrounded by dimension tables.A big central fact table (orders) with foreign keys pointing to many small dimension tables (customers, stores, ...). A foreign key (FK) says that every value in a column exists in a column of another table. A unique constraint says that no value repeats.
Statistics: Per-column summaries (NDV, histogram, most common values) used for estimates.The database cannot look at all data for every query, so it keeps a small summary per column, built by a command (ANALYZE) that reads a sample. The summary includes the number of distinct values (NDV), the most common values, and a histogram (a list of ranges, called buckets, with roughly how many values fall in each). The optimizer uses these statistics to produce its estimates. The collection of tables, columns, constraints and statistics that the database knows about is its catalog (or system catalog).
Subqueries: Queries nested inside another query. A correlated subquery refers to a column of the outer query, so it seems to run once per outer row unless the optimizer rewrites it as a join.A view is a saved query with a name; using it in another query means that query's text is pasted in. A CTE (common table expression) is a named sub-result written with WITH name AS (...). A subquery is a query inside a query. A correlated subquery refers to a column of the outer query, so it seems to run once per outer row.
Subsumption (view matching): Proving that a query can be answered from a stored view.
System R constants: Default selectivities (1/10, 1/3, 1/4) used when statistics are missing.
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 pushdown: Using a bounded heap for ORDER BY ... LIMIT k so only k items are kept.
Uniformity assumption: The assumption, built into partitioners, that keys spread evenly.
Value list (skipping): A per-block list of the distinct values of a low-cardinality column.
Vectorized execution: Processing batches of values per function call.
Views: Saved queries with a name. Using a view in another query pastes its text in, so the optimizer plans the combined query.A view is a saved query with a name; using it in another query means that query's text is pasted in. A CTE (common table expression) is a named sub-result written with WITH name AS (...). A subquery is a query inside a query. A correlated subquery refers to a column of the outer query, so it seems to run once per outer row.
Volatility (IMMUTABLE/STABLE/VOLATILE): A function's declared stability, which decides whether a query using it may be cached.
Zone map: Per-file min and max values of a column, used to skip files.A zone map stores the minimum and maximum of a column for each block of rows. If your range does not overlap a block's min/max, you skip the block without reading it. Partition pruning is the same idea at table level: a table is split into partitions by a key (for example by date), and the engine skips partitions that cannot match. Both rely on values being comparable, so that "min" and "max" mean something.