Самый быстрый способ генерировать ключи по которым делать выборку на php или другом языке и выбирать в базе через WHERE, это самый быстрый способ. Но в таблице не должно быть дыр, поэтому формируйте временную таблицу без дыр и уже выбирайте из неё, ну и пересоздавайте её через какое-то время по крону. Вот выборка 7-ми записей:
<?php
$max_sort_n = $db->query("SELECT MAX(sort_n) FROM users", array(), "el");
$sort_n = rand(7, $max_sort_n);
if($max_sort_n)
{
$res = $db->query("SELECT id, login FROM users WHERE sort_n BETWEEN ?i AND ?i", array($sort_n - 6, $sort_n), "assoc");
}
?>
