Спонсорские ссылки
-
Статья
Версия для печати
Обсудить на форуме
MySQL. Деревья. Добавление материализованного пути к паре id—parent_id.

© Роман Чернышов (RXL), 27.12.2011 — 29.12.2011.


После публикации моей статьи «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 тоже разделить таблицу на две части, то скорость деградации производительности может снизится. Это вопрос для исследования.
Версия для печати
Обсудить на форуме