Глубоко вложенные подзапросы для обхода деревьев в MySQL - PullRequest
Новая
       32

Глубоко вложенные подзапросы для обхода деревьев в MySQL

4 голосов
/ 28 мая 2010

У меня есть таблица в моей базе данных, где я храню древовидную структуру, используя модель гибридного вложенного набора (MPTT) (модель со значениями lft и rght) и модель списка смежности (сохраняя parent_id в каждый узел). 

my_table (id, parent_id, lft, rght, alias)

Этот вопрос не относится ни к одному из аспектов дерева MPTT, но я подумал, что оставлю его на всякий случай, если у кого-нибудь есть хорошая идея о том, как использовать это.

Я хочу преобразовать путь псевдонимов в конкретный узел. Например: "users.admins.nickf" найдет узел с псевдонимом «nickf», который является дочерним по отношению к псевдониму «admin», который является дочерним по отношению к «users», который находится в корне. На (parent_id, alias).

существует уникальный индекс

Я начал с написания функции, чтобы она разделяла путь на части, а затем запрашивал базу данных один за другим: 

SELECT `id` FROM `my_table` WHERE `parent_id` IS NULL AND `alias` = 'users';-- 1
SELECT `id` FROM `my_table` WHERE `parent_id` = 1 AND `alias` = 'admins';   -- 8
SELECT `id` FROM `my_table` WHERE `parent_id` = 8 AND `alias` = 'nickf';    -- 37

Но потом я понял, что могу сделать это с помощью одного запроса, используя переменное количество вложений: 

SELECT `id` FROM `my_table` WHERE `parent_id` = (
    SELECT `id` FROM `my_table` WHERE `parent_id` = (
        SELECT `id` FROM `my_table`
        WHERE `parent_id` IS NULL AND `alias` = 'users'
    ) AND `alias`  = 'admins'
) AND `alias` = 'nickf';

Поскольку количество подзапросов зависит от количества шагов в пути, я столкнусь с проблемами, связанными с слишком большим количеством подзапросов ? (Если и есть такая вещь)

Существуют ли лучшие / более умные способы выполнения этого запроса?

Ответы [ 2 ]

3 голосов
/ 28 мая 2010

Это работает? 

select r0.id 
  from my_table as r0 
  join my_table as r1 on(r0.parent_id = r1.id) 
  join my_table as r2 on(r1.parent_id = r2.id)
 where r0.alias='nickf'
   and r1.alias='admins'
   and r2.alias='users'
   and r2.parent_id is null

Мне кажется, что вложенные подзапросы на самом деле не нужны ..

или я не прав, что-то упустил?

2 голосов
/ 11 июня 2010

Я задавался вопросом об этом сам и искал что-то, что не становилось медленнее, когда вы углублялись (имеется в виду большее количество уровней в обоих вариантах выше). Проблема, с которой я столкнулся в «моей версии», заключается в том, что она должна создавать каждый возможный путь, прежде чем он сузит результат до того, который вы на самом деле ищете ... так что я думаю, что версия lexu должна превзойти мою даже для очень большого вложения, потому что это простое соединение, но я надеюсь, что кто-то может его увидеть и хочу расширить его дальше.

Кроме того, этот способ сделать это определенно выиграл бы от хранимого процесса и / или просмотра его части 'paths' (без предложения HAVING). Возможно, с этим это лучшее решение, но я, к сожалению, пока недостаточно знаю о производительности SQL, чтобы сказать наверняка. Я могу сказать, что мой становится медленнее, так как данные (число возможных комбинаций путей) увеличиваются, но с представлением (поскольку результат кэшируется и используется для его сужения), оно кажется быстрым (самый большой набор данных, который я нашел было 370 всего, в какой-то момент я создам гораздо больший набор для тестирования.) 

SELECT node.id, GROUP_CONCAT(parent.alias
                 ORDER BY parent.lft SEPARATOR '.') AS path_name
FROM my_table AS node, my_table AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rght
GROUP BY node.id HAVING path_name = 'users.admins.nickf'
...