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

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

    Давайте рассмотрим простой пример.
    Есть таблица:
    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. Притом, если число записей уже настолько большое, то очень рекомендую эту информацию прекалькулировать в отдельных таблицах.
    Mail.ru Group
    Building the Internet

    Comments 39

      +9
      Жалко, что методически SQL тут и не пахнет. Сплошные лайфхаки — для того чтобы обойти несовершенство MySQL. В общем — если бы я у своего подчиненного увидел бы такие select — то влепил бы выговор, отправил бы на учебу или уволил. И нечем тут гордиться.

      Например:
      >SELECT article, dealer, price
      FROM shop s1
      WHERE price=(SELECT MAX(s2.price)
      FROM shop s2
      WHERE s1.article = s2.article);

      Самый «классический». Но возникает вопрос — а индекс по article есть !? Скорее всего нет — отсюда и провал в скорости. Опять же индекс по price не поможет — т.к. сравнивать значения в float процессору тяжелее. (выход кстати есть — храните суммы в _целых числах_ — типа копейках. А делите на 100 при печати и выводе на экран). Тогда индекс (article, price) — даст вам миллиардную производительность.

      >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;

      Полное извращение над SQL92 — Рекомендуется в условии ON писать только соединения, а отбор (типа s1.price<s2,price) только после в WHERE. Большинство оптимизаторов это поймут правильно (но не MySQL видимо)

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

      Кроме order by price в присоединяемых select — который по понятным причинам в исходящую выбору (хотя жрет процессорное время) не входит и надо досортировывать — прикольным «order by null».
      Не забываем что в агрегатных функциях мы нарываемся еще и на эскалацию блокировки

      >Притом, если число записей уже настолько большое, то очень рекомендую эту информацию прекалькулировать в отдельных таблицах.

      С этого и надо начинать. Если у вас часто такие запросы — то структура данных должна под это ложиться. Т.е. сначала задумываемся о «функциях» системы, а затем логически подходим к «конструкции», а не наоборот — как и положено в business driven architecture

        +5
        Жалко, что методически SQL тут и не пахнет

        Для методичности приведены другие примеры, а этот приведен для расширения кругозора.

        Самый «классический». Но возникает вопрос — а индекс по article есть !? Скорее всего нет — отсюда и провал в скорости. Опять же индекс по price не поможет — т.к. сравнивать значения в float процессору тяжелее. (выход кстати есть — храните суммы в _целых числах_ — типа копейках. А делите на 100 при печати и выводе на экран). Тогда индекс (article, price) — даст вам миллиардную производительность.


        Классический второй метод! А этот метод будет ВСЕГДА медленным. Индекс по article есть, это отмеченно в статье. Но количество запросов равно кол-ву записей в таблице, т.е. в данном случае 100к. Что будет медленно в любой случае.

        Индекс по price вам тут ничем не поможет (про (article, price) я вообще молчу) ибо происходит fullscan таблицы и сравнение каждой записи с результатом выборки.

        т.к. сравнивать значения в float процессору тяжелее

        Именно по-этому формат decimal

        Полное извращение над SQL92 — Рекомендуется в условии ON писать только соединения, а отбор (типа s1.price<s2,price) только после в WHERE

        Вы не можете перенести это в WHERE это именно условия соединения а не отбор.
          –4
          Вы не можете перенести это в WHERE это именно условия соединения а не отбор.
          Это можно перенести в WHERE и разницы абсолютно никакой не будет, насколько я в курсе оптимизатор MySQL так и делает (так же как и вместо JOIN добавить таблицу в FROM + условие отбора в WHERE).
            +3
            Вы не правы:
            Обратите внимание, что используется именно LEFT JOIN, поэтому
            1. Нам в любом случае нужен ON
            2. Если вы перенесете условие в блок WHERE

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


            То получите ровным счетом ничего, т.к. делаете self-join по одному и тому же аттрибуту, тем самым всем записям найдется соответствие и условие s2.article IS NULL никогда не выолнится.

            FROM shop s1 
            LEFT JOIN shop s2 ON s1.article = s2.article AND s1.price < s2.price
            

            А такой вариант позволяет вам для строк, у которых совпадает article с другой строкой, но нет ни одной цены которая больше, в качестве значения получить NULL.
              +1
              Да, вы правы, я невнимательно прочитал, думал что там речь идёт про JOIN (который INNER).
            0
            >Индекс по price вам тут ничем не поможет (про (article, price) я вообще молчу) ибо происходит fullscan таблицы и сравнение каждой записи с результатом выборки.

            Не согласен. Как минимум вы уходите от декартова произведения в N^2 в 20*lg(N) — на 1 млн.записей записях это всего 12 млн.сравнений

            По поводу fullscan таблицы — если есть индекс (article, price) — то чтения таблицы вообще не будет (ваши поля типа dealer и пр). С чего это? Да и не факт что чтение таблицы это плохо. Современные дисковые станции перебрасывают в память данные контроллерами DMA — это вообще не требует процессорного времени в отличие от memcpy() копирований.
              0
              Да, тут вы правы, использование покрывающего индекса в подзапросе дает некоторый эффект, но это все еще N подзапросов.
            +4
            влепил бы выговор, отправил бы на учебу или уволил.


            Похоже в вашу компанию очередь из высококлассных программистов, а время вхождения у них ничтожно, раз вы можете себе такое позволить.
              +2
              Скорее всего да. Просто наше решение многоплатформенное и мы можем позволить себе платить высококлассному Oracle специалисту >150k — поэтому написание SQL строго регламентировано — что гарантирует его читаемость, переносимость и «разгоняемость»
            +2
            6-й пункт отдаленно напоминает трюк max-concat. Он был описан в документации mysql к версии до 4.1 включительно (в том же разделе, на который Вы привели ссылку). Видимо, потом его удалили, чтобы народ не пользовался неоптимальными методами. Ссылка. Можно считать это 7-м подходом.
              0
              Да, спасибо, добавлю его в статью.
              +2
              Про такие особенности СУБД полезно знать — и еще полезнее это знание не использовать :)
                0
                Поддерживаю!)
                +1
                В 6-ом примере конечно, все получится, но вот сомнения по поводу 100 000 записей. GROUP_CONCAT имеет ограничения связанные с group_concat_max_len, который по умолчанию равен 1024 символам. При превышении данного лимита результат обрезается.
                Дошел до MAX() в 6-ом примере и понял, что невнимательно посмотрел на запрос.

                Но пардон — 6-ое решение действительно правильно, а вот ваше 5-ое — нет. Даже если выполнить эти два запроса, они вернут разные результаты.
                  +2
                  Может Oracle когда-нибудь перенесет аналитические функции в младшего брата.
                  Тут пригодились бы KEEP или OVER.
                    0
                    А как тогда старшего продавать?

                    Аналитика — большое облегчение, да. Без keep разум рождает чудовищ :)
                    0
                    удалено, ибо уже есть такой вариант
                      0
                      вообще-то там чуть иначе, но да — ваш вариант не сахар :)
                      П.С. удалено вслед за Fraqster
                        0
                        На самом деле намного интереснее задача получения N дилеров с максимальными/минимальными ценами и тут без коррелирующих запросов уже не получится
                          0
                          кстати, непонятно, возможно ли это на MySQL, ибо в запросе

                          ...WHERE price in (select price from shop as foo where foo.article = shop.article order by price limit 2)
                          

                          оно ругается на
                          #1235 — This version of MySQL doesn't yet support 'LIMIT & IN/ALL/ANY/SOME subquery'
                          версия 5.5.16
                          А в MS SQL такая конструкция (в виде TOP 2) прокатывает
                            0
                            получился такой вариант для получения двух минимальных цен, для большего количества — надо 2 поментять на нужное число:

                            SELECT shop.article, shop.dealer, shop.price
                            FROM `shop`
                            INNER JOIN shop AS cntr ON shop.article = cntr.article
                            AND shop.price >= cntr.price
                            GROUP BY shop.article, shop.price
                            HAVING (
                            COUNT( cntr.price )
                            ) <= 2
                            
                            

                            но работает неоптимально, но зато для любого количества минимальных цен, а также для любого диапазона. Правда количество строк по статье может быть больше быть в случае одинаковых цен, но тут ничего не попишешь :)
                      0
                      Четвертое решение уже сейчас не будет работать в таком виде на Maria DB (https://mariadb.com/kb/en/derived-table-merge-optimization/), чтобы работало достаточно добавить LIMIT с заведомо большим числом в derived выборку
                      SELECT article, dealer, price FROM ( SELECT article, dealer, price FROM shop ORDER BY price desc LIMIT 1000000000000 ) as t GROUP BY article ORDER BY NULL;
                        +2
                        Это получается какая-то война с СУБД и с языком SQL вместо их использования… В таких случаях я сожалею, что не могу вместо SQL-запроса составить сразу его план.

                        Для сравнения, на Microsoft SQL Server это делается так:
                        select article, dealer, price
                        from (
                            select *, rownumber() over (partition by article order by price desc) as r
                            from shop) as s1
                        where r = 1
                        
                          +1
                          На MS SQL спокойно пишется так. (я проверил — правда 10 тыс. записей слишком быстро работают — добавил 1 млн. записей

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

                          отрабатывает ~ 2 сек. даже на холодном кэше. Вот что значит hash match, А если выкинуть dealer (вряд ли надо хранить 45 символов для каждой записи — лучше сделать DealerID и внешнюю таблицу — то с индексом article, price — мгновенно.
                            +2
                            Сравнил оба запроса на миллионе записей.

                            Без индексов: мой вариант — 1050мс, ваш вариант — 950мс
                            С индексом (article, price desc): мой вариант — 1050мс (хм), ваш вариант — 780мс
                            С индексом (article, price desc) + включенный столбец dealer: мой вариант — 333мс, ваш вариант — 780мс.

                            В общем, вариант tri_botinka лучше работает без оптимизаций, но мой вариант можно сильнее оптимизировать.
                            Сравнивал на MS SQL Server Express 2005 — на более новых версиях результаты могут быть немного другими (честно говоря, я надеюсь изменение того времени, которое "(хм)").
                          +1
                          Особенности сортировки конечно знать надо, но вот использоваться в боевом коде — ни в коем случае! Именно поэтому все борются с выборками по index_desc, а Вы наоборот их культивируете. И вообще, зачем написана эта статья? ;)
                            +2
                            Провел тесты на ORACLE:
                            CREATE TABLE tmp_shop (
                              id INTEGER,
                              article INTEGER NOT NULL,
                              dealer VARCHAR(45) NOT NULL,
                              price NUMBER(8,2) NOT NULL,
                               constraint PK_tmp_shop primary key (ID) using index tablespace IDX
                            ) TABLESPACE  DAT;
                            
                            
                            INSERT INTO tmp_shop (id, article, dealer, price) 
                            SELECT rownum, CEIL(dbms_random.value(8,2) * 9999), CEIL(dbms_random.value(8,2) * 999), dbms_random.value(8,2) * 9999
                            FROM dual
                            connect by level < 1000000;
                            
                            create index i_tmp_shop_FND on tmp_shop (article asc) tablespace IDX;
                            --=0.848
                            SELECT article, dealer, price 
                            FROM   tmp_shop s1
                            WHERE  price=(SELECT MAX(s2.price)
                                FROM tmp_shop s2
                                WHERE s1.article = s2.article);
                                
                            DROP index i_tmp_shop_FND;
                            create index i_tmp_shop_FND on tmp_shop (article, price) tablespace IDX;
                            --0.502
                            SELECT s1.article, dealer, s1.price
                            FROM tmp_shop s1
                            JOIN (
                                SELECT article, MAX(price) AS price
                                FROM tmp_shop
                                GROUP BY article
                            ) s2 ON s1.article = s2.article AND s1.price = s2.price;
                            
                            --4.38
                            select article, dealer, price 
                            from (
                                select s.*, row_number() over (partition by article order by price desc) as r
                                from tmp_shop s)  s1
                            where r = 1;
                            
                            --2.1
                            select article, MAX(dealer) KEEP(DENSE_RANK FIRST ORDER BY price DESC), MAX(price)
                            FROM tmp_shop
                            GROUP BY article
                            
                              0
                              Отсюда можно сделать вывод, что аналитические функции тоже не всегда панацея.
                                0
                                В вашем примере в первом селекте индекс вообще не должен использоваться.
                                И по моему впечатлению вы не сбрасывали кеш между запросами.
                                У меня замеры такие: 17.989, 15.616, 19.374 и 19.079, т.е. всё достаточно ровно.
                                  0
                                  Да, кеш не сбрасывал. Индексы создавал, как в статье написано, чтобы не было разночтений.
                                  По вашим замерам все равно получается, что обычный hash join лучше аналитической функции.
                                    0
                                    У меня тестовая база слабая. Я думаю на продакшене отказ от повтроного фулскана должен дать выигрыш. Разброс то совсем незначительный.
                                0
                                Попробуйте, пожалуйста, перед третьим запросом включить dealer в индекс, как сделал я. Желательно в качестве неключевого столбца, если такая возможность есть.

                                Также меня очень интересует, есть ли хоть какая-то разница между первым и вторым запросом. Они показали разные результаты на разных индексах — но что они покажут на одинаковой схеме БД?
                                  +1
                                  Включил в индекс, разница разительная:
                                  Время без индексов: 4.4с (стоимость 5753 — фулскан таблицы ), с индексом: 0,044с (стоимость 3915 — фулскан индекса ). Таблицу между вариантами пересоздавал.

                                  У первого и второго запроса с одинаковыми индексом от 3 варианта одинаковая стоимость и время выполнения 0,5с.

                                  Так что, похоже, 3ий вариант самый быстрый.
                                    0
                                    А что вы вообще меряете? 0,044 с — это выполнение или выполнение с фетчем? Что за время?
                                    Честно говоря фулскан индекса это нонсенс.
                                      0
                                      0.044 — это первые 50 записей, без полного фетча.
                                        0
                                        Тогда вы некорректно сравниваете и не учитываете оптимизацию, например с nested loop-ами.
                                +1
                                На PostgreSQL вот так выглядят результаты, только записей взял миллион
                                pastebin.com/u7C34tVW
                                  0
                                  Не самый оптимальный запрос по скорости (где-то в середине производительности), зато в один проход :)
                                  Это для PostgreSQL

                                  CREATE TYPE reorder_type AS (  price NUMERIC(12,2) ,dealer INTEGER );
                                  
                                  SELECT article, (max(ROW(price , dealer)::text) :: reorder_type).*
                                  FROM test GROUP BY article
                                  

                                  Используется индекс по article.

                                  ну или еще более безбашенный подход (он тоже не скоростной, к сожалению )
                                  CREATE OR REPLACE FUNCTION max_func(st test,val test) RETURNS test IMMUTABLE LANGUAGE sql AS 
                                  $$ SELECT CASE WHEN $1.price > $2.price THEN $1 ELSE $2 END; $$;
                                  
                                  CREATE AGGREGATE max(test) (SFUNC = max_func, STYPE = test);
                                  
                                  SELECT (max(t)).* FROM test t GROUP BY article
                                  

                                  0
                                  По поводу замеров времени выполнения и сравнений с вариантами запросов с аналитическими функциями на ORACLE и выводов что двойной фулскан таблицы лучше одиночного с аналитикой.
                                  Всё это не имеет смысла без снятия трейсов и полного фетча. По трейсам скорее всего будет видно, что двойные чтения упираются в обращения к диску, аналитика — в память или процессор. Что лучше — зависит от конкретных условий, поэтому выводы о том какой вариант лучше мне кажутся некорректными.
                                  Я предочитаю одиночный фулскан таблицы с аналитикой.

                                  Only users with full accounts can post comments. Log in, please.