$idArray = mysql_query("SELECT `id` FROM `downloads` ");
$array = array();
while ($arrayRes = mysql_fetch_array($idArray))
$array[] = $arrayRes[0];
$randArray = array_rand($array, 1);
$sql = $array[$randArray[0]];
$item = mysql_fetch_assoc(mysql_query("SELECT `id` FROM `downloads` WHERE `id` = '$sql' LIMIT 1 "));
echo $item['id']; // рандомно выдаст id из всех существующихСобственно вот. Запрос в базу может быть другой, но принцип такой.
Это по нагрузке меньше чем order by rand, но на слишком больших базах всё равно будет выдавать нагрузку (тестировал на 2000 записях при дополнительном цикле - генерация не больше сек.).
Написал недавно, если кто придумает что полегче - напишите, для меня тоже актуально!