Odpowiedź na pytanie.

Historia pytania.

Modele danych hierarchicznych tradycyjnie używają list sąsiedztwa lub zagnieżdżonych zbiorów do reprezentacji struktur drzewiastych. Chociaż listy sąsiedztwa minimalizują przechowywanie i upraszczają wstawianie, raportowanie analityczne często wymaga "materializowanych ścieżek" (np. "Root/Kategoria/Podkategoria"), aby umożliwić wydajne filtrowanie za pomocą wzorców prefiksowych. Przed SQL:1999, spłaszczanie tych hierarchii wymagało kursorów proceduralnych lub rekurencji po stronie aplikacji. Wprowadzenie rekursywnych wyrażeń tabeli wspólnej (CTE) w standardzie ANSI SQL umożliwiło deklaratywne przeszukiwanie, ale konstrukcja deterministycznych, uporządkowanych ścieżek z ograniczeniami głębokości wprowadza złożoności dotyczące zakończenia rekurencji i stabilności sortowania.

Problem.

Musisz przekształcić rekursywną listę sąsiedztwa w zdenormalizowany format, w którym każdy wiersz zawiera pełne pochodzenie przodków jako ciąg rozdzielony (np. "/A/B/C"). Rozwiązanie musi spełniać trzy ograniczenia: (1) rodzeństwo na każdym poziomie musi pojawiać się w leksykograficznym porządku wewnątrz ścieżki, (2) przeszukiwanie nie może przekroczyć określonej maksymalnej głębokości, aby zapobiec niekontrolowanym zapytaniom na źle sformatowanych danych, oraz (3) wdrożenie musi używać ściśle składni SQL ANSI bez dodatkowych rozwinięć hierarchii.

Rozwiązanie.

Rozwiązanie wykorzystuje podejście z dwustopniowym CTE. Najpierw, nie-rekursywny CTE oblicza pozycję porządkową każdego węzła wśród jego rodzeństwa przy użyciu funkcji okna. To wstępne obliczenie jest niezbędne, ponieważ ANSI SQL zabrania używania funkcji okna w rekurencyjnej części CTE, aby zapewnić monotoniczne zakończenie. Następnie, rekursywny CTE przeszukuje drzewo, łącząc nazwy węzłów i wstępnie obliczone klucze sortujące, przy jednoczesnym zastosowaniu ograniczenia głębokości i opcjonalnego wykrywania cykli w klauzuli WHERE.

WITH RECURSIVE 
OrderedNodes AS (
  -- Etap 1: Przypisz deterministyczny porządek rodzeństwu
  SELECT 
    node_id, 
    parent_id, 
    node_name,
    ROW_NUMBER() OVER (PARTITION BY parent_id ORDER BY node_name, node_id) AS sibling_order
  FROM taxonomy
),
PathBuilder AS (
  -- Część kotwicząca: Zainicjuj węzły korzeniowe
  SELECT 
    node_id,
    node_name,
    1 AS depth,
    CAST(node_name AS VARCHAR(1000)) AS materialized_path,
    CAST(sibling_order AS VARCHAR(100)) AS sort_key
  FROM OrderedNodes
  WHERE parent_id IS NULL
  
  UNION ALL
  
  -- Część rekurencyjna: Dodaj dzieci
  SELECT 
    c.node_id,
    c.node_name,
    p.depth + 1,
    p.materialized_path || '/' || c.node_name,
    p.sort_key || '.' || CAST(c.sibling_order AS VARCHAR(100))
  FROM OrderedNodes c
  INNER JOIN PathBuilder p ON c.parent_id = p.node_id
  WHERE p.depth < 5  -- Ścisłe ograniczenie głębokości
    AND p.materialized_path NOT LIKE '%/' || c.node_name || '%'  -- Zabezpieczenie przed cyklem
)
SELECT 
  node_id, 
  materialized_path,
  depth
FROM PathBuilder
ORDER BY sort_key;

Sytuacja z życia

Opis problemu.

Globalna platforma e-commerce utrzymuje taksonomię produktów z ponad 100,000 kategorii w bazie danych PostgreSQL (w trybie zgodności z ANSI SQL). Zespół marketingowy wymaga codziennego eksportu CSV dla zewnętrznej platformy reklamowej, która oczekuje w pełni kwalifikowanych ścieżek kategorii (np. "Elektronika/Komputery/Laptopy") z ściśle alfabetycznym porządkiem na każdym poziomie, aby zapewnić spójne kierowanie na odpowiednią grupę docelową. Istniejące rozwiązanie używało skryptu w Pythonie, który wykonywał zapytania N+1, co skutkowało czasem działania wynoszącym 20 minut i częstymi przekroczeniami czasu.

Rozważane różne rozwiązania.

Rozwiązanie A: Cache po stronie aplikacji z zaplanowanym odbudowaniem. Zespół rozważał materializowanie ścieżek w cache Redis za pośrednictwem zadania w tle co 6 godzin. Zalety obejmowały prostą implementację w Pythonie i zmniejszone obciążenie bazy danych w godzinach szczytu. Jednak wady to znaczna przestarzałość danych (do 6 godzin), złożoność unieważniania cache, gdy kategorie były przenoszone, oraz nadmierne zużycie pamięci dla całego drzewa.

