Hacker News Reader

Comment by Jupe | Hacker News Reader

Wait, what?

  order by random()

Does that even make sense? Why would anyone ever need this? Better to order by a stored value and randomize the presentation order, IMO.

Seems completely dependent on when random() gets evaluated. If it gets evaluated at every inspection of the row during the sort, I'm little amazed that it hangs some times.

View on HN

The `ORDER BY RANDOM() LIMIT n` idiom is fairly well established for taking a random sample of uniformly distributed rows. It is also easily augmented to take weighted samples: `WHERE weight > 0 ORDER BY -LN(RANDOM())/weight LIMIT n`.

Queries of this form are easilly parallelized. Most systems that support distributed query processing, for example, optimize ORDER/LIMIT n queries such that each worker returns just the top n rows from its partition. These top rows are then merged in a central worker and limited one last time to produce the final result.

Even so, if your system supports the TABLESAMPLE clause and offers a formulation that lets you specify your actual distribution of interest (TABLESAMPLE SYSTEM often does not), you're probably better off using it.

For anyone who is curious, the weighted sampling logic is the SQL translation of Algorithm A from Efraimidis and Spirakis's 2006 paper [1]:

    Algorithm A
    Input: A population V of weighted items
    Output: A WRS of size n
    1: For each v[i] in V, u[i] = random(0, 1) and k[i] = u^(1/w[i])
    2: Select the n items with the largest keys k[i] as a WRS

Instead of the more direct tanslation of `ORDER BY POW(RANDOM(), (1/weight)) DESC`, we use the convenient fact that logarithm is a monotone transform over the positive reals to take the log of the ORDER BY argument without changing the sort order:

       ORDER BY POW(RANDOM(), (1/weight)) DESC
    => ORDER BY LN(POW(RANDOM(), (1/weight))) DESC  -- LN preserves order.
    => ORDER BY LN(RANDOM()) / weight DESC          -- LN(x^a) = LN(x) * a.
    => ORDER BY -LN(RANDOM()) / weight              -- Order by `x DESC` is same as by `-x`.

[1] Pavlos S Efraimidis and Paul G Spirakis. Weighted random sampling with a reservoir. Information Processing Letters, 97(5):181–185, 2006

Thanks for this cool bit of information.

You'd use order by random() when you want to get a random sample of rows in a table. Without that, you'd end up with rows clustered according to some internal value, probably ordered by the primary key.

Of course, this is a bad idea if you have a table with lots of rows, and you'd be better off rolling an N-sided dice M times, where N is the number of rows in the table.

But ORDER BY random() will scan the whole table and assign values.

This is the plan I get:

    Limit (cost=56.39..56.41 rows=10 width=40)
    -> Sort (cost=56.39..59.79 rows=1360 width=40)
    Sort Key: (random())
    -> Seq Scan on test (cost=0.00..27.00 rows=1360 width=40)

One should use "FROM table TABLESAMPLE SYSTEM (size)", this is the plan:

    Sample Scan on test (cost=0.00..5.36 rows=136 width=32)
    Sampling: system ('10'::real)

You can also use different distribution method than "SYSTEM", and you can make it reproducible with a seed.

https://www.postgresql.org/docs/current/sql-select.html#SQL-...

ORDER BY random() is a really un-optimized bad practice to get a random sample on PostgreSQL. If you use another SQL database, the best thing to do is to use UUIDv4 as primary key, and use "ORDER BY pk LIMIT size".

Note that `FROM table TABLESAMPLE SYSTEM (n/N)` is a safe substituion for `ORDER BY random() LIMIT n` only when you don't need a sample that's guaranteed to be from a uniform distribution of rows. That's because TABLESAMPLE SYSTEM samples blocks, not individual rows:

> The SYSTEM method does block-level sampling with each block having the specified chance of being selected; all rows in each selected block are returned.

order by stored uuidv4 will get you the same rows the next time you run it. If you sample using where random() < 0.001 (or something like that) you'll get different rows each time.

> If you use another SQL database, the best thing to do is to use UUIDv4 as primary key, and use "ORDER BY pk LIMIT size".

What if I want a different random order tomorrow?

Then you sort descending of course /s

> > If you use another SQL database, the best thing to do is to use UUIDv4 as primary key, and use "ORDER BY pk LIMIT size".

> What if I want a different random order tomorrow?

If your data is large, and you want different samples. You can always always "select * from pk > gen_random_uuid() order by pk limit 10"

You have a very small chance to get ffffffff-... and get zero elements.

This is not perfect, I admit, but ORDER BY random() is one of the most wasteful thing.

If getting random samples is very important, the best you can you is migrate to postgres and use TABLESAMPLE.

> But ORDER BY random() will scan the whole table and assign values.

Er, no, it will assign values to the result set, which may not involve a full table scan.

Good point, but in the case of OP, without condition, it will do a full table scan.

Also, any case of "WHERE filter ORDER BY random() LIMIT n" means "I want a tiny sample from a broad filter". So it might not be a full table scan, but it will still assign value to a lot of rows.

> Good point, but in the case of OP, without condition, it will do a full table scan.

And that has nothing to do with the ORDER BY random().

Yes it does, because of LIMIT N. An unordered result set will stop after the first N matches.

Now that is correct.

> If you use another SQL database

Just a side note: TABLESAMPLE is part of the SQL standard, and e.g. Oracle supports this as well.

Agreed. (And thanks; never came across this before... ever. in 20 years)

I guess some projects need to randomly select a few rows from a table? I was thinking of the wikipedia random topic, but that's only one-at-a-time, not a set of records.

It does make sense. It gets you a non-repeating sample of the table.

It is probably not very efficient, but semantically it is fairly straightforward. In fact I thought that "hang" was going to mean "took so long I thought it was hung" but that turned out not be the issue here.

Yeah. It's odd that you got down-voted for this comment. "ORDER BY random() LIMIT 10" is known to be slow on large tables. The correct way to do get a random sample is to use "SELECT ... FROM table TABLESAMPLE SYSTEM (10)" https://www.postgresql.org/docs/current/sql-select.html#SQL-...

You can even use a repeatable seed with this method.

Note that TABLESAMPLE SYSTEM is not guaranteed to give you a uniform sample, as it samples blocks, whereas ORDER BY RANDOM() LIMIT samples uniformly distributed rows. Some database systems support TABLESAMPLE RESERVOIR to guarantee uniform sampling behavior.

The hanging query has nothing at all to do with the random ordering. RTFA

Surprised no one has pointed it out, but the queries involve Pokémon. According to a quick Google search there are a grand total of ~800 different Pokémon. You aren't wrong, but a table scan over 800 rows isn't exactly worth worrying about.

1008 numbered Pokémon as of the latest game (excluding the forthcoming DLC), although the true count is possibly implementation dependent - at the very least some Pokémon have different 'forms' which can have different stats, and so will be stronger/faster/healthier.

The world of Pokémon can be crazily complicated if you let it ;-).

Reply on news.ycombinator.com