Glossary

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

Access unit: The fixed chunk (page, block, request) the hardware or service reads in one operation.
Adjacency: Which values are stored next to which; exclusive, since a byte has one address.
AM-GM inequality: The arithmetic mean of positive numbers is at least their geometric mean; a sum with a fixed product is smallest when the terms are equal.
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.
ARC: Adaptive Replacement Cache: self-tuning policy with recency and frequency lists plus ghost lists.
Bandwidth: Bytes (or bits) moved per second.Latency is how long one operation takes before the first byte arrives. Bandwidth (also throughput) is how many bytes arrive per second after that. A truck driving 500 km has a high latency (many hours) and may still carry a huge amount: high bandwidth.
Bit-packing: Storing every value of a block with the same fixed number of bits.
Block: The unit compressed independently; sets ratio, read amplification, blast radius and parallelism.1 other meaning →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.
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.
Bucketing: Hash-partitioning two tables by the join key into the same number of buckets, so a join needs no shuffle.
Bytes touched / bytes needed: The one ratio of this mechanism; the amplification of a read.
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.
Characteristic size: Latency × bandwidth: the request size at which time spent waiting equals time spent transferring.
Clustered table: A table stored sorted by a key.
Clustering: Arranging rows physically so that units can be skipped for a given predicate.
Clustering depth: For a value, how many units' [min, max] ranges could contain it. A measure of clustering quality.
Clustering payoff: The gain from clustering, about min(G, 1/s).
Column: One named field of a 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.
Column chunk: The piece of a row group that holds one column.
Column family: A group of columns declared together in the schema and stored together with its own policy.
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.
Compaction interval (tau*): The cost-minimizing time between compactions, sqrt(bU / (a w)).
Compare-and-swap (CAS): An atomic instruction that updates a variable only if it still has the expected old value.A lock or latch lets only one thread enter a piece of code or data at a time (a latch is a short lock inside a database). CAS (compare-and-swap) is one CPU instruction: "set this variable to new only if it still equals old". It either succeeds or fails and never blocks. Lock-free algorithms are built from it.
Composite-key rule: In a sort key (a, b), b helps only if the cardinality of a is at most the number of units (C_a ≤ U).
Compression: A program that turns data into fewer bytes. The compression ratio r = original size ÷ compressed size. If 100 MB becomes 25 MB, r = 4. Lossless compression gives back exactly the same bytes; everything here is lossless.
Conserved-cost rule: A design that seems to remove a cost has moved it to another party or time.
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.
Deletion vector: A compact bitmap of dead row positions, stored beside an immutable file.
Delta encoding: Storing differences between consecutive values instead of the values.
Dictionary encoding: Replacing each value by a small integer index into a table of distinct values.
Direct I/O (O_DIRECT): Reading and writing that bypass the operating system's page cache; needs aligned requests.
Document layout: Self-describing records that carry their own field names and types.
DSM (decomposition storage model): Columnar layout: each attribute stored as its own sequence.
Encoding (versus compression): A structure-aware, queryable representation; a codec is opaque and needs decompression.Compression makes data smaller. Generic compressors (gzip, LZ4) look for repeated byte patterns. Encodings are simpler, type-aware tricks, for example dictionary encoding (store each distinct value once, then store small numbers that point into the dictionary), run-length encoding (RLE) (store "India x 5,000" instead of five thousand copies), delta encoding (store the difference from the previous value) and bit-packing (use only as many bits per value as the largest value needs).
Equality delete: A delete that names a predicate (for example id = 42) instead of a position.
Erasure coding (EC): Splitting data into k chunks plus m parity chunks so that any k of n rebuild it.
Fixed cost per operation (F): The cost paid for each request whatever its size.Most mechanisms charge a setup cost per operation, whatever its size. A flush to disk costs about the same for 1 byte or 100 KB. So doing many things in one operation (batching) is cheaper per item. The price of batching: the first item waits for the last.
Freshness gap: The staleness between two copies of the same data kept in different layouts.
fsync: System call that pushes a file's data and the device cache to durable media.A system call that asks the OS: "push my file's cached data all the way to the device, and ask the device to empty its own cache too." It is the main tool to make data durable. It is also slow, because it waits for the physical device.
FTL (flash translation layer): An SSD's mapping from logical to physical addresses.An SSD cannot overwrite a small piece of data in place. Its internal software, the FTL (flash translation layer), writes new data to a fresh place, keeps a lookup table, and later cleans old data, which means one logical write can cause several physical writes (typically 2 to 3 times, sometimes more).
Garbage collection (GC): Runtime component that finds unreachable objects and reclaims their memory.In Java, Go, C# and similar languages you never call free. A background component, the garbage collector, finds objects that nothing refers to any more and reclaims their memory. A tracing collector does this by starting from known roots (variables) and following every reference to mark the objects that are still live. The live set is the total size of all live objects. A generational collector splits the heap into a young generation (new objects, collected often and cheaply) and an old generation (objects that survived several collections). Pauses are moments when the program is stopped so the collector can work.
Global sort: Sorting across all files, so file ranges are disjoint; costs a range-partitioned shuffle.
Granularity: The smallest increment a mechanism handles or bills.The smallest piece a mechanism handles. If a courier charges per whole kilogram, one kilogram is the granularity, even if you ship 100 grams. When what you need is smaller than the granularity, you pay for the difference. This mechanism calls that difference granularity waste.
Group commit: Many transactions share one log flush.
Heap table: A table whose rows are stored in no particular order.
Hidden partitioning: Declaring a partition as a transform of a data column so the optimizer can map predicates to partitions.
Hilbert curve: A space-filling curve with no large jumps; usually touches fewer units than Morton order.
Hive-style partitioning: One directory per value of a column, so the predicate is encoded in the path.
HOT update: A PostgreSQL optimization that keeps a new row version on the same page and skips index updates.
In-place update: Overwriting old bytes with new bytes.
Index: A separate structure, such as a B-tree, that finds rows without scanning the whole table. It has to be maintained on every write and kept in memory to be fast.A separate structure (such as a B-tree, the classic sorted tree used by databases) that lets you find rows without scanning the whole table. This mechanism looks mostly at how the table itself is laid out. Indexes as search structures are a separate topic. We will only meet the idea of skipping parts of a table.
Indirection: An extra lookup layer between a name and a physical location.A lookup layer between "the name you use" and "where the thing really is", like a phone book or a URL redirect. It lets you move things without telling everyone.
io_uring: Linux asynchronous I/O interface that submits many requests with few kernel calls.
KB: A byte holds roughly one character. In this mechanism KB, MB, GB are about a thousand, a million and a billion bytes. A KiB is exactly 1,024 bytes, so a 4 KiB page is 4,096 bytes. We use KiB when the exact size matters.
Key-value layout: Storage that treats the value as opaque and organizes everything by key.
Lakehouse: A data lake on object storage with a table format (manifests and a catalog) that adds transactions.
Late materialization: Building full rows or decoding values only after filtering.
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.
Leveled compaction: One run per level; low read and space cost, high write cost.
Line-fill buffer / MLP: Hardware slots that allow about 10-20 memory requests in flight (memory-level parallelism).
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.
Little's rule: Items in flight = throughput x latency.
Local versus global ordering: Sorting within each file (cheap, no file-level skipping) versus across all files (expensive, enables file skipping).
Log-structured layout: Append-only layout where physical position comes from arrival time.
LRU-K: An eviction policy that uses the time of the K-th last access; resists scans.
Manifest list: An Iceberg file that lists manifests; effectively the zone maps of the zone maps.
MB: A byte holds roughly one character. In this mechanism KB, MB, GB are about a thousand, a million and a billion bytes. A KiB is exactly 1,024 bytes, so a 4 KiB page is 4,096 bytes. We use KiB when the exact size matters.
Memtable: The in-memory write buffer of an LSM-tree.
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 is data: Metadata needs its own layout, skipping and compaction.
Metadata-growth rule: Metadata grows linearly with data but one read has fixed capacity, so metadata needs its own hierarchy.
Micro-partition: A small immutable unit chosen by the system (for example 50-500 MB), with statistics for every column.
Mismatch rule: Mismatches among write, read and update units create amplification.
mmap: Mapping a file into memory so the kernel loads pages on demand by page faults.
Morton order (Z-order): A space-filling curve made by interleaving the bits of the coordinates.
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 granularity: Using two or more unit sizes (for example file, row group, page), each with its own summary.
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.
Oldest-reader age: Age of the oldest active reader; the metric that predicts stuck reclamation.
Opacity: The store cannot look inside values; it forfeits optimizations that reappear in the application.
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.
Page fault: A synchronous event when a memory access needs data not yet in memory; the kernel then reads it.
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 evolution: Changing a table's partition scheme over time.
PAX: Hybrid layout: rows partitioned into groups, column-major within each group.
Positional delete: A delete naming a file and a row position.
Projection: An extra copy of a table stored in a different sort order.2 other meanings →
Range partitioner: A step that sends each row to the file that owns its key range.
Read-modify-write: Reading a unit, changing part of it and writing it back; caused by misaligned writes.
Rent (clustering): The recurring cost of restoring sortedness: write rate × U/d.
Repetition and definition levels: Per-value bits that preserve the tree path when nested data is flattened into columns.
RLE (run-length encoding): Storing a value and its repeat count.
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.
Row group: A block of rows (for example 128 MB) that is the unit of independent metadata and rewrite.
RUM conjecture: The claim that Read, Update and Memory cost cannot all be optimized together; unproven.
Scan resistance: Property that a long one-time scan cannot evict the useful working set.
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.
Shredding: Projecting self-describing documents into typed columns.
Skip-budget rule: The total skip power of a layout is fixed by the number of units; multidimensional clustering only redistributes it.
Slotted page: A page with a slot directory that maps record IDs to offsets and absorbs variable-length records.
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.
Sortedness decays: Sortedness is consumed by writes and restored only by rewriting.
Space amplification: Bytes stored per byte of live data.
Space-filling curve: A mapping from several dimensions to one line, used to order data (Z-order, Hilbert).
SPDK: User-space NVMe driver that bypasses the kernel.
Substrate: The storage medium and its access cost; sets the exchange rate for layout choices.
Tiered compaction: Several runs per level merged together; low write cost, high read and space cost.
Tiered storage: Placing hot data on a small fast medium and cold data on a large slow one.
TinyLFU: A cache admission filter based on estimated access frequency.
Tombstone: A marker record that says a key was deleted; must outlive every older copy.
Transaction: A group of operations executed as one all-or-nothing unit.A group of reads and writes that the database treats as one unit: either all of it takes effect, or none of it does. In SQL you mark it with BEGIN ... COMMIT (make it permanent) or ROLLBACK (throw it away). Example: moving 30 from Anna's wallet to Ben's wallet.
TTL: Time to live: how long an entry may be served before it expires.A lifetime attached to a cache entry. After the TTL expires, the entry is dropped or treated as missing.
u/(1-u): Cleaning cost per byte reclaimed when a fraction u of a unit is live.
Unit of update (U/d): The rewritten unit size divided by the changed bytes.
Unverifiable-assumption rule: Ask what a mechanism assumes it cannot verify and who pays when it is wrong.
Vacuum: PostgreSQL's collector for dead row versions.
Variance rule: Variance costs more than volume; failures are silent behind a harmless average.
Version chain: The linked set of versions of one record.
Wandering tree: CoW propagation: a leaf rewrite forces rewrites of all ancestors up to the root.
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.
Write-ahead log (WAL): Write-ahead log: ordered, append-only description of changes, forced before commit.Before a database changes its data pages, it first appends a description of the change to a sequential file called the log. If the machine crashes, the database replays the log to recover. Every serious database has one (it may be called WAL, redo log or binlog). Each position in the log has an increasing number, called an LSN (log sequence number; other systems call it SCN or GTID). In this mechanism the key fact is: the log is a complete, ordered record of every change, and it already exists..
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.