How to optimize slow MySQL Query due to ORDER BY RAND()?

Question

So I have this relatively simple query to pull a random row based on a few criteria from two different MyISAM tables:

SELECT 
    table1 . * , table2 . * 
FROM 
    Table1 AS table1
LEFT JOIN 
    Table2 AS table2
USING (
    col1
)
WHERE 
    table1.col1 !=  '5324372'
AND 
    table1.col2 LIKE  'S'
AND (
    table1.col3 LIKE  'I'
    OR table1.col3 LIKE  'V-G'
)
AND (
    table2.col1 =  'A'
    OR table2.col2 =  'B'
)
ORDER BY RAND( ) 
LIMIT 1

...which at the beginning worked fine, but as my Database began to grow, now takes several seconds to execute.

All columns used above are indexed, so it's not an indexing problem.

From what I've researched, it's due to the ORDER BY RAND() line which apparently runs very slow on large tables.

I've seen some potential solutions to this problem, but they are quite cryptic and I could not wrap my head around any of them in relation to my query above.

I'm actually surprised that MySQL does not have a built-in solution to this very slow ORDER BY RAND() problem as it would seem to me like it is a very basic need for many types of applications needing to select a random row.

So how can I optimize my query above so that I get the same/similar effect without the long execution times?

score 2 · Answer 1 · answered Oct 31 '11 at 22:54

2

Sorting is typically an N*log(N) operation. Normally, sorting is avoided as much as possible by the query planner / generator / optimiser, by combining it with indexes, or the order that naturally arises from subqueries. Sorting by random cannot be "optimised out" in any way. The solution: don't do it.

answered Oct 31 '11 at 22:54

wildplasser

43,142
8
66
109

1

This answer doesn't help me at all because I still need to be able to select a row at random for my application. – ProgrammerGirl Oct 31 '11 at 23:15

usef_ksa · Accepted Answer · 2011-11-01T13:49:27.747

1

You are choosing only one row , I think you can choose one row randomly by LIMIT randomly. Example:

If you have:

SELECT * table  ORDER BY RAND( )  LIMIT 1;

change it to

SELECT * table    LIMIT $randomvalue  ,$randomvalue + 1;

$randomvalue is a random value chosen from the application level.

update: the following answer is more clear than the above one.

//get the total number of rows
$result= mysql_query(" SELECT  COUNT(*) AS total FROM `table` ");
$row = mysql_fetch_array($result);
$total=$row['total'];


//create random value from 1 to the total of rows 
$randomvalue =rand(1,$total);


//get the random row

$result= mysql_query(" SELECT  * FROM `table` limit $randomvalue,1");

edited Nov 01 '11 at 13:49

answered Oct 31 '11 at 23:09

usef_ksa

1,669
3
23
40

I prefer a purely-MySQL solution to this problem. However, with your solution, how would I calculate $randomvalue and what would I base it on? – ProgrammerGirl Oct 31 '11 at 23:16
Well, choosing a number between 1 and the expected rowcount seems logical. It would reduce your expected complexity to O(N). And possibly more, because you'd avoid a lot of disk traffic. – wildplasser Oct 31 '11 at 23:40
@Programmer . I think it is not possible as wildplasser said. for the random value, make sure it do not exceed the total number of rows. – usef_ksa Oct 31 '11 at 23:44
@usef_ksa: You should edit your answer so that it is "LIMIT $randomvalue, 1", and clarifying that $randomvalue is based simply on the COUNT(*) of the query minus 1. I did that, and it worked faster than ORDER BY RAND() without having to complicate the query. Thanks. – ProgrammerGirl Nov 01 '11 at 10:18

How to optimize slow MySQL Query due to ORDER BY RAND()?

2 Answers2

Linked