Głębokość rekurencyjnego potomka PostgreSQL

Muszę obliczyć głębokość potomka na podstawie jego przodka. Kiedy rekord ma object_id = parent_id = ancestor_id, jest uważany za węzeł główny (przodek). Próbowałem WITH RECURSIVEuruchomić zapytanie w PostgreSQL 9.4 .

Nie kontroluję danych ani kolumn. Schemat danych i tabeli pochodzi z zewnętrznego źródła. Stół stale rośnie . Obecnie około 30 000 rekordów dziennie. Może brakować dowolnego węzła w drzewie i w pewnym momencie zostaną one pobrane ze źródła zewnętrznego. Zazwyczaj są one pobierane w created_at DESCkolejności, ale dane są pobierane za pomocą asynchronicznych zadań w tle.

Początkowo mieliśmy rozwiązanie kodu tego problemu, ale teraz, mając ponad 5 milionów wierszy, ukończenie zajmuje prawie 30 minut.

Przykładowa definicja tabeli i dane testowe:

CREATE TABLE objects (
  id          serial NOT NULL PRIMARY KEY,
  customer_id integer NOT NULL,
  object_id   integer NOT NULL,
  parent_id   integer,
  ancestor_id integer,
  generation  integer NOT NULL DEFAULT 0
);

INSERT INTO objects(id, customer_id , object_id, parent_id, ancestor_id, generation)
VALUES (2, 1, 2, 1, 1, -1), --no parent yet
       (3, 2, 3, 3, 3, -1), --root node
       (4, 2, 4, 3, 3, -1), --depth 1
       (5, 2, 5, 4, 3, -1), --depth 2
       (6, 2, 6, 5, 3, -1), --depth 3
       (7, 1, 7, 7, 7, -1), --root node
       (8, 1, 8, 7, 7, -1), --depth 1
       (9, 1, 9, 8, 7, -1); --depth 2

Pamiętaj, że object_idto nie jest wyjątkowe, ale kombinacja (customer_id, object_id)jest wyjątkowa.
Uruchamianie takiego zapytania:

WITH RECURSIVE descendants(id, customer_id, object_id, parent_id, ancestor_id, depth) AS (
  SELECT id, customer_id, object_id, parent_id, ancestor_id, 0
  FROM objects
  WHERE object_id = parent_id

  UNION

  SELECT o.id, o.customer_id, o.object_id, o.parent_id, o.ancestor_id, d.depth + 1
  FROM objects o
  INNER JOIN descendants d ON d.parent_id = o.object_id
  WHERE
    d.id <> o.id
  AND
    d.customer_id = o.customer_id
) SELECT * FROM descendants d;

Chciałbym, aby generationkolumna została ustawiona jako obliczona głębokość. Po dodaniu nowego rekordu kolumna generacji jest ustawiona na -1. W niektórych przypadkach parent_idmoże nie zostać jeszcze wyciągnięty. Jeśli parent_idnie istnieje, powinien pozostawić kolumnę generowania ustawioną na -1.

Ostateczne dane powinny wyglądać następująco:

id | customer_id | object_id | parent_id | ancestor_id | generation
2    1             2           1           1            -1
3    2             3           3           3             0
4    2             4           3           3             1
5    2             5           4           3             2
6    2             6           5           3             3
7    1             7           7           7             0
8    1             8           7           7             1
9    1             9           8           7             2

Wynikiem zapytania powinno być zaktualizowanie kolumny generowania do właściwej głębokości.

Zacząłem pracować od odpowiedzi na to powiązane pytanie dotyczące SO .

Zapytanie, które masz, jest zasadniczo poprawne. Jedynym błędem jest druga (rekurencyjna) część CTE, w której masz:

INNER JOIN descendants d ON d.parent_id = o.object_id

Powinno być na odwrót:

INNER JOIN descendants d ON d.object_id = o.parent_id 

Chcesz połączyć obiekty z ich rodzicami (które już zostały znalezione).

Zatem można zapisać zapytanie, które oblicza głębokość (nic innego się nie zmienia, tylko formatowanie):

