Статья: "MySQL. Иерархические запросы. Часть 2."

Статья

MySQL. Иерархические запросы. Часть 2.

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

Небольшое дополнение к ранее вышедшей статье «MySQL. Иерархические запросы». Здесь предлагаю решение той же самой задачи — выборки поддерева на связях id — parent_id, но без динамического SQL — на временных таблицах. Такой вариант работает много быстрее, но процедуры оказываются жестко привязанными к таблицам.

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

Для начала создаем тестовую таблицу:

Код: (MySQL)

CREATE TABLE t1 (
id INT UNSIGNED NOT NULL AUTO_INCREMENT,
parent_id INT UNSIGNED NOT NULL,
lvl SMALLINT UNSIGNED NOT NULL,
PRIMARY KEY (id),
UNIQUE KEY parent (parent_id, id),
UNIQUE KEY lvl (lvl, id)
) ENGINE = MYISAM;

Этой процедурой заполним таблицу тестовыми данными:

Код: (MySQL)

CREATE PROCEDURE fill2(IN levels INT UNSIGNED, IN branches INT UNSIGNED)
BEGIN
DECLARE lvl INT UNSIGNED DEFAULT 1;
DECLARE n INT UNSIGNED;

CREATE TEMPORARY TABLE _fill_tmp1 (id INT UNSIGNED NOT NULL) ENGINE=MEMORY;

INSERT INTO t1 (parent_id, lvl) VALUES (0, 0);

WHILE lvl < levels DO
INSERT INTO _fill_tmp1
SELECT t1.id FROM t1
WHERE t1.lvl = lvl - 1;

SET n = 0;

while n < branches DO
INSERT INTO t1 (parent_id, lvl)
SELECT id, lvl FROM _fill_tmp1;

SET n = n + 1;
END WHILE;

TRUNCATE TABLE _fill_tmp1;

SET lvl = lvl + 1;
END WHILE;

DROP TABLE _fill_tmp1;
END;

Параметрами можно регулировать количество уровней — levels и степень ветвления дерева (сколько у каждого узла будет потомков) — branches.

Заполним таблицу деревом из 6 уровней и с степенью ветвления 10. Должно получиться SUM(branchesⁿ) узлов, где n от 0 до levels - 1. В нашем случае должно получиться 111111 узлов.

mysql> call fill2(6, 10);
Query OK, 0 rows affected (1.78 sec)

mysql> select count(*) from t1;
+----------+
| count(*) |
+----------+
| 111111 |
+----------+
1 row in set (0.00 sec)

mysql> select * from t1 order by lvl, id limit 31;
+----+-----------+-----+
| id | parent_id | lvl |
+----+-----------+-----+
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 1 | 1 |
| 4 | 1 | 1 |
| 5 | 1 | 1 |
| 6 | 1 | 1 |
| 7 | 1 | 1 |
| 8 | 1 | 1 |
| 9 | 1 | 1 |
| 10 | 1 | 1 |
| 11 | 1 | 1 |
| 12 | 2 | 2 |
| 13 | 3 | 2 |
| 14 | 4 | 2 |
| 15 | 5 | 2 |
| 16 | 6 | 2 |
| 17 | 7 | 2 |
| 18 | 8 | 2 |
| 19 | 9 | 2 |
| 20 | 10 | 2 |
| 21 | 11 | 2 |
| 22 | 2 | 2 |
| 23 | 3 | 2 |
| 24 | 4 | 2 |
| 25 | 5 | 2 |
| 26 | 6 | 2 |
| 27 | 7 | 2 |
| 28 | 8 | 2 |
| 29 | 9 | 2 |
| 30 | 10 | 2 |
| 31 | 11 | 2 |
+----+-----------+-----+
31 rows in set (0.00 sec)

Похоже на правду...

Процедура для выборки заданного поддерева:

Код: (MySQL)

CREATE PROCEDURE fetch_subtree_ids2(
IN base INT UNSIGNED,
IN max_levels INT UNSIGNED
)
BEGIN
DECLARE currlevel INT DEFAULT 1;
DECLARE cnt INT DEFAULT 0;

DROP TABLE IS EXISTS _fst_parents, _fst_tmp, _fst_result;

CREATE TEMPORARY TABLE _fst_parents (id INT UNSIGNED NOT NULL) ENGINE=MEMORY;
CREATE TEMPORARY TABLE _fst_tmp (id INT UNSIGNED NOT NULL) ENGINE=MEMORY;
CREATE TEMPORARY TABLE _fst_result (id INT UNSIGNED NOT NULL) ENGINE=MEMORY;

INSERT INTO _fst_parents VALUES (base);
INSERT INTO _fst_result VALUES (base);

-- В случае если max_levels равно 0, то допускаем 100000 уровней.
SET max_levels = IF(max_levels, max_levels, 100000);

REPEAT
INSERT INTO _fst_tmp
SELECT h.id
FROM _fst_parents t, t1 h
WHERE h.parent_id = t.id;

SELECT COUNT(*) INTO cnt FROM _fst_tmp;

INSERT INTO _fst_result
SELECT id FROM _fst_tmp;

TRUNCATE TABLE _fst_parents;

INSERT INTO _fst_parents
SELECT id FROM _fst_tmp;

TRUNCATE TABLE _fst_tmp;

SET currlevel = currlevel + 1;
UNTIL (cnt = 0 OR currlevel > max_levels) END REPEAT;

SELECT COUNT(id) FROM _fst_result;

DROP TABLE _fst_parents, _fst_tmp, _fst_result;
END;

Процедура чисто для демонстрации — чтобы замерить время, затрачиваемое на выборку идентификаторов поддерева. Для реальной работы надо заменить строку

Код: (MySQL)

SELECT COUNT(id) FROM _fst_result;

на

Код: (MySQL)

SELECT id FROM _fst_result;

Проверим работу процедуры на практике! Напоминаю, что у нас 6 уровней, фактор ветвления 10 и в итоге — 111111 узлов. Выберем все дерево:

mysql> call fetch_subtree_ids2(1, 0);
+-----------+
| COUNT(id) |
+-----------+
| 111111 |
+-----------+
1 row in set (0.67 sec)

Query OK, 0 rows affected (0.67 sec)

Полное дерево выбралось за 0.67 секунды. Это, конечно, долго, но и узлов много. Попробуем выбрать в 100 раз меньший фрагмент:

mysql> call fetch_subtree_ids2(50, 0);
+-----------+
| COUNT(id) |
+-----------+
| 1111 |
+-----------+
1 row in set (0.01 sec)

Query OK, 0 rows affected (0.01 sec)

На выборку поддерева из 1111 элементов (4 уровня) затрачено всего 10 миллисекунд! Замечу, что такое поддерево великовато для типичных задач с каталогами и на практике может потребоваться еще меньше времени.

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

Версия для печати

Обсудить на форуме