The task of displaying trees in MySql. Display Method on Stored Procedures

Good day.

I really wanted to raise the issue of tree structures in MySql. Specifically, about fetching and storing data ...
Oracle and PostgresSQL users have a good life, these databases have built-in tools for fetching recursive data (see Hierarchical (recursive) queries ).
Mysql users have to work with what is, that is, work on the client side.
Since this topic has not been raised once, I’ll try to talk about a specific problem and how to solve it.

Task

There is a project in php, it has a twofold structure implemented in the mysql catalog table (id int NOT NULL, pid int NOT NULL, ...)
pid is the id of the parent. That is, the data is stored in one table, each cell refers to the parent. In this way the whole tree is formed.
Naturally, a bunch of related data is stored in the table, the description of which I will omit, since they will not affect the essence of the task, but will only get in the way.

An example of such data storage:

1. CREATE TABLE catalog(
2. id INT NOT NULL PRIMARY,
3. pid INT NOT NULL,
4. someData text NOT NULL)
5. comment = "табличка с рекурентной стркутурой";

* This source code was highlighted with Source Code Highlighter.

id	pid	someData
1	0	Catalog
2	1	Book 1
3	1	Book 2
4	3	Chapter 1
5	3	Chapter 2
6	3	Chapter 3

The entire tree is sampled recursively on the client side. The total base size is 500Mb, and will only continue to grow. Since there are many branches and nodes, the total number of queries to the database currently ranges from 300 to 1000.

As a result of recursive sampling, an array of data is formed (for some reason, also of a recursive form), which is given to the template engine.
The task is to optimize the selection so as to pull out the necessary data with one request (well, or two or three, but not so that there are so many ...)

Solution option

The task as a whole is trivial. She was repeatedly decided. Additional data is entered that is used to limit the selection from the table. The whole question comes down to what kind of additional field (s) it is. One way or another, additional data leads to redundancy, which means overhead for maintaining data correctness.

In publications, the most common solution is an additional field of the varchar type, in which id-tags are stored with text separated by a special character. This field is sorted and limited to something like like% ...%.

In general, the solution is very good, but has its drawbacks:

1. natural restriction on hierarchy nesting.
2. Overhead and difficulty maintaining this field. (in my case, if you write a script that supports this field, it will just hang by timeout, which means you need to do these actions in cron)
3. a serious load on the network, which is the basis for the statement of the problem, the load didn’t go away, it’s just in the background, and the server slows down anyway.
4. in case of transfer of tree nodes, you need to update the data of this field.

As a result, we get a rather difficult and difficult decision. There was no time for its implementation, as always.

To solve all the above problems, you need to act differently. Firstly, the formation of additional data is best done where this data is located, that is, on the side of the database. Secondly, supporting additional data is an overhead operation, so it’s better to update it every time.

This concept is implemented as follows: a simple procedure is written that would generate data for the tmp__index temporary plate, making a recursive tree traversal.
Here is the actual procedure code: Starting the procedure is preceded by creating a temporary plate, and then a simple select tears out the necessary data.

1. DELIMITER $$
2. DROP PROCEDURE IF EXISTS `getIndexToTmpTable`$$
3. /**
4. main_id - идентификатор корня или метка поиска
5. search_id - идентификатор для начала поиска
6. zlevel - максимальный уровень вложенности, чтобы не упрыгать слишком глубоко,
7. - установить -1 - чтобы отключить ограничение по вложенности
8. sublevel - текущий уровень вложенности, для того чтобы складировать в базу
9. - установить 1
10. */
11. CREATE PROCEDURE `getIndexToTmpTable` (
12. in main_id INT,
13. in search_id INT,
14. in zlevel INT,
15. in sublevel INT )
16. BEGIN
17. DECLARE done INT DEFAULT 0;
18. DECLARE catalog_id INT;
19. DECLARE catalog_pid INT;
20. DECLARE cur1 CURSOR FOR select id,pid from catalog where pid=search_id;
21. DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;
22. IF sublevel<=1 THEN /** чтобы установть только раз*/
23. IF zlevel<=0 THEN
24. /** число наобум */
25. SET max_sp_recursion_depth= 15;
26. ELSE
27. SET max_sp_recursion_depth= zlevel+1;
28. END IF;
29. END IF;
30. OPEN cur1;
31. IF main_id = search_id THEN
32. /** вставим саму запись, чтобы был полный боекомплект */
33. insert into tmp__index set
34. id = main_id,
35. pid =(select pid from catalog where id=main_id limit 1),
36. rid =main_id,
37. level = sublevel-1;
38. END IF;
39. /** нужно влючить глубину рекурсии */
40. REPEAT
41. FETCH cur1 INTO catalog_id,catalog_pid;
42. IF NOT done THEN
43. /** вставим текущую найденную запись */
44. insert into tmp__index set
45. id = catalog_id,
46. pid = catalog_pid,
47. rid = main_id,
48. level = sublevel;
49. /** спустимся по ниже */
50. call getIndexToTmpTable(main_id,catalog_id,zlevel,sublevel+1);
51. END IF;
52. UNTIL done END REPEAT;
53. CLOSE cur1;
54. END$$
55. DELIMITER ;

* This source code was highlighted with Source Code Highlighter.

