Статья: "MySQL. Деревья. Добавление материализованного пути к паре id—parent

Статья

MySQL. Деревья. Добавление материализованного пути к паре id—parent_id.

После публикации моей статьи «SQLite. Деревья. Добавление материализованного пути к паре id—parent_id» один из читателей попросил меня «портировать» алгоритм на MySQL. Я не возражал и в данной статье попытаюсь это сделать.

Обзор различий

MySQL очень сильно отличается от SQLite. Прежде всего, это разные сегменты рынка: SQLite позиционируется только для встраиваемых баз данных, а MySQL, в основном, позиционируется для web-решений, хотя встречается и в других применениях, включая встраиваемые. Существенные различия есть и в возможностях этих СУБД. Причем, сказать, что одна СУБД лучше другой тоже нельзя. Перечислю важные для данной статьи стороны:

SQLite поддерживает транзакционность «в базе». MySQL для этого требует использование формата InnoDB, хотя наиболее популярным является формат MyISAM.
Поддержка внешних ключей реализована в обеих СУБД, но в SQLite на текущий момент есть нарекания.
В SQLite отсутствует язык пользовательских процедур и нет переменных, что ограничивает возможности триггеров и вынуждает искать обходные пути. В MySQL этот язык достаточно развит, чтобы описать сложный алгоритм обработки, но тоже есть отдельные недостатки. Например, операторы выдачи исключений появились лишь в версии 5.5, когда как на момент написания статьи наиболее распространенные для хостингов версии — 5.0 и 5.1.
В MySQL на одно событие можно установить только один триггер, когда как в SQLite таких триггеров может быть несколько.
В SQLite допустимо перекрывать операции чтения и обновления одной и той же таблицы в одном операторе. Причем, можно даже изменять (в том числе добавлять и удалять) строки той же таблицы в назначенных на нее триггерах. MySQL ничего такого не допускает.

Реализация

Из-за перечисленных особенностей MySQL (невозможность в триггере обновлять «свою» таблицу) пришлось вынести поле материализованного пути в отдельную таблицу. Естественно, делать это пришлось с копией id. По той же причине удаление зависимых узлов поручено внешним ключам. Для активации внешних ключей и корректной работы триггеров также необходима поддержка транзакций — по этому используем для таблиц движок InnoDB.

Для статьи я буду использовать MySQL версии 5.5. В MySQL 5.0 и 5.1 оператор SIGNAL нужно заменить на чтение несуществующей таблицы: это приводит к исключению. В имени таблицы (длиной до 64 символов) можно кратко передать смысл исключения.

mysql> SELECT a FROM __exception__integrity_check;
ERROR 1146 (42S02): Table 'test.__exception__integrity_check' doesn't exist

Создаем таблицы:

Код: (MySQL) tables.sql

CREATE TABLE tree
(
id INT UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT,
parent_id INT UNSIGNED DEFAULT NULL,
content VARCHAR(100) NOT NULL DEFAULT '',
FOREIGN KEY (parent_id) REFERENCES tree (id)
ON DELETE CASCADE ON UPDATE RESTRICT
) ENGINE=INNODB;

CREATE TABLE tree_path
(
id INT UNSIGNED NOT NULL PRIMARY KEY,
path VARCHAR(255) CHARACTER SET latin1
NOT NULL DEFAULT '' UNIQUE,
FOREIGN KEY (id) REFERENCES tree (id)
ON DELETE CASCADE ON UPDATE RESTRICT
) ENGINE=INNODB;

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

Код: (SQL)

SELECT t.id, t.parent_id, t.content
FROM tree_path tp, tree t
WHERE tp.path LIKE CONCAT(
(
SELECT tp2.path
FROM tree_path tp2
WHERE tp2.id = 1 -- Идентификатор корня поддерева.
),
'%'
)
AND t.id = tp.id
ORDER BY tp.path;

Набор триггеров:

Код: (MySQL) triggers.sql

delimiter $$
CREATE TRIGGER tree__ai AFTER INSERT ON tree
FOR EACH ROW
BEGIN
DECLARE new_path VARCHAR(255);

