CTE vs T-SQL-Schleife zur Bestimmung der Tiefe der Objekthierarchie

Question

Ich habe eine Tabelle, bestehend aus etwa 70.000 Zeilen und zwei Spalten (VARCHAR(16)): id und parent_id.

Ich möchte eine 'Tiefe' Spalte füllen, die zeigt, wie weit ein bestimmter Datensatz vom 'root' Knoten entfernt ist.

z.B.

id,parent_id,depth 
A,NULL,0 
B,A,1 
C,A,1 
D,B,2 
E,D,3 

usw.

Ich begann durch eine Abfrage auf this answer auf eine ähnliche Frage basiert Schreiben:

WITH myCTE(id, depth) AS 
(
    SELECT id, 0 FROM objects where id = 'A' 
    UNION ALL 
    SELECT objects.id, depth + 1 FROM myCTE JOIN objects ON objects.parent_id = myCTE.id 
) 
SELECT id, depth FROM myCTE 

Mit meinem Dataset (~ 80.000 Zeilen) die über fast zwei Stunden in Anspruch nimmt auszuführen !

schrieb ich dann meine Frage als eine Schleife und bekam weit bessere Leistung:

ALTER TABLE objects ADD depth INT NULL 
DECLARE @counter int 
DECLARE @total int 
SET @counter = 0 
UPDATE objects SET depth = 0 WHERE id = 'A' 

SELECT @total = COUNT(*) FROM objects WHERE depth IS NULL 

WHILE (@total > 0) 
BEGIN 
    UPDATE objects SET depth = @counter + 1 WHERE parent_id IN (
     SELECT id FROM objects WHERE depth = @counter 
    ) 
    SELECT @total = COUNT(*) FROM objects WHERE depth IS NULL 
    SET @counter = @counter + 1 
END 

Der obige Code dauert nur ein paar Minuten (und es hat den Vorteil, die Ergebnisse zu der vorhandenen Tabelle hinzufügen)

Meine Frage ist, ob meine Ergebnisse typisch für die Verwendung eines CTE für dieses Problem sind oder ob ich etwas übersehen habe, das es erklären könnte? Indizes, vielleicht? (Ich habe gerade keine auf dem Tisch)

Answer 1

Sie benötigen einen Index über parent_id. Der rekursive Teil eines CTE verwendet immer eine Join mit verschachtelten Schleifen und ist undurchlässig Hinweise zu verbinden (Ergebnisse zu einem stack spool hinzugefügt werden und die Zeilen nacheinander in LIFO-Reihenfolge verarbeitet)

Ohne einen Index auf parent_id es braucht um die Tabelle mehrmals auf der Innenseite der verschachtelten Schleifen zu scannen. Die Leistung wird mit der Anzahl der Zeilen exponentiell abnehmen.

Ihre Abfrage ohne Rekursion kann unterschiedliche Join-Typen (Hash oder Merge) verwenden, die die Tabelle nur für jede Rekursionsstufe zweimal scannen. In diesem Fall wird höchstwahrscheinlich ein Hash hinzugefügt, da Sie keine nützlichen Indizes haben, die eine Sortierung vermeiden würden.

Answer 2

Haben Sie überlegt, den HierarchieID-Datentyp zu verwenden? Es würde dein Leben so viel einfacher machen.

CREATE TABLE Groups.tblHierarchyNode 
(
     NodeID    Int IDENTITY (0,1), 
     NodeHID    HierarchyID NOT NULL, -- DB Hierarchy ID of where I am in a tree 
     HierarchyLevel  AS NodeHID.GetLevel(), -- Numerical level of where I am in tree 
) 

Ich benutze dies für viele meiner hierarchischen Tabellen jetzt. Sie müssen ein bisschen schlauer bei der Tabellenpopulation sein, aber Berichte sind ein Kinderspiel, wie sich in der Hierarchie auf und ab bewegt, Vorfahren, Nachkommen und so weiter.