Hierarchical data structures and performance

Introduction



In my previous article, I gave a brief overview of the basic models for storing hierarchical structures in relational databases. As it should be, many readers have become an edge question about the performance of the presented algorithms.

In this article I will try to open the veil over this burning issue, and in the next I promise to touch upon optimization issues and the search for non-standard solutions.

Training


So, testing. Like any other testing, ours also requires certain actions to prepare, analyze, develop goals and an action plan.

In fact, the goal is to conduct a series of stress tests of various algorithms on various data volumes. It would also be nice to run tests on several different hardware platforms, but, alas, the author is not capable of it (time and money are all to blame).

Naturally, it would be good to conduct tests of the most important and significant operations, which are usually performed on certain trees. After quite a lot of thought, it was decided to dwell on the following list of tested operations:
  1. Whole tree selection
  2. Fetching a path to a given node
  3. Branch selection of a given node
  4. Search for the parent of the given node
  5. Search for heirs of a given node
  6. Add a new node to the end of the specified parent node
  7. Moving a node (or, in other words, changing a parent)
  8. Removing a node (and the entire branch below it)

It is worth noting that we bring these operations closer to combat conditions, i.e. the input for us will be the identifiers of the nodes and their parents. This will allow you not to be tied to specific implementations of each of the algorithms.

Further, we stipulate that we are interested in the performance of pure SQL, so we will only measure its operation.

The author does not claim to be a complete list of operations. Perhaps someone will recall operations to search for neighbors of a node or to select all leaves of a tree, and even in a given branch - please, everyone has the right to expand and supplement this experiment. In the meantime, I will focus on the basic, in my opinion, basic minimal functionality.

Now I want to dwell in more detail on the implementation of the functions themselves, tests on which will be carried out in the future. But, if you are only interested in bare figures and facts, you can proceed to the next section of the article.

Not all declared functions have trivial solutions in different methods, especially in pure SQL. For example, selecting a branch in an AL-tree is a purely recursive task. But is it worth doing this at the SQL level? ..
In general, you should consider several of the following provisions:
- The database management system on which the tests are performed - MySQL version 5.0.x. The engine is InnoDB (convenient for implementing cascading operations for AL-Tree at the database level).

- Query queries are executed with the SQL_NO_CACHE flag to evaluate the "net" cost of query execution.

- Trees of different types have the same physical structure of nodes (i.e. a tree of one type is randomly created, and the rest of the trees are built from the first).

- The algorithms Nested Set and Materialized Path were strengthened by the level field, which stores the nesting level of the current node in the tree. In particular, we can say that this allows you to increase, for example, the performance of selecting the heirs of a node in the MP tree by more than 100 times! In fact, without this field, these algorithms, in a sense, lose their attractiveness. Therefore, we can talk not so much about their tuning when adding this field, but about the necessary condition for their functioning. Thus, the structure of our test base is as follows:

