Алгоритмы (боремся с разжижением мозга)

Цитата ("ArtPro"):

Кстати вот задачка 3:
найдите максимально быстрый вариант выборки случайных значений из таблицы
SELECT * FROM tTable ORDER BY RAND() LIMIT 10; - вариант для новичка.
усложним задачу тем, что id не непрерывны.

Ну вот, Вы опять даете неполное задание. О каких объемах данных идет речь? И, как я понял, рассматривается именно MySQL? (ряд других СУБД имеют свои решения данной задачи)

Если таблица небольшая, скажем, пара сотен записей, то вышеприведенный пример с ORDER BY RAND() работает прекрасно.
Более того, это наиболее надежное решение из всех возможных, при этом соблюдается приемлемаю производительность, и на это решение тратится минимум времени (и соответственно средств заказчика).
Другие решения или ненадежны, или работают менее универсально, или неоправданно сложны, или требуют блокировок или транзакций с уровнем изоляции минимум repeatable read.

Допустим, имеем таблицу с большим количеством записей...

=====
Лабораторная работа N1, случайные выборки из таблицы.

Создаем таблицу table1 с первичным ключом id, генерим 500.000 записей.
Делаем ряд запросов (тесты проводим с MyISAM и InnoDB без блокировок и транзакций), запускаем по 10 раз, вычисляем среднее и минимальное время.

1. Делаем запрос с ORDER BY RAND()

SELECT id FROM table1 ORDER BY RAND() LIMIT 10;

MyISAM 0.78 сек
InnoDB 1.20 сек

2. Делаем запрос, предварительно сделав запрос SELECT COUNT(*) ..., и вычислив случайные номера записей (rx), с использованием UNION:

(SELECT id FROM table1 LIMIT r1, 1)
UNION
(SELECT id FROM table1 LIMIT r2, 1)
UNION
(SELECT id FROM table1 LIMIT r3, 1)
UNION
(SELECT id FROM table1 LIMIT r4, 1)
UNION
(SELECT id FROM table1 LIMIT r5, 1)
UNION
(SELECT id FROM table1 LIMIT r6, 1)
UNION
(SELECT id FROM table1 LIMIT r7, 1)
UNION
(SELECT id FROM table1 LIMIT r8, 1)
UNION
(SELECT id FROM table1 LIMIT r9, 1)
UNION
(SELECT id FROM table1 LIMIT r10, 1);

MyISAM 1.31 сек
InnoDB 2.90 сек

Выводы.

Способ N1 с ORDER BY RAND(), несмотря на то, что он очень неэффективный, работает очень надежно, гарантированно выдавая результат независимо от состояния набора данных, в том числе и при условии конкурентного доступа.

Для способа N2 придется использовать а) предварительный запрос SELECT COUNT(...) и б) блокировки (для MyISAM) или транзакции с уровнем изоляции repeatable read или sirializable (для InnoDB ) чтобы гарантировать корректный результат в условиях конкурентного доступа к данным. Если это делать, то время выполнения этих запросов можно увеличить еще примерно на 50%.

Использование набора запросов, объединенных через UNION, работает медленнее на больших наборах данных, чем даже тормозной ORDER BY RAND(). UNION ALL позволяет выиграть несколько микросекунд, но проблему не решает.

=====
Лабораторная работа N2.

Если сужать исходный набор данных, используя например WHERE RAND() < 0.1, то ORDER BY RAND() работает значительно быстрее.
Например, на используемой мной в примере выше таблице c 500.000 записями запрос

SELECT id FROM table1 WHERE RAND() < 0.1 ORDER BY RAND() LIMIT 10;

отрабатывает за 0.34 сек, почти в 2.5 раза быстрее.

Но все равно это не хороший путь, я не спорю. Хотя и его нельзя отвергать в ряде случаев.

=====
Но вообще, если в высокозагруженной системе нужно делать частые выборки случайных записей из некоторой таблицы или вьюва, даже если это миллионы записей, то намного правильнее хранить ID этих записей (а если позволяют ресурсы, то и таблицу целиком, но это уже опционально) в памяти в кеше, и делать поиск случайных записей именно в памяти, затем при необходимости извлекая записи из таблицы сразу по ID. Даже если там 10 млн записей, это всего лишь 40 Mb в кеше, не так уж и много для выделенного для данной задачи сервера.

Цитата ("ArtPro"):

задача №2
пока ответов нет

Потому что условие неполное, как и в остальных Ваших задачах.
Из текущей постановки данной задачи, не зная деталей и ограничений, там что угодно можно придумать, десятки вариантов решений.

Цитата ("tvv"):

там что угодно можно придумать, десятки вариантов решений.

я этого и добиваюсь.
иногда варианты, которые рождаются с голове, рождают "Фичи", которые нравятся заказчику и исходные условия корректируются.

зачастую у клиентов возникают идеи сервисов в виде 1-2 предложений.
но не суть важно.
я просто хочу расшевелить программеров.
Сам знаю как достает делать рутину и интересных задачек не так и много, но они же интересные.

ArtPro, а как Вы решили Вашу задачу N3?

Я не оригинален. Для начала узнаем общее кол-во записей в таблице:

SELECT COUNT(*) FROM tTable;

