Reservoir sampling
Also called: Vitter's Algorithm Z
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.
What this means
A trick for grabbing a fair, fixed-size random sample from a stream when you don't know how long the stream is, in a single pass, without counting first. ANALYZE uses it to pick its sample rows evenly across a table it hasn't measured yet, so the early rows aren't favored over the late ones.
Why it matters operationally
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.