-- Вычисление материализованного пути.
SET new_path = CONCAT(
IFNULL(
(
SELECT tp.path
FROM tree_path tp
WHERE tp.id = NEW.parent_id
),
'/'
),
NEW.id,
'/'
);
INSERT INTO tree_path (id, path)
VALUES (NEW.id, new_path);
END;$$
CREATE TRIGGER tree__bu BEFORE UPDATE ON tree
FOR EACH ROW
BEGIN
-- Смена id или ссылка на самого себя как на предка?
IF OLD.id != NEW.id OR NEW.parent_id <=> OLD.id THEN
SIGNAL SQLSTATE VALUE '42000'
SET MESSAGE_TEXT =
'An attempt to damage the integrity of the tree.';
END IF;
END;$$
CREATE TRIGGER tree__au AFTER UPDATE ON tree
FOR EACH ROW
BEGIN
DECLARE old_path, new_path VARCHAR(255) CHARACTER SET latin1;

SET old_path = (
SELECT tp.path
FROM tree_path tp
WHERE tp.id = OLD.id
);
SET new_path = CONCAT(
IFNULL(
(
SELECT tp.path
FROM tree_path tp
WHERE tp.id = NEW.parent_id
),
'/'
),
OLD.id,
'/'
);

-- Закольцовка пути?
IF new_path LIKE CONCAT('%/', OLD.id, '/_%') THEN
SIGNAL SQLSTATE VALUE '42000'
SET MESSAGE_TEXT =
'An attempt to damage the integrity of the tree.';
END IF;

-- Изменение пути у всего поддерева.
UPDATE tree_path
SET path = REPLACE(path, old_path, new_path)
WHERE path LIKE CONCAT(old_path, '%');
END;$$
delimiter ;

Тесты

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

Проверка на правильные действия: вставка дерева, перемещение и удаление поддерева.

mysql> INSERT INTO tree (parent_id, id) VALUES
-> (NULL, 1), (NULL, 2), (1, 3), (1, 4), (3, 5),
-> (3, 6), (4, 7), (4, 8), (5, 9), (5, 10);
Query OK, 10 rows affected (0.01 sec)
Records: 10 Duplicates: 0 Warnings: 0

mysql> SELECT * FROM tree; SELECT * FROM tree_path;
+----+-----------+---------+
| id | parent_id | content |
+----+-----------+---------+
| 1 | NULL | |
| 2 | NULL | |
| 3 | 1 | |
| 4 | 1 | |
| 5 | 3 | |
| 6 | 3 | |
| 7 | 4 | |
| 8 | 4 | |
| 9 | 5 | |
| 10 | 5 | |
+----+-----------+---------+
10 rows in set (0.00 sec)

+----+------------+
| id | path |
+----+------------+
| 1 | /1/ |
| 3 | /1/3/ |
| 5 | /1/3/5/ |
| 10 | /1/3/5/10/ |
| 9 | /1/3/5/9/ |
| 6 | /1/3/6/ |
| 4 | /1/4/ |
| 7 | /1/4/7/ |
| 8 | /1/4/8/ |
| 2 | /2/ |
+----+------------+
10 rows in set (0.00 sec)

mysql> UPDATE tree SET parent_id = 7 WHERE id = 3;
Query OK, 1 row affected (0.01 sec)
Rows matched: 1 Changed: 1 Warnings: 0

mysql> SELECT * FROM tree; SELECT * FROM tree_path;
+----+-----------+---------+
| id | parent_id | content |
+----+-----------+---------+
| 1 | NULL | |
| 2 | NULL | |
| 3 | 7 | |
| 4 | 1 | |
| 5 | 3 | |
| 6 | 3 | |
| 7 | 4 | |
| 8 | 4 | |
| 9 | 5 | |
| 10 | 5 | |
+----+-----------+---------+
10 rows in set (0.00 sec)

+----+----------------+
| id | path |
+----+----------------+
| 1 | /1/ |
| 4 | /1/4/ |
| 7 | /1/4/7/ |
| 3 | /1/4/7/3/ |
| 5 | /1/4/7/3/5/ |
| 10 | /1/4/7/3/5/10/ |
| 9 | /1/4/7/3/5/9/ |
| 6 | /1/4/7/3/6/ |
| 8 | /1/4/8/ |
| 2 | /2/ |
+----+----------------+
10 rows in set (0.00 sec)

