Статья
Версия для печати
Обсудить на форуме (2)
MySQL. Иерархические запросы.


Автор: RXL
Написано: 22.11.2008.
Права на статью принадлежат автору и Клубу программистов «Весельчак У».

Содержание.


Введение.

Недавно прочел статью «SQL. Иерархические (рекурсивные) запросы.» [1]. Интересная статья, но в ней утверждается, что MySQL не поддерживает иерархических запросов. Совершенно согласен с автором — напрямую не поддерживаются. Но реализовать подобие можно!
Традиционно, для MySQL применяют программный метод, когда клиент считывает из базы узлы по номеру предка, затем считывает их потомков и так до тех пор, пока все потомки не будут прочитаны. Реализация возможна как рекурсивная, так и итеративная, как это было давно еще объяснено Alf-ом в серии статей [2]. Главный недостаток — множественные пересылки запросов и данных между клиентом и сервером.
Не редко, для упрощения программы и минимизации количества запросов к базе, применяют простейший метод — считывают из базы все узлы, что может быть накладно по объему пересылаемых (и хранимых в памяти) ненужных данных.
Давайте рассмотрим другие, более интересные способы получения фрагмента иерархического дерева, требующие одного — двух запросов для получения информации и не тянущие за собой ненужных данных: строчный иерархический идентификатор и классический — id и parent_id.

Строчный иерархический идентификатор.

В комментариях к статье [1] была высказана идея хранения иерархической информации в строковом столбце таблицы. Такая строка состоит из последовательных элементов — последовательностей символов одинаковой длины. Элемент представляет собой уникальный среди своих соседей по ветке идентификатор.
Посмотрим структуру строчного идентификатора на примере, где каждый элемент представлен одним символом диапазона a..z:

Код:
            Корневой элемент — пустая строка. Может отсутствовать.
a           Элемент первого уровня.
aa          Элемент второго уровня.
b           Второй элемент первого уровня.
ba
baa
baaa        Первый элемент ветки 'baa'.
baab
...
baaz        Последний — 26-й элемент ветки 'baa'.

Аналогичный пример для элементов из двух символьной последовательности:

Код:
aa
aaaa
ab
abaa
abaaaa
abaaaaaa    Первый элемент ветки 'abaaaa'.
abaaaaab
....
abaaaazz    Последний — 676-й элемент ветки 'abaaaa'.

Особенность такого подхода в том, что идентификатор узла содержит информацию о всех предках узла в дереве. Технически, он так же отличается тем, что максимальное число соседей и максимальное число уровней задаются на этапе проектирования и создания таблицы. Чтобы иметь возможность расширять эти ограничения в будущем, необходимо учитывать в клиентской программе и в запросах к таблице возможность изменения размера элемента, диапазона используемых символов и размера поля строчного идентификатора.
Адресация всей ветки происходит по префиксу, оператором LIKE 'префикс%'. Т.е. одним запросом можно получить данные о всех узлах ветки дерева — это сказочно удобно. Также не сложно перенести узлы ветки в другую часть дерева простыми строковыми операциями.
В SQL подобная таблица будет выглядеть так:

Код: (MySQL)
CREATE TABLE branches
(
    hierachy VARCHAR(32) BINARY NOT NULL,
    PRIMARY KEY (hierachy)
);

Введем тестовые данные:

Код: (MySQL)
INSERT INTO branches (hierachy) VALUES
    ('a'),
    ('aa'),
    ('aaa'),
    ('aaaa'),
    ('aaaaa'),
    ('aaaab'),
    ('aaaac'),
    ('aaaad'),
    ('aaab'),
    ('aaac'),
    ('ab'),
    ('aba'),
    ('abaa'),
    ('abab'),
    ('abb'),
    ('abc'),
    ('abd'),
    ('b'),
    ('ba'),
    ('baa'),
    ('bab');

Перемещение ветки 'ba' в позицию 'abab' можно сделать так:

Код: (MySQL)
UPDATE branches br
SET br.hierachy = CONCAT('abab', SUBSTR(br.hierachy, LENGTH('ba') + 1))
WHERE br.hierachy LIKE 'ba%';

Для выборки фрагмента дерева (ветки) 'aa' используем следующий запрос:

