Glossary

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

2Q: Replacement policy with a FIFO queue for first-time pages, a ghost queue of identifiers, and an LRU list for proven pages.
Admission control: Declining new work before any resources are committed to it.
Algebraic aggregate: An aggregate (SUM, COUNT, MIN, MAX) whose state is O(1) per group and can be combined partially.
Allocation: malloc: In C, malloc(n) returns a block of n bytes and free(p) gives it back. The library that implements them (an allocator, for example glibc malloc or jemalloc) must remember which blocks are free. It may return the blocks in any order.
Allocator: Library (malloc, jemalloc) that hands out and takes back blocks of memory.
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.
Arena (region allocator): A large chunk with a bump pointer; all allocations are freed together by resetting the pointer.
Bandwidth ratio (r): Memory bandwidth divided by the bandwidth of the spill device; sets the cost of spilling.
Belady's anomaly: The effect that more frames can cause more page faults under some policies (FIFO), not under stack algorithms (LRU).
Belady's MIN: Optimal replacement: evict the page whose next use is furthest in the future; needs the future.
Bimodal behaviour: Performance that is either very good or very bad, with nothing in between (LRU on a loop).
Bin-packing: Choosing groups of small files to rewrite as files near the target size.
Broadcast join: A join that copies the small side to every executor so the large side does not move.
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.
Bump-pointer allocation: Allocation by adding the size to a pointer inside a big block.
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:
Cardinality estimate: The optimizer's guess of how many rows a step produces; the basis of memory grant sizes.Before running a query, the query optimizer guesses how many rows each step will produce. This guess is the cardinality estimate. Memory grants (Part 4) are built from it.
Cgroup: Linux feature that limits the resources, such as bytes of memory, of a group of processes.
Clock: LRU approximation using a reference bit per frame and a hand that sweeps the frames.1 other meaning →
Coalescing: Merging neighbouring free blocks into a larger one.1 other meaning →
Cooperative spilling: The manager asks consumers to free memory, and each consumer chooses what to release.
Correlated failure: Failures that happen together because of a common cause (same rack, batch, software).
Correlated reference period: Several references to a page that belong to one logical access and should count once (LRU-K).
Cyclic access: Repeatedly reading the same n pages in order; the worst case for LRU when the pool is smaller than n.
Dictionary encoding: Replacing each value by a small integer index into a table of distinct values.
Dirty page: A page changed in memory but not yet written to disk.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.
Double buffering: Caching the same page twice, in the kernel's page cache and in the engine's own pool.
External fragmentation: Free memory exists but not in one contiguous piece, so large requests fail.
External merge sort: Sort of data larger than memory: write sorted runs to disk, then merge them in passes.
First touch: Linux NUMA rule: a page is placed on the node of the thread that first writes it.
Frame: One slot of the buffer pool that holds one page.1 other meaning →
free: In C, malloc(n) returns a block of n bytes and free(p) gives it back. The library that implements them (an allocator, for example glibc malloc or jemalloc) must remember which blocks are free. It may return the blocks in any order.
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.
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.
Generational GC: A collector that treats young objects separately, relying on most objects dying young.
Ghost entry (ghost list): An identifier of an evicted page kept without its data, to measure what a different policy would have hit.
Goodput: Completed work whose result is still wanted.Throughput is work completed per second. Goodput is work completed per second whose result is still wanted. If a client has already given up (timed out), finishing its request adds throughput but no goodput.
Grace hash partitioning: Hashing both join inputs into partitions written sequentially, then joining partition pairs one at a time.
Grant (memory grant): The amount of memory promised to an operator before it runs.
Grant feedback: Recording a plan's actual peak memory and using it to size the next grant.
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.
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: Memory region for run-time allocations (also the managed-language object area).2 other meanings →A running program asks the operating system (OS) for memory. The heap is the region where a program allocates objects whose size or lifetime is decided at run time. RSS (resident set size) is how much physical RAM the OS currently charges to the process. RSS and "heap in use" are different numbers, and the gap between them matters here.
Heavy right tail: A distribution where rare very large values dominate risk.
High and low watermark (soft and hard): Memory levels at which spilling begins (soft) and admission stops and kills begin (hard).
Hit rate (h): The share of requests answered from the cache.
Holistic aggregate: An aggregate (MEDIAN, exact COUNT DISTINCT) with no bounded intermediate state.
Huge pages: 2 MB virtual-memory pages that extend TLB reach by ~500×.
Hysteresis: Behavior that depends on history: the threshold to enter a state differs from the threshold to leave it.A system whose behavior depends on its recent past, so it does not flip back and forth at a single threshold. A thermostat that turns on at 19 °C and off at 21 °C has a 2-degree hysteresis band. It avoids flapping, at the price of a wider swing.
Intel RDT: Hardware features that partition last-level cache and throttle memory bandwidth per class of service.
Internal fragmentation: Wasted space inside an allocated block because of rounding to size classes or alignment.
Interning: Keeping one shared copy of each distinct value (usually a string) so equal values are one object.
Latch: A short lock inside a database protecting a page or structure.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.
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.
Live set: Total size of the objects that are still reachable; determines tracing GC cost.
Log-normal: A distribution whose logarithm is bell-shaped; errors are multiplicative with a heavy right tail.
LRU / LRU-K: Evict the least recently used page / use the K-th most recent reference time instead of the last.
LZ4: A very fast compression codec, suited to spill files.
Memory context: PostgreSQL's arena-like allocation scope tied to an executor phase (query, portal, tuple).
Memory grant quantization: Giving grants only at pass boundaries, because cost falls in steps.
mmap: Mapping a file into memory so the kernel loads pages on demand by page faults.
Non-participant: A memory holder not registered with the manager, therefore invisible to accounting.
NUMA: Non-uniform memory access: memory attached to another socket is slower to reach.On a server with several CPU sockets, each socket has its own directly attached memory. Reading another socket's memory (remote access) is slower than reading your own (local access). The name is Non-Uniform Memory Access.
O_DIRECT: Flag that makes file I/O bypass the kernel page cache.
Off-heap memory: Memory outside the managed heap, invisible to the garbage collector, managed explicitly.
OOM killer: Linux component that kills a process when the machine runs out of memory.
Out of memory (OOM): A process asking for memory that is not available. It may get an error, or on Linux the kernel's OOM killer may kill it; cgroups set such limits for groups of processes.If a process asks for memory that is not there, it may get an error (an "out of memory" error). On Linux, if the whole machine runs out, the kernel's OOM killer picks a process and kills it. A cgroup (control group) is a Linux feature that gives a group of processes a limit, for example memory.max, on how many bytes they may use.
Over-commit: Admitting more work than memory, assuming peaks do not coincide.
Page: A fixed-size block (usually 4 KB) in which the OS maps a program's virtual addresses to physical RAM. The CPU caches recent mappings in the TLB; rarely used pages can be swapped to disk.3 other meanings →Programs use virtual addresses. Hardware and the OS translate them to physical RAM in blocks called pages (usually 4 KB). A small cache in the CPU, the TLB (Translation Lookaside Buffer), remembers recent translations. If the OS runs short of RAM it can write rarely used pages to disk. This is called swap.
Page cache: The kernel's cache of file pages.When a program writes a file, the operating system usually keeps the data in memory first (the page cache) and writes it to the disk later. A call named fsync forces the data onto the disk and waits until it is there. Data that is only in the page cache is lost if the machine loses power. Replication (copies on other machines) is the other way to survive a crash.
Page cleaner (background writer): Background thread that writes dirty pages so clean frames are available for eviction.
Pin: Short-term reference count that prevents a frame from being evicted.
Pipeline break: A point where an operator must finish all of its input before producing output.
Pointer swizzling: Storing in one field either a memory address or a page id, so in-memory lookups skip the page table of the pool.
Poison pill: A record that fails deterministically on every retry and can block an ordered partition.
Preemption: Stopping a running task so others can use its resources.Stopping a running task so that something else can use the resource.
Preemption cost: What it costs to take a resource back from a holder in the middle of use.
Premature promotion: Moving objects to the old generation too early because their request was still in flight.
Queue: A line of work waiting for its turn, like people waiting at a bank counter. A scheduler is the part of a system that decides who is served next.1 other meaning →
Read/write barrier (GC): Small code run on reference operations so a concurrent collector can stay correct.
Reference counting: Keeping a count of holders of a buffer and freeing it when the count reaches zero.
Reserve: Memory held back so the system has time to respond to pressure.
Residency: Which part of the data is in memory at a given moment.
Ring buffer: A small private set of frames reused by one scan so it does not disturb the main pool.1 other meaning →
RSS: Resident set size: physical RAM currently charged to a process.A running program asks the operating system (OS) for memory. The heap is the region where a program allocates objects whose size or lifetime is decided at run time. RSS (resident set size) is how much physical RAM the OS currently charges to the process. RSS and "heap in use" are different numbers, and the gap between them matters here.
Sequential flooding: A scan pushing the whole working set out of an LRU cache.
Shuffle output: Intermediate files written by one stage for later stages to read.
Size class: A standard allocation size to which requests are rounded up.
Sort: Ordering rows by a key. A sort needs memory proportional to its input; when there is not enough, a good engine spills sorted runs to disk and merges them back.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.
Sort-merge fallback: Switching an oversized hash partition to sort-based processing, which needs nothing to fit.
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.
Stack: The region of memory where a thread keeps its function calls' local variables, allocated and freed in last-in, first-out order; objects whose size or lifetime is decided at run time go on the heap instead.A running program asks the operating system (OS) for memory. The heap is the region where a program allocates objects whose size or lifetime is decided at run time. RSS (resident set size) is how much physical RAM the OS currently charges to the process. RSS and "heap in use" are different numbers, and the gap between them matters here.
Stack algorithm: Replacement policy whose contents at size c are a subset of the contents at size c+1 (LRU).
Storage pages: The fixed-size blocks, typically 8 KB, in which a database stores tables on disk and caches them in its buffer pool. Not the same as the operating system's 4 KB virtual-memory pages.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.
Swap: OS mechanism that writes memory pages to disk to free RAM, choosing victims by recency.
The OOM killer: The Linux kernel mechanism that, when the machine runs out of memory, picks a process and kills it to free memory.If a process asks for memory that is not there, it may get an error (an "out of memory" error). On Linux, if the whole machine runs out, the kernel's OOM killer picks a process and kills it. A cgroup (control group) is a Linux feature that gives a group of processes a limit, for example memory.max, on how many bytes they may use.
THP (transparent huge pages): Linux feature that creates huge pages automatically; background compaction can stall allocations.
TLB: Translation Lookaside Buffer: CPU cache of virtual-to-physical address translations.
TLB reach: Amount of memory the TLB entries cover (entries × page size).
TLB shootdown: Interrupting cores to invalidate a translation, whose cost grows with core count.
UDF / UDAF: User-defined function or aggregate function; its internal state is invisible to the engine.
Usable frames: Total frames minus pinned frames minus dirty frames awaiting log flush.
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.
Validity bitmap: One bit per value saying whether the value is present (not null). Compared with a position list, it costs N bits against m·log₂N; crossover at density 1/log₂N (about 5%).
Victim selection: Choosing which query or consumer loses memory or is killed.
Virtual memory: The addresses a program uses, translated by the hardware and OS to physical RAM in pages. It lets the OS give each process its own address space and swap rarely used pages to disk.Programs use virtual addresses. Hardware and the OS translate them to physical RAM in blocks called pages (usually 4 KB). A small cache in the CPU, the TLB (Translation Lookaside Buffer), remembers recent translations. If the OS runs short of RAM it can write rarely used pages to disk. This is called swap.
Working set: The set of pages a workload keeps coming back to.
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..
Zero-copy: Using bytes directly as in-memory values, with no decode step.1 other meaning →