The Hidden Full-Table Scan in `ORDER BY random()`

Ask PostgreSQL for 100 random users from a table of 100 million and LIMIT 100 does not make the other 99,999,900 candidates disappear. The engine still needs a random key for every qualifying row before it can know which hundred belong at the front.

The planner may avoid a full sort by keeping a top-N heap, but it cannot use an ordinary index to predict fresh values from the volatile random() function. The expensive part is the scan and per-row scoring, not merely the final hundred rows.

Rows live on disk pages. Tables are filtered and scanned in particular orders. Some sampling methods work at the row level, some at the block level, and some give you approximate sizes rather than exact counts. Once the data has a physical layout, randomness stops being an abstract ideal and starts negotiating with the engine.

The naive query

The first thing many people write is some variation of:

SELECT *
FROM users
ORDER BY random()
LIMIT 100;

This is a perfectly understandable query. It asks the engine to assign a random value to every candidate and then keep the top few.

On a small table, that is fine. On a large table, it is exactly the kind of innocent-looking query that can become much more expensive than you meant. If you randomize every row and only keep a few, the engine touches a lot more of the table than the final answer suggests.

SQL can return random rows. The useful question is what guarantee you need badly enough to pay for.

Different sampling goals

PostgreSQL exposes sampling features that make the trade-offs clearer. There are at least three different requests hiding behind “random rows”:

• Give me an approximately random fraction of the table.
• Give me exactly k rows.
• Give me a sample that is reproducible.

Those are different requirements, and each one pushes you toward a different implementation.

Bernoulli-style row sampling

A natural model is row-level independent sampling: keep each row with probability $p$.

This is conceptually clean, and it leads to one nice formula immediately:

If a table has n rows and each row is independently kept with probability p, then the expected sample size is pn. Expected size is not exact size. If you need roughly 1% of a huge table, a Bernoulli-style sample is a good fit. If you need exactly 100 rows, it is not the same problem.

Block-level sampling

A database may also sample at the page or block level rather than the row level. That can be much faster, because the engine operates closer to the physical storage layout.

But it also means the sample quality is partly shaped by that layout. If related rows happen to live near each other on disk, a block-level sample can overrepresent local neighborhoods of the data.

That is the pattern this post emphasizes:

• Row-level randomness is closer to the probability story.
• Block-level randomness is closer to the storage story.

Neither is universally right. They answer slightly different questions.

Reproducibility matters

In analysis or debugging, “give me a random sample” often really means:

Give me a random-looking sample that I can get again tomorrow.

That is a very different request from “surprise me every time.” So one useful axis in database sampling is not just speed or representativeness, but whether the sampling rule can be seeded or repeated in a stable way.

The same seed and sampling arguments reproduce a PostgreSQL sample only while the table remains unchanged. That condition belongs in the promise; a seed is not a time machine.

One concrete SQL landscape

The syntax below is PostgreSQL-shaped.¹ Other engines expose different knobs, but the trade-off is the same: exact size, row-level independence, block-level speed, and repeatability are separate requirements.

-- Naive: easy to write, often costly on large tables
SELECT *
FROM users
ORDER BY random()
LIMIT 100;

-- Approximate fraction, conceptually row-level
SELECT *
FROM users
TABLESAMPLE BERNOULLI (1);

-- Approximate fraction, closer to physical storage
SELECT *
FROM users
TABLESAMPLE SYSTEM (1);

-- Reproducible, if the engine supports it
SELECT *
FROM users
TABLESAMPLE SYSTEM (1)
REPEATABLE (42);

These examples show how quickly one request turns into several distinct trade-offs. BERNOULLI (1) and SYSTEM (1) ask for an approximate one percent sample, not exactly one percent and not exactly 100 rows.

There is another semantic trap: PostgreSQL applies TABLESAMPLE before WHERE. Sampling one percent of the physical table and then filtering is different from first defining a population with WHERE and sampling one percent of that population. The syntax is short enough to hide the distinction.

The table has physical geometry. BERNOULLI stays close to the row-level probability story but scans the table. SYSTEM saves I/O by sampling blocks, then inherits whatever clustering lives inside those blocks. ORDER BY random() gives exact-size uniform selection among qualifying rows at the price of touching them all.

There is no best random-row query. There is only a guarantee, a storage layout, and a bill.