1. CREATE TEMPORARY TABLE tmp__index(id int,pid int ,rid int);
2. call getIndexToTmpTable(,,1,1);
3. select c.* from catalog as c join tmp__index as t on t.rid=c.id

* This source code was highlighted with Source Code Highlighter.

Let's stop for a moment and think about what we have done and how good it is:

1. we do all 3 queries to the database
2. got rid of the problems associated with supporting an additional field, since everything is dynamically generated
3. this procedure cannot loop, mysql limits the recursion depth
4. we can control how deeply we need to go around the tree (that is, to what level)
5. we know everything about every element, right down to the level at which it is
6. secondary execution of the procedure on the same data can be eliminated using the local cache of the query result.

Honestly, I was very surprised that such functionality is so easily implemented by database tools. However, we go further, the task is not completely resolved. Now the question arises - what to do with this array. There are only two options:

1. rewrite all the templates in a new way.
2. make the tree structure linear.

I believe that if possible, it is better to refactor the templates so that they understand the linear data structure. This is the most solid way. But unfortunately in my case it’s easier and faster to make a tree structure, rather than shortening the entire project ...

So I did this: I formed a tree carapace based on links, sequentially placing a link to the child element in the parent element. After the tree frame was formed, I went through it recursively and created a tree with real data.


The figure shows the view of the frame I receive. I schematically indicated the name of the field there, but in reality only identifiers are stored there in the form $ id => array (...), where $ id is the identifier of the element, and the array contains a set of links to the root elements of the array. It is important to understand that records with the same name refer to the same memory location. The total amount of data stored in memory is the number of elements + the overhead of storing an array of links.

Here is the conversion code, it is inside the class. Please do not judge strictly, it was written quickly, from under a stick:

1. protected $_idToData = null;
2. protected $_dataArray = null;
3. /**
4. * генерация рекурентно данных на основе дерева ссылок
5. * для работы заполнить дерево ссылок, массив связки с данными и массив данных
6. * $_idToData, $_data
7. *
8. * @param array& $curItemFrom
9. * @param array& $curItemTo
10. */
11. protected function _recGenTreeResult(array&$curItemFrom,array&$curItemTo)
12. {
13. foreach($curItemFrom as $id=>&$list)
14. {
15. if(!isset($this->_idToData[$id]) || !isset($this->_dataArray[ $this->_idToData[$id] ]))
16. throw new Exception('recursion build error!');
17. $curItemTo[] = $this->_dataArray[ $this->_idToData[$id] ];
18. $i = count($curItemTo)-1;
19. if(count($list))
20. {
21. $curItemTo[$i]['dir'] = array();
22. $this->_recGenTreeResult(&$list,&$curItemTo[$i]['dir']);
23. }
24. }
25. }
26. function listToTree($dataArray)
27. {
28. $this->_dataArray = &$dataArray;
29. $this->_idToData = array();
30. $parentList = array();
31. $rootIds = array();
32. // а теперь делаем рекурентную структуру для вывода
33. // сохраняем id-> num в массиве data для быстрого доступа
34. foreach ($this->_dataArray as $k=>$d)
35. $this->_idToData[$d['id']] = $k;
36. foreach ($this->_dataArray as $k=>$d)
37. {
38. // делаем соотношения $pid=>array($id, ...), чтобы потом превратить его в дерево
39. $parentList[$d['pid']][$d['id']]= array();
40. // если есть, то значит у этого товарища есть родитель ...
41. if(isset($this->_idToData[$d['pid']]))
42. {
43. // берем его родителя и делаем в него ссылку на этого товарища
44. if(isset($parentList[ $this->_dataArray[ $this->_idToData[$d['pid']] ]['pid']]))
45. if(empty($parentList[ $this->_dataArray[ $this->_idToData[$d['pid']] ]['pid']][ $d['pid'] ]))
46. $parentList[ $this->_dataArray[ $this->_idToData[$d['pid']] ]['pid']][ $d['pid'] ] = &$parentList[$d['pid']];
47. }
48. else $rootIds [$d['pid'] ] = true;
49. }
50. $result = array();
51. foreach(array_keys($rootIds) as $pid)
52. $this->_recGenTreeResult(&$parentList[$pid],&$result);
53. return $result;
54. }

* This source code was highlighted with Source Code Highlighter.

As a result, we got a quite workable thing. In the case of a large base and depth of recursion, this solution can also be bad. specifically, it can be bad for mySql server. I would solve this problem by introducing a caching table (constant) that would store the results of the descent from the beginning of a certain element and copy them to a temporary table. That is, the classic recursion cache would be obtained, only in SQL. This is close to dynamic programming techniques. Maybe someday I’ll realize it if the local cache is not enough for stable operation. Although I think that's enough ...

---

links to what to read:

• Php conf2 2008 conference - tree structure slides
• stored procedures, official documentation: http://dev.mysql.com/doc/refman/5.1/en/create-procedure.html
• cursors, official documentation: http://dev.mysql.com/doc/refman/5.1/en/cursors.html
• article about cursors: http://habrahabr.ru/blogs/mysql/46333/
• links in php: http://php.su/learnphp/?re
• Hierarchical (recursive) queries
• Full Hierarchy Database Hierarchies

UPD The article was written by Nikolai Punin ([email protected]), which, unfortunately, has no invite yet.