Итак, дано:
Две таблицы — shops и products
Грубо говоря — площадка, где разные магазины размещают свои товары.
И вот, встала необходимость сделать на главной странице выдачу товаров, но так, чтоб пользователь не видел кучу товаров одного магазина. Магазины надо чередовать.
shops:
- id int not null auto_increment primary key,
- name varchar(255) null
products:
- id int not null auto_increment primary key,
- shop_id int not null,
- name varchar(255) null,
Немного погуглив — толкового решения найдено не было. Но появилась мысль, как реализовать выборку с чередованием магазинов.
Изначально опишу алгоритм:
- Необходимо выбрать все товары и отсортировать их по магазину.
- Далее пронумеровать каждый товар, начиная с 1 с интервалом, равным количеству магазинов.
- При нумерации, как только заканчиваются товары одного магазина — нумерация сбрасывается на ноль, сдвигается на единицу, и начинается снова
- Выбрать товары, отсортировав их по пронумерованному полю
И все это средствами MySQL. И желательно одним запросом.
Сложив в голове план — можно приступить к реализации. Что нам понадобиться?
- @i — Счетчик, который будет нумеровать наши товары
- @cnt — Количество магазинов
- @delta — дельта, на которую сдвигается счетчик при нумерации товаров следующего магазина
- @cur — id текущего магазина, для добавления дельты и сброса счетчика при нумерации нового магазина
Объявим наши переменные:
set @cnt = 0;
set @i = 0;
set @delta = 0;
set @cur = 0;Далее присвоим начальные значения (кол-во магазинов и id первого магазина).
select @cur:=id from shops order by id limit 1;
select @cnt:=count(id) from shops;Теперь можно приступить к самой выборке. Что нам необходимо?
- Необходимо нумеровать товары с интервалом, равным кол-ву магазинов.
- При окончании товаров одного магазина — сбрасывать счетчик, добавлять дельту и менять текущий магазин.
У меня получился такой запрос:
select id, shop_id, @i:=@i+@cnt as counter,
IF(@cur<>shop_id,@delta:=@delta+1,@delta) as delta,
IF(@cur<>shop_id,@i:=@delta,@i) as cur,
IF(@cur<>shop_id,@cur:=shop_id,@cur) as curshop
from t_product order by shop_idПодробнее о том, что здесь есть что:
@i:=@i+@cntВ каждой строке мы увеличиваем наш счетчик на число, равное кол-ву магазинов. Т.е., если у нас 5 магазинов, то у нас получится следующая нумерация: 0, 5, 10, 15 и т.д.
IF(@cur<>shop_id,@delta:=@delta+1,@delta) as deltaКак только у нас появляется новый магазин — мы увеличиваем сдвиг на единицу. Т.е. для первого магазина сдвиг будет равен 0, для второго — 1 и т.д.
IF(@cur<>shop_id,@i:=@delta,@i) as cur,При смене магазина нам так-же надо сбросить наш счетчики начать нумеровать товары с начала, не забыв добавить сдвиг.
IF(@cur<>shop_id,@cur:=shop_id,@cur) as curshopИ в конце концов — обновить текущий магазин, товары которого мы нумеруем…
В результате мы получим выборку типа:
| id | shop_id | counter | delta | cur | curshop |
|---|---|---|---|---|---|
| 43989 | 1 | 10 | 0 | 10 | 1 |
| 46989 | 1 | 20 | 0 | 20 | 1 |
| 114172 | 1 | 30 | 0 | 30 | 1 |
| 83989 | 1 | 40 | 0 | 40 | 1 |
| 67172 | 1 | 50 | 0 | 50 | 1 |
| 94672 | 2 | 11 | 1 | 11 | 2 |
| 6489 | 2 | 21 | 1 | 21 | 2 |
| 41989 | 2 | 31 | 1 | 31 | 2 |
| 61672 | 2 | 41 | 1 | 41 | 2 |
| 97489 | 3 | 12 | 2 | 12 | 3 |
Тут мы видим, что счетчик прибавляется корректно, при смене магазина он сбрасывается, добавляется сдвиг и нумерация начинается с начала (с учетом сдвига).
Собственно, дело осталось за малым. Обернуть полученную выборку в подзапрос и отсортировать по нашему счетчику:
select id as product_id, shop_id, cur from (
select id, shop_id, @i:=@i+@cnt as counter,
IF(@cur<>shop_id,@start:=@delta+1,@delta) as delta,
IF(@cur<>shop_id,@i:=@delta,@i) as cur,
IF(@cur<>shop_id,@cur:=shop_id,@cur) as curmag
from products order by shop_id
) as A order by cur ;Вуаля! У нас получилась выборка товаров с чередующимися магазинами:
| product_id | shop_id | cur |
|---|---|---|
| 4187 | 1 | 10 |
| 7483 | 2 | 11 |
| 4045 | 3 | 12 |
| 9091 | 4 | 13 |
| 1457 | 5 | 14 |
| 2387 | 6 | 15 |
| 8109 | 7 | 16 |
| 1445 | 8 | 17 |
| 2102 | 9 | 18 |
| 9245 | 10 | 19 |
| 6744 | 1 | 20 |
| 7854 | 2 | 21 |
| 2164 | 3 | 22 |
Есть один минус — товары у каждого магазина идут по порядку. Т.е. в начале мы увидим самый первый товар первого магазина, затем первый товар второго магазина, третьего, четвертого и т.д. Дальше пойдут вторые товары магазинов, третьи и так далее.
Дабы избавиться от этой закономерности нам необходимо перемешать товары в первоначальной выборке, обернув ее в еще один подзапрос:
select id as product_id, shop_id, cur from (
select id, shop_id, @i:=@i+@cnt as counter,
IF(@cur<>shop_id,@start:=@delta+1,@delta) as delta,
IF(@cur<>shop_id,@i:=@delta,@i) as cur,
IF(@cur<>shop_id,@cur:=shop_id,@cur) as curmag
from products order by shop_id
from (select id, shop_id from products order by shop_id, rand()) as A order by shop_id) as B order by cur;Так наши товары уже будут перемешаны еще до их нумерации.
Собственно на этом решение задачи и закончилось. Полный запрос можно посмотреть под катом.
set @cnt = 0;
set @i = 0;
set @start = 0;
set @cur = 0;
select @cur:=id from shops order by id limit 1;
select @cnt:=count(id) from shops;
select id as product_id, shop_id, cur from (
select id, shop_id, @i:=@i+@cnt as counter,
IF(@cur<>shop_id,@start:=@delta+1,@delta) as delta,
IF(@cur<>shop_id,@i:=@delta,@i) as cur,
IF(@cur<>shop_id,@cur:=shop_id,@cur) as curmag
from products order by shop_id
from (select id, shop_id from products order by shop_id, rand()) as A order by shop_id) as B order by cur;Ради интереса — посмотрел скорость выборки. Результаты на мой взгляд получились неплохие:
10 магазинов, 10000 товаров — ~16ms (0.016s)
100 магазинов, 1000000 товаров — ~2568ms (2.568s)
100 магазинов, 10000000 товаров — 129951ms (2m 9.951s)
Я считаю, что это неплохие результаты, хотя, конечно, надо потестировать в боевом режиме.
P.S. Для меня пока остался только один невыясненный вопрос. Все хорошо, но что делать при пагинации? Ведь каждая следующая страница — это новый запрос.
Соответственно, перемешанные в магазинах товары будут получать новый порядковый номер и могут попадаться в выборке не один раз.
Если есть мысли на этот счет — буду благодарен услышать их в комментах.
Всем спасибо за внимание )
Комментарии (37)
belousovsw
31.03.2017 10:11В таблице с магазинами заведите поле для последнего сгенрированного Вами идентификатора товара в рамках конкретного магазина, а в таблице с товаром заведите поле для нумерации товара в пределах одного магазина и при вставке заполняйте его порядковым номером, и последний номер сохраняйте в поле таблицы магазинов.
Получится то же эффект что и у Вас в статье, только генерировать Вы будете не на этапе выборки, а на этапе вставки. Что при выборке даст высочайшую производительность.
CrazyXoma
31.03.2017 10:21Тогда выборка будет всегда одинаковая. Товары будут всегда иметь постоянный порядковый номер и выводиться на одном месте.
А показываться должны случайные товары
danilychen
31.03.2017 10:22Можно добавить в таблицу с магазинами и в таблицу с товарами по столбцу, где будут хранится рандомные числа. Соответственно заполняться они должны при создании магазина и товара. А потом сортируйте по этим полям. И пагинацию можно использовать.
CrazyXoma
31.03.2017 10:23Опять же — тогда выборка будет всегда одинаковая. Нужны именно случайные товары
danilychen
31.03.2017 10:26+1О какой пагинации тогда речь? Нужно фиксировать какой-то интервал времени, чтобы можно было использовать пагинацию (час, день, неделя)
CrazyXoma
31.03.2017 10:28Случайные товары на главной… Изначально выводятся 20 к примеру. При прокручивании страницы — добавляются еще 20 и т.д…
Получается бесконечный скроллинг из случайных товаров. Причем так, чтоб товары одного магазина не шли подряд.
TT13
31.03.2017 11:22На самом деле выборка будет случайной если грамотно использовать имеющиеся в таблицах рандомные числа. Как вариант — перед выборкой генерируете случайный диапазон (фиксированного размера), в который попадет только часть рандомных чисел. Это работает довольно быстро.
CrazyXoma
31.03.2017 11:24Опять-же, выборка будет довольно статичной.
Согласен, если пронумеровать товары при добавлении, а потом выбирать диапазон — можно получить список товаров, удовлетворяющий условию, по которому магазины не должны повторяться. Но порядок в таком случае поять-же будет всегда одинаковый…TT13
31.03.2017 11:32Пронумеровать — это если записи не будут удаляться. Если нужно равномерное распределение — лучше использовать рандомные числа.
Как бонус получаете работающую пагинацию, просто используете сгенерированный ранее диапазон и значения повторятся уже не будут.CrazyXoma
31.03.2017 11:42Но последовательность всегда будет одинакова…
т.е. если товары идут в порядке 1,4,3,5,12,36,51,10,22
То порядок будет всегда такой…
4,3,5 или 3,5,12 или 1,4,3…
Т.е. порядок не перемешивается…
tehSLy
31.03.2017 10:23+3По чесноку, с первых строк задача вызвала недоумение, дочитал по диагонали, наблюдая простыни запросов, и минуты времени на их выполнение. Это опять же вызвало недоумение.
Вообще у меня в это утро много чего вызывает недоумениеМожете объяснить несколько подробнее преследуемые цели? Конечно, умные функции в запросах это круто, но забивать гвозди пневмопрессом — это перебор(А может тут все же и не гвозди, вот я и хочу разобраться).CrazyXoma
31.03.2017 10:26Ну суть проста — есть N магазинов, есть по M товаров в каждом.
На главной странице выводятся случайные товары.
Но получается так, что если у одного магазина 30 товаров, а у остальных по 5 (грубо говоря), то на главной странице может висеть половина товаров из одного магазина.
Чего и надо избежать.
Т.е. несмотря на кол-во товаров в магазине (1000 или 10) их необходимо вставлять в топ 20 с одинаковой вероятностью.tehSLy
31.03.2017 14:03А что за группы товаров? Это топы по популярности внутри магазина/в целом, либо это топы по определенной группе товаров (опять же внутри магазина/в целом), либо что? Просто мне видится более логичным, раз уж нужны рандомные магазины, то и выбирать рандомные магазины, а там и товары джойнить.
CrazyXoma
31.03.2017 14:15Не правильно поняли… Нужны рандомные товары… Совсем рандомные. Без топов.
Т.е. список случайных товаров всех магазинов. Но так, чтоб магазины не шли друг за другомtehSLy
31.03.2017 14:44Тогда в чем проблема записывать все айди товаров, доступных в данном магазине в отдельную таблицу; при обращении, средствами платформы вывести N неравных, рандомных айдишников магазинов — столько, сколько нужно, для страницы, либо для списка в целом, если кешировать. И потом, с помощью той же платформы получить айдишник товара в диапазоне от 0 до количества доступных товаров, для данного магазина — замассивить эти айдишники, и потом дернуть одним запросом. ~20 строк кода, перфоманс++, все как надо, просто и лаконично, порчу на приход новых разработчиков не наводит.
http3
31.03.2017 10:59Согласен на счет популярных.
А также можно было счетчик добавить в таблицу товаров.
vlreshet
31.03.2017 12:21+1Не бросайте помидорами за вопрос — а не проще ли на стороне сервера делать n параллельных запросов к БД (где n — количество магазинов), и потом перемешивать их на стороне сервера? Да, возможно это будет чуть медленнее чем одним запросом, но это можно нивелировать кешированием (тогда даже быстрее станет), плюс совершенно исчезает проблема пагинации.
demimurych
31.03.2017 12:31А Вы правильно смотрели скорость выполнения запроса? Делали EXPLAINE и SQL_NO_CACHE?
Предполагаю что, те цифры которые вы увидели при выполнении запросов, это цифры уже загруженным кешем от предыдущего выполнения этих же запросов.
Но даже если закрыть на это глаза в выборке 100 магазинов, 1000000 товаров — ~2568ms (2.568s) то есть на незначительном количестве данных вы имеете УЖЕ 2 секунды просто на получение данных. Что не приемлемо в принципе.
Впрочем, Вам конечно виднее, и возможно вы никогда не выйдете за рамки 10 магазинов.
sspat
31.03.2017 12:41Такие запросы база не может кешировать в принципе, тут и rand() и подзапросы, результат-то каждый раз разный.
https://dev.mysql.com/doc/refman/5.7/en/query-cache-operation.html
CrazyXoma
31.03.2017 13:39За скорость — честно не смотрел через експлейн… Просто посмотрел, как шторм ответил. + это на локальной машине, а не на сервере.
aspirineilia
31.03.2017 13:28Любителям извращений можно ещё и с GROUP_CONCAT + FIND_IN_SET поиграться.
reilag
31.03.2017 14:09Пагинировать лучше всего, кешируя только последовательность ID товаров в каком-нибудь Redis. Предварительно к сессии привяжи этот токен.
Domini
31.03.2017 16:19Я возможно не до конца понял, что вам надо, но в первую очередь в голову пришел следующий подход.
При добавлении товара всегда проставлять ему номер по порядку в рамках конкретного магазина. Это относительно дешево. В таблице магазинов держать максимальный номер по порядку для каждого магазина.
Кэшировать соответствие магазин — максимальный номер по порядку. Если магазинов не планируется в ближайшее время тысячи, то тоже относительно дешево. Поскольку изменения происходят редко, то консистентность кэша достаточно поддерживать просто протуханием через некоторое время — новый товар не будет отображаться лишь это время.
Выбрать генератор случайных чисел, у которого можно независимо от других его вызовов (условно, вроде mt_rand из PHP не подойдет) читать и писать состояние (сид фактически). Для первой страницы генерировать случайный сид и писать его в генератор. Для каждого магазина (ну или для нужного количества, если на странице надо показать меньше записей, чем всего магазинов) генерировать число от 1 до максимального номера по порядку этого магазина (см. кэш выше). После генерации достаточного количества прочитать состояние сида.
Построить индекс shop_id, index по таблице products. Сделать в неё запрос вида SELECT… FROM products WHERE (shop_id, index) IN((X1, I1), (X2, I2), ...), где Xn и In — идентификатор n-ого магазина и сгенерированный для него случайный номер по порядку. Запрос должен быть дешевым.
Вывести это на страницу. В ссылке на вторую страницу передать прочитанное состояние сида. На второй странице сидировать им, а не случайным.
Оставшаяся проблема: товары будут повторяться на последующих страницах, когда генератор будет создавать одно и то же случайное число на разных страницах.
Скорее всего есть решение проще.
SbWereWolf
01.04.2017 13:44CrazyXoma случая выборка получается запросами к случайным записям, то есть
LIMIT 1,random_offset
В WHERE можно задать магазин, если запрос будет параметризированным, то с его отработкой (быстродействием) не будет проблем.
Хотя конечно если между сервером приложений и сервером СУБД сетевой обмен на один запрос занимает сотни миллесекунд, то время на то что бы надёргать 20 записей, уйдёт больше чем если один раз дёрнуть всё выборку пронумерованную вашим способом :)
kolu4iy
02.04.2017 14:56Задать веса магазинам, в зависимости от количества товара в каждом (больше товара — реже встречается). Так вы избежите ситуации "на странице товара одного магазина". Использовать вес для рандома. Только не надо настоящий рандом — он медленный. Надо его симулировать. Вообще, если честно, задача кажется надуманной, но не буду с вами спорить.
LeonidZ
Вы просто невероятный извращенец. Такое впечатление, что у вас там 2-3 магазина, и в каждом по 100 товаров. Т.к. иначе запросы у вас будут выполняться по много секунд, и это просто недопустимо для выполнения во время загрузки страницы.
Возможно, вы это делаете раз в 10 минут и кешируете, а при загрузке просто берете подготовленные данные из кеша — но все равно это очень-очень плохой способ.
Я вам не предложу взамен готового решения, т.к. нет условий задачи. С моей точки зрения, перебирать все товары — уже очень плохо, перемешивать все товары — еще хуже (представьте, что их там несколько миллиардов).
Скорее всего показывать на главной нужно самые популярные товары, а популярность у вас 100% обсчитывается по крону и пишется в отдельную табличку — и не важно на самом деле, что случайно попадет 2-3 товара из всей пачки из 1 магазина.
Если же магазинов много (больше, чем товаров), то при обсчете популярности проще ы shops добавить колонку most_popular_product_id и обновлять ее, а затем выбирать случайные 20 магазинов с их самыми популярными продуктами.
Если же вам нужен полный рандом среди абсолютно всех товаров, то зачем городить огород, если можно (это ужасно, но на порядок лучше того, что сделали вы) тогда select * from products order by rand() limit 20;
И это полный рандом, с распределением среди магазинов, пропорциональным количеству товаров у них.
CrazyXoma
Я буду считать это за комплимент =)
А по сути:
Я при вел пример, что для 10 магазинов и 10000 товаров запрос выполняется 0.056с.
Нет, нужны именно все товары в случайном порядке
Именно в этом и состояла задача, чтоб не попали 2-3 товара из 1-го магазина
Опять же — получается, что в выборке будут попадаться товары одного магазина.
Ну и в заключении напишу, что это все таки пока теоретические изыскания =)
second_pilot
Order by rand()? Это примерно так же медленно будет
CrazyXoma
примерно так-же медленно, но не вернет нужного результата
hooper
Есть такие оконные функции. Изучите. Они много умеют.
ps: Согласен с остальными. Изврату не место в prod-е. Проблема в логике задачи.
symbix
Если бы они еще в mysql были… К сожалению, самое близкое, что есть в mysql — это group_concat.