Предлагаю супер вариант.
Фаза 1 - подготовка
1. создаем таблицу
[sql]
CREATE TABLE rand4table1
(
num INT NOT NULL AUTO_INCREMENT,
id_table1 INT NOT NULL,
PRIMARY KEY(NUM)
);
[/sql]
2. делаем соответсвенно
[sql]
INSERT INTO rand4table1
SELECT 0, id FROM table1;
[/sql]
Фаза 2 выборка.
1.
[sql]
SELECT @Cnt:=COUNT(NUM) cnt FROM rand4table1;
SELECT @id:=id_table1 FROM rand4table1 WHERE num = @Cnt*rand() LIMIT 1;
SELECT * FROM table_1 WHERE id = @id;
[/sql]
ипользуем cnt вместо Max - так как нам все равно, а мускулу приятнее.
используем rand мускулевский - зачем не знаю, но типа так независимее
Если нет записи - делаем еще один select - просто запись за дыркой
[sql]
SELECT * FROM table_1 WHERE id > @id ORDER BY id LIMIT 1;
[/sql]
и увеличиваем счетчик непопаданий.
2. проверяем счетчик непопаданий. Если он вышел за пределы некоего эмпирического критерия выполняем фазу 1.
Система автономна и устойчива. Операции нересурсоемки.
Можно вариант апргрейднуть с целью уменьшения кол-ва запросов - например делать сразу
[sql]
SELECT * FROM table_1 WHERE id >= @id ORDER BY id LIMIT 1;
[/sql]
и проверять на совпадение @id и id полученного, для выяснения попадания в дырку - не знаю что будет лучше.
---------------
Просто как новационная идея

принимаются ахи, охи и помидоры на кетчуп.