mysql> DELETE FROM tree WHERE id = 7;
Query OK, 1 row affected (0.01 sec)

mysql> SELECT * FROM tree; SELECT * FROM tree_path;
+----+-----------+---------+
| id | parent_id | content |
+----+-----------+---------+
| 1 | NULL | |
| 2 | NULL | |
| 4 | 1 | |
| 8 | 4 | |
+----+-----------+---------+
4 rows in set (0.00 sec)

+----+---------+
| id | path |
+----+---------+
| 1 | /1/ |
| 4 | /1/4/ |
| 8 | /1/4/8/ |
| 2 | /2/ |
+----+---------+
4 rows in set (0.00 sec)

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

mysql> UPDATE tree SET id = 100 WHERE id = 1;
ERROR 1644 (42000): An attempt to damage the integrity of the tree.
mysql> UPDATE tree SET parent_id = 100 WHERE id = 1;
ERROR 1452 (23000): Cannot add or update a child row: a foreign key constraint fails (`test`.`tree`, CONSTRAINT `tree_ibfk_1` FOREIGN KEY (`parent_id`) REFERENCES `tree` (`id`) ON DELETE CASCADE)
mysql> UPDATE tree SET parent_id = 1 WHERE id = 1;
ERROR 1644 (42000): An attempt to damage the integrity of the tree.
mysql> UPDATE tree SET parent_id = 8 WHERE id = 1;
ERROR 1644 (42000): An attempt to damage the integrity of the tree.

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

Код: (Perl)

#!/usr/bin/perl -W

use DBI;
use strict;

$| = 1;

(scalar(@ARGV) != 2) and die('Invalid parameters!');

my ($levels, $branches) = @ARGV;
my ($db, $stm1, $cnt, $trans, $start_time);

$trans = 10000; # Транзакций на COMMIT.

$db = DBI->connect('dbi:mysql:host=localhost;dbname=test', 'root', '') or die('DB not connected!');

$stm1 = $db->prepare('INSERT INTO tree (parent_id) VALUES (?)');

$start_time = time();

my (@curr, @next);

@next = (1);
$cnt = 0;

for (1..$levels)
{
@curr = @next;
@next = ();

for my $parent_id (@curr)
{
for (1..$branches)
{
$cnt++;
$db->begin_work() if $cnt % $trans == 1;
$stm1->bind_param(1, $parent_id, { 'TYPE' => DBI::SQL_INTEGER });
$stm1->execute();
push(@next, $db->last_insert_id('', '', '', ''));
$db->commit() if $cnt % $trans == 0;
}
}
}

$db->commit() if $cnt % $trans;

# Результат: число уровней, число ветвей на узел, время выполнения скрипта.
print ("$levels $branches " . (time() - $start_time) . "\n");

$stm1->finish();
$db->disconnect();

Добавляю тестовые данные: корни двух деревьев.

mysql> INSERT INTO tree (parent_id) VALUES (NULL), (NULL);
Query OK, 2 rows affected (0.00 sec)
Records: 2 Duplicates: 0 Warnings: 0

mysql> SELECT * FROM tree; SELECT * FROM tree_path;
+----+-----------+---------+
| id | parent_id | content |
+----+-----------+---------+
| 1 | NULL | |
| 2 | NULL | |
+----+-----------+---------+
2 rows in set (0.01 sec)

+----+------+
| id | path |
+----+------+
| 1 | /1/ |
| 2 | /2/ |
+----+------+
2 rows in set (0.00 sec)

Кстати, странность при такой форме вставки: идентификатор 3 куда-то пропадает. Пока не разбирался, так как для данных тестов это не важно.

Создаю дерево с 3-мя ветвлениями по 10 ветвей в каждом.

$ ./fill.pl 3 10
3 10 1

Получается 2 + 1110 узлов.

mysql> SELECT * FROM tree; SELECT * FROM tree_path;
+------+-----------+---------+
| id | parent_id | content |
+------+-----------+---------+
| 1 | NULL | |
| 2 | NULL | |
| 4 | 1 | |
| 5 | 1 | |
.....
| 1112 | 113 | |
| 1113 | 113 | |
+------+-----------+---------+
1112 rows in set (0.00 sec)

