I've populated your test table with 20,000 rows. Then I have tested (and benchmarked for performance) 3 different ways to get your random row. The approach #2 was the fastest one:

1. Simple Approach - 0.09 sec execution time

SELECT * FROM `test_data`
ORDER BY RAND()
LIMIT 1

Execution plan:

As you may see, it requires full table scan, i.e. reading all 20,000 rows, calculating 20,000 random numbers, then SORTING 20,000 rows (by RAND), then fetching the first row after sorting. Also, the sorting happens not in memory but using I/), i.e. "using filesort".

So I decided to try making it a bit more efficient - see below ...

2. Avoiding Table Scan - 0.07 sec execution time (fastest)

Instead of the full table scan we just go through full index scan to get the random id, then fetch the complete record once. The execution time reduced from 0.09 to 0.07 sec.

SELECT t2.* FROM  
(SELECT id FROM `test_data`
ORDER BY RAND()
LIMIT 1) AS t1
INNER JOIN test_data as t2 ON t1.id = t2.id

3. Procedure - fetching loop with random number of fetches - 0.30 sec (slowest execution)

The idea was to get random row by performing random number of FETCHES from the unsorted cursor in the loop. The last fetched ID would be the ID of resulting random record. In theory, benefits of this approach would include:

• no sorting needed at all
• average scan depth should be N/2, not N like in the full scans above
• random number needs to be calculated only once, not 20,000 times (this is minor, but still...)

here is the code

CREATE PROCEDURE test()
BEGIN
  DECLARE done INT DEFAULT FALSE;
  DECLARE current_id INT;
  DECLARE row_counter INT;
  DECLARE random_row_number INT;
  DECLARE cur1 CURSOR FOR SELECT id FROM test_data;
  DECLARE CONTINUE HANDLER FOR NOT FOUND SET @done = TRUE;

  SELECT @row_counter := COUNT(*) FROM test_data;

  SET @random_row_number = floor(1 + (rand() * @row_counter));

  SET @row_counter = 1;                                                   

  OPEN cur1;                                                   

  read_loop: LOOP
    FETCH cur1 INTO current_id;

    IF @done THEN
      LEAVE read_loop;
    END IF;

    IF @row_counter >= @random_row_number THEN
      LEAVE read_loop;
    END IF;

    SET @row_counter = @row_counter + 1;                                       
  END LOOP;

  CLOSE cur1;

  SELECT * FROM test_data WHERE id = current_id; 
 END

unfortunately, this procedural approach was good in theory but turned to be the slowest in practice. Most likely b/c MySQL cursor operations slowed things down. If anyone has any other idea why this approach with random number of fetches was so slow, please comment!

Thanks!