Далее просто вычислим произвольное число от 0 до кол-ва записей в этой таблице

rand_row = round(rand() * row_count);

Теперь без проблем можно сделать выборку произвольной записи:

SELECT * FROM tTable LIMIT rand_row, 1;

На PHP все очень просто:

$row_count = mysql_result(mysql_query('SELECT COUNT(*) FROM tTable;'), 0);

$query = array();

while (count($query) < 10) {

$query = '(SELECT * FROM tTable LIMIT '.rand(, $row_count).', 1)';

}

$query = implode(' UNION ', $query);

$res = mysql_query($query);

Все просто и быстро. На исходной таблице с десятью тысячами записей прирост производительности по сравнению с первоначальным «ленивым» начальным вариантом более чем в 12 раз.
Если записей в исходной таблице не так много и появление повторяющихся строк в выборке неприемлемо — то можно предварительно сформировать список неповторяющихся произвольных значений, а потом уже составить по ним запрос.

Решение на MySQL
Как вариант можно еще сделать это в виде хранимой процедуры:

CREATE PROCEDURE `spRandomSelect`(IN aSchema VARCHAR(50), IN aTable VARCHAR(50), IN aNumRows INTEGER(11))

NOT DETERMINISTIC

READS SQL DАТА

BEGIN

DECLARE iQuery VARCHAR(10000);

DECLARE iNumRows INTEGER(11);


SET iNumRows = (SELECT `TABLE_ROWS` FROM `information_schema`.`TABLES` t

WHERE t.`TABLE_SCHEMA` = aSchema AND t.`TABLE_NAME` = aTable);

SET iQuery = '';

loop1: LOOP

SET iQuery = CONCAT(iQuery, '(SELECT * FROM `', aSchema, '`.`', aTable,

'` LIMIT ', ROUND(RAND(UNIX_TIMESTAMP() + aNumRows) * iNumRows), ', 1)');

IF aNumRows > 1 THEN

SET iQuery = CONCAT(iQuery, ' UNION ');

END IF;

SET aNumRows = aNumRows - 1;

IF aNumRows > THEN

ITERATE loop1;

END IF;

LEAVE loop1;

END LOOP loop1;

SET @iQuery = iQuery;

PREPARE iExecStmt FROM @iQuery;

EXECUTE iExecStmt;

DRОP PREPARE iExecStmt;

END;

Вы, по сути, используете то же решение, что я привел ранее с UNION.
К сожалению, на больших объемах данных оно работает даже медленнее, чем ORDER BY RAND(), (пожалуйста смотрите цифры в моей "лабораторной работе" ).

Но главная проблема: этот вариант работает неправильно при условиях наличия конкурентного доступа к данным (если не использовать полную блокировку таблиц, или высокие уровни изоляции транзакций).


Типичный пример проблемы:
— Вы делаете шаг 1: выполнили SELECT COUNT(*), и предвычислили номер записи, например это оказалась последняя запись.
— Другая транзакция удалила эту запись.
— Вы делаете шаг 2: пытаетесь получить эту запись, номер которой вычислили ранее в шаге 1. Epic fail.


Кстати, Ваш ответ дословно повторяет статью на Хабре от 11 марта 2009 года: посилання
(Кстати, случайно автор этой статьи — не Вы ли, или кто-то из Ваших знакомых?)

Там ниже в комментах к этой статье я привел достаточное количество обоснований, доказывающих ошибочность и неэффективность этого решения, привел замеры времени, и т.д.


По сути, у этого решения, что Вы используете, только одно преимущество — относительно (по сравнению с ORDER BY RAND()) низкое потребление памяти на сервере. При условии что правильно оттюнили настройки MySQL, конечно.
Но увы... даже если бы оно и работало правильно, все равно предложенное Вами решение лучше на практике не использовать. Слишком много недостатков.

Кстати, попробуйте для эксперимента выбрать предложенным Вами способом не 10, а например 100 случайных записей. Очень удивитесь. Например, на моем наборе данных это заняло более 10 секунд (сравните менее чем с 1 секундой на ORDER BY RAND(), или 3.2 секунды на решении с курсором).


Еще одна ошибка в предложенном Вами способе: данный способ не учитывает повторы.
То есть, если rand($count) выдаст какое-то значение например дважды, а это вполне возможно, то данный способ вернет не 10 записей, как это требуется по условию, а меньшее количество.

Цитата ("tvv"):

(Кстати, случайно автор этой статьи — не Вы ли, или кто-то из Ваших знакомых?)

не,я не автор, автора знаю, работали вместе.

это всего лишь один из вариантов у которого есть недостатки, но что радует, что вам не лень тестить

Цитата ("ArtPro"):

это всего лишь один из вариантов у которого есть недостатки, но что радует, что вам не лень тестить

Это весьма серьезные недостатки.
Причем такие, которые делают это решение неприемлемым в коммерческих проектах.
Надеюсь, автор той статьи на Хабре не использует предложенное им решение на практике.

Цитата ("tvv"):

Надеюсь, автор той статьи на Хабре не использует предложенное им решение на практике.

с рядом ограничений все работает

до этого было сделано вообще так, что генерировался массив из 10 случайных чисел в пределах максимального id
и потом where id IN (массивчик наш)
получали <=10 чисел и делали еще выборку недостающих.