Also called: Vitter’s Algorithm Z
In plain English
Reservoir sampling is a technique for picking a fixed-size random sample from a stream of unknown length in a single pass. PostgreSQL uses it inside ANALYZE to choose its sample rows fairly, without knowing the row count in advance.
Why it matters
It is why ANALYZE reads only a bounded sample — about 30,000 rows by default — instead of the whole table, keeping statistics collection fast even on a billion-row table while still giving every row an equal chance of being chosen.