-- Adjacency List Tree Structure
CREATE TABLE `al_tree` (
`id` bigint(20) NOT NULL auto_increment,
`parent_id` bigint(20) default NULL ,
`name` varchar (50) NOT NULL ,
PRIMARY KEY (`id`),
KEY `fk_tree_tree` (`parent_id`),
CONSTRAINT `fk_tree_tree` FOREIGN KEY (`parent_id`) REFERENCES `al_tree` (`id`) ON DELETE CASCADE ON UPDATE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=utf8

-- Nested Set Tree Structure
CREATE TABLE `ns_tree` (
`id` bigint(20) NOT NULL auto_increment,
`name` varchar (50) NOT NULL ,
`lft` bigint(20) NOT NULL ,
`rgt` bigint(20) NOT NULL ,
` level ` bigint(20) NOT NULL ,
PRIMARY KEY (`id`),
KEY `nslrl_idx` (`lft`,`rgt`,` level `)
) ENGINE=InnoDB DEFAULT CHARSET=utf8

-- Materialized Path Tree Structure
CREATE TABLE `mp_tree` (
`id` bigint(20) NOT NULL auto_increment,
`name` varchar (50) NOT NULL ,
` path ` varchar (100) NOT NULL ,
` level ` int (11) NOT NULL ,
PRIMARY KEY (`id`),
KEY `mpp_idx` (` path `)
) ENGINE=InnoDB DEFAULT CHARSET=utf8


* This source code was highlighted with Source Code Highlighter .


- For working with the Nested Set and Materialized Path trees, functions and procedures were written at the database level to simplify the routine operations of working with trees. In particular, the functions STRFIND, REPLACE_PATH and the procedures MOVE_NODE_NS, MOVE_NODE_MP, REMOVE_NODE_MP:
STRFIND (str, delimtr) were added
--
-- Функция ищет количество вхождений символа delimtr в строку str.
-- Фактически эта функция используется для поиска уровня
-- вложенности узла в дереве типа MATERIALIZED PATH.
-- (Кол-во разделителей в пути узла и есть уровень вложенности)
--
-- @param str VARCHAR(255) - исходная строка
-- @param delimtr CHAR(1) - искомый символ
-- @return INT - кол-во вхождений
--
CREATE FUNCTION `STRFIND`(str VARCHAR (255), delimtr CHAR (1)) RETURNS INT
BEGIN
DECLARE _cnt INT ;
DECLARE _start INT ;
SET _cnt = -1;
SET _start = 1;
WHILE _start > 0 DO
SET _start = LOCATE( delimtr, str);
SET str  = SUBSTRING ( str, _start + 1);
SET _cnt  = _cnt + 1;
END WHILE ;
RETURN _cnt;
END


* This source code was highlighted with Source Code Highlighter .


REPLACE_PATH (_str, _match, _replace)
--
-- Функция замещает в заданной строке _str
-- подстроку _match на строку _replace,.
-- если _match найдена начиная от начала строки _str
-- Удобна для использования в деревьях типа
-- MATERIALIZED PATH для изменения путей.
--
-- @param _str VARCHAR(255) - исходная строка
-- @param _match VARCHAR(255) - подстрока поиска
-- @param _replace VARCHAR(255) - подстрока замены
-- @return VARCHAR(255) - новыя строка
--
CREATE FUNCTION `REPLACE_PATH`( _str VARCHAR (255), _match VARCHAR (255), _replace VARCHAR (255)) RETURNS VARCHAR (255)
BEGIN
IF _str LIKE CONCAT(_match, '%' ) THEN
RETURN CONCAT( _replace, SUBSTRING ( _str, LENGTH(_match)+1, LENGTH(_str)));
END IF ;
RETURN _str;
END


* This source code was highlighted with Source Code Highlighter .


The main difference between the given function and the built-in REPLACE is that it is guaranteed to change the given line only if a match is found FROM the BEGINNING of the line and will make changes only once.

MOVE_NODE_NS (node_id, parent_id)
--
-- ПРОЦЕДУРА ПЕРЕМЕЩЕНИЯ ВЕТКИ В ДЕРЕВЕ ТИПА NESTED SET
--
-- @param node_id - идентификатор узла, который следует переместить
-- @param parent_id - идентификатор узла в который следует переместить
--
CREATE PROCEDURE MOVE_NODE_NS( node_id BIGINT, parent_id BIGINT)
BEGIN
DECLARE done INT DEFAULT 0;
DECLARE c_id, c_lft, c_rgt, c_lvl, nWidth, nLeft, nRight, dtKey, nLvl, pRight, addLvl, addKey BIGINT;
DECLARE c_name VARCHAR (50);

-- Создаем курсор который будет хранить всю ветку,
-- которую мы перемещаем
DECLARE mvBranch CURSOR FOR
SELECT id, name, lft - dtKey, rgt - dtKey, level - nLvl FROM ns_tree
WHERE lft >= nLeft AND rgt <= nRight;

DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;

-- Собираем необходимые данные о выбранной ветке
SELECT rgt - lft + 1, lft, rgt, lft - 1, level INTO nWidth, nLeft, nRight, dtKey, nLvl
FROM ns_tree WHERE id = node_id;

-- Выбираем ветку в курсор
OPEN mvBranch;

-- Удаляем ветку из дерева
DELETE FROM ns_tree WHERE lft BETWEEN nLeft AND nRight;

-- Обновляем ключи в дереве
UPDATE ns_tree SET rgt = rgt - nWidth WHERE rgt > nRight;
UPDATE ns_tree SET lft = lft - nWidth WHERE lft > nRight;

-- выбираем данные о родителе в новом дереве
SELECT rgt, level + 1 INTO pRight, addLvl FROM ns_tree WHERE id = parent_id;

SELECT MAX (node.rgt) INTO addKey FROM ns_tree node, ns_tree parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node. level = parent. level + 1 AND parent.id = parent_id;

-- создаем в дереве пространство, куда будет
-- помещена выбранная ранее ветка
UPDATE ns_tree SET rgt = rgt + nWidth WHERE rgt >= pRight;
UPDATE ns_tree SET lft = lft + nWidth WHERE lft > pRight;

-- преобразуем ветку должным образом и вставляем.
-- в новое дерево
REPEAT
FETCH mvBranch INTO c_id, c_name, c_lft, c_rgt, c_lvl;
IF NOT done THEN
INSERT INTO ns_tree VALUES (c_id, c_name, c_lft + addKey, c_rgt + addKey, c_lvl + addLvl);
END IF ;
UNTIL done END REPEAT;

CLOSE mvBranch;
END


* This source code was highlighted with Source Code Highlighter .


MOVE_NODE_MP (node_id, parent_id)
--
-- ПРОЦЕДУРА ПЕРЕМЕЩЕНИЯ ВЕТКИ В ДЕРЕВЕ ТИПА MATERIALIZED PATH
--
-- @param node_id - идентификатор узла, который следует переместить
-- @param parent_id - идентификатор узла в который следует переместить
--
CREATE PROCEDURE MOVE_NODE_MP( node_id BIGINT, parent_id BIGINT)
BEGIN
DECLARE done, m_cnt, m_rows, p_cnt, p_rows INT DEFAULT 0;
DECLARE c_id, p_id, n_pos, n_lvl, np_id, np_lvl, new_pos, dt_lvl, ch_id, ch_pos BIGINT;
DECLARE c_path, p_path, n_path, np_path, ch_path, new_path VARCHAR (100);

-- Создаем курсор, в который выбираем ветку,
-- которую следует переместить
DECLARE mvBranch CURSOR FOR
SELECT SQL_CALC_FOUND_ROWS node.id, node. path FROM mp_tree node, mp_tree parent
WHERE node. path LIKE CONCAT(parent. path , '%' ) AND parent.id = node_id;

-- Создаем курсор, в который вибираем все ветки справа
-- от перемещаемой, находящиеся с ней на одном уровне
DECLARE pChildren CURSOR FOR
SELECT SQL_CALC_FOUND_ROWS node.id, node. path ,
CAST ( SUBSTRING (REVERSE(node. path ), 1, LOCATE( '.' , node. path )-1) AS UNSIGNED) as pos
FROM mp_tree node, mp_tree parent
WHERE node. path LIKE CONCAT(parent. path , '%' ) AND node. level = parent. level + 1
AND CAST ( SUBSTRING (REVERSE(node. path ), 1, LOCATE( '.' , node. path )-1) AS UNSIGNED) > n_pos
AND parent.id = p_id
ORDER BY pos;

DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;

-- Собираем необходимые данные
SELECT path , CAST ( SUBSTRING (REVERSE( path ), 1, LOCATE( '.' , path )-1) AS UNSIGNED), level INTO n_path, n_pos, n_lvl FROM mp_tree
WHERE id = node_id;

SELECT parent.id, parent. path INTO p_id, p_path FROM mp_tree node, mp_tree parent
WHERE parent. path = SUBSTRING ( node. path , 1, (LENGTH(node. path ) - LOCATE( '.' , REVERSE(node. path ))))
AND node.id = node_id;

SELECT id, path , level INTO np_id, np_path, np_lvl FROM mp_tree WHERE id = parent_id;

-- Находим разницу в уровнях между уровнями перемещаемых узлов
-- и новым родителем:
SET dt_lvl = np_lvl - n_lvl + 1;

SELECT MAX ( CAST ( SUBSTRING (REVERSE(node. path ), 1, LOCATE( '.' , node. path )-1) AS UNSIGNED)) + 1
INTO new_pos FROM mp_tree node, mp_tree parent WHERE node. path LIKE CONCAT(parent. path , '%' )
AND node. level = parent. level + 1 AND parent.id = parent_id;

-- Перемещаем ветку
OPEN mvBranch;
SELECT FOUND_ROWS() INTO m_rows;

WHILE m_cnt < m_rows DO
FETCH mvBranch INTO c_id, c_path;
UPDATE mp_tree
SET path = REPLACE_PATH( path , n_path, CONCAT(np_path, '.' , new_pos)), level = level + dt_lvl WHERE id = c_id;
SET m_cnt = m_cnt + 1;
END WHILE ;
CLOSE mvBranch;

-- Исправляем данные о путях в ветке из которой.
-- переместили заданную ветку
OPEN pChildren;
SELECT FOUND_ROWS() INTO p_rows;

WHILE p_cnt < p_rows DO
FETCH pChildren INTO ch_id, ch_path, ch_pos;
UPDATE mp_tree SET path = REPLACE_PATH( path , ch_path, CONCAT(p_path, '.' , ch_pos - 1)) WHERE path LIKE CONCAT( ch_path, '%' );
SET p_cnt = p_cnt + 1;
END WHILE ;
CLOSE pChildren;
END


* This source code was highlighted with Source Code Highlighter .


REMOVE_NODE_MP (node_id)
--
-- ПРОЦЕДУРА УДАЛЕНИЯ ВЕТКИ В ДЕРЕВЕ ТИПА MATERIALIZED PATH
--
-- @param node_id - идентификатор узла, который следует удалить
--
CREATE PROCEDURE REMOVE_NODE_MP( node_id BIGINT)
BEGIN
DECLARE n_pos, ch_id, p_id, ch_pos BIGINT;
DECLARE n_path, ch_path, p_path VARCHAR (100);
DECLARE done, p_cnt, p_rows INT DEFAULT 0;

-- Создаем курсор, в который вибираем все ветки справа
-- от перемещаемой, находящиеся с ней на одном уровне
DECLARE pChildren CURSOR FOR
SELECT SQL_CALC_FOUND_ROWS node.id, node. path ,
CAST ( SUBSTRING (REVERSE(node. path ), 1, LOCATE( '.' , node. path )-1) AS UNSIGNED) as pos
FROM mp_tree node, mp_tree parent
WHERE node. path LIKE CONCAT(parent. path , '%' ) AND node. level = parent. level + 1
AND CAST ( SUBSTRING (REVERSE(node. path ), 1, LOCATE( '.' , node. path )-1) AS UNSIGNED) > n_pos
AND parent.id = p_id
ORDER BY pos;

DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;

-- Собираем необходимые данные
SELECT path , CAST ( SUBSTRING (REVERSE( path ), 1, LOCATE( '.' , path )-1) AS UNSIGNED) INTO n_path, n_pos FROM mp_tree
WHERE id = node_id;

SELECT parent.id, parent. path INTO p_id, p_path FROM mp_tree node, mp_tree parent
WHERE parent. path = SUBSTRING ( node. path , 1, (LENGTH(node. path ) - LOCATE( '.' , REVERSE(node. path ))))
AND node.id = node_id;

-- Удаляем вветку
DELETE FROM mp_tree WHERE path LIKE CONCAT( n_path, '%' );

-- Исправляем данные о путях в ветке из удалили заданную ветку
OPEN pChildren;
SELECT FOUND_ROWS() INTO p_rows;

WHILE p_cnt < p_rows DO
FETCH pChildren INTO ch_id, ch_path, ch_pos;
UPDATE mp_tree SET path = REPLACE_PATH( path , ch_path, CONCAT(p_path, '.' , ch_pos - 1)) WHERE path LIKE CONCAT( ch_path, '%' );
SET p_cnt = p_cnt + 1;
END WHILE ;
CLOSE pChildren;
END


* This source code was highlighted with Source Code Highlighter .


In fact, now all the subtleties of the implementation are disclosed, you can stop here and move on to the questions of conducting tests.

Testing



Testing was carried out using a self-written console program on the following configuration:
Hardware:
CPU: Intel® Core(TM)2 Duo CPU E7200 @ 2.53GHz 6Mb 64bit
RAM: 4 Gb
HD: 2 x 250Gb 7200rpm RAID 1


Software:
OS: Debian Linux 2.6.26-1-amd64 (64bit)
PHP-CLI: 5.2.6-5 with Suhosin-Patch 0.9.6.2
MySQL: 5.0.51a, for debian-linux-gnu (x86_64) using readline 5.2


Let's just say that this device is a server that is far from being heavily loaded at the moment (about 100,000 fairly simple HTTP requests per day), which is almost not noticeable for such a configuration.

You can download the program from here and try to test it on your machine (it works only in a Unix-like environment). You will find instructions on how to use the program in the downloaded distribution package in the README.TXT file.

During testing, 5 tree configurations were selected:
  • 100 knots and nesting level 5
  • 1000 knots and nesting level 10
  • 10,000 knots and nesting level 20
  • 100,000 nodes and nesting level 25
  • 500,000 nodes and nesting level 30

These are trees over which tests were successfully completed. All tests were completed in less than 6 hours, while most of the time, of course, took the last test with trees at half a million nodes.

The tree creation algorithm works in such a way that the law of distribution of nodes in a tree is approximately the following:
Where along the abscissa axis are identifiers of nodes in ascending order, and along the ordinate axis is the number of nodes in the branches of a node with a given identifier.

In connection with this state of things, the following test scheme was chosen. For sampling, an iterative step-by-step scheme for checking the operation of sampling algorithms in different parts of the tree. Iterations are organized as follows:

id > 1 < 10          - шаг 1
id > 10 < 100        - шаг 10
id > 100 < 1000      - шаг 100
id > 1000 < 10000    - шаг 1000
id > 10000 < 100000  - шаг 10000
id > 100000          - шаг 100000


This allows you to track the dependence of the search and selection functions on the distribution law of nodes.

For the change functions, the scheme is slightly different. Since the change operations themselves for most algorithms are quite expensive operations, it makes no sense to check them in an iterative way (the waiting time for testing completion increases too much). Therefore, the verification method is based on making changes to one of the largest nodes, which is located at the beginning of the tree. In addition, such a test will be performed once. In order to outline the overall picture and outline the range of problems - this is quite enough.

Analysis



So, the tests are completed, the data is collected. I believe that it makes no sense to dump all the numbers that we got in the results in this article. However, they are available for download as an archive . So everyone can see them with their own eyes.

It would be much more interesting to show empirically what these results are. Let's look at what some of the graphs look like for a 100,000 node tree.

Все ниже посчитано и указанно в секундах.



Fig. 1. Entire tree selection
The following graphs show the dependence of fluctuations of the sampling functions on the search in different parts of the tree. In fact, the numbers along the ordinate axis indicate the steps discussed above.


Fig. 2. Поиск узла-родителя


Fig. 3. Search for heirs заданного узла


Fig. 4. Выбор всей ветки заданного узла


Fig. 5. Finding the full path from the root to the given node.
Next, the change functions that were performed on trees of various types are illustrated.


Fig. 6. Добавление нового узла в дерево


Fig. 7. Node move


Fig. 8. Removing the node and all its descendants from the tree

In general, in absolute figures, one can draw the following conclusions:
Adjacency List:
Knots ALL PATH BRANCH PARENT Childen ADD MOVE Remove
one hundred 0,00245 0.00016 0.00416 0.00009 0.00011 0,00059 0,00037 0.00009
1000 0,00335 0,00025 0,03579 0.00009 0.00011 0,00387 0,00037 0.00009
10,000 0.01244 0,00058 0.38146 0,00024 0,00036 0,03548 0,00081 0.00011
100,000 0.10798 0.00105 2,55379 0.00155 0,00138 0.06382 0.00119 0.13931
500,000 0.62305 0.00124 43,91373 0,00053 0,00209 0,05232 0,00077 0,00041


Nested Sets
Knots ALL PATH BRANCH PARENT Childen ADD MOVE Remove
one hundred 0,00020 0.00015 0,00020 0.00017 0.00019 0,00367 0.02285 0.00314
1000 0.00129 0,00040 0,00093 0.00017 0,00059 0,02593 0.19237 0,02619
10,000 0.01387 0.00433 0.00825 0.01771 0.00460 0.38235 1,37070 0.37219
100,000 0.17165 0,07634 0.14261 0.17218 0,09953 101,749 213,461 59.1912
500,000 0.83033 0.41670 0.62517 0.42942 0.15318 1427.96 3,712.30 1627.97


Materialized Path
Knots ALL PATH BRANCH PARENT Childen ADD MOVE Remove
one hundred 0,00020 0.00017 0,00020 0.00016 0.00019 0,00076 0,02633 0,00059
1000 0,00137 0,00069 0,00107 0.00016 0,00071 0.00136 0.22232 0.00136
10,000 0.01560 0,00608 0.01372 0,00056 0,00737 0,00679 1,44434 0.00801
100,000 0.18680 0.10466 0.17608 0,00064 0.18546 0.92136 41.5875 1,06560
500,000 0.99102 0.56412 0.59418 0,00090 0.56800 2.02149 2950.40 1.67124


Let's think about all these numbers and graphs.

Firstly, all algorithms on small amounts of data (up to 10,000 nodes inclusive) showed quite acceptable performance on all functions.

Secondly, problem operations exist, namely:
Fetching the entire branch in the AL tree. Look, this operation takes up to 2.5 seconds.

Хотелось бы отметить, что мы немного схитрили в нашем тесте. И вот каким образом. В алгоритме списков смежности (AL) мы реализовали выбор пути методом множественных JOIN'ов таблицы с собой же. Да, результат впечатляющий, особенно в сравнении с результатом выборки ветки рекурсивным способом. Но вряд ли вы выберите такой путь реализации данной функции для своего приложения. Разве что в качестве временной оптимизации. Ведь вам нужно знать максимальный уровень вложенности и не попасть под ограничение СУБД на количество JOIN'ов в одном запросе. Мы же просто провели тест.


Next, we have problems with node move operations in NS and MP algorithms starting from 10,000 nodes in the tree (over 1 second) and then things get even worse - at 100,000 nodes for MP - this figure is over 40 seconds, for NS - almost 4 minutes. At 500,000 nodes, the numbers completely go beyond the reasonable limits - almost 50 minutes for MP and over 1 hour for NS.

For NS, a similar picture develops in the remaining change operations. For 10,000 elements, the addition takes over 1.5 minutes, and for 500,000 over 23 minutes. With the removal, the same problem is almost a minute for 100,000 nodes and over 27 minutes for 500,000 nodes.

MP also feels pretty confident on quite large volumes in the operations of deleting and adding nodes. On trees with 100,000 elements, these operations occur within 1 second, which is more than a positive result. And even at 500,000 nodes, these operations occur within a few seconds.

This means that the Nested Set should be used with virtually static trees, which, if they change, are extremely rare. At the same time, it’s worthwhile to think about creating a tool that completely rebuilds the tree on demand, using the AL-scheme as a base (as our program for generating random trees does). This, as evidenced by the facts, is much faster than the routine of NS itself. Or even abandon this algorithm in favor of the Materialized Path.

Conclusion



As we were able to find out, the demand for such algorithms as the Nested Set and Materialized Path is primarily due to large amounts of data, where they can optimize some search and selection queries that will be critical for the application. Or under high loads, where query optimization is also important. In this case, we are talking about optimizing operations such as finding a path and fetching the entire branch in the Adjacency List tree. In practice, it’s also worth talking about optimizing the operations of searching for neighbors, selecting the “leaves” of the entire tree or in a branch of a given node, as well as other operations not considered here (which, in fact, are difficult for AL at the level of SQL queries).

Against the background of the results, the Nested Set is qualitatively inferior to the Materialized Path, which is quite confident in the operations of deleting and adding (and how often do you move nodes in your trees? ...). In addition, I see good prospects for optimizing this algorithm, which we will discuss in the next article.

Good luck in the development!

Это кросс-пост оригинальной статьи с моего блога