Экзотическая GROUP BY В MySQL

Question

Рассмотрим типичный оператор GROUP BY в SQL: у вас есть таблица типа

+------+-------+
| Name | Value |
+------+-------+
| A    |     1 |
| B    |     2 |
| A    |     3 |
| B    |     4 |
+------+-------+

И вы просите

SELECT Name, SUM(Value) as Value
FROM table
GROUP BY Name

Вы получите

+------+-------+
| Name | Value |
+------+-------+
| A    |     4 |
| B    |     6 |
+------+-------+

Вы можете себе представить, что SQL генерирует промежуточную отсортированную таблицу, такую ​​как

+------+-------+
| Name | Value |
+------+-------+
| A    |     1 |
| A    |     3 |
| B    |     2 |
| B    |     4 |
+------+-------+

, а затем агрегирует вместе последовательные строки: столбцу «Значение» был присвоен агрегатор (в данном случае SUM), поэтому его легко агрегировать. Столбцу «Имя» не был дан агрегатор, и поэтому он использует то, что вы могли бы назвать «тривиальным частичным агрегатором»: учитывая две одинаковые вещи (например, А и А), он объединяет их в одну копию одного из входы (в данном случае А). При любом другом вводе он не знает, что делать, и вынужден начинать агрегирование заново (на этот раз со столбцом «Имя», равным B).

Я хочу сделать более экзотическую агрегацию. Мой стол выглядит как

+------+-------+
| Name | Value |
+------+-------+
| A    |     1 |
| BC   |     2 |
| AY   |     3 |
| AZ   |     4 |
| B    |     5 |
| BCR  |     6 |
+------+-------+

И предполагаемый вывод

+------+-------+
| Name | Value |
+------+-------+
| A    |     8 |
| B    |    13 |
+------+-------+

Откуда это? A и B являются «минимальными префиксами» для этого набора имен: они встречаются в наборе данных, и каждое имя имеет один из них в качестве префикса. Я хочу объединить данные, сгруппировав строки, когда их имена имеют одинаковый минимальный префикс (и, конечно, добавьте значения).

В предыдущей модели группировки игрушек промежуточная отсортированная таблица будет

+------+-------+
| Name | Value |
+------+-------+
| A    |     1 |
| AY   |     3 |
| AZ   |     4 |
| B    |     5 |
| BC   |     2 |
| BCR  |     6 |
+------+-------+

Вместо использования «тривиального частичного агрегатора» для Имен, мы бы использовали тот, который может агрегировать X и Y вместе, если X является префиксом Y; в этом случае он возвращает X. Таким образом, первые три строки будут объединены в строку с (Name, Value) = (A, 8), тогда агрегатор увидит, что A и B не могут быть объединены, и будет двигаться дальше в новый «блок» строк для агрегирования.

Хитрость заключается в том, что значение, которое мы группируем, является «нелокальным»: если бы A не было именем в наборе данных, то AY и AZ были бы минимальным префиксом. Оказывается, строки AY и AZ объединяются в одну и ту же строку в конечном выводе, но вы не можете знать этого, просто глядя на них изолированно.

Чудесным образом, в моем случае использования минимальный префикс строки может быть определен без ссылки на что-либо еще в наборе данных. (Представьте, что каждое из моих имен представляет собой одну из строк «привет», «мир» и «бар», за которыми следует любое количество символов z. Я хочу сгруппировать все имена с одним и тем же «базовым» словом вместе.)

На мой взгляд, у меня есть два варианта:

1) Простой вариант: вычислить префикс для каждой строки и группы по этому значению напрямую. К сожалению, у меня есть индекс по имени, и вычисление минимального префикса (длина которого зависит от самого имени) не позволяет мне использовать этот индекс. Это вызывает полное сканирование таблицы, которое слишком медленно.

2) Сложный вариант: каким-то образом убедить MySQL использовать «агрегатор частичного префикса» для Name. Это сталкивается с проблемой «нелокальности», описанной выше, но это нормально, если мы сканируем таблицу в соответствии с моим индексом по имени, поскольку тогда каждый минимальный префикс будет встречаться до любой из других строк, префиксом которой он является; мы никогда бы не попытались объединить AY и AZ вместе, если бы A был в наборе данных.

В декларативном языке программирования # 2 было бы довольно просто: извлекать строки по одной в алфавитном порядке, отслеживая текущий префикс. Если имя вашей новой строки имеет префикс, оно входит в список, который вы используете в данный момент. В противном случае, начните новый сегмент с этим в качестве префикса В MySQL я заблудился относительно того, как это сделать. Обратите внимание, что набор минимальных префиксов заранее неизвестен.

Answer 1

Вот несколько советов о том, как выполнить задачу. Это находит любые префиксы, которые полезны. Это не то, что вы просили, но вам может помочь поток запроса и использование @variables, а также необходимость в 2 (фактически 3) уровнях вложенности.

SELECT  DISTINCT `Prev`
    FROM  
        (
        SELECT  @prev := @next AS 'Prev',
                @next := IF(LEFT(city, LENGTH(@prev)) = @prev, @next, city) AS 'Next'
            FROM ( SELECT  @next := ' ' ) AS init
            JOIN ( SELECT  DISTINCT city FROM  us ) AS dedup
            ORDER BY  city
        ) x
    WHERE  `Prev` = `Next` ;