-- calculate generation / depth, no updates
WITH RECURSIVE descendants
  (id, customer_id, object_id, parent_id, ancestor_id, depth) AS
 AS ( SELECT id, customer_id, object_id, parent_id, ancestor_id, 0
      FROM objects
      WHERE object_id = parent_id

      UNION ALL

      SELECT o.id, o.customer_id, o.object_id, o.parent_id, o.ancestor_id, d.depth + 1
      FROM objects o
      INNER JOIN descendants d ON  d.customer_id = o.customer_id
                               AND d.object_id = o.parent_id  
      WHERE d.id <> o.id
    ) 
SELECT * 
FROM descendants d
ORDER BY id ;

W przypadku aktualizacji wystarczy zastąpić ostatni SELECT, UPDATEłącząc wynik polecenia cte, z powrotem do tabeli:

-- update nodes
WITH RECURSIVE descendants
    -- nothing changes here except
    -- ancestor_id and parent_id 
    -- which can be omitted form the select lists
    ) 
UPDATE objects o 
SET generation = d.depth 
FROM descendants d
WHERE o.id = d.id 
  AND o.generation = -1 ;          -- skip unnecessary updates

Testowany na SQLfiddle

Dodatkowe komentarze:

• ancestor_idi parent_idnie są potrzebne, aby być na liście select (przodek jest oczywiste, rodzic nieco skomplikowane, aby dowiedzieć się, dlaczego), więc można zachować je w SELECTzapytaniu jeśli chcesz, ale można bezpiecznie usunąć je z UPDATE.
• (customer_id, object_id)Wygląda na kandydata na UNIQUEograniczenia. Jeśli Twoje dane są zgodne z tym, dodaj takie ograniczenie. Połączenia wykonywane w rekurencyjnym CTE nie miałyby sensu, gdyby nie były unikalne (inaczej węzeł mógłby mieć 2 rodziców).
• jeśli dodasz to ograniczenie, (customer_id, parent_id)będzie kandydatem na FOREIGN KEYograniczenie, które REFERENCES(unikalne) (customer_id, object_id). Najprawdopodobniej nie chcesz jednak dodawać tego ograniczenia FK, ponieważ w swoim opisie dodajesz nowe wiersze, a niektóre wiersze mogą odnosić się do innych, które nie zostały jeszcze dodane.
• Z pewnością występują problemy z wydajnością zapytania, jeśli zostanie ono wykonane w dużej tabeli. Nie w pierwszym uruchomieniu, ponieważ i tak prawie cała tabela zostanie zaktualizowana. Ale za drugim razem będziesz chciał wziąć pod uwagę tylko nowe wiersze (i te, których nie dotknął pierwszy bieg) do aktualizacji. CTE w obecnej postaci będzie musiało zbudować duży wynik.
  W AND o.generation = -1końcowej aktualizacji upewni się, że wiersze, które zostały zaktualizowane w pierwszym uruchomieniu, nie zostaną ponownie zaktualizowane, ale CTE jest nadal kosztowną częścią.

