Групповой максимум в MariaDB
Проблема
Требуется найти максимальную строку в каждой группе строк. Например, требуется найти самый большой город в каждом штате. Хотя легко найти MAX(население) ... GROUP BY штат, трудно найти имя `города`, связанного с этим `населением`. К сожалению, в MySQL и MariaDB нет синтаксиса для прямого решения этой задачи.
Эта статья находится в стадии разработки, в основном для очистки. Содержание достаточно точно во время разработки.
В статье представлены два «хороших» решения. Они различаются таким образом, что ни одно из них не является «идеальным»; вы должны попробовать оба и взвесить плюсы и минусы.
Также будут представлены несколько «плохих» решений, а также причины их отклонения.
В руководстве MySQL представлено 3 решения; только «Некоррелированное» является «хорошим», остальные два — «плохими».
Пример данных
Для демонстрации работы различных попыток кодирования я разработал эту простую задачу: найти самый большой город в каждой канадской провинции. Вот пример исходных данных (5493 строки):
+------------------+----------------+------------+ | province | city | population | +------------------+----------------+------------+ | Saskatchewan | Rosetown | 2309 | | British Columbia | Chilliwack | 51942 | | Nova Scotia | Yarmouth | 7500 | | Alberta | Grande Prairie | 41463 | | Quebec | Sorel | 33591 | | Ontario | Moose Factory | 2060 | | Ontario | Bracebridge | 8238 | | British Columbia | Nanaimo | 84906 | | Manitoba | Neepawa | 3151 | | Alberta | Grimshaw | 2560 | | Saskatchewan | Carnduff | 950 | ...
Вот желаемый результат (13 строк):
+---------------------------+---------------+------------+ | province | city | population | +---------------------------+---------------+------------+ | Alberta | Calgary | 968475 | | British Columbia | Vancouver | 1837970 | | Manitoba | Winnipeg | 632069 | | New Brunswick | Saint John | 87857 | | Newfoundland and Labrador | Corner Brook | 18693 | | Northwest Territories | Yellowknife | 15866 | | Nova Scotia | Halifax | 266012 | | Nunavut | Iqaluit | 6124 | | Ontario | Toronto | 4612187 | | Prince Edward Island | Charlottetown | 42403 | | Quebec | Montreal | 3268513 | | Saskatchewan | Saskatoon | 198957 | | Yukon | Whitehorse | 19616 | +---------------------------+---------------+------------+
Дублируемый максимум
Следует учитывать, хотите ли вы видеть несколько строк для победителей с одинаковыми значениями. Для используемого набора данных это означало бы, что два самых больших города в провинции имели одинаковое население. В данном случае дубликаты маловероятны. Но существуют многие случаи использования группового максимума, где дубликаты вероятны.
Два лучших алгоритма отличаются тем, показывают ли они дубликаты.
Использование некоррелированного подзапроса
Характеристики:
- Превосходная производительность или средняя производительность
- Он покажет дубликаты
- Требуется дополнительный индекс
- Вероятно, требуется версия 5.6
- Если все пойдет хорошо, он будет выполняться за время O(M), где M — количество выходных строк.
«Некоррелированный подзапрос»:
SELECT c1.province, c1.city, c1.population
FROM Canada AS c1
JOIN
( SELECT province, MAX(population) AS population
FROM Canada
GROUP BY province
) AS c2 USING (province, population)
ORDER BY c1.province;
Но это также «требует» дополнительного индекса: INDEX(провинция, население). Кроме того, MySQL не всегда мог эффективно использовать этот индекс, поэтому «требуется 5.6». (Я не уверен в фактической версии.)
Без дополнительного индекса вам потребуется версия 5.6, которая может создавать индексы для подзапросов. Это обозначено как <auto_key0> в EXPLAIN. Тем не менее, производительность хуже с автоматически сгенерированным индексом, чем с вручную созданным.
Без дополнительного индекса и версии 5.6 это «решение» попало бы в категорию «Неудачные», так как оно будет выполняться за время O(N*N).
Использование переменных
Характеристики:
- Хорошая производительность
- Не показывает дубликаты (выбирает один для отображения)
- Постоянное время выполнения O(N) (N = количество входных строк)
- Только один проход по данным
SELECT
province, city, population -- The desired columns
FROM
( SELECT @prev := '' ) init
JOIN
( SELECT province != @prev AS first, -- `province` is the 'GROUP BY'
@prev := province, -- The 'GROUP BY'
province, city, population -- Also the desired columns
FROM Canada -- The table
ORDER BY
province, -- The 'GROUP BY'
population DESC -- ASC for MIN(population), DESC for MAX
) x
WHERE first
ORDER BY province; -- Whatever you like
Для вашего приложения измените строки с комментариями.
Неудачные решения
* «Коррелированный подзапрос» (из документации MySQL):
SELECT province, city, population
FROM Canada AS c1
WHERE population =
( SELECT MAX(c2.population)
FROM Canada AS c2
WHERE c2.province= c1.province
)
ORDER BY province;
Производительность O(N*N) (то есть ужасная)
* LEFT JOIN (из документации MySQL):
SELECT c1.province, c1.city, c1.population
FROM Canada AS c1
LEFT JOIN Canada AS c2 ON c2.province = c1.province
AND c2.population > c1.population
WHERE c2.province IS NULL
ORDER BY province;
Средняя производительность (2N-3N, в зависимости от join_buffer_size).
Для времени O(N*N)... На обработку нескольких тысяч строк потребуется одна секунда; миллион строк может занять часы.
Топ-N в каждой группе
Это разновидность «группового максимума», где требуется получить N наибольших (или наименьших) элементов в каждой группе. Произведите следующие замены для вашего случая:
- провинция —> ваше поле для группировки
- Канада —> ваша таблица
- 3 —> количество элементов каждой группы для отображения
- население —> ваше числовое поле для определения «Топ-N»
- город —> дополнительные поля, которые вы хотите отобразить
- Измените SELECT и ORDER BY, если необходимо
- DESC для получения «наибольших»; ASC для «наименьших»
SELECT
province, n, city, population
FROM
( SELECT @prev := '', @n := 0 ) init
JOIN
( SELECT @n := if(province != @prev, 1, @n + 1) AS n,
@prev := province,
province, city, population
FROM Canada
ORDER BY
province ASC,
population DESC
) x
WHERE n <= 3
ORDER BY province, n;
Вывод:
+---------------------------+------+------------------+------------+ | province | n | city | population | +---------------------------+------+------------------+------------+ | Alberta | 1 | Calgary | 968475 | | Alberta | 2 | Edmonton | 822319 | | Alberta | 3 | Red Deer | 73595 | | British Columbia | 1 | Vancouver | 1837970 | | British Columbia | 2 | Victoria | 289625 | | British Columbia | 3 | Abbotsford | 151685 | | Manitoba | 1 | ...
Производительность этой операции — O(N), фактически около 3N, где N — количество исходных строк.
EXPLAIN EXTENDED возвращает
+----+-------------+------------+--------+---------------+------+---------+------+------+----------+----------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+------------+--------+---------------+------+---------+------+------+----------+----------------+ | 1 | PRIMARY | <derived2> | system | NULL | NULL | NULL | NULL | 1 | 100.00 | Using filesort | | 1 | PRIMARY | <derived3> | ALL | NULL | NULL | NULL | NULL | 5484 | 100.00 | Using where | | 3 | DERIVED | Canada | ALL | NULL | NULL | NULL | NULL | 5484 | 100.00 | Using filesort | | 2 | DERIVED | NULL | NULL | NULL | NULL | NULL | NULL | NULL | NULL | No tables used | +----+-------------+------------+--------+---------------+------+---------+------+------+----------+----------------+
Объяснение, показанное в том же порядке, что и EXPLAIN, но пронумерованное в хронологическом порядке: 3. Получить идентификатор подзапроса = 2 (начало) 4. Сканировать выходные данные подзапроса id=3 (x) 2. Подзапрос id=3 — сканирование таблицы Канада 1. Подзапрос id=2 — `начало` для простого инициализирования двух переменных. Да, потребовалось два сортирования, хотя, вероятно, в оперативной памяти.
Значения Main Handler:
| Handler_read_rnd | 39 | | Handler_read_rnd_next | 10971 | | Handler_write | 5485 | -- #rows in Canada (+1)
Топ-N в каждой группе, вариант II
Этот вариант быстрее предыдущего, но зависит от того, что `город` уникален в наборе данных. (из openark.org)
SELECT province, city, population
FROM Canada
JOIN
( SELECT GROUP_CONCAT(top_in_province) AS top_cities
FROM
( SELECT SUBSTRING_INDEX(
GROUP_CONCAT(city ORDER BY population DESC),
',', 3) AS top_in_province
FROM Canada
GROUP BY province
) AS x
) AS y
WHERE FIND_IN_SET(city, top_cities)
ORDER BY province, population DESC;
Вывод. Обратите внимание, как может быть более 3 городов на провинцию:
| Alberta | Calgary | 968475 | | Alberta | Edmonton | 822319 | | Alberta | Red Deer | 73595 | | British Columbia | Vancouver | 1837970 | | British Columbia | Victoria | 289625 | | British Columbia | Abbotsford | 151685 | | British Columbia | Sydney | 0 | -- Nova Scotia's second largest is Sydney | Manitoba | Winnipeg | 632069 |
Значения Main Handler:
| Handler_read_next | 5484 | -- table size | Handler_read_rnd_next | 5500 | -- table size + number of provinces | Handler_write | 14 | -- number of provinces (+1)
Топ-N с использованием MyISAM
(Это не требует, чтобы ваша таблица была MyISAM, но она требует временной таблицы MyISAM для своей функции PRIMARY KEY с двумя столбцами.) См. предыдущий раздел для внесения изменений для вашего случая.
-- build tmp table to get numbering
-- (Assumes auto_increment_increment = 1)
CREATE TEMPORARY TABLE t (
nth MEDIUMINT UNSIGNED NOT NULL AUTO_INCREMENT,
PRIMARY KEY(province, nth)
) ENGINE=MyISAM
SELECT province, NULL AS nth, city, population
FROM Canada
ORDER BY population DESC;
-- Output the biggest 3 cities in each province:
SELECT province, nth, city, population
FROM t
WHERE nth <= 3
ORDER BY province, nth;
+---------------------------+-----+------------------+------------+
| province | nth | city | population |
+---------------------------+-----+------------------+------------+
| Alberta | 1 | Calgary | 968475 |
| Alberta | 2 | Edmonton | 822319 |
| Alberta | 3 | Red Deer | 73595 |
| British Columbia | 1 | Vancouver | 1837970 |
| British Columbia | 2 | Victoria | 289625 |
| British Columbia | 3 | Abbotsford | 151685 |
| Manitoba | ...
SELECT for CREATE:
+----+-------------+--------+------+---------------+------+---------+------+------+----------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+------+---------------+------+---------+------+------+----------------+
| 1 | SIMPLE | Canada | ALL | NULL | NULL | NULL | NULL | 5484 | Using filesort |
+----+-------------+--------+------+---------------+------+---------+------+------+----------------+
Other SELECT:
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
| 1 | SIMPLE | t | index | NULL | PRIMARY | 104 | NULL | 22 | Using where |
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
Значения main handler (сумма всех операций):
| Handler_read_rnd_next | 10970 | | Handler_write | 5484 | -- number of rows in Canada (write tmp table)
Оба варианта «Топ-N», вероятно, занимают примерно одинаковое время.
Функции окон
Прямо из Percona Live... MariaDB 10.2 имеет «функции окон», которые делают «групповой максимум» намного проще.
Код:
В процессе разработки
Журнал изменений
Разработан в феврале 2015 года; Добавлено решение с MyISAM в июле 2015 года; Добавлено решение от Openark в апреле 2016 года; Добавлено решение с окнами в апреле 2016 года.
Я не включал технику(и) с использованием GROUP_CONCAT. Они полезны в некоторых ситуациях с небольшими наборами данных. Их можно найти в ссылках ниже.
См. также
- В этом есть некоторые из этих алгоритмов, а также другие: Блог Питера Броули
- Блог Яна Кнешка из 2007 года
- Обсуждение на StackOverflow о «Некоррелированном подзапросе»
- Другие ссылки: Внутренний ORDER BY удален
- Добавление большого LIMIT в подзапрос может помочь. Почему ORDER BY в подзапросе игнорируется
- Тред на StackOverflow
- row_number(), rank(), dense_rank()
- http://rpbouman.blogspot.de/2008/07/calculating-nth-percentile-in-mysql.html][Блог про процентили]
Рик Джеймс любезно разрешил нам использовать эту статью в базе знаний.
Сайт Рика Джеймса содержит другие полезные советы, руководства, оптимизации и рекомендации по отладке.
Исходный источник: http://mysql.rjweb.org/doc.php/groupwise_max
© 2023 MariaDB
Licensed under the Creative Commons Attribution 3.0 Unported License and the GNU Free Documentation License.
https://mariadb.com/kb/en/groupwise-max-in-mariadb/
