Автор:
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 подобная таблица будет выглядеть так:
CREATE TABLE branches
(
hierachy VARCHAR(32) BINARY NOT NULL,
PRIMARY KEY (hierachy)
);
Введем тестовые данные:
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' можно сделать так:
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':
SELECT br.hierachy
FROM branches br
WHERE br.hierachy IN ('a', 'aa', 'aaa')
ORDER BY br.hierachy;
Проверку на использование индекса приводить не будем: здесь картина точно такая же, как и при выборке фрагмента дерева.
Отрицательными сторонами этого метода являются большая длина индекса и сложность генерации уникального идентификатора — необходимо выбирать из таблицы идентификаторы всех соседей и находить среди них неиспользованные значения.
Куда ближе, понятнее и менее ограниченна классическая система иерархии с использованием числовых идентификаторов узла и его предка. Недостаток ее в том, что для выбора ветки с N уровнями иерархии необходимо выполнить N запросов к таблице. Если такие СУБД, как Oracle, поддерживают иерархические запросы уже в синтаксисе (физически они выполняют туже работу, но скрытно). Хотелось бы сделать какую-нибудь автоматизацию и перенос логики на сервер.
В MySQL 4.1 и выше есть агрегатная функция, позволяющая объединить значения столбца группируемых строк в виде строки значений, разделенных запятыми (или другим разделителем — на выбор), а также отсортировать их в нужном порядке.
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 и заполним данными:
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);
Теперь процедура:
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)
Работает и корректно. Теперь проверим скорость на больших искусственных данных.
Для начала создадим процедуру, которая наполнит нам таблицу данными:
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 так, чтобы исключить влияние пересылки данных к клиенту на точность замеров. Найдем строку:
SET @stm = CONCAT('SELECT id FROM test1 WHERE id IN (', ids, ')');
Заменим ее на:
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. Весьма неплохой результат.
Добавим в процедуру дополнительные возможности: возможность менять таблицу, имена полей, ограничивать уровень сканирования и возвращать результат в переменную — параметр.
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)
Создадим еще процедуру, которая покажет предков узла:
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: получить результат в виде строки в переменной, как в последнем примере, или получить рекордсет для обработки его в клиентской программе.
Публикация статьи на иных ресурсах, кроме
сайта Клуба программистов «Весельчак У», допускается только с разрешения автора.