Выведите все подкатегории раздела каталога на любой глубине вложенности с помощью рекурсивного запроса

ЗадачаSeniorРедко

Проверила команда СопроводОбновлено

Короткий ответ

Напишите WITH RECURSIVE из двух частей. Якорь выбирает сам раздел, рекурсивный шаг присоединяет к найденным строкам их детей по parent_id, пока новых строк не останется. По дороге копите уровень и путь в массиве, в конце сортируйте по этому массиву. Добавьте массив пройденных id: проверка по нему остановит рекурсию, если в данных есть цикл.

Почему этот вопрос задают

Деревья хранят во многих базах: категории, оргструктуру, комментарии. Senior здесь показывает, что знает устройство рекурсивного запроса и заранее думает о порядке строк и плохих данных.

Условие задачи

В магазине электроники дерево каталога лежит в таблице categories(id, parent_id, name), у разделов верхнего уровня parent_id пустой. Выведите раздел «Компьютеры» и все его подкатегории на любой глубине: имя, уровень (у самого раздела 1) и путь от верха дерева через знак «>». За каждой категорией идут ее потомки, соседние категории — по алфавиту.

idparent_idname
1NULLКомпьютеры
21Ноутбуки
31Комплектующие
42Игровые ноутбуки
52Ультрабуки
63Видеокарты
73Процессоры
8NULLТелефоны
98Смартфоны
108Аксессуары

Как подойти к решению

  1. Опишите якорь: выберите строку самого раздела и задайте ей уровень 1
  2. Присоедините в рекурсивной части детей к уже найденным строкам по parent_id
  3. Копите по дороге уровень, путь из имен и массив пройденных id
  4. Отсекайте строку, чей id уже есть в массиве пройденных, иначе цикл в данных сделает рекурсию бесконечной
  5. Отсортируйте результат по массиву пути, чтобы потомки шли сразу за родителем

Решение

Якорь дает одну строку, каждый шаг добавляет следующий уровень, и рекурсия кончается, когда новых детей нет. Массив пути сравнивается поэлементно, поэтому ветка «Комплектующие» целиком идет раньше ветки «Ноутбуки». Условие c.id <> ALL (t.ids) на чистом дереве ничего не меняет и защищает от цикла.

SQL
WITH RECURSIVE tree AS (
  SELECT id, name, 1 AS level, ARRAY[id] AS ids, ARRAY[name] AS path
  FROM categories
  WHERE id = 1
  UNION ALL
  SELECT c.id, c.name, t.level + 1, t.ids || c.id, t.path || c.name
  FROM categories c
  JOIN tree t ON c.parent_id = t.id
  WHERE c.id <> ALL (t.ids)
)
SELECT name, level, array_to_string(path, ' > ') AS full_path
FROM tree
ORDER BY path;
Вывод
       name       | level |                full_path
------------------+-------+------------------------------------------
 Компьютеры       |     1 | Компьютеры
 Комплектующие    |     2 | Компьютеры > Комплектующие
 Видеокарты       |     3 | Компьютеры > Комплектующие > Видеокарты
 Процессоры       |     3 | Компьютеры > Комплектующие > Процессоры
 Ноутбуки         |     2 | Компьютеры > Ноутбуки
 Игровые ноутбуки |     3 | Компьютеры > Ноутбуки > Игровые ноутбуки
 Ультрабуки       |     3 | Компьютеры > Ноутбуки > Ультрабуки
(7 rows)

Что спросят следом

  • Как сделать то же встроенными средствами PostgreSQL 14 и новее?

  • Как найти путь от категории вверх до корня?

  • В каталоге миллион категорий, и дерево читают на каждой странице. Что сделаете?

Доступно по подписке

Ответы на эти вопросы

Частые ошибки

  • «Порядок строк и так будет правильный, рекурсия идет по дереву»

    Без ORDER BY порядок не гарантирован. На деле PostgreSQL выдает строки по уровням, в ширину. Соберите путь в массив и сортируйте по нему

  • «Напишу UNION вместо UNION ALL, и от цикла это защитит»

    UNION отбрасывает только полностью одинаковые строки. Когда в строке копится уровень или путь, при цикле каждая строка новая, и запрос не остановится. Проверяйте пройденные id явно

  • «Отсортирую по level, потом по имени»

    Так строки встанут по уровням, и потомки оторвутся от родителей. Порядок обхода дает только сортировка по полному пути

  • «Склею путь в строку и отсортирую по тексту»

    Сортировка текста зависит от правил сравнения базы: в части локалей пробелы и знаки при первом сравнении не учитываются. Массив сравнивается поэлементно, и ветки не перемешаются

