Выбрать несколько записей из каждой группы.

Автор: Василий Лукьянчиков , vl (at) sqlinfo (dot) ru

Судя по сообщениям на форуме SQLinfo, выбор более одной строки из группы - часто встречающаяся задача (например, несколько популярных/новых товаров из каждой категории, последние новости для каждой рубрики, и т.д.), которая вызывает сложности при попытке решить её средствами SQL. В статье объясняется несколько способов как одним запросом получить N первых, последних или случайных строк из группы и дана оценка их эффективности с точки зрения производительности.

Разберем решения на примере таблицы сообщений, имеющей поля (post_id, user_id, date_added, post_text), в которой хранится id сообщения, id пользователя, дата добавления и текст поста. Предполагается, что комбинация (user_id, date_added) уникальна, т.е. пользователь не может разместить 2 сообщения в один момент времени.

Код создания и заполнения таблицы

CREATE TABLE `posts` (

  `post_id` int(11) NOT NULL AUTO_INCREMENT,

  `user_id` int(11) NOT NULL,

  `date_added` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,

  `post_text` text NOT NULL,

  PRIMARY KEY (`post_id`),

  UNIQUE KEY `user_id` (`user_id`,`date_added`)

) ENGINE=InnoDB DEFAULT CHARSET=utf8;

INSERT INTO `posts` VALUES (1,1,'2018-04-17 05:37:15','Есть таблица товаров. Каждый товар относится к какой-то категории. Как вывести по 3 товара из каждой категории?');

INSERT INTO `posts` VALUES (2,1,'2018-04-17 05:43:26','В идеале хочется получить последние N товаров из каждой категории одним запросом. Может есть какой-нибудь элегантный способ?');

INSERT INTO `posts` VALUES (3,2,'2018-04-17 11:13:22','Выборка по N последних товаров каждой категории. Просто не хочется делать запрос на каждую категорию.');

INSERT INTO `posts` VALUES (4,1,'2018-04-17 15:38:04','Как вывести по N строк из каждой группы? Например, последние новости для каждой рубрики или несколько популярных товаров из каждой категории');

INSERT INTO `posts` VALUES (5,1,'2018-04-17 15:52:18','Помогите написать запрос. Выбор по несколько строк из каждой группы в запросе');

INSERT INTO `posts` VALUES (6,4,'2018-04-18 12:17:05','MySQL не поддерживает LIMIT внутри IN подзапросов. Как написать запрос с лимитом строк внутри каждой группы?');

INSERT INTO `posts` VALUES (7,4,'2018-04-18 14:55:36','К сожалению, в MySQL нет windows function. Используйте user variables для их эмуляции.');

INSERT INTO `posts` VALUES (8,1,'2018-04-23 02:17:14','Помогите ускорить выборку случайных строк из группы.');

INSERT INTO `posts` VALUES (9,4,'2018-04-25 17:22:02','TOP в подзапросе выдает ошибку.');

INSERT INTO `posts` VALUES (10,4,'2018-04-26 22:28:45','Нужно выбрать из каждой группы по 2 последних элемента и 2 случайных.');

Пусть нам требуется выбрать 3 последних сообщения каждого пользователя. Некоторые из предложенных ниже вариантов после незначительных изменений могут быть использованы для выборки 3 случайных сообщений каждого пользователя (о чем будут даны соответствующие пояснения).

1. зависимый подзапрос

Для каждой строки таблицы считаем количество строк с тем же идентификатором пользователя (user_id) и большей датой добавления (date_added). Если количество таких строк меньше 3, значит рассматриваемая строка и есть нужная нам строка, т.е. входит в группу трёх последних сообщений пользователя.

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

2. join + group by

Та же идея, что и в предыдущем случае, только реализована через самообъединение таблицы и группировку. Каждой строке сопоставляется набор строк с тем же user_id и большей или равной date_added, после группировки мы получаем для каждой строки (количество сообщений того же пользователя с большей датой добавления) + 1. Иными словами, если мы пронумеруем сообщения пользователя по убыванию date_added, то полученное число будет порядковым номером строки в этой нумерации.

Этот способ часто рекомендуют в интернете в качестве решения задачи (встречаются вариации с left join). Однако его производительность не самая оптимальная в сравнении с другими методами, рассмотренными в этой статье. Вероятно, причина популярности этого решения в том, что join многим интуитивно представляется более простым решением.

Обратите внимание: в режиме ONLY_FULL_GROUP_BY придется усложнять запрос: сначала выбрать нужные post_id, затем по ним дополнительным join извлечь остальные поля (подробнее см статью Группировка в MySQL). Простое перечисление всех полей в части group by в разы увеличивает время выполнения запроса.

