Pull to refresh
VK
Building the Internet

Группировка с условием

VK corporate blog MySQL *
Периодически возникает задача, которая требует сгруппировать набор данных с условием, что для атрибутов, не участвующих в группировке, нужно взять кортеж с максимальным значением по одному из полей.

Давайте рассмотрим простой пример.
Есть таблица:
CREATE TABLE IF NOT EXISTS shop (
  id INT NOT NULL AUTO_INCREMENT,
  article INT(4) ZEROFILL NOT NULL,
  dealer VARCHAR(45) NOT NULL,
  price DECIMAL(8,2) NOT NULL,
  PRIMARY KEY (id))
ENGINE = InnoDB;

Необходимо для всех article найти dealer с максимальной ценой.

Для этой задачи существует несколько очевидных и простых решений, но я знаю одно из них, которое значительно превосходит все остальные.
Сталкивались с этой задачей? Хотите увидеть новый способ ее решения? Прошу под кат.

Эту задачу не обошла стороной даже официальная документация mysql.com, и предлагается 3 варианта решения:
Перед каждым запросом буду указывать индекс и время его выполнения. Таблица заполнена на 100 000 записей
DELIMITER $$
CREATE PROCEDURE InsertRand()
    BEGIN
        DECLARE i INT;
        SET i = 1;
        START TRANSACTION;
        WHILE i <= 100000 DO
            INSERT INTO shop (article, dealer, price) VALUES (CEIL(RAND() * 9999), CEIL(RAND() * 999), RAND() * 9999);
            SET i = i + 1;
        END WHILE;
        COMMIT;
    END$$
DELIMITER ;


Первый idx(article) 2,169 c:

SELECT article, dealer, price
FROM   shop s1
WHERE  price=(SELECT MAX(s2.price)
    FROM shop s2
    WHERE s1.article = s2.article);


Второй idx(article, price) 0,203 c

SELECT s1.article, dealer, s1.price
FROM shop s1
JOIN (
    SELECT article, MAX(price) AS price
    FROM shop
    GROUP BY article
) AS s2 ON s1.article = s2.article AND s1.price = s2.price;


Третий idx(article, price) 0,593 c

SELECT s1.article, s1.dealer, s1.price
FROM shop s1
LEFT JOIN shop s2 ON s1.article = s2.article AND s1.price < s2.price
WHERE s2.article IS NULL;


Ну, а теперь мое решение:


Внимание! Используйте этот метод на свой страх и риск! В будущих версиях MySQL поведение группировки может измениться.

Данное решение основано на том, что group by для атрибутов, к которым не указаны групповые операции и которые не участвуют в группировке, берет первое встреченное значение. Таким образом, если набор данных предварительно отсортировать, то мы получим кортежи с искомым максимальным значением.

4. idx(price) 0,328 c

SELECT article, dealer, price
FROM (
    SELECT article, dealer, price 
    FROM shop
    ORDER BY price desc) 
as t
GROUP BY article
ORDER BY NULL;

Т.к. предыдущие примеры были без какой-либо сортировки, а group by автоматически добавляет ее, то необходимо указать ORDER BY NULL, чтобы данные дополнительно не сортировались, иначе результаты будут несопоставимы.
Но зачем нам создавать промежуточную таблицу, ведь отсортированные данные мы можем получить, использовав индекс:
5. idx(article,price) 0,110 c

SELECT article, dealer, price
FROM shop use index (idx)
GROUP BY article DESC
ORDER BY NULL;


Бонусное решение:


Решение было найдено в блоге Mitch Dickinson. Оно не претендует на самое быстрое, но уж очень оригинальное.

6. idx(article) 0,202 c

SELECT article, 
       SUBSTRING_INDEX(GROUP_CONCAT(dealer ORDER BY price DESC),',',1) AS dealer,
       MAX(price) AS price
FROM shop
GROUP BY article;


В комментариях dm9 привел еще 1 вариант решения, который был описан в документации к ранним версиям:
SELECT article,
    SUBSTRING( MAX( CONCAT(LPAD(price,6,'0'),dealer) ), 7) AS dealer,
    0.00+LEFT(MAX( CONCAT(LPAD(price,6,'0'),dealer) ), 6) AS price
FROM   shop
GROUP BY article;


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

P.S.: Внимательный читатель, наверное, заметил, что методы 4-6 для каждого article дают лишь 1 поставщика с максимальной ценой, в отличие от первых методов, при которых возвращаются все поставщики. Но при решении этой задачи меня интересовал любой из поставщиков, поэтому данная проблема была несущественной.

P.P.S.: Альтернативный метод, который предложен в этой статье, хорошо себя показывает при средних размерах таблиц. При количестве записей более миллиона, наиболее оптимальным будет метод 2. Притом, если число записей уже настолько большое, то очень рекомендую эту информацию прекалькулировать в отдельных таблицах.
Tags:
Hubs:
Total votes 71: ↑55 and ↓16 +39
Views 52K
Comments Comments 39

Information

Founded
Location
Россия
Website
vk.com
Employees
5,001–10,000 employees
Registered
Representative
Миша Буданов