Мой (SQL) выбор случайных строк, новый способ, помогите оценить, насколько он хорош? - PullRequest
0 голосов
/ 10 марта 2011

Я снова столкнулся с проблемой выбора случайного подмножества строк. И, как многие, вероятно, знают, ORDER BY RAND () довольно неэффективен, или, по крайней мере, это консенсус. Я прочитал, что mysql генерирует случайные значения для каждой строки в таблице, затем фильтрует, затем упорядочивает по этим случайным значениям, а затем возвращает множество. Наибольшее влияние на производительность, по-видимому, оказывает тот факт, что генерируется столько же случайных чисел, сколько строк в таблице. Поэтому я искал, возможно, лучший способ вернуть случайное подмножество результатов для такого запроса:

SELECT id FROM <table> WHERE <some conditions> LIMIT 10; 

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

SELECT id FROM <table> WHERE <some conditions> ORDER BY RAND() LIMIT 10; (a)

Теперь, подумав, я предложил другой вариант для этой задачи:

SELECT id FROM <table> WHERE (<some conditions>) AND RAND() > x LIMIT 10; (b)

(Конечно, мы можем использовать < вместо >). Здесь мы берем x из диапазона 0.0 - 1.0. Теперь я не совсем уверен, как MySQL справляется с этим, но я предполагаю, что сначала он выбирает строки, соответствующие <some conditions> (используя index [es]?), А затем генерирует случайное значение и видит, должен ли он возвращать или отбрасывать строку. Но что я знаю :) вот почему я спрашиваю здесь. Итак, некоторые наблюдения об этом методе:

  • Во-первых, это не гарантирует, что запрашиваемое количество строк будет возвращено, даже если совпадающих строк будет намного больше, чем необходимо, особенно это верно для x значений, близких к 1.0 (или близких к 0.0, если мы используем <) * * тысяча двадцать-два
  • возвращенный объект на самом деле не имеет случайного порядка, это просто объекты, выбранные случайным образом, по порядку использованного индекса или по тому, как они хранятся (?) (Конечно, в некоторых случаях это может вообще не иметь значения)
  • нам, вероятно, нужно выбрать x в соответствии с размером набора результатов, поскольку, если у нас большой набор результатов и x, скажем, 0.1, очень вероятно, что будут возвращены только некоторые случайные первые результаты. большую часть времени; с другой стороны, если у вас небольшой набор результатов и вы выбрали большой x, вполне вероятно, что мы могли бы получить меньше объектов, чем нам хотелось бы, хотя их достаточно

Теперь несколько слов о производительности. Я провел небольшое тестирование с использованием jmeter. <table> имеет около 20 тыс. Строк, и примерно 2-3 тыс. Строк соответствуют 1034 *. Я написал простой PHP-скрипт, который выполняет запрос и print_r - результат. Затем я настраиваю тест с использованием jmeter, который запускает 200 потоков, то есть 200 запросов в секунду, и запрашивает указанный скрипт PHP. Я запускал его до тех пор, пока не было выполнено около 3 000 запросов (среднее время ответа стабилизировалось задолго до этого). Также я выполнил все запросы с SQL_NO_CACHE, чтобы предотвратить какой-либо эффект кеша запросов. Среднее время ответа было:

  • ~ 30 мс для запроса (а)
  • 13-15 мс для запроса (b) с x = 0.1
  • 17-20 мс для запроса (b) с x = 0.9, как ожидается, большее значение x медленнее, так как должно отбрасывать больше строк

Итак, мои вопросы: что вы думаете об этом методе выбора случайных строк? Может быть, вы использовали это или попробовали и видите, что это не сработало? Может быть, вы можете лучше объяснить, как MySQL обрабатывает такой запрос? Какие могут быть некоторые оговорки, о которых я не знаю?

РЕДАКТИРОВАТЬ: Я, вероятно, не был достаточно ясен, дело в том, что мне нужны случайные строки запроса, а не просто таблица, поэтому я включил <some conditions>, и их довольно много. Более того, в таблице гарантированно есть пропуски в id, но это не имеет большого значения, поскольку это не случайные строки из таблицы, а из запроса, и таких запросов будет довольно много, поэтому предложения, включающие многократное обращение к таблице, не звучат привлекательно. <some conditions> будет меняться, по крайней мере, немного между запросами, что означает, что будут запросы с различными условиями.