Строго говоря, этот способ как и предыдущий (с помощью зависимого подзапроса) можно использовать для выборки случайных строк из группы, но только в новых версиях, где есть поддержка обобщенных табличных выражений. Вместо исходной таблицы в запросе будет использоваться результат select posts.*, rand() new_col from posts, и сравнение не по полю date_added, а по new_col. Будем считать, что варианты 1 и 2 не применимы для поиска случайных строк в группах, потому что:

3. group_concat()

Для каждого пользователя с помощью group_concat() составляется список идентификаторов его сообщений, отсортированный по убыванию даты. Используя substring_index(), вырезаем первые 3 значения post_id, и по ним извлекается вся строка.

К сожалению, MySQL не умеет решать уравнения, поэтому для поиска по условию с find_in_set будет просканирована вся таблица сообщений. Есть обходной путь: используя строковые функции и union all, вырезать id сообщений из списка и объединить их в один столбец. Тогда оптимизатор сможет использовать их для поиска нужных строк в таблице сообщений, а не наоборот.

Этот способ можно применять для выборки 3 случайных сообщений каждого пользователя. Для этого достаточно указать иной вид сортировки внутри group_concat: order by rand() вместо order by date_added desc.

4. оконные функции

Начиная с MariaDB 10.2 / MySQL 8 добавлена поддержка оконных функций. С помощью row_number() можно для каждого пользователя сделать отдельную нумерацию сообщений в порядке убывания даты. После чего выбрать те записи, у которых № меньше или равен 3.

Производительность - двойное сканирование таблицы: сначала для нумерации (нет возможности ограничиться нумерацией только нескольких строк из группы), потом отбросить не удовлетворяющие условию where i <= 3.

Для случайных сообщений пользователя достаточно заменить сортировку по убыванию даты order by date_added desc на случайную - order by rand().

5. пользовательские переменные

Та же идея, что и в предыдущем варианте, только реализована с помощью пользовательских переменных (user variables). Актуально для версий, в которых нет оконных функций.

Как и в примере с row_number(), мы нумеруем сообщения каждого пользователя в порядке убывания даты добавления (только делаем это с помощью пользовательских переменных), затем оставляем только те строки, у которых № меньше или равен 3.

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

Обратите внимание на добавление ещё одной переменной @z:=1, которая более нигде не применяется. С некоторых пор оптимизатор научился упрощать тривиальные с его точки зрения from-подзапросы, перенося условия из них во внешний запрос. Однако, если в подзапросе используются переменные, то пока оптимизатор материализует такие подзапросы.

В общем, пользовательские переменные - мощный инструмент написания и оптимизации запросов, но нужно быть очень внимательными при работе с ними, понимать на каком эффекте основан, используемый вами трюк, и проверять работоспособность в новых версиях. Подробнее см Оптимизация запросов MySQL с использованием пользовательских переменных

6. подзапросы lateral

В MySQL 8.0.14 добавлена поддержка зависимых подзапросов в части FROM, с помощью которых наша задача решается оптимальным образом. Сначала формируется список идентификаторов пользователей (производная таблица t1) и для каждого из выбираются нужные строки (коррелированный from-подзапрос t2).

К удивлению, при выборе строк в подзапросе t2 сервер читает все строки группы и делает файловую сортировку вместо нахождения 3 нужных строк по уникальному индексу (user_id, date_added). Возможно в будущих версиях это поведение будет исправлено.

На сегодняшний день можно применить следующий трюк, благодаря которому MySQL будет использовать индекс - расширить выражение сортировки следующим образом:

Для выборки случайных строк из группы достаточно в lateral подзапросе заменить сортировку на случайную - order by rand().

Заключение

Сводная таблица, показывающая среднее время выполнения изложенных выше способов для нахождения трёх последних и трёх случайных сообщений каждого пользователя на тестовых данных в 16000 строк, равномерно распределенных среди count(distinct user_id) = 20.

Если ваша СУБД поддерживает подзапросы lateral, то используйте их. Вообще, каждый раз, когда есть необходимость "для каждого значения выбрать ..." - возможно вы сможете эффективно решить задачу, используя LATERAL производные таблицы. Подробнее об этой функциональности можно прочитать в статье В MySQL 8.0.14 добавлена поддержка производных таблиц типа LATERAL.

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

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

P.S.При выборе подходящего варианта проводите тестирование в своем окружении.
Если после прочтения статьи ваш вопрос остался нерешенным, задавайте его на форуме SQLinfo.

© Все права на данную статью принадлежат порталу SQLInfo.ru. Перепечатка в интернет-изданиях разрешается только с указанием автора и прямой ссылки на оригинальную статью. Перепечатка в бумажных изданиях допускается только с разрешения редакции.