Вот как я это делаю:
select * from table_with_600k_rows where rand() < 10/600000 limit 10
Мне это нравится, потому что он не требует других таблиц, его просто написать, и он очень быстро выполняется.