Historia pytania
Model Nested Set został spopularyzowany przez Joe Celko w latach 90. jako metoda reprezentacji struktur drzewiastych w SQL bez rekurencyjnych połączeń. Dzięki przypisaniu każdemu węzłowi lewego (lft) i prawego (rgt) granicy całkowite poddrzewa można wybrać za pomocą prostych zapytań zakresowych. Jednakże, ponieważ standard nie narzuca ograniczeń integralności interwałów, równoległe masowe wstawienia lub błędy migracji z przeszłości często wprowadzają uszkodzenia, w których interwały częściowo się nakładają, niszcząc semantykę hierarchiczną. To pytanie pojawia się w scenariuszach hurtowni danych, gdzie hierarchie muszą być walidowane przed zasileniem kostek OLAP lub silników rekomendacji.
Problem
W ważnym zagnieżdżonym zestawie jakiekolwiek dwa węzły muszą być albo rozłączne (a.rgt < b.lft), albo w ścisłej relacji zawarcia (a.lft < b.lft AND a.rgt > b.rgt). Częściowe nakładanie się - gdzie a.lft < b.lft ale a.rgt znajduje się pomiędzy b.lft a b.rgt - tworzy logiczną niemożliwość, gdzie węzeł wydaje się być zarówno rodzeństwem, jak i potomkiem, łamiąc zapytania do poddrzewa. Wykrycie tych naruszeń wymaga porównania każdej pary interwałów, aby znaleźć przecięcia, które nie mają odpowiedniego zawarcia, co jest kosztowne obliczeniowo, jeśli robi się to proceduralnie.
Rozwiązanie
Stosujemy samo połączenie przy użyciu algebry interwałowej, aby zidentyfikować krzyżowania bez zawarcia. Predykat wykrywa, kiedy węzeł a zaczyna się przed węzłem b, ale kończy się wewnątrz zakresu b, co wskazuje na częściowe nakładanie się.
SELECT a.id AS violating_node_a, b.id AS violating_node_b, a.lft AS a_left, a.rgt AS a_right, b.lft AS b_left, b.rgt AS b_right FROM nested_set a JOIN nested_set b ON a.lft < b.lft -- a zaczyna się przed b AND a.rgt > b.lft -- a kończy się po rozpoczęciu b (przecięcie) AND a.rgt < b.rgt -- ale a kończy się przed końcem b (brak zawarcia) WHERE a.id < b.id; -- Unikaj symetrycznych duplikatów
To zapytanie zwraca wszystkie pary węzłów, które nielegalnie się przecinają. Aby uczynić je wykonalnym w środowiskach produkcyjnych z wieloma odczytami, złożone indeksy na (lft, rgt) i (rgt, lft) umożliwiają skany tylko na indeksach, zmniejszając złożoność z pełnych skanów tabeli O(n²) do wyszukiwań zakresowych O(n log n).
Podczas migracji taksonomii produktów detalicznych w czasie rzeczywistym z systemu IBM DB2 do hurtowni danych PostgreSQL, zespół inżynieryjny wybrał Model Nested Set, aby wspierać szybkie zapytania o kategorie do pulpitów analitycznych. Pipeline ETL obliczył wartości lft i rgt za pomocą funkcji okna w partiach, ale warunki wyścigu w API eksportującym z systemu legacy spowodowały błędy off-by-one, co zaowocowało 147 nakładającymi się interwałami kategorii. Te nakładania spowodowały podwójne liczenie produktów w raportach przychodów, zawyżając prognozowane sprzedaże o 12%.
Oceniono trzy strategie naprawcze.
Strategia 1: Walidacja proceduralna przy użyciu kursora. Funkcja PL/pgSQL iterowała przez każdy węzeł, sprawdzając rekurencyjnie nakładanie się poprzez porównanie każdego węzła z pozostałymi o wyższych wartościach lft. Chociaż koncepcyjnie prosta, ta metoda wymagała blokady na poziomie wiersza i zajmowała 38 minut na 2,3 miliona kategorii, łamiąc surowy SLA na świeżość pięciu minut dla aktualizacji zapasów. Została odrzucona z powodu nieakceptowalnego pogorszenia współbieżności.
Strategia 2: Odbudowa przez rekursywne CTE. Rozważano całkowite porzucenie modelu zestawu zagnieżdżonego i odbudowanie drzewa z listy przyległości przy użyciu rekursywnego CTE do wygenerowania nowych, poprawnych interwałów. To naprawiłoby uszkodzenie, ale wymagałoby pełnego przepisania tabeli i tymczasowego wstrzymania API katalogu, skutkując w efekcie zablokowaniem wyszukiwania produktu. Traktowałoby to również objaw zamiast identyfikować konkretne uszkodzone rekordy do audytu.
Strategia 3: Algebra interwałowa oparta na zbiorach (ANSI SQL). Zastosowaliśmy zapytanie samo-połączenia przy użyciu wyłącznie standardowych predykatów SQL. Dzięki wykorzystaniu indeksów B-drzew na kolumnach interwałów walidacja została zakończona w 4,2 sekundy, identyfikując dokładnie, które 147 par węzłów naruszyło zasady zawarcia. Pozwoliło to na kwarantannę tylko dotkniętych subkategorii do ręcznej poprawy, jednocześnie utrzymując resztę katalogu na żywo.
Wybraliśmy Strategię 3, ponieważ zapewniła precyzyjne operacje bez blokowania zapisujących lub wymagania czasu przestoju. Rezultatem była czysta taksonomia, gdzie granice interwałów tworzyły ścisłe supersetki, przywracając integralność referencyjną i zapewniając, że późniejsze aktualizacje zgodne z ACID nie mogłyby wprowadzić nowych nakładań się z powodu dodanych ograniczeń bazy danych.
Jak odróżniasz między ważną relacją zawarcia rodzic-potomek a nieprawidłowym częściowym nakładaniem się, gdy piszesz predykat łączenia?
Kandydaci często mylą przecięcie z zawarciem. Piszą a.lft < b.lft AND a.rgt > b.lft (co tylko sprawdza przecięcie) i mylnie uważają, że wykrywa to naruszenia. Krytyczny szczegół to ekskluzywność punktu końcowego: dla ścisłego zawarcia prawa granica rodzica musi przekraczać prawą granicę dziecka (a.rgt > b.rgt). Częściowe nakładanie występuje konkretnie wtedy, gdy a.lft < b.lft AND a.rgt > b.lft AND a.rgt < b.rgt. Początkujący często pomijają trzeci warunek, co powoduje, że zapytanie zwraca fałszywie pozytywne wyniki dla ważnych par rodzic-potomek. Ponadto zapominają wykluczyć pary własne (a.id != b.id) lub obsłużyć symetryczne duplikaty poprzez egzekwowanie a.id < b.id, co skutkuje redundantnymi raportami naruszeń.
Dlaczego węzeł może wydawać się nie mieć nakładań, a mimo to być osierocony od korzenia, i jak to wykryć korzystając tylko z operacji zbiorowych?
Osierocony węzeł istnieje, gdy żaden pojedynczy wiersz nie zawiera całego jego interwału (lft, rgt), co oznacza, że nie ma ścieżki do korzenia. Kandydaci często próbują rozwiązać to przy pomocy LEFT JOIN szukającego rodziców NULL, ale to nie odróżnia prawidłowego węzła głównego (który nie powinien mieć rodzica) od prawdziwych osieroconych. Poprawne podejście wykorzystuje NOT EXISTS z wykluczeniem globalnego korzenia:
SELECT c.id FROM nested_set c WHERE NOT EXISTS ( SELECT 1 FROM nested_set p WHERE p.lft < c.lft AND p.rgt > c.rgt ) AND c.lft != (SELECT MIN(lft) FROM nested_set);
Szczególnym przypadkiem, który pomijają początkujący, jest scenariusz z wieloma korzeniami: jeśli tabela przypadkowo zawiera dwa oddzielne drzewa, węzeł z drugim najmniejszym lft może wydawać się nie mieć rodzica, jeśli tylko sprawdzamy minimalne lft. Zapytanie musi wyraźnie zidentyfikować pojedynczy korzeń (minimalne lft) i wykluczyć go; w przeciwnym razie fałszywie oznaczają drugi korzeń jako osierocony.
Jak wykryłbyś naruszenie wielorodzinne - gdzie węzeł jest zawarty przez dwóch oddzielnych przodków, którzy nie są w relacji hierarchicznej - używając wyłącznie ANSI SQL bez funkcji okna?
To różni się od wykrywania nakładań, ponieważ dwóch przodków jest oddzielnych (ważnym rodzeństwem), a mimo to obaj nieprawidłowo zawierają ten sam węzeł potomny. To narusza własność drzewa (jednego rodzica), ale nie tworzy nakładania interwałowego między przodkami. Kandydaci często próbują GROUP BY child_id HAVING COUNT(*) > 1 na wszystkich przodkach, ale to nie działa, ponieważ ważny głęboki węzeł naturalnie ma wielu przodków (dziadków itd.). Rozwiązanie wymaga zidentyfikowania najbliższego rodzica: przodka z maksymalną wartością lft, która nadal jest mniejsza niż lft dziecka.
SELECT c.id AS child_id FROM nested_set c JOIN nested_set p ON p.lft < c.lft AND p.rgt > c.rgt WHERE NOT EXISTS ( SELECT 1 FROM nested_set p2 WHERE p2.lft > p.lft AND p2.rgt < p.rgt AND p2.lft < c.lft AND p2.rgt > c.rgt ) GROUP BY c.id HAVING COUNT(*) > 1;
Podzapytanie filtruje najbliższych rodziców, zapewniając, że nie istnieje żaden węzeł pośredni między kandydatem a dzieckiem. Początkujący pomijają tę logikę "najbliższego przodka", zamiast tego zliczając wszystkich kontenerów i błędnie oznaczając każdy głęboki węzeł jako naruszenie.