How does MySQL's ORDER BY RAND() work?

I've been doing some research and testing on how to do fast random selection in MySQL. In the process I've faced some unexpected results and now I am not fully sure I know how ORDER BY RAND() really works.

I always thought that when you do ORDER BY RAND() on the table, MySQL adds a new column to the table which is filled with random values, then it sorts data by that column and then e.g. you take the above value which got there randomly. I've done lots of googling and testing and finally found that the query in my blog is indeed the fastest solution:

SELECT * FROM Table T JOIN (SELECT CEIL(MAX(ID)*RAND()) AS ID FROM Table) AS x ON T.ID >= x.ID LIMIT 1;

While common ORDER BY RAND() takes 30-40 seconds on my test table, his query does the work in 0.1 seconds. He explains how this functions in the blog so I'll just skip this and finally move to the odd thing.

My table is a common table with a PRIMARY KEY id and other non-indexed stuff like username, age, etc. Here's the thing I am struggling to explain

SELECT * FROM table ORDER BY RAND() LIMIT 1; /*30-40 seconds*/
SELECT id FROM table ORDER BY RAND() LIMIT 1; /*0.25 seconds*/
SELECT id, username FROM table ORDER BY RAND() LIMIT 1; /*90 seconds*/

I was sort of expecting to see approximately the same time for all three queries since I am always sorting on a single column. But for some reason this didn't happen. Please let me know if you any ideas about this. I have a project where I need to do fast ORDER BY RAND() and personally I would prefer to use

SELECT id FROM table ORDER BY RAND() LIMIT 1;
SELECT * FROM table WHERE id=ID_FROM_PREVIOUS_QUERY LIMIT 1;

which, yes, is slower than Jay's method, however it is smaller and easier to understand. My queries are rather big ones with several JOINs and with WHERE clause and while Jay's method still works, the query grows really big and complex because I need to use all the JOINs and WHERE in the JOINed (called x in his query) sub request.

Thanks for your time!

 Answers

While there's no such thing as a "fast order by rand()", there is a workaround for your specific task.

For getting any single random row, you can do like this : https://thiscode4u.blogspot.com/2018/07/mysql-order-by-rand-case-study-of.html (I couldn't see a hotlink url. If anyone sees one, feel free to edit the link.)

The text is in german, but the SQL code is a bit down the page and in big white boxes, so it's not hard to see.

Basically what he does is make a procedure that does the job of getting a valid row. That generates a random number between 0 and max_id, try fetching a row, and if it doesn't exist, keep going until you hit one that does. He allows for fetching x number of random rows by storing them in a temp table, so you can probably rewrite the procedure to be a bit faster fetching only one row.

The downside of this is that if you delete A LOT of rows, and there are huge gaps, the chances are big that it will miss tons of times, making it ineffective.

Update: Different execution times

SELECT * FROM table ORDER BY RAND() LIMIT 1; /30-40 seconds/

SELECT id FROM table ORDER BY RAND() LIMIT 1; /0.25 seconds/

SELECT id, username FROM table ORDER BY RAND() LIMIT 1; /90 seconds/

I was sort of expecting to see approximately the same time for all three queries since I am always sorting on a single column. But for some reason this didn't happen. Please let me know if you any ideas about this.

It may have to do with indexing. id is indexed and quick to access, whereas adding username to the result, means it needs to read that from each row and put it in the memory table. With the * it also has to read everything into memory, but it doesn't need to jump around the data file, meaning there's no time lost seeking.

This makes a difference only if there are variable length columns (varchar/text), which means it has to check the length, then skip that length, as opposed to just skipping a set length (or 0) between each row.

---

I can tell you why the SELECT id FROM ... is much slower than the other two, but I am not sure, why SELECT id, username is 2-3 times faster than SELECT *.

When you have an index (the primary key in your case) and the result includes only the columns from the index, MySQL optimizer is able to use the data from the index only, does not even look into the table itself. The more expensive is each row, the more effect you will observe, since you substitute the filesystem IO operations with pure in-memory operations. If you will have an additional index on (id, username), you will have a similar performance in the third case as well.

MySQL's LIMIT syntax can be slow for large offsets

A couple of weeks ago I posted an alternative to ORDER BY RAND() when using MySQL which uses MySQL's LIMIT syntax to jump to a record chosen at random based on the number of records in the table. I received a Tweet earlier this week which pointed out that LIMIT is slow when dealing with large offsets so take a look at this here.

Table used

I tested this on INNODB and MyISAM versions of the same table with 170429 records. The INNODB table uses 172 MB and the MyISAM 105 MB. This is real data and not some random database table I created for the purposes of this post, although it's not the sort of table you'd normally pull random records out from.

Using LIMIT to fetch the last record

The best way to see how slow it can potentially be is to use LIMIT to select the very last record. By doing this we'll get the maximum time it will take to run this query if the last record is the one selected at random.

The first query gets the count from the table:

SELECT COUNT(*) FROM mytable;

This returned 170432. Now to select the last record (note the offset is 1 less than the total number of records):

SELECT * FROM mytable LIMIT 170431, 1;

I ran this a number of times and took around 1.8 seconds for INNODB and 0.5 seconds for MyISAM on the machine I ran it on. This is far too slow if it's something that might be called frequently in a web application, although it might be a little better on some beefier hardware.

Comparing LIMIT with ORDER BY RAND()

The next thing to do was to benchmark the result from using LIMIT with ORDER BY RAND() to see if had been correct in my previous post that using LIMIT really is faster. So:

