Seleccionar filas aleatorias con MySQL

El ORDER BY RAND() la solución que la mayoría de la gente recomienda no escala a tablas grandes, como ya sabe.

SET @r := (SELECT FLOOR(RAND() * (SELECT COUNT(*) FROM mytable)));
SET @sql := CONCAT('SELECT * FROM mytable LIMIT 1 OFFSET ', @r);
PREPARE stmt1 FROM @sql;
EXECUTE stmt1;

Cubro esta y otras soluciones en mi libro, Antipatrones SQL:Cómo evitar las trampas de la programación de bases de datos .

Si quiere hacer esto con PHP, puede hacer algo como esto (no probado):

<?php
$mysqli->begin_transaction();
$result = $mysqli->query("SELECT COUNT(*) FROM mytable")
$row = $result->fetch_row(); 
$count = $row[0]; 
$offset = mt_rand(0, $count);
$result = $mysqli->query("SELECT * FROM mytable LIMIT 1 OFFSET $offset");
...
$mysqli->commit();