Частичный вывод:

+----------------+
| Prev           |
+----------------+
| Alamo          |
| Allen          |
| Altamont       |
| Ames           |
| Amherst        |
| Anderson       |
| Arlington      |
| Arroyo         |
| Auburn         |
| Austin         |
| Avon           |
| Baker          |

Проверьте Al% города:

mysql> SELECT DISTINCT city FROM us WHERE city LIKE 'Al%' ORDER BY city;
+-------------------+
| city              |
+-------------------+
| Alabaster         |
| Alameda           |
| Alamo             | <--
| Alamogordo        | <--
| Alamosa           |
| Albany            |
| Albemarle         |
...
| Alhambra          |
| Alice             |
| Aliquippa         |
| Aliso Viejo       |
| Allen             | <--
| Allen Park        | <--
| Allentown         | <--
| Alliance          |
| Allouez           |
| Alma              |
| Aloha             |
| Alondra Park      |
| Alpena            |
| Alpharetta        |
| Alpine            |
| Alsip             |
| Altadena          |
| Altamont          | <--
| Altamonte Springs | <--
| Alton             |
| Altoona           |
| Altus             |
| Alvin             |
+-------------------+
40 rows in set (0.01 sec)

Answer 2

Редактировать 2

Мне пришло в голову, что если бы таблица была упорядочена по Name, это было бы намного проще (и быстрее). Поскольку я не знаю, отсортированы ли ваши данные, я включил сортировку в этот запрос, но если данные отсортированы, вы можете удалить (SELECT * FROM table1 ORDER BY Name) t1 и просто использовать FROM table1

SELECT prefix, SUM(`Value`)
FROM (SELECT Name, Value, @prefix:=IF(Name NOT LIKE CONCAT(@prefix, '_%'), Name, @prefix) AS prefix
      FROM (SELECT * FROM table1 ORDER BY Name) t1
      JOIN (SELECT @prefix := '~') p
      ) t2
GROUP BY prefix

Обновлен SQLFiddle

Редактировать

Поспав о проблеме, я понял, что нет необходимости делать IN, достаточно просто добавить в таблицу JOINed предложение WHERE NOT EXISTS:

SELECT t1.Name, SUM(t2.Value) AS `Value`
FROM table1 t1
JOIN table1 t2 ON t2.Name LIKE CONCAT(t1.Name, '%')
WHERE NOT EXISTS (SELECT * 
                  FROM table1 t3
                  WHERE t1.Name LIKE CONCAT(t3.Name, '_%')
                  )
GROUP BY t1.Name

Обновлено объяснение (Name изменено на UNIQUE ключ от PRIMARY)

id  select_type         table   type    possible_keys   key         key_len     ref             rows    Extra   
1   PRIMARY             t1      index   Name            Name        11          NULL            6       Using where; Using index; Using temporary; Using filesort
1   PRIMARY             t2      ALL     NULL            NULL        NULL        NULL            6       Using where; Using join buffer (Block Nested Loop)
3   DEPENDENT SUBQUERY  t3      index   NULL            Name        11          NULL            6       Using where; Using index

Обновлено SQLFiddle

Оригинальный ответ

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

SELECT Name
FROM table1 t1
WHERE NOT EXISTS (SELECT * 
                  FROM table1 t2
                  WHERE t1.Name LIKE CONCAT(t2.Name, '_%')
                  )

Для ваших образцов данных это даст

Name
A
B

Теперь вы можете суммировать все значения, где имя начинается с одного из этих префиксов Обратите внимание, что мы изменили шаблон LIKE в этом запросе, чтобы он также совпадал с префиксом, иначе мы не будем считать значения для A и B в вашем примере:

SELECT t1.Name, SUM(t2.Value) AS `Value`
FROM table1 t1
JOIN table1 t2 ON t2.Name LIKE CONCAT(t1.Name, '%')
WHERE t1.Name IN (SELECT Name
                  FROM table1 t3
                  WHERE NOT EXISTS (SELECT * 
                                    FROM table1 t4
                                    WHERE t3.Name LIKE CONCAT(t4.Name, '_%')
                                    )
                  )
GROUP BY t1.Name

Выход:

Name    Value
A       8
B       13

EXPLAIN говорит, что оба этих запроса используют индекс на Name, поэтому должны быть достаточно эффективными. Вот результат объяснения на моем сервере MySQL 5.6:

id  select_type         table   type    possible_keys   key         key_len     ref             rows    Extra   
1   PRIMARY             t1      index   PRIMARY         PRIMARY     11          NULL            6       Using index; Using temporary; Using filesort
1   PRIMARY             t3      eq_ref  PRIMARY         PRIMARY     11          test.t1.Name    1       Using where; Using index
1   PRIMARY             t2      ALL     NULL            NULL        NULL        NULL            6       Using where; Using join buffer (Block Nested Loop)
3   DEPENDENT SUBQUERY  t4      index   NULL            PRIMARY     11          NULL            6       Using where; Using index

Демонстрация SQLFiddle