Dmitry T.

Если PK int.

select min(id),max(id) from table where ... ; // если данные меняются не часто можно кешировать значения
$rand = get_rand($min_id, $max_id);
select * from table where id => $rand and ... limit 1;