EXPLAIN EXTENDED

Usual way to select random rows from a MySQL table looks like this:

SELECT  *
FROM    t_random
ORDER BY
        RAND(20090301)
LIMIT 10

This creates a fake RAND() column along with the query columns, sorts on it and returns bottom 10 results.

EXPLAIN EXTENDED on this query returns quite expected Using temporary; Using filesort

This plan will use Θ(N×log(N)) time on sorting alone. If temporary will hit memory limits, the time will increase even more rapidly.

Here’s the result of the query above:

More than 13 seconds, and it’s only a million rows. And financial databases may have billions.

But do we really need sorting anyway?

Say, we need to select 10 rows out of 1 000 000. If we just iterate the rows, which is the probability of each row to be selected on its turn?

As no rows differ from each other for our purposes, each remaining row may be selected with equal probabilty. This means, that if on a certain turn we have C rows left uninspected with L rows yet to select, then the probability of the current row to be selected will be just L / C. That simple.

Unfortunately, MySQL doesn’t provide us with row numbers, that’s why we’ll need to perform certain tricks with variables to work around this:

SELECT  *
FROM    (
        SELECT  @cnt := COUNT(*) + 1,
                @lim := 10
        FROM    t_random
        ) vars
STRAIGHT_JOIN
        (
        SELECT  r.*,
                @lim := @lim - 1
        FROM    t_random r
        WHERE   (@cnt := @cnt - 1)
                AND RAND(20090301) < @lim / @cnt
        ) i

In the first subquery (called vars) we initialize the variables, including COUNT(*). We’ll need STRAIGHT_JOIN here to ensure that the first query will be executed first.

Expressions in WHERE conditions, like @cnt := @cnt - 1, are evaluated on each row. Expressions in SELECT clause, like @lim := @lim - 1, are evaluated only when the row is selected (that’s is, after all WHERE conditions were evaluated and found to be true). That’s exactly what we want: we need to decrement @cnt each time a row is inspected, and decrement @lim each time a row is selected.

Running this query, we get:

Only 0,56 seconds. Much much nicer.

This is, of course, not very honest result, as I deliberately created table t_random using MyISAM storage. You may have noted that the COUNT(*) is used in the first subquery to initialize @cnt. It’s instant on a MyISAM table (as it’s stored in the table’s metadata), but takes some time on InnoDB.

But let’s see the results for InnoDB:

SELECT  *
FROM    t_random_innodb
ORDER BY
        RAND(20090301)
LIMIT 10

SELECT  rnd_id, rnd_value
FROM    (
        SELECT  @cnt := COUNT(*) + 1,
                @lim := 10
        FROM    t_random_innodb
        ) vars
STRAIGHT_JOIN
        (
        SELECT  r.*,
                @lim := @lim - 1
        FROM    t_random_innodb r
        WHERE   (@cnt := @cnt - 1)
                AND RAND(20090301) < @lim / @cnt
        ) i

Also nice.

There is, of course, more place for optimization:

1. It’s possible to cache or estimate COUNT(*) for an InnoDB table and use it to initialize @cnt. This of course may cut some latest rows or even return fewer rows than requested, but it’s OK if you don’t need high accuracy.
2. It’s possible to select MIN() and MAX() id‘s from the table, do the things above in a loop (without actial table scan), store results into a temporary table and then join only 10 id’s you need (using correlated subqueries with >= id LIMIT 1, if your id‘s are sparse). This also may return fewer rows than requested.

But if you just need to rewrite your working but inefficient query without much effort, that’s exactly what you need.