Rozwiązanie B: Widok bazy danych z użyciem rekursywnego CTE. To podejście tworzy widok, który oblicza ścieżki na żądanie za pomocą wzorca rekursywnego CTE ANSI SQL. Zalety obejmują gwarantowaną świeżość danych (wyniki w czasie rzeczywistym), jednolite źródło prawdy oraz wykorzystanie optymalizatora zapytań bazy danych dla łączeń. Wady obejmują intensywne wykorzystanie CPU na serwerze bazy danych i ryzyko nieskończonej rekurencji, jeśli dane zawierają odniesienia cykliczne (np. kategoria przypadkowo powiązane z własnym potomkiem).

Rozwiązanie C: Kolumna materializowana z utrzymywanym wyzwalaczem. To dodałoby kolumnę materialized_path do tabeli i aktualizowało ją za pomocą wyzwalaczy przy dodawaniu, aktualizacji lub usuwaniu. Zalety obejmują niezwykle szybkie wykonanie odczytu (proste skanowanie indeksu). Wady obejmują znaczną złożoność zapisu, skomplikowaną logikę wyzwalaczy do obsługi przenosin lub zmiany nazw poddrzew oraz trudności w utrzymaniu ograniczenia porządku leksykograficznego, gdy zmieniają się nazwy rodzeństwa.

Wybrane rozwiązanie i wynik.

Zespół wybrał Rozwiązanie B (Widok Rekursywnego CTE), ponieważ obciążenie skierowane na odczyt (stosunek 100:1 odczyt-do-zapisu) korzystało na obliczeniach na żądanie bez obciążeń konserwacyjnych wyzwalaczy. Aby złagodzić ryzyko cyklu, wdrożyli sprawdzenie wzorca LIKE w klauzuli WHERE i dodali limit głębokości do 5 poziomów w oparciu o zasady biznesowe. Utworzyli również złożony indeks na (parent_id, node_name), aby zoptymalizować sortowanie funkcji okna w kotwicznym CTE. Wynik obniżył czas eksportu z 20 minut do 8 sekund, jednocześnie wykrywając i izolując 3 cykliczne odniesienia w danych dziedzicznych w trakcie fazy wprowadzania.

Co często umyka kandydatom

Dlaczego funkcje agregujące lub okna nie mogą występować w rekursywnym członie CTE i jak to wpływa na porządkowanie rodzeństwa?

Standardy ANSI SQL ograniczają rekurencyjnego człona od zawierania funkcji agregujących (jak SUM) lub funkcji okiennych (jak ROW_NUMBER), aby zapewnić, że zapytanie rekurencyjne jest monotoniczne i zapewnia osiągnięcie punktu ustalonego. Funkcje okienne wymagają materializacji i partycjonowania całego zbioru roboczego, co może naruszać semantykę strumienia wymaganą do zakończenia rekurencji i wprowadzać non-deterministykę. W konsekwencji nie możesz obliczyć porządku rodzeństwa dynamicznie w ramach rekurencji. Prawidłowe podejście to wstępne obliczenie pozycji porządkowych w osobnym non-rekurencyjnym CTE (jak pokazano w rozwiązaniu), a następnie odwołanie się do tej obliczonej kolumny w rekurencyjnym połączeniu. Kandydaci często próbują umieścić ROW_NUMBER() bezpośrednio w liście SELECT rekurencyjnej, co skutkuje błędami składniowymi lub nieprzewidywalnymi planami wykonania.

Jak radzisz sobie z odniesieniami cyklicznymi w hierarchii bez użycia proprietarnych składni wykrywania cykli, takich jak klauzula CYCLE PostgreSQL?

Czysty ANSI SQL nie zapewnia wbudowanego mechanizmu wykrywania CYCLE (chociaż SQL:2023 wprowadził klauzule CYCLE i SEARCH, nie są one jeszcze szeroko wdrożone). Aby zapobiec nieskończonej rekurencji, musisz ręcznie śledzić odwiedzone węzły. Standardową przenośną techniką jest gromadzenie rozdzielonego ciągu odwiedzonych identyfikatorów węzłów (lub tablicy, jeśli jest obsługiwana) i sprawdzanie, czy obecny node_id już istnieje w tym akumulatorze przed kontynuowaniem. Użycie predykatu takiego jak WHERE p.materialized_path NOT LIKE '%/' || c.node_id || '%' skutecznie przycina cykle, chociaż ta metoda zakłada rozsądne limity głębokości, aby zapobiec przepełnieniu długości ciągu. Alternatywnie, można użyć ciągu bitowego lub haszowanej ścieżki dla większych zestawów danych.

Co zapewnia deterministyczne porządkowanie, gdy dwa rodzeństwa mają identyczne nazwy, i dlaczego całkowite porządkowanie jest krytyczne dla materializowanych ścieżek?

Determinacja polega na ustanowieniu całkowitego porządku wśród rodzeństwa. Jeśli funkcja okna używa tylko ORDER BY node_name, a dwa rodzeństwa mają tę samą nazwę, baza danych może zwrócić je w dowolnym porządku (zdefiniowanym przez implementację), co prowadzi do non-deterministycznych ciągów ścieżek w różnych wykonaniach zapytań lub wersjach bazy danych. Ta non-deterministyczność łamie pamięć podręczną wyników zapytań, komplikuje testowanie i może powodować "fluktuacje" danych w systemach podrzędnych. Rozwiązaniem jest dodanie unikalnego elementu rozstrzygającego, zazwyczaj klucza głównego node_id, do klauzuli ORDER BY: ORDER BY node_name, node_id. To gwarantuje, że każdy węzeł rodzeństwa ma unikalną pozycję porządkową, zapewniając, że materializowana ścieżka i pomocniczy sort_key są reprodukowalne i stabilne.