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

    Доброго времени суток.

    Очень хотелось поднять вопрос о древовидных структурах в 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 $$
    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(<id_корня>,<id_корня>,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. {
    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.


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



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


    UPD Статья написана Пуниным Николаем (nicolay.punin@gmail.com), у которого, к сожалению, пока нет инвайта.

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 16

      +5
      Может я скажу глупость,
      но почему бы не пользоваться «Nested set model» — en.wikipedia.org/wiki/Nested_set_model
        +1
        не всегда удобно…
          0
          сразу примеры. когда «не всегда»? :-)
            +1
            часто обновляемые данные?
              +1
              часто переносимые узлы?
              а чуть более конкретнее? расскажите пример задачи, объёмы данных, характер данных, причины и характер обновления данных.
              мне интересно — потому что всегда все говорят о таинственных «часто обновляемых данных», но конкретных примеров как-то нет.
              • UFO just landed and posted this here
                • UFO just landed and posted this here
          +2
          Я писал как-то набор процедур для mysql для работы с nested sets. Посмотреть можно здесь: 89.249.21.130/mysql_nested_sets.sql
          Если нужны будут пояснения — могу написать подробно.
        0
        а почему MSSQL не упомянули про встроенные средства отбора… может они и не по деревьям но все же…
        есть конструкция with 'имя курсора' as {}
          0
          зачем сложная РЕКУРСИВНАЯ процедура, если можно вполне целостность поля поддерживать и средствами триггеров.

          далее:

            0
            ёмаё
            1) естественное ограничение на вложенность иерархии.
            никто не заставляет искать по целому полю. первые N уровней (где N > 50) вполне отсекут лишнее в любой даже самой глубокой иерархии

            2) серьезнная нагрузка на сеть
            запрос выполняется на mysql-сервере. откуда у нас появился оверхед на сеть при выполнении 1 (одного) запроса?

            а пункт 4 из минусов и вовсе вторит пункту 2 (ну это вероятно для усиления трагичности). да и сам пункт вполне разруливается триггером.

            «ограничение чем-нибудь типа like %...%.»
            а вы приведите пример типовых задач, которые решаются при использовании вами дерева.
            задачи вроде: получить всех потомков выполняется за 1 быстрый запрос, получить всех предков — 2 быстрых запроса (быстрые, это значит используют индекс)
              0
              ps:
              «Времени на его реализацию как всегда не было.»
              да уж, времени на составление хука в пхп, вызывающегося при изменении стрктуры, на пару с 1 примитивным запросом (или триггера, см. выше) не было. зато было время на написание рекурсивной процедуры в 50+ строк :-) хехе
              0
              Автору крайне рекомендую почитать Managing Hierarchical Data in MySQL
                0
                Автору большое спасибо за пост! правда пришлось немного поколдовать с кодом.
                Во-первых опечатка в запросе создания временной таблицы(забыли про уровень).
                Правильный запрос такой:
                CREATE TEMPORARY TABLE tmp__index(id int,pid int ,rid int, level int);

                Во-вторых на моем дереве (глубина=3) постоянно не хватало max_sp_recursion_depth
                В коде процедуры заменил:
                IF zlevel<=0 THEN
                /** число наобум */
                SET max_sp_recursion_depth= 15;
                ELSE
                SET max_sp_recursion_depth= zlevel+1;
                END IF;

                на
                SET max_sp_recursion_depth= 15;
                и заработало.
                В-третьих, непонятно зачем делается запрос с Join select c.* from catalog as c join tmp__index as t on t.rid=c.id если можно взять сразу всё select'ом в начале процедуры и записать это во временную таблицу, а потом вернуть.
                После этих правок всё заработало. Еще раз большое спасибо!
                  0
                  Сорри, цитаты поехали.

                Only users with full accounts can post comments. Log in, please.