Poniżej przedstawiono próbę rozwiązania tych problemów: popraw CTE, aby uwzględnić jak najmniej wierszy i użyj (customer_id, obejct_id)zamiast (id)do identyfikacji wierszy (więc idjest całkowicie usuwany z zapytania. Może być użyty jako pierwsza aktualizacja lub kolejna:

WITH RECURSIVE descendants 
  (customer_id, object_id, depth) 
 AS ( SELECT customer_id, object_id, 0
      FROM objects
      WHERE object_id = parent_id
        AND generation = -1

      UNION ALL

      SELECT o.customer_id, o.object_id, p.generation + 1
      FROM objects o
        JOIN objects p ON  p.customer_id = o.customer_id
                       AND p.object_id = o.parent_id
                       AND p.generation > -1
      WHERE o.generation = -1

      UNION ALL

      SELECT o.customer_id, o.object_id, d.depth + 1
      FROM objects o
      INNER JOIN descendants d ON  o.customer_id = d.customer_id
                               AND o.parent_id = d.object_id
      WHERE o.parent_id <> o.object_id
        AND o.generation = -1
    )
UPDATE objects o 
SET generation = d.depth 
FROM descendants d
WHERE o.customer_id = d.customer_id
  AND o.object_id = d.object_id
  AND o.generation = -1        -- this is not really needed

Zwróć uwagę, jak CTE składa się z 3 części. Pierwsze dwa są częściami stabilnymi. W pierwszej części znajdują się węzły główne, które nie były wcześniej aktualizowane i nadal generation=-1tak są, więc muszą być nowo dodanymi węzłami. Druga część zawiera elementy potomne (z generation=-1) węzłów nadrzędnych, które zostały wcześniej zaktualizowane.
Trzecia część rekurencyjna odnajduje wszystkich potomków pierwszych dwóch części, jak poprzednio.

Testowany na SQLfiddle-2

@ypercube zawiera już obszerne wyjaśnienia, więc przejdę do sedna tego, co muszę dodać.

Jeśli parent_idnie istnieje, powinien pozostawić kolumnę generowania ustawioną na -1.

Zakładam, że ma to mieć zastosowanie rekurencyjne, tzn. Reszta drzewa zawsze ma generation = -1po każdym brakującym węźle.

Jeśli brakuje (jeszcze) dowolnego węzła w drzewie, musimy znaleźć wiersze z generation = -1tym ...
... są węzłami głównymi
... lub mieć nadrzędnego generation > -1.
I stamtąd przemierzaj drzewo. Węzły podrzędne tego wyboru również muszą mieć generation = -1.

Weź jeden z generationelementów nadrzędnych zwiększony o jeden lub wróć do 0 dla węzłów głównych:

WITH RECURSIVE tree AS (
   SELECT c.customer_id, c.object_id, COALESCE(p.generation + 1, 0) AS depth
   FROM   objects      c
   LEFT   JOIN objects p ON c.customer_id = p.customer_id
                        AND c.parent_id   = p.object_id
                        AND p.generation > -1
   WHERE  c.generation = -1
   AND   (c.parent_id = c.object_id OR p.generation > -1)
       -- root node ... or parent with generation > -1

   UNION ALL
   SELECT customer_id, c.object_id, p.depth + 1
   FROM   objects c
   JOIN   tree    p USING (customer_id)
   WHERE  c.parent_id  = p.object_id
   AND    c.parent_id <> c.object_id  -- exclude root nodes
   AND    c.generation = -1           -- logically redundant, but see below!
   )
UPDATE objects o 
SET    generation = t.depth
FROM   tree t
WHERE  o.customer_id = t.customer_id
AND    o.object_id   = t.object_id;

Część nierekurencyjna jest w SELECTten sposób pojedyncza , ale logicznie równoważna dwóm związkom @ ypercube SELECT. Nie wiesz, która jest szybsza, musisz przetestować.
O wiele ważniejszy punkt dla wydajności to:

Indeks!

Jeśli w ten sposób wielokrotnie dodajesz wiersze do dużej tabeli, dodaj indeks częściowy :

CREATE INDEX objects_your_name_idx ON objects (customer_id, parent_id, object_id)
WHERE  generation = -1;

Osiągnie to więcej wydajności niż wszystkie inne dotychczas omówione ulepszenia - w przypadku powtarzających się małych dodatków do dużego stołu.

Dodałem warunek indeksu do rekurencyjnej części CTE (nawet jeśli jest to logicznie redundantne), aby pomóc planistce zapytań zrozumieć, że indeks częściowy ma zastosowanie.

Ponadto prawdopodobnie powinieneś mieć również UNIQUEograniczenie na (object_id, customer_id)wspomnianym już @ypercube. Lub, jeśli z jakiegoś powodu nie możesz narzucić wyjątkowości (dlaczego?), Dodaj zwykły indeks. Kolejność kolumn indeksu ma znaczenie, btw:

• Czy indeks złożony jest również przydatny w przypadku zapytań dotyczących pierwszego pola?