mysql> SELECT br.hierachy
    FROM branches br
    WHERE br.hierachy LIKE 'aa%'
    ORDER BY br.hierachy;
+----------+
| hierachy |
+----------+
| aa       |
| aaa      |
| aaaa     |
| aaaaa    |
| aaaab    |
| aaaac    |
| aaaad    |
| aaab     |
| aaac     |
+----------+
9 rows in set (0.00 sec)

Посмотрим, что говорит об этом запросе оптимизатор MySQL:

mysql> EXPLAIN SELECT br.hierachy FROM branches br
    -> WHERE br.hierachy LIKE 'aa%' ORDER BY br.hierachy;
+----+-------------+-------+-------+---------------+---------+---------+------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  |
+----+-------------+-------+-------+---------------+---------+---------+------+
|  1 | SIMPLE      | br    | range | PRIMARY       | PRIMARY | 98      | NULL |
+----+-------------+-------+-------+---------------+---------+---------+------+
+------+--------------------------+
| rows | Extra                    |
+------+--------------------------+
|    9 | Using where; Using index |
+------+--------------------------+

Индекс здесь используется и, что примечательно — выбирается вся ветка BTREE, адресованная префиксом 'aa'. Не хочу огорчать, но если префикс будет состоять из одного символа, то оптимизатор MySQL выбирает полное сканирование таблицы. Что хорошо, а что нет — нельзя понять, не зная размеров и строения дерева. Может «full scan» будет быстрее, если дерево слабо разветвлено или если в таблице мало строк.
Вот таким образом будет выглядеть выборка всех предков узла 'aaab':

Код: (MySQL)
SELECT br.hierachy
FROM branches br
WHERE br.hierachy IN ('a', 'aa', 'aaa')
ORDER BY br.hierachy;

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

Классическая иерархия — id и parent_id.

Куда ближе, понятнее и менее ограниченна классическая система иерархии с использованием числовых идентификаторов узла и его предка. Недостаток ее в том, что для выбора ветки с N уровнями иерархии необходимо выполнить N запросов к таблице. Если такие СУБД, как Oracle, поддерживают иерархические запросы уже в синтаксисе (физически они выполняют туже работу, но скрытно). Хотелось бы сделать какую-нибудь автоматизацию и перенос логики на сервер.
В MySQL 4.1 и выше есть агрегатная функция, позволяющая объединить значения столбца группируемых строк в виде строки значений, разделенных запятыми (или другим разделителем — на выбор), а также отсортировать их в нужном порядке.

Код: (MySQL)
GROUP_CONCAT([DISTINCT] expr [,expr ...]
[ORDER BY {unsigned_integer | col_name | expr}
[ASC | DESC] [,col_name ...]]
[SEPARATOR str_val])

Эта функция позволит нам несколько сократить время пересылки данных клиенту: вместо списка значений приходит одна строка.
В MySQL 4.1 также появились операторы для работы с SQL-операторами, составляемыми на стороне сервера. По сути это то, что называется «динамический SQL». Но почему-то разработчики сделали так, что внутри процедур, функций и триггеров применять эти операторы нельзя. Только начиная с версии 5.0.13, разрешено применять их внутри процедур (но не функций и триггеров) [3]. Ими мы и воспользуемся для создания процедуры, которая предоставит нам список идентификаторов узлов по номеру базового узла ветки.
Следует помнить, что эти операторы работают только с «user-defined» переменными, имена которых начинаются с символа «@». Такие переменные не имеют жесткого типа, не нуждаются в объявлении и являются глобальными в рамках сессии.
Создадим для тестов таблицу test1 и заполним данными:

Код: (MySQL)
CREATE TABLE T1 (
    id INT NOT NULL,
    parent_id INT NOT NULL,
    PRIMARY KEY (id),
    UNIQUE parent (parent_id, id)
);

INSERT INTO t1 (parent_id, id) VALUES
    (0, 1), (0, 2), (0, 3), (0, 4), (1, 5),
    (1, 6), (1, 7), (5, 8), (5, 9), (9, 10);

Теперь процедура:

