Glossary

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

ANN (approximate nearest neighbor): Search that returns neighbours that are probably, not certainly, the closest.
Bitmap heap scan: PostgreSQL plan step that builds a temporary bitmap from index scans and visits table pages in physical order.
Bitmap index: For each distinct value, a bit vector with one bit per row; predicates become boolean operations on words.
Block-max WAND / WAND: Algorithms that skip scoring documents that cannot reach the current top-k, using score upper bounds.
BRIN: PostgreSQL's block-range index: a tiny min/max summary per range of pages.
Buffer pool: The database's own RAM area holding copies of disk pages, with dirty and pinned frames.A database stores tables in files, cut into fixed-size pages (typically 8 KB; do not confuse them with 4 KB virtual-memory pages). A buffer pool is the database's own area of RAM that holds copies of such pages. Each slot in the pool is a frame. A hit means the page is already in a frame. A miss means it must be read from disk. The hit rate is hits ÷ accesses. A page changed in memory but not yet written to disk is dirty. The working set is the set of pages the workload keeps coming back to.
Bε-tree (fractal tree): A B-tree whose nodes reserve space for buffered updates; a continuum between B-tree and LSM.
Cardinality: The number of distinct values a label can take. The series count is the product over all labels.2 other meanings →The number of distinct things in a set. "20 million files" is a statement about cardinality. Metadata size follows cardinality (how many objects), not bytes.
Cardinality estimation: The planner's guess of how many rows a predicate or operation returns.
Clustered index / index-organized table: A table stored inside a B-tree sorted by the key, so rows and index are one structure.
Clustered storage: In a heap table, rows are stored in any order, wherever there is space. In a clustered (or index-organized) table, the rows are stored inside a B-tree sorted by the primary key, so the table is an index.
Collation: The rules for comparing and sorting text; different rules give different orders.
Composite index: An index on a tuple of several columns, ordered lexicographically.
Correlation (statistic): A measure of how closely a column's values follow the physical row order.
Covering index: An index containing every column a query needs, allowing an index-only scan.
Cracking: Building an index gradually as a side effect of running queries.
Curse of dimensionality: In high dimensions, distances concentrate and "nearest" loses meaning, so pruning fails.
Dead index entry / index bloat: Entries pointing at no-longer-visible row versions; an index larger than its live content needs.
Derived data: Data computed from other data and kept in step with it. An index is derived from the table. Derived data can disagree with its source; keeping it true is the main running cost of an index.
Derived state: Data computed from other data and kept in step with it (an index is derived from its table).
Early binding / late binding: Index entry refers to a physical address (early) or to a logical key (late).
EXPLAIN: The SQL command that shows the plan the query planner chose (which scans, indexes and joins, and its row estimates) without, or with ANALYZE alongside, running the query.The query planner decides how to run a query: scan the whole table, or use an index, and which one. It guesses how many rows each step returns using statistics about the data. EXPLAIN shows the chosen plan. An index that exists but is not chosen costs you everything and buys you nothing.
Expression index: An index on a computed value such as lower(email).
Extended statistics: Statistics on column groups, built to capture correlation.
Fanout: Number of children per tree page: page size ÷ entry size.
Generated column: A column whose value the database computes from other columns and stores.
Geohash / S2 / H3: Discrete global grids that map a location to a hierarchical cell id.
Global secondary index: An index partitioned by the indexed column itself, so one lookup goes to one partition.
Hash index: An index that answers equality only, by hashing the key.
Heap: In a heap table, rows are stored in any order, wherever there is space. In a clustered (or index-organized) table, the rows are stored inside a B-tree sorted by the primary key, so the table is an index.2 other meanings →
Heap table: A table whose rows are stored in no particular order.
Hilbert curve / Z-order (Morton): Space-filling curves that map multi-dimensional points to one dimension.
HNSW: A layered neighbour graph that finds nearest neighbours by greedy navigation.
HOT update: A PostgreSQL optimization that keeps a new row version on the same page and skips index updates.
INCLUDE column: A payload column stored only in index leaf pages, not part of the key.
Index-only scan: A query answered from the index alone without fetching table rows.
Interesting order: An ordering supplied by an index that lets the plan skip a sort.
Inverted index: A map from each term to the list of documents that contain it.
IVF (inverted file): An index that partitions vectors into cells by centroid and probes only a few cells.
Learned index: An index that replaces a search structure with a model of the data distribution.
Leftmost prefix: The rule that a composite index serves predicates on a leading prefix of its columns.
Lexicographic order: Dictionary-style ordering of tuples: compare first column, then second, and so on.
Local secondary index: An index kept separately inside each partition, covering only that partition's rows.
Memory cliff: The step increase in cost when an index or working set no longer fits in memory.
MVCC: Keeping old versions so readers do not block writers and writers do not block readers.A technique where an update does not overwrite a row but creates a new version, so that readers who started earlier can still see the old one. Each reader works on a consistent snapshot. Old versions are removed later by a cleanup job (called vacuum in Postgres).
Nested loop join: Join that looks up matches for each row of one input; good for few rows, bad for millions.
nlist / nprobe: IVF parameters: number of clusters, and number of clusters searched per query.
Order-preserving encoding: Turning typed values into bytes so that byte order equals logical order.
Page: The fixed-size unit (commonly 4-16 KiB) read and written by storage and databases.3 other meanings →Storage hardware and databases do not read single bytes. They read fixed-size chunks called pages (or blocks), typically 4 KiB to 16 KiB on a local disk. To read one 200-byte row you must read its whole page.
Partial index: An index containing entries only for rows matching a predicate.
Partition: A set of files proven to share a value; the claim that allows pruning.3 other meanings →A table in a data lake is really a set of files. A partition is a group of files that share a value, for example all files for date = 2025-03-01. Systems often store each partition in its own folder: orders/date=2025-03-01/part-0001.parquet.
Planner (optimizer): The component that chooses how a query is executed.The query planner decides how to run a query: scan the whole table, or use an index, and which one. It guesses how many rows each step returns using statistics about the data. EXPLAIN shows the chosen plan. An index that exists but is not chosen costs you everything and buys you nothing.
Posting list: The sorted list of document ids for one term in an inverted index.
Primary key: A unique, non-null identifier for each row.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.
Product quantization (PQ): Compressing vectors by replacing sub-vectors with codebook indexes.
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.
Quadtree: Spatial tree that splits each square into four equal squares.
R-tree: Spatial tree of nested, possibly overlapping bounding boxes.
Random I/O: Reading or writing blocks scattered across storage rather than next to each other. Each access pays a fixed setup cost (a seek, a flash read, a network round trip), so it costs far more per byte than sequential I/O.Reading pages that sit next to each other is sequential and cheap per page. Reading pages scattered around is random and costs more per page, because each read pays a fixed setup cost (a disk seek, a flash read, a network round trip). The ratio of the two costs is the key number of Part 1. Call the cost of one sequential page read s and one random page read r.
Recall: Of the real defects, the fraction that were caught.Of the results returned, precision is the fraction that is correct. Of all the correct answers that exist, recall is the fraction you returned. If 10 items are truly relevant and you return 8 of them among 20 results, recall = 8/10 = 80% and precision = 8/20 = 40%.
Roaring bitmap: A bitmap index that stores each 65,536-row chunk as an array, a bitmap or runs, whichever is smallest.
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 stretch of neighboring index entries readable in one sequential pass.1 other meaning →
s/r ratio: Cost of sequential access divided by cost of random access; sets the index crossover.
Scatter-gather: Fanning a request out to N shards and waiting for their answers.To query a dataset split over many machines (shards), a coordinator sends the query to the shards (scatter) and merges the answers (gather). The query is finished only when the slowest shard answers, so the latency of the whole is the maximum over shards. Slow outliers (the "tail", measured by percentiles such as p99, the time that 99% of requests beat) therefore hurt more as you add shards.
Secondary index: Any index other than the primary key's.The primary key (PK) uniquely identifies a row. A secondary index is any additional index on other columns.
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.
Sequential: Reading or writing one place after another, like appending to a file. It avoids the per-access cost of jumping around, so it is far cheaper than random I/O, especially on spinning disks.Sequential means writing one place after another (like appending to a file). Random means jumping between different places. On a hard disk, each jump costs a mechanical move of about 5–10 ms. On flash, random writes are also more costly. Sequential is much cheaper.
Shard: A partition is a slice of a table, split by some key (for example by date). A shard is a partition placed on a different machine.1 other meaning →
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.
Skip list: A sorted linked list with random-height express pointers; lock-free inserts need no rebalancing.
Skip pointer: Entry in a posting list that lets a search jump ahead over many postings.
Skip scan: Technique that enumerates distinct values of a leading column to use a composite index without a predicate on it.
Sparse index: An index with one entry per group of rows (granule) instead of per row.
Stopword: A very common word whose posting list covers most documents.
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.
TID: PostgreSQL tuple identifier (block, offset): a physical row address.
Tombstone: A marker record that says a key was deleted; must outlive every older copy.
Top-k early termination: Stopping a search once no remaining candidate can enter the top k.
UUIDv4 / UUIDv7 / ULID: Random identifiers (v4) versus time-ordered identifiers (v7, ULID).
Visibility map: PostgreSQL's per-page record of "all versions visible", used by index-only scans.
Write amplification: Bytes written per byte of user data.If you write 1 MB of data and the system physically writes 10 MB (because of rewriting and merging), the write amplification is 10.
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.
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.