Сигналы для интервьюера

Сильный ответ

Сам считает, сколько шагов сделает рекурсия на этих данных, и сверяет число строк в ответе с размером ветки

Тревожный сигнал

Собирает дерево тремя LEFT JOIN на фиксированную глубину и переходит к рекурсии только после подсказки

Красный флаг

Готов вытаскивать уровни по одному запросу в цикле приложения и не видит, сколько обращений к базе это даст

Как еще могут спросить

  • Как обойти древовидную структуру в SQL с помощью WITH RECURSIVE?
  • Выведите всех потомков узла дерева, которое хранится через parent_id
  • Как работает рекурсивный CTE и когда он останавливается?
  • Как получить всю иерархию категорий одним запросом?

Похожие вопросы

ЗадачаJuniorЧасто

Найдите сотрудников, которые получают больше своего руководителя

Соедините таблицу employees саму с собой: псевдоним e для сотрудника, m для руководителя, условие m.id = e.manager_id. Затем оставьте строки, где e.salary > m.salary. Директор без руководителя выпадет на соединении, и это верно: сравнивать его не с кем. Псевдонимы называйте по ролям, тогда их трудно перепутать.

  • JOIN
  • самосоединение
250
ЗадачаMiddleЧасто

Выведите всех операторов поддержки с числом закрытых обращений, включая тех, у кого закрытых нет

Возьмите операторов левой таблицей и присоедините обращения через LEFT JOIN, а фильтр status = 'closed' поставьте в ON. Тогда оператор без закрытых обращений останется в выборке со строкой из NULL справа. Считайте count(t.id): он пропускает NULL и дает 0. count(*) посчитал бы эту пустую строку и вернул 1.

  • LEFT JOIN
  • COUNT
303
ЗнаниеMiddleЧасто

Как прочитать план EXPLAIN ANALYZE и найти в нем узел, на который уходит время?

План читают от вложенных узлов к верхнему: каждый узел получает строки от дочерних. Время в actual time включает время детей, поэтому собственное время узла — его время минус время дочерних узлов. Если узел запускался несколько раз, умножьте время на loops. Ищите узел с самым большим собственным временем и сверяйте оценку строк с фактом.

  • EXPLAIN
  • оптимизация запросов
263
ЗнаниеSeniorИногда

Чем схема «звезда» отличается от «снежинки» и как выбрать гранулярность таблицы фактов?

В «звезде» таблица фактов окружена плоскими измерениями: от продажи до категории товара один JOIN. В «снежинке» измерения нормализованы, категория вынесена в свою таблицу, и тот же отчет требует двух соединений. Гранулярность — это то, что означает одна строка факта. Объявите ее до выбора мер и берите самую мелкую из источника, например позицию чека.

  • проектирование схемы
  • хранилище данных
140

Частые вопросы по теме

Короткие ответы на частые вопросы по этой теме.

Нет, WITH RECURSIVE встречается и на middle как продвинутая тема: оргструктура и вложенные комментарии есть во многих проектах. От senior ждут большего, чем синтаксис: порядка обхода, защиты от цикла и мыслей о том, как еще хранить дерево.

Держите в голове три части: якорь, UNION ALL и шаг, который ссылается на сам CTE. Напишите по памяти обход оргструктуры вниз от руководителя и вверх от сотрудника. Так на собеседовании вы не перепутаете направление соединения.

Обычный CTE считается один раз, как именованный подзапрос. Рекурсивный повторяет вторую часть: каждый шаг видит только строки прошлого шага и добавляет новые, пока шаг не вернет пустой результат.

Общие вопросы на интервью

Общий вопросС опытомЧасто

Почему вы хотите работать у нас?

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

  • мотивация
  • о компании
290
Общий вопросБез опытаЧасто

Какие у вас сильные стороны?

Хватит двух-трех сильных сторон, которые нужны на этой работе, если к каждой есть пример: что сделали и какой был результат. Берите качества из текста вакансии, а не из списка «ответственный, коммуникабельный». Без опыта примеры ищите в учебе, практике и подработке. Говорите спокойно, без лишней скромности и без хвастовства.

  • сильные стороны
  • без опыта
