SQLinfo.ru - Все о MySQL

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

Дата: 28.03.2019

Автор: Василий Лукьянчиков , 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, значит рассматриваемая строка и есть нужная нам строка, т.е. входит в группу 3-ёх последних сообщений пользователя.

select t1.* from posts t1
where (select count(*) from posts t2 where t1.user_id=t2.user_id and t2.date_added > t1.date_added) < 3;

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

2. join + group by

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

select t1.* from
posts t1 join posts t2 on t1.user_id=t2.user_id and t2.date_added >= t1.date_added
group by t1.post_id
having count(*) <=3;

Этот способ часто рекомендуют в интернете в качестве решения задачи (встречаются вариации с 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 не применимы для поиска случайных строк в группах, потому что:

  • в старых версиях они действительно не применимы :)
  • в новых их производительность будет существенно хуже по сравнению с иными доступными вариантами решений (см способы 4 и 7)

3. group_concat()

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

select t1.* from posts t1 join
(select user_id, substring_index(group_concat(post_id order by date_added desc), ',', 3) x from posts t2 group by user_id) t
on t.user_id = t1.user_id and find_in_set(t1.post_id,x);

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

with cte as (
select substring_index(group_concat(post_id order by date_added desc), ',', 3) x from posts group by user_id
)
select posts.* from (
select substring_index(x,',',1) post_id from cte
union all
select substring_index(substring_index(x,',',2),',',-1) from cte
union all
select substring_index(x,',',-1) from cte) t
join posts on t.post_id = posts.post_id;

Будет ли такой трюк эффективным зависит от:

  • сколько строк из группы нужно выбрать
  • есть ли возможность использовать with (доступны с MariaDB 10.2 / MySQL 8). Если в явном виде дублировать from-подзапрос, то каждый из них будет материализован в отдельную временную таблицу.

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

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

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

select post_id, user_id, date_added, post_text from
(select posts.*,
row_number() over (partition by user_id order by date_added desc) i
from posts) t where i <= 3;

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

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

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

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

select post_id, user_id, date_added, post_text from
(select posts.*, if(@gr=user_id, @i:=@i+1, @i:=1 + least(@gr:=user_id,0)) x
from posts, (select @i:=0, @gr:=0) t order by user_id, date_added desc) t1 where x <=3;

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

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

select post_id, user_id, date_added, post_text from
(select t2.*, if(@gr=user_id, @i:=@i+1, @i:=1 + least(@gr:=user_id,0)) x
from (select posts.*, rand() q, @z:=1 from posts) t2, (select @i:=0, @gr:=0) t order by user_id, q) t1 where x <=3

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

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

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

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

select t2.* from (select user_id from posts group by user_id) as t1,
lateral (select * from posts where t1.user_id=posts.user_id order by date_added desc limit 3) as t2;

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

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

.. order by user_id desc, date_added desc limit 3
Спасибо за совет Гильяму Бишоту.

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

Заключение

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

время, с
3 последних 3 случайных
1. зависимый подзапрос 10.8 -
2. join + group by 11 -
3. group_concat() 0.06 0.03
3. модифицированный вариант + WITH 0.03 0.016
3. модифицированный вариант без WITH 0.08 -
4. row_number() 0.15 0.17
5. пользовательские переменные 0.13 0.14
6. LATERAL 0.005 0.03

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

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

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

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

Дата публикации: 28.03.2019

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

Статьи :
 Установка и настройка MySQL
 Коды ошибок в MySQL
>Программирование в MySQL
 Оптимизация производительности
 Кодировка символов в MySQL
 Хранение данных в MySQL
 MySQL Cluster
См. также:
 Оптимизация производительности MySQL
 Онлайн-курс по оптимизации MySQL
 Услуги по оптимизации MySQL