+------+-----------------+
| id | path |
+------+-----------------+
| 1 | /1/ |
| 10 | /1/10/ |
| 74 | /1/10/74/ |
.....
| 714 | /1/10/74/714/ |
| 713 | /1/9/73/713/ |
| 2 | /2/ |
+------+-----------------+
1112 rows in set (0.00 sec)

Проверяем время перемещения дерева узла 1 на узел 2, подсчитываем число строк в перемещенном дереве и максимальную длину получившегося ключа.

mysql> UPDATE tree SET parent_id = 2 WHERE id = 1;
Query OK, 1 row affected (0.10 sec)
Rows matched: 1 Changed: 1 Warnings: 0

mysql> SELECT COUNT(*), MAX(LENGTH(path))
   -> FROM tree_path
   -> WHERE path LIKE (
   -> SELECT CONCAT(path, '%')
   -> FROM tree_path
   -> WHERE id = 1
   -> )
   -> ORDER BY path;
+----------+-------------------+
| COUNT(*) | MAX(LENGTH(path)) |
+----------+-------------------+
| 1111 | 17 |
+----------+-------------------+
1 row in set (0.00 sec)

mysql> SELECT *
   -> FROM tree_path
   -> WHERE path LIKE (
   -> SELECT CONCAT(path, '%')
   -> FROM tree_path
   -> WHERE id = 1
   -> )
   -> ORDER BY path;
+------+-------------------+
| id | path |
+------+-------------------+
| 1 | /2/1/ |
| 10 | /2/1/10/ |
| 74 | /2/1/10/74/ |
| 714 | /2/1/10/74/714/ |
.....
| 712 | /2/1/9/73/712/ |
| 713 | /2/1/9/73/713/ |
+------+-------------------+
1111 rows in set (0.01 sec)

Попробуем те же тесты с еще большим деревом. Очистим базу и, для чистоты эксперимента, вернем AUTO_INCREMENT в начало.

mysql> DELETE FROM tree;
Query OK, 2 rows affected (0.10 sec)

mysql> ALTER TABLE tree AUTO_INCREMENT = 1;
Query OK, 0 rows affected (0.02 sec)
Records: 0 Duplicates: 0 Warnings: 0

mysql> INSERT INTO tree (parent_id) VALUES (NULL), (NULL);
Query OK, 2 rows affected (0.00 sec)
Records: 2 Duplicates: 0 Warnings: 0

Создаю дерево с 4-мя ветвлениями по 10 ветвей в каждом.

$ ./fill.pl 4 10
4 10 7

Такие же тесты.

mysql> SELECT COUNT(*) FROM tree;
+----------+
| COUNT(*) |
+----------+
| 11112 |
+----------+
1 row in set (0.00 sec)

mysql> UPDATE tree SET parent_id = 2 WHERE id = 1;
Query OK, 1 row affected (0.87 sec)
Rows matched: 1 Changed: 1 Warnings: 0

mysql> SELECT COUNT(*), MAX(LENGTH(path))
   -> FROM tree_path
   -> WHERE path LIKE (
   -> SELECT CONCAT(path, '%')
   -> FROM tree_path
   -> WHERE id = 1
   -> )
   -> ORDER BY path;
+----------+-------------------+
| COUNT(*) | MAX(LENGTH(path)) |
+----------+-------------------+
| 11111 | 23 |
+----------+-------------------+
1 row in set (0.02 sec)

mysql> DELETE FROM tree WHERE id = 1;
Query OK, 1 row affected (0.76 sec)

Стало заметно медленнее. Проверил еще вариант "fill.pl 1 10000": почти тоже самое время перемещения — 0.87 секунды, но длина ключа всего 11. То есть здесь большая зависимость от числа узлов, а не от длины ключа. Во всяком случае, падение производительности не такое резкое, как у SQLite при тех же параметрах тестов. Возможно, что если в SQLite тоже разделить таблицу на две части, то скорость деградации производительности может снизится. Это вопрос для исследования.

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

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