Ответы [ 3 ]

0 голосов
/ 10 марта 2011

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

Либо используйте запрос статуса таблицы, чтобы определить следующий auto_increment, либо число строк, либо используйте (выберите count (*)). Затем вы можете заранее определить значение auto_increment для случайного элемента, а затем выбрать этот уникальный элемент.

Это не удастся, если у вас есть пробелы в поле auto_increment, но если он будет быстрее, чем другие ваши методы, вы могли бы выполнить цикл несколько раз или вернуться к отказоустойчивому методу в случае возврата нулевых строк. В лучшем случае это может быть большая экономия, в худшем - сравнимый с вашим текущим методом.

0 голосов
/ 10 марта 2011

Вы используете неправильную структуру данных.

Обычный метод примерно такой:

  1. Узнайте количество элементов n - что-то вроде SELECT count(id) FROM tablename.
  2. Выберите r различных случайных чисел в интервале [0, n). Я обычно рекомендую LCG с подходящим образом выбранными параметрами, но простой выбор r случайных чисел и отбрасывание повторов также работает.
  3. Вернуть эти элементы. Твердый бит.

Похоже, что MySQL поддерживает индексированные поиски с чем-то вроде SELECT id from tablename ORDER BY id LIMIT :i,1, где: i - это связанный параметр (я забыл, какой синтаксис использует mysqli); альтернативный синтаксис LIMIT 1 OFFSET :i. Это означает, что вы должны делать r запросов, но это может быть достаточно быстро (это зависит от накладных расходов на оператор и насколько эффективно он может выполнять OFFSET).

Альтернативный метод, который должен работать для большинства баз данных, немного похож на разделение на интервалы:

  1. SELECT count(id),max(id),min(id) FROM tablename. Тогда вы знаете, что строки [0, n-1] имеют идентификаторы [min, max].
  2. Итак, строки [a, b] имеют идентификаторы [min, max]. Вы хотите грести я. Если я == а, вернуть мин. Если я == b, вернуть макс. В противном случае, делить пополам:

    1. Выберите split = min+(max-min)/2 (избегая целочисленного переполнения).
    2. SELECT count(id),max(id) WHERE :min < id AND id < split и SELECT count(id),min(id) WHERE :split <= id and id < :max. Два числа должны равняться b-a + 1, если таблица не была изменена ...
    3. Выясните, в каком диапазоне находится i, и обновите a, b, min и max соответствующим образом. Повторите.

Существует множество крайних случаев (я, вероятно, включил несколько ошибок по одному) и несколько потенциальных оптимизаций (вы можете сделать это для всех индексов одновременно, и вам на самом деле не нужно делать два запросы на итерацию, если вы не предполагаете, что i == b подразумевает id = max). На самом деле не стоит делать, если SELECT ... OFFSET даже смутно эффективен.

0 голосов
/ 10 марта 2011

Исходя из собственного опыта, я всегда использовал ORDER BY RAND(), но это влияет на производительность больших наборов данных.Например, если у вас была таблица, которая была слишком большой, чтобы поместиться в памяти, MySQL создаст временную таблицу на диске, а затем выполнит сортировку файлов для рандомизации набора данных (если это позволяет механизм хранения).Ваше предложение LIMIT 10 не будет влиять на время выполнения запроса AFAIK, но оно уменьшит размер данных для отправки обратно клиенту.

По сути, лимит и порядок следования происходят после выполнения запроса (полное сканирование таблицы, чтобы найти совпадающие записи, затем упорядочить, а затем ограничить).Любые строки за пределами вашего предложения LIMIT 10 отбрасываются.

В качестве примечания добавление в SQL_NO_CACHE отключит внутренний кэш запросов MySQL, но не помешает вашей операционной системе кэшировать данные (из-заслучайный характер этого запроса, я не думаю, что он в любом случае сильно повлияет на ваше время выполнения..

...