Можно ли написать циклический запрос, получающий последнюю запись из древа, не делая несколько запросов в цикле?

Question

[KoRNeT46RuS]

Есть таблица с полем parent_id. Связь идет один к одному. Тоесть У одной родительской записи может быть только одна дочерняя.
У меня есть идентификатор первого элемента. Можно ли одним запросом найти самого первого родителя, у которого parent_id будет null, вместо того, чтобы в цикле запрашивать в БД поиск по parent_id?

id | parent_id | title
1 null 1
2 null 2
3 1 3
4 3 4

Т.е. Есть идентификатор 4. Одним запросом получить запись, что крайний родитель 1.

Comments

[Дмитрий]

1. Recursive Common Table Expressions

2. Использовать для хранения деревьев какие нибудь варианты

Answer 1

[Сергей c0re]

-- вывод ветки дерева
WITH RECURSIVE
cte (id, title, parent_id) AS (
  SELECT     id,
             title,
             parent_id
  FROM       test
  WHERE      id = 1 -- < id узла от которого выводить
  UNION ALL
  SELECT     t.id,
             t.title,
             t.parent_id
  FROM       test t
  INNER JOIN cte
          ON t.parent_id = cte.id
)
SELECT * FROM cte;

для того чтобы идти от потомка к родителю, необходимо "развернуть" связь в ON t.parent_id = cte.id т.е. ON t.id = cte.parent_id и из полученного выбрать запись с parent_id is null

т.е. так:

-- вывод самого верхнего родителя по дочернему узлу
WITH RECURSIVE
cte (id, title, parent_id) AS (
  SELECT     id,
             title,
             parent_id
  FROM       test
  WHERE      id = 4 -- < id узла
  UNION ALL
  SELECT     t.id,
             t.title,
             t.parent_id
  FROM       test t
  INNER JOIN cte
          ON t.id = cte.parent_id
)
SELECT * FROM cte
  WHERE parent_id IS NULL;

см. пример

для MySQL 5+ можно так:

SELECT * FROM (
  SELECT  id,
          title,
          parent_id 
    FROM (SELECT * FROM test ORDER BY id DESC) test_sorted
    JOIN (select @pv := 4) initialisation -- < id узла
    WHERE find_in_set(id, @pv)
      AND length(@pv := concat(@pv, ',', COALESCE(parent_id, '')))
) t
  WHERE parent_id is null