Код: (MySQL)
CREATE PROCEDURE fetch_subtree_ids(IN base INT UNSIGNED)
BEGIN
    DECLARE ids TEXT DEFAULT '';

    SET @parents = base;
    SET ids = base;

    loop1: LOOP
        SET @stm = CONCAT(
            'SELECT GROUP_CONCAT(id) INTO @parents FROM test1',
            ' WHERE parent_id IN (', @parents, ')'
        );

        PREPARE fetch_childs FROM @stm;
        EXECUTE fetch_childs;
        DROP PREPARE fetch_childs;

        IF @parents IS NULL THEN LEAVE loop1; END IF;

        SET ids = CONCAT(ids, ',', @parents);
    END LOOP;

    SET @stm = CONCAT('SELECT id FROM test1 WHERE id IN (', ids, ')');

    PREPARE fetch_childs FROM @stm;
    EXECUTE fetch_childs;
    DROP PREPARE fetch_childs;
END;

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

mysql> CALL fetch_subtree_ids(1);
+----+
| id |
+----+
|  1 |
|  5 |
|  6 |
|  7 |
|  8 |
|  9 |
| 10 |
+----+
7 rows in set (0.00 sec)

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

Код: (MySQL)
CREATE PROCEDURE fill(IN nn INT)
BEGIN
    DECLARE n INT;

    SET n = 0;

    WHILE n < nn DO
        INSERT INTO test1 (parent_id, id) VALUES (n, n + 1);
        SET n = n + 1;
    END WHILE;
END;

Очистим таблицу и наполним ее с помощью fill():

mysql> DELETE FROM t1;
Query OK, 10 rows affected (0.00 sec)

mysql> CALL fill(10000);
Query OK, 0 rows affected (0.69 sec)

mysql> CALL fetch_subtree_ids(0);
............
10000 rows in set (8.84 sec)

Query OK, 0 rows affected (10.15 sec)

Большой объем возвращаемых данных мешает точно измерить затраченное на выборку время. Модифицируем процедуру fetch_subtree_ids так, чтобы исключить влияние пересылки данных к клиенту на точность замеров. Найдем строку:

Код: (MySQL)
SET @stm = CONCAT('SELECT id FROM test1 WHERE id IN (', ids, ')');

Заменим ее на:

Код: (MySQL)
SET @stm = CONCAT('SELECT COUNT(*) FROM test1 WHERE id IN (', ids, ')');

И протестируем:

mysql> CALL fetch_subtree_ids(0);
+----------+
| COUNT(*) |
+----------+
|    10000 |
+----------+
1 row in set (6.59 sec)

Query OK, 0 rows affected (6.59 sec)

Сканирование дерева в 10000 последовательных узлов обошлось в 6.59 секунд. Трудно найти такую вложенность. Уменьшив вложенность до 1000, получил 0.59 секунд. До 100 — 0.08. Весьма неплохой результат.

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

Код: (MySQL)
CREATE PROCEDURE fetch_subtree_ids(
    IN name_table VARCHAR(64),
    IN name_id VARCHAR(64),
    IN name_parent VARCHAR(64),
    IN base INT UNSIGNED,
    IN max_levels INT,
    IN result_in_var BOOLEAN,
    OUT result_ids MEDIUMTEXT
)
BEGIN
    DECLARE ids MEDIUMTEXT DEFAULT '';
    DECLARE currlevel INT DEFAULT 0;

    SET @parents = base;

    IF result_in_var THEN
        SET result_ids = '';
    END IF;

    -- В случае если max_levels равно 0, то допускаем 100000 уровней.
    -- Отрицательные значения дадут один уровень — это побочное явление.
    SET currlevel = IF(max_levels, 1, -100000);

    REPEAT
        -- Внимание! Значение base тоже входит в результат.
        IF result_in_var THEN
            -- Если result_in_var истинно, то результат сохраняем в result_ids.
            SET result_ids = CONCAT(result_ids, IF(LENGTH(result_ids), ',', ''), @parents);
        ELSE
            -- Иначе сохраняем в локальной переменной.
            SET ids = CONCAT(ids, IF(LENGTH(ids), ',', ''), @parents);
        END IF;

        SET @stm = CONCAT(
            'SELECT GROUP_CONCAT(', name_id, ') INTO @parents FROM ', name_table,
            ' WHERE ', name_parent, ' IN (', @parents, ')'
        );

        PREPARE fetch_childs FROM @stm;
        EXECUTE fetch_childs;
        DROP PREPARE fetch_childs;

        SET currlevel = currlevel + 1;
    UNTIL (@parents IS NULL OR currlevel > max_levels) END REPEAT;

    IF NOT result_in_var THEN
        -- Если результат не в переменной — вернем рекордсет.
        SET @stm := CONCAT(
            'SELECT ', name_id, ' FROM ', name_table,
            ' WHERE ', name_id, ' IN (', ids, ')'
        );

        PREPARE fetch_childs FROM @stm;
        EXECUTE fetch_childs;
        DROP PREPARE fetch_childs;
    END IF;