276
Общий вопросБез опытаЧасто

Кем вы видите себя через 5 лет?

Расскажите, какие задачи хотите решать через несколько лет и чему для этого научитесь. Свяжите план с тем, что дает эта компания, и покажите первый шаг, который уже сделали. Точную должность называть не обязательно. Важнее, чтобы план был реальным и вел через эту работу, а не мимо нее.

  • мотивация
  • карьерные планы
289
ИсторияС опытомЧасто

Расскажите о конфликте с коллегой: из-за чего он возник и как вы его решили?

Расскажите один реальный конфликт по рабочему вопросу: из-за чего разошлись, чего хотела каждая сторона и как вы договорились. Говорите спокойно, без оценок коллеги. Покажите, что вы искали решение, где-то уступили и сохранили рабочие отношения. Закончите результатом и тем, что теперь делаете, чтобы похожий спор не повторился.

  • конфликты
  • работа в команде
252
ИсторияС опытомЧасто

Каким профессиональным достижением вы гордитесь больше всего?

Назовите одно достижение, близкое к задачам новой работы, и расскажите его как историю: какая была проблема, что сделали лично вы и что изменилось в цифрах. Сильнее всего звучит результат, который держится и после вас: новый порядок работы, правило, схема. Если результат общий, прямо скажите, какая часть в нем ваша.

  • достижения
  • результат в цифрах
276
Общий вопросБез опытаЧасто

Опыта работы еще нет, а интервьюер просит рассказать о себе: что вы скажете?

Начните с того, кто вы сейчас и на какую работу пришли. Вместо стажа расскажите об учебе, практике и подработке, которые похожи на задачи вакансии, и назовите один результат с цифрой. Закончите тем, почему хотите начать карьеру именно здесь. Уложитесь в одну-две минуты и не пересказывайте резюме по порядку.

  • о себе
  • без опыта
244

Вопросы руководителю на интервью

ИсторияРуководительЧасто

Как вы делегируете задачи: что отдаете команде, а что оставляете себе?

Назовите свое правило: что вы отдаете команде и что оставляете себе, и покажите его на одной задаче. Расскажите, кому и почему передали, какие полномочия и рамки дали, как проверяли без мелкого контроля. Закончите честным итогом: что получилось хуже или медленнее, чем у вас, и что вы выиграли.

  • делегирование
  • команда
255
КейсРуководительЧасто

Два сотрудника вашей команды месяц не разговаривают друг с другом, и общий отчет уже сорвал срок — что сделаете?

Поговорите сначала с каждым по отдельности: что случилось, с чего началось и что мешает работать. Потом соберите обоих вместе и обсуждайте работу: кто за какие данные и шаги отвечает. За такой ссорой часто стоит размытая ответственность. Запишите договоренности, назовите новый срок для сорванного отчета и через пару недель проверьте, что все работает.

  • конфликт
  • ответственность
242
ИсторияРуководительЧасто

Расскажите о сотруднике, которого вы вырастили: каким он пришел и чего добился?

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

  • развитие сотрудников
  • наставничество
303
ИсторияРуководительЧасто

Расскажите о цели, которую ваша команда не выполнила: когда вы это поняли и что сделали?

Назовите цель с цифрой и честный итог. Главное в ответе — момент, когда вы поняли, что цель срывается, и по какой цифре это увидели. Дальше расскажите, кому и когда сказали, что пересобрали, чтобы спасти главное, и какой один вывод сделали для следующего плана.

  • цели
  • провал
241
Общий вопросРуководительЧасто

Как вы измеряете результат своей команды?

Назовите два-три показателя, которые отражают то, ради чего существует ваша команда, и их текущие цифры. Добавьте показатель качества, который не дает гнаться за одним числом. Скажите, как часто смотрите на цифры, кто их видит и какое решение вы приняли по ним в последний раз.

  • показатели
  • цели
216
ИсторияРуководительЧасто

Расскажите, как вы разложили цель компании на задачи для своей команды

Возьмите одну цель компании с цифрой и сроком и покажите, как вы ее разбили: на какие части, по какому признаку, какие личные цели получил каждый сотрудник. Расскажите, как следили за ходом и что меняли по дороге. Закончите итогом план-факт честно, даже если цель выполнена не целиком.

  • цели
  • планирование
227