SELECT * FROM mytable ORDER BY RAND() LIMIT 1

I ran this query a number of times as well, and it took around 33 seconds for INNODB and 30 seconds for MyISAM each time. So clearly using LIMIT is much faster although it's still not a suitable solution if random data needs to be selected frequently in an on demand application.

Another alternative

I have another alternative which is almost instant, even on large tables but it does require an adjustment to the table and some additional business logic for your application. However it does solve the issue with speed of random records on a large table if you need random data frequently. This will be posted this time next week.

Related posts:

• Ordering by specific field values with MySQL
• An alternative to ORDER BY RAND() for MySQL
• Randomly ordering a MySQL result set

An alternative to ORDER BY RAND() for MySQL

I've posted previously about how to randomly order a resultset with MySQL using RAND() but the issue with RAND() is it will be inefficient on large tables because each row needs to have the random number calculated before the resultset can be ordered. This post looks at an alternative which requires two queries but will be much more efficient for large tables.

Please note

I have written a later post titled "MySQL's LIMIT syntax can be slow for large offsets". While using LIMIT syntax as shown in this post is a lot faster than ORDER BY RAND() it's still slow for larger tables. I'm currently working on a better alternative.

The alternative, and a note about INNODB vs MyISAM tables

The alternative suggested in this post uses COUNT(*) first to get the number of records in the table and then picks the record by using MySQL's LIMIT syntax. Note that INNODB does not cache the count of a table like MyISAM does so it takes slightly longer to return the count.

Example table

I often use an example table containing fruit. Here's the output from SELECT * FROM fruit:

+----------+--------+-----------+
| fruit_id | name   | somevalue |
+----------+--------+-----------+
|        1 | Banana |         2 |
|        2 | Orange |         4 |
|        3 | Cherry |         3 |
|        4 | Apple  |         1 |
+----------+--------+-----------+

MySQL only solution

It's possible to do this entirely with MySQL SQL queries without having to run code in PHP or other programming language. The following SQL queries first gets a count from the table, then selects a random offset based on that count. It then prepares a statement so the calculated offset can be used and executes the statement. Note that the offset is cast as a signed integerl without this you'll get the error message "ERROR 1210 (HY000): Incorrect arguments to EXECUTE".

SELECT @count := COUNT(*) FROM fruit;
SET @offset = CONVERT(FLOOR(RAND() * @count), SIGNED);
PREPARE mystatement FROM "SELECT * FROM fruit LIMIT ?, 1";
EXECUTE mystatement USING @offset;
DEALLOCATE PREPARE mystatement;

The output from the above will result in a random record returned each time e.g.:

+----------+--------+-----------+
| fruit_id | name   | somevalue |
+----------+--------+-----------+
|        3 | Cherry |         3 |
+----------+--------+-----------+

This works from the MySQL command line but doesn't appear to work in tools like phpMyAdmin (which does successfully execute the SQL but doesn't output any data) or MySQL Query Browser. It does work programatically from PHP (and therefore will for other programming languages). For exmample this:

mysql_query('SELECT @count := COUNT(*) FROM fruit');
mysql_query('SET @offset = CONVERT(FLOOR(RAND() * @count), SIGNED)');
mysql_query('PREPARE mystatement FROM "SELECT * FROM fruit LIMIT ?, 1"');
$res = mysql_query('EXECUTE mystatement USING @offset');
$row = mysql_fetch_assoc($res);
print_r($row);

outputs this:

Array
(
    [fruit_id] => 1
    [name] => Banana
    [somevalue] => 2
)

Using a programming language

Doing this outside MySQL is done in a similar way by getting the count from the table first, working out a random offset and then running a second query to get the record. This example uses PHP:

$res = mysql_query("SELECT COUNT(*) FROM fruit");
$row = mysql_fetch_array($res);
$offset = rand(0, $row[0]-1);

$res = mysql_query("SELECT * FROM fruit LIMIT $offset, 1");
$row = mysql_fetch_assoc($res);

Conclusion

My example only uses a small table and in this instance would be easier to simply use "ORDER BY RAND()" but ordering in this way is inefficient and performance will start to suffer as the table grows. Instead it can be more efficient to run a couple of queries instead to work out an offset based on the number of records in the table, and then use MySQL's LIMIT syntax to pull that record out of the table as shown in this post.

Related posts:

• Ordering by specific field values with MySQL
• MySQL's LIMIT syntax can be slow for large offsets
• Execute MySQL statements from a text file
• "Randomly" order data across multiple pages with MySQL
• Randomly ordering a MySQL result set
• Using the MySQL command line tool

Mysql: Display a random entry from a MySQL database

This example displays one random link from the example database


<?php

//connect to server with username and password, this is the default settings

//when MySQL is installed on Windows XP(Not recommended)

$connection = mysql_connect ("localhost","root", "") or die ("Cannot make the connection");

//connect to database

$db = mysql_select_db ("test",$connection) or die ("Cannot connect to database");

//our SQL query

$sql_query = "SELECT * FROM test ORDER BY RAND() LIMIT 1";

//store the SQL query in the result variable

$result = mysql_query($sql_query);

if(mysql_num_rows($result)){
//output as long as there are still available fields
while($row = mysql_fetch_row($result)){
echo ("<a href=\"$row[2]\">$row[3]</a>");
echo (": $row[4]<br>");
}
} //if no fields exist
else{
echo "no values in the database";
}
?>