END;

Проверим скорость процедуры при возврате данных в переменной:

mysql> call fetch_subtree_ids('test1', 'id', 'parent_id', 0, 0, true, @a);
Query OK, 0 rows affected (6.28 sec)

mysql> call fetch_subtree_ids('test1', 'id', 'parent_id', 0, 1000, true, @a);
Query OK, 0 rows affected (0.66 sec)

mysql> call fetch_subtree_ids('test1', 'id', 'parent_id', 0, 100, true, @a);
Query OK, 0 rows affected (0.07 sec)

mysql> call fetch_subtree_ids('test1', 'id', 'parent_id', 0, 10, false, @a);
+----+
| id |
+----+
|  1 |
|  2 |
|  3 |
|  4 |
|  5 |
|  6 |
|  7 |
|  8 |
|  9 |
+----+
9 rows in set (0.01 sec)

Query OK, 0 rows affected (0.01 sec)

Создадим еще процедуру, которая покажет предков узла:

Код: (MySQL)
CREATE PROCEDURE fetch_parent_ids(
    IN name_table VARCHAR(64),
    IN name_id VARCHAR(64),
    IN name_parent VARCHAR(64),
    IN base INT UNSIGNED,
    IN max_levels INT,
    IN result_in_var BOOLEAN,
    OUT result_ids MEDIUMTEXT
)
BEGIN
    DECLARE currlevel INT;
    DECLARE ids MEDIUMTEXT DEFAULT '';

    IF result_in_var THEN
        SET result_ids = '';
    END IF;

    SET @parent = base;

    -- В случае если max_levels равно 0, то допускаем 100000 уровней.
    -- Отрицательные значения дадут один уровень — это побочное явление.
    SET currlevel = IF(max_levels, 1, -100000);

    SET @stm = CONCAT(
        'SELECT ', name_parent, ' INTO @parent FROM ', name_table, ' WHERE ', name_id, ' = ?'
    );
    PREPARE fetch_parent FROM @stm;

    REPEAT
        EXECUTE fetch_parent USING @parent;

        IF result_in_var THEN
            -- Если result_in_var истинно, то результат сохраняем в result_ids.
            SET result_ids = CONCAT(result_ids, IF(LENGTH(result_ids), ',', ''), @parent);
        ELSE
            -- Иначе сохраняем в локальной переменной.
            SET ids = CONCAT(ids, IF(LENGTH(ids), ',', ''), @parent);
        END IF;

        SET currlevel = currlevel + 1;
    UNTIL (NOT @parent OR currlevel > max_levels) END REPEAT;

    DROP PREPARE fetch_parent;

    IF NOT result_in_var THEN
        -- Если результат не в переменной — вернем рекордсет.
        SET @stm = CONCAT(
            'SELECT ', name_id, ' FROM ', name_table,
            ' WHERE ', name_id, ' IN (', ids, ')'
        );

        PREPARE fetch_parents FROM @stm;
        EXECUTE fetch_parents;
        DROP PREPARE fetch_parents;
    END IF;
END;

В данном случае можно было обойтись без PREPARE/EXECUTE, но тогда пришлось бы проститься с универсальность — работой с любой таблицей.
Проверим:

mysql> CALL fetch_parent_ids('t1', 'id', 'parent_id', 100, 10, true, @a);
Query OK, 0 rows affected (0.01 sec)

mysql> SELECT @a;
+-------------------------------+
| @a                            |
+-------------------------------+
| 99,98,97,96,95,94,93,92,91,90 |
+-------------------------------+
1 row in set (0.00 sec)

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

Ссылки.





Публикация статьи на иных ресурсах, кроме сайта Клуба программистов «Весельчак У», допускается только с разрешения автора.

Версия для печати
Обсудить на форуме (2)