Alternative to ORDER BY RAND() on joined tables?

Question

I have a table of approx 3500 Items. In another table I'm storing user votes - the Item id, the user id and the score. When a user hits this script, it must randomly select an Item they haven't already voted on.

At the moment I'm using LEFT JOIN then testing for null to find the set of Items they haven't voted on. Trouble is, using ORDER BY RAND() on this derived table is causing memory issues as the derived set is being copied to a temporary table for sorting.

SELECT i.id 
FROM items i 
LEFT JOIN (
    SELECT id 
    FROM votes 
    WHERE voter_id=X
    ) v 
ON i.id=v.id 
WHERE v.id IS NULL 
ORDER BY RAND() 
LIMIT 1

The items table isn't large by any means, but with many people hitting this script at the same time (and many of them revisiting the same page many times) MySQL is struggling.

The common alternatives (picking random id lower than the MAX()) won't work were - is there any other way? Am I better returning the whole resultset & using PHP to pick one at random?

Answer 1

Burçin Yazıcı - I'm using MySQL so timestamps won't yield mili/micro seconds. I did try using PHP's microtime() and insert that into the query, but this still results in 'using temporary; using filesort' when explaining.

For the time being I'm leaving the query unsorted, returning all results, then using PHP's

mysql_data_seek($result, rand(0, mysql_num_rows($result)-1));
$row=mysql_fetch_object($result);

to pick a random row. I'm cautious of the performance impact of mysql_data_seek but its taking the pressure off the database for now.