Задача отображения деревьев в MySql. Способ отображения на хранимых процедурах.

Предисловие.

Эта статья когда-то(года этак 2 назад) публиковалась на habrahabr.ru от имени моего друга, т.к. тогда ещё у меня не было аккаунта на habrahabr. Потом друг убрал её из своих статей. Не убрал, вот она. Публиковать повторно не хочется, поэтому чтобы материал не пропадал, публикую здесь. Поэтому сразу оговорюсь, что cтатья - не рекомендация к действию. Была конкретная проблема, конкретная задача, я её решил вот так. Потратил на это времени часа этак два. Если бы мне нужно было решать аналогичную задачу с нуля, то так я делать не стал бы уж точно. В итоге, получился такой добротный костыль. Привожу статью в том виде, как она была. Это одна из первых моих статей.
PS: я в курсе, что есть nested sets и другие способы организации иерархических данных. Ещё раз напомню, мы сейчас говорим о костыле.

Итак, поехали "костылять"

Очень хотелось поднять вопрос о древовидных структурах в MySql. А конкретно о выборках и хранении данных.. Пользователям Oracle и PostgresSQL живется хорошо, в этих БД есть встроенные средства выборки рекурентных данных (см. Иерархические (рекурсивные) запросы). Пользователям Mysql приходится работать уже с тем, что есть, то есть работа на стороне клиента. Поскольку эта тема не однократно поднималась, то я попробую рассказать о конкретной задаче и способе её решения.

Задача

Есть проект на php, в нем двевовидная структура реализованнная в таблице mysql catalog (id int NOT NULL,pid int NOT NULL, ...) pid - это id родителя. То есть данные хранятся в одной таблице, каждая ячейка ссылается на родительскую. Таким образом формируется все дерево. Естественно в таблице хранится куча связанных данных, описание которых я опущу, так как они на суть задачи не повлияют, а будут только мешаться. Пример такого хранения данных:

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	Каталог
2	1	Книга 1
3	1	Книга 2
4	3	Глава 1
5	3	Глава 2
6	3	Глава 3

Производится выборка данных всего дерева рекурентно на стороне клиента. Общий объем базы 500Мб, и дальше будет только расти. Поскольку ветвей и узлов много, то общее количество запросов к базе на данный момент колеблется от 300 до 1000. В результате рекурентной выборки формируется массив данных (зачем-то тоже рекурентного вида), который отдается на сьедение шаблонизатору. Задача, оптимизировать выборку так, чтобы выдергивать необходимые данные одним запросом (ну или двумя-тремя, но не так, чтобы их было так много... ) Надо сказать, что структура хранения данных менять нельзя, т.к. под нее написано куча кода. Переписывать всё - долго. И написано всё так, что никакой абстракции не подставишь.

Вариант решения

Задача в целом тривиальна. Она неоднократно решалась;. Вводятся дополнительные данные, которые используются для ограничения выборки из таблицы. Весь вопрос сводится только к тому, что это за дополнительное поле (поля). Так или иначе дополнительные данные ведут к избыточности, а значит к накладным расходам по поддержке корректности данных. В публикациях наиболее часто встречается решение с дополнительным поле типа varchar, в котором хранятся id-шники текстом, разделенные спецсимволом. По этому полю осуществляется сортировка и ограничение чем-нибудь типа like %...%. В целом решение очень хорошее, но имеет свои недостатки:

1. естественное ограничение на вложенность иерархии.
2. накладные расходы и сложности по поддержке этого поля. (в моем случае если писать скрипт занимающийся поддержкой этого поля, то он будет просто виснуть по таймауту, а значит нужно делать эти действия в cron)
3. серьезнная нагрузка на сеть, которая и является основой для постановки задачи, нагрузка не куда не делась, просто она в фоне, а сервер все-равно тормозит.
4. в случае переноса узлов дерева нужно обновлять данные этого поля.

В итоге получаем достаточно тяжелое и сложное решение. Времени на его реализацию как всегда не было. Чтобы решить все изложенные выше проблемы, необходимо действовать по другому. Во-первых, формирование дополнительных данных лучше делать там, где эти данные находятся, то есть на стороне базы данных. Во-вторых, поддержка дополнительных данных - накладная операция, поэтому лучше обновлять их каждый раз. Эта концепция реализуется следующим образом: пишется не сложная процедура, которая бы формировала данные для временной таблички tmp__index, производя рекурентный обход дерева. Вот реальный код процедуры:

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

Остановимся на минуткуи и подумаем что мы сделали и на сколько это хорошо:

1. делаем все 3-я запросами к БД
2. избавились от проблем связанных с поддержкой дополнительного поля, так как все генерится динамически
3. данная процедура не может зациклится, mysql ограничивает на глубину рекурсии
4. мы можем сами контролировать насколько глубоко нужно обойти дерево (то есть до какого уровня)
5. мы знаем о каждом элементе все, вплоть до того, на каком уровне он находится
6. вторичное исполнение процедуры на одних и тех же данных можно устранить, используя локальный кеш результата запроса.

Честно говоря, меня очень удивило, что такой функционал так легко реализуется средствами БД. Однако идем дальше, задача до конца не решена. Теперь встает вопрос - что с этим массивом делать. Варианта всего два:

1. переписать все шаблоны на новый лад.
2. сделать древовидную структуру из линейной.

Я считаю, что если есть возможность, то лучше рефакторить шаблоны для того, чтобы они понимали линейную структуру данных. Это наиболее добротный путь. Но к сожалению в моем случае легче и быстрее сделать древодиную структуру, а не корячить весь проект... Так что я сделал так: сформировал каракас дерева на основе ссылок, последовательно помещая ссылку на элемент-дитя в элемент-родитель. После формирования каркаса дерева я проходил по нему рекурентно и создавал уже дерево с реальными данными.

; На рисунке показан вид получаемого мной каркаса. Я схематично указал там название поля, но реально там хранятся только идентификаторы в виде $id=>array(...), где $id - инедтификатор элемента, а массив содержит набор ссылок на корневые элементы массива. Важно понимать, что записи с одним и тем же именем ссылаются на одно и тоже место памяти. Общий объем хранимых в памяти данных - число элементов + накладные расходы нах хранение массива ссылок. Вот код преобразования, он в внутри класса. Прошу не судить строго, писалось быстро, из-под палки:

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. {
14. foreach($curItemFrom as $id=>&$list)
15. {
16. if(!isset($this->_idToData[$id]) || !isset($this->_dataArray[ $this->_idToData[$id] ]))
17. throw new Exception('recursion build error!');
19. $curItemTo[] = $this->_dataArray[ $this->_idToData[$id] ];
20. $i = count($curItemTo)-1;
21. if(count($list))
22. {
23. $curItemTo[$i]['dir'] = array();
24. $this->_recGenTreeResult(&$list,&$curItemTo[$i]['dir']);
25. }
26. }
29. }
30. function listToTree($dataArray)
31. {
32. $this->_dataArray = &$dataArray;
33. $this->_idToData = array();
34. $parentList = array();
35. $rootIds = array();
36. // а теперь делаем рекурентную структуру для вывода
37. // сохраняем id-> num в массиве data для быстрого доступа
38. foreach ($this->_dataArray as $k=>$d)
39. $this->_idToData[$d['id']] = $k;
41. foreach ($this->_dataArray as $k=>$d)
42. {
43. // делаем соотношения $pid=>array($id, ...), чтобы потом превратить его в дерево
44. $parentList[$d['pid']][$d['id']]= array();
47. // если есть, то значит у этого товарища есть родитель ...
48. if(isset($this->_idToData[$d['pid']]))
49. {
50. // берем его родителя и делаем в него ссылку на этого товарища
51. if(isset($parentList[ $this->_dataArray[ $this->_idToData[$d['pid']] ]['pid']]))
52. if(empty($parentList[ $this->_dataArray[ $this->_idToData[$d['pid']] ]['pid']][ $d['pid'] ]))
53. $parentList[ $this->_dataArray[ $this->_idToData[$d['pid']] ]['pid']][ $d['pid'] ] = &$parentList[$d['pid']];
54. }
55. else $rootIds [$d['pid'] ] = true;
56. }
60. $result = array();
62. foreach(array_keys($rootIds) as $pid)
63. $this->_recGenTreeResult(&$parentList[$pid],&$result);
66. return $result;
70. }

* This source code was highlighted with Source Code Highlighter.

В итоге, получили вполне работоспособную штуку. В случае большой базы и глубины рекурсии данному решению тоже может быть плохо. конкретно может быть плохо mySql-серверу. я бы решал эту проблему введением кеширующей таблицы (постоянной), которая бы хранила бы результаты спуска от начала определенного элемента, и копировала бы их во временную таблицу. То есть получался бы классический кеш рекурсии, только на SQL. Это близко к методам динамического программирования. Может быть когда-нибудь дореализую, если локального кеша не хватит на стабильную работу. Хотя я думаю, что хватит...

---

ссылки на то, что почитать:

• Конференция php conf2 2008 - слайды по древовидным структурам
• хранимые процедуры,официальная документация: http://dev.mysql.com/doc/refman/5.1/en/create-procedure.html.
• курсоры, официальная документация: http://dev.mysql.com/doc/refman/5.1/en/cursors.html.
• статья про курсоры: http://habrahabr.ru/blogs/mysql/46333/.
• ссылки в php: http://php.su/learnphp/?re.
• Иерархические (рекурсивные) запросы.
• Full Hierarchy иерархические структуры в базах данных.