In komplexen ERP-Systemen haben viele Entitäten eine hierarchische Natur, wenn homogene Objekte sich zu einem Baum von Beziehungen „Vorfahr - Nachkomme“ anordnen — das ist sowohl die organisatorische Struktur des Unternehmens (all diese Filialen, Abteilungen und Arbeitsgruppen) als auch ein Produktkatalog, Tätigkeitsbereiche und die Geografie der Verkaufsstellen,…
Tatsächlich gibt es keinen einzigen , in dem nicht eine gewisse Hierarchie entstanden wäre. Aber selbst wenn Sie nicht „im Geschäft“ arbeiten, können Sie dennoch leicht mit hierarchischen Beziehungen konfrontiert werden. Plakativ gesagt, selbst Ihr Stammbaum oder der Grundriss eines Einkaufszentrums sind dieselbe Struktur.
Es gibt viele Möglichkeiten, einen solchen Baum in einer Datenbank zu speichern, aber heute konzentrieren wir uns nur auf eine Variante:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- Vergessen Sie nicht, dass FK nicht das automatische Erstellen eines Indexes impliziert, im Gegensatz zu PK
Und während Sie in die Tiefe der Hierarchie blicken, wartet sie geduldig darauf, wie [un]effektiv Ihre „naiven“ Ansätze zur Arbeit mit einer solchen Struktur sein werden.
Lassen Sie uns typische auftretende Aufgaben durchgehen, ihre Implementierung in SQL und versuchen, ihre Leistung zu verbessern.
#1. Насколько глубока кроличья нора?
Lassen Sie uns zur Klarheit annehmen, dass diese Struktur die Unterordnung der Abteilungen in der Organisationsstruktur widerspiegeln wird: Abteilungen, Divisionen, Sektoren, Filialen, Arbeitsgruppen,… egal wie Sie sie nennen wollen.
Lassen Sie uns zuerst unser „Baum“-Daten aus 10.000 Elementen generieren
INSERT INTO hier
WITH RECURSIVE T AS (
SELECT
1::integer id
, '{1}'::integer[] pids
UNION ALL
SELECT
id + 1
, pids[1:(random() * array_length(pids, 1))::integer] || (id + 1)
FROM
T
WHERE
id < 10000
)
SELECT
pids[array_length(pids, 1)] id
, pids[array_length(pids, 1) - 1] pid
FROM
T;Beginnen wir mit der einfachsten Aufgabe – alle Mitarbeiter zu finden, die innerhalb eines bestimmten Sektors arbeiten, oder in den Begriffen der Hierarchie – alle Nachkommen eines Knotens zu finden. Und es wäre auch gut, die „Tiefe“ des Nachkommens zu ermitteln… All dies könnte notwendig sein, zum Beispiel für den Aufbau einer .
Es wäre alles gut, wenn es dort nur ein paar Nachkommen auf wenigen Ebenen gäbe und die Anzahl im zweistelligen Bereich bliebe. Aber wenn es mehr als 5 Ebenen sind und die Nachkommen bereits im Dutzend sind, kann es Probleme geben. Lassen Sie uns anschauen, wie traditionelle Suchvarianten "nach unten im Baum" geschrieben (und funktionieren) werden. Aber zuerst definieren wir, welche Knoten für unsere Untersuchungen am interessantesten sein werden.
Die tiefsten Teilbäume: WITH RECURSIVE T AS ( SELECT id , pid , ARRAY[id] path FROM hier WHERE pid IS NULL UNION ALL SELECT hier.id , hier.pid , T.path || hier.id FROM T JOIN hier ON hier.pid = T.id ) TABLE T ORDER BY array_length(path, 1) DESC;
id | pid | path
---------------------------------------------
7624 | 7623 | {7615,7620,7621,7622,7623,7624}
4995 | 4994 | {4983,4985,4988,4993,4994,4995}
4991 | 4990 | {4983,4985,4988,4989,4990,4991}
... Die weitenDie tiefsten ... SELECT path[1] id , count(*) FROM T GROUP BY 1 ORDER BY 2 DESC; WITH RECURSIVE T AS ( SELECT id , pid , ARRAY[id] path FROM hier WHERE pid IS NULL UNION ALL SELECT hier.id , hier.pid , T.path || hier.id FROM T JOIN hier ON hier.pid = T.id ) TABLE T ORDER BY array_length(path, 1) DESC;
id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25Für diese Abfragen haben wir einen typischen
rekursiven JOIN verwendet. Offensichtlich wird bei diesem Abfragemodell:
die Anzahl der Iterationen mit der Gesamtanzahl der Nachkommen übereinstimmen (und es sind schließlich mehrere Dutzend), und dies kann eine beträchtliche Menge an Ressourcen und folglich Zeit in Anspruch nehmen. Überprüfen wir es im "weitesten" Teilbaum:
WITH RECURSIVE T AS ( SELECT id FROM hier WHERE id = 5300 UNION ALL SELECT hier.id FROM T JOIN hier ON hier.pid = T.id ) TABLE T;
Wie vermutet, haben wir alle 30 Datensätze gefunden. Aber wir haben dafür 60 % der gesamten Zeit aufgewendet – weil wir dabei auch 30 Suchen im Index durchgeführt haben. Geht es auch schneller? 
Massenlesungen über den Index.
Brauchen wir für jeden Knoten einen separaten Indexabfrage? Es stellt sich heraus, dass das nicht nötig ist – wir können
schon bei mehreren Schlüsseln in einem einzigen Zugriff aus dem Index lesen. = ANY(array) mit In jede solche Gruppe von Identifikatoren können wir alle auf dem vorherigen Schritt gefundenen IDs nach „Knoten“ aufnehmen. Das heißt, bei jedem folgenden Schritt werden wir.
alle Nachkommen einer bestimmten Ebene gleichzeitig suchen. Nur gibt es da ein Problem:.
bei der rekursiven Abfrage kann man sich nicht im inneren Abfrage selbst ansprechen, und wir müssen doch irgendwie nur das gefundenen auf der vorherigen Ebene filtern... Es stellt sich heraus, dass man eine verschachtelte Abfrage für die gesamte Auswahl nicht machen kann; aber für ein bestimmtes Feld geht es. Und dieses Feld kann auch ein Array sein – was wir zur Nutzung benötigen.ANY ANY.
Klingt etwas seltsam, aber in der Darstellung ist es ganz einfach.
MIT REKURSIVER CTE T ALS (
SELECT
ARRAY[id] id$
FROM
hier
WHERE
id = 5300
UNION ALL
SELECT
ARRAY(
SELECT
id
FROM
hier
WHERE
pid = ANY(T.id$)
) id$
FROM
T
WHERE
coalesce(id$, '{}') '{}' -- Austrittsbedingung für die Schleife - leeres Array
)
SELECT
unnest(id$) id
FROM
T; 
Und hier ist das Wichtigste nicht einmal der Gewinn von 1,5-fach an Zeit, sondern dass wir weniger Puffer abgezogen haben, da wir nur 5 statt 30 Zugriffe auf den Index haben!
Ein zusätzlicher Vorteil ist, dass nach dem letzten unnest die Identifikatoren in „Levels“ sortiert bleiben.
Knotenmerkmal
Der nächste Punkt, der zur Verbesserung der Leistung beitragen kann, ist dass „Blätter“ keine Kinder haben können, das heißt, dass wir für sie „nach unten“ überhaupt nichts suchen müssen. In der Formulierung unserer Aufgabe bedeutet das, dass wenn wir der Kette von Abteilungen gefolgt sind und zu einem Mitarbeiter gelangen, es keinen Sinn macht, weiter in diesem Zweig zu suchen.
Lassen Sie uns in unsere Tabelle ein zusätzliches boolean-Feld, das uns sofort sagt, ob dieser spezielle Eintrag in unserem Baum ein „Knoten“ ist – das heißt, ob er überhaupt Nachkommen haben kann.
ALTER TABLE hier
ADD COLUMN branch boolean;
UPDATE
hier T
SET
branch = TRUE
WHERE
EXISTS(
SELECT
NULL
FROM
hier
WHERE
pid = T.id
LIMIT 1
);
-- Anfrage erfolgreich ausgeführt: 3033 Zeilen in 42 ms geändert.Ausgezeichnet! Es stellt sich heraus, dass nur etwas über 30 % aller Elemente des Baums Nachkommen haben.
Jetzt wenden wir eine etwas andere Mechanik an – Verbindungen mit dem rekursiven Teil durch LATERAL, was es uns ermöglicht, sofort auf die Felder der rekursiven „Tabelle“ zuzugreifen, während wir die Aggregatfunktion mit Filterbedingungen nach Knotenmerkmal verwenden, um die Schlüsselauswahl zu reduzieren:
MIT REKURSIVER CTE T ALS (
SELECT
array_agg(id) id$
, array_agg(id) FILTER(WHERE branch) ns$
FROM
hier
WHERE
id = 5300
UNION ALL
SELECT
X.*
FROM
T
JOIN LATERAL (
SELECT
array_agg(id) id$
, array_agg(id) FILTER(WHERE branch) ns$
FROM
hier
WHERE
pid = ANY(T.ns$)
) X
ON coalesce(T.ns$, '{}') '{}'
)
SELECT
unnest(id$) id
FROM
T; 
Wir konnten einen weiteren Zugriff auf den Index einsparen und haben mehr als das Zwei- bis Dreifache an Volumen gewonnen das abgezogen wird.
#2. Вернемся к корням
Dieser Algorithmus wird nützlich sein, wenn Sie Datensätze für alle Elemente „aufwärts im Baum“ sammeln müssen, während Sie Informationen darüber bewahren, mit welchem Ursprungsblatt (und welchen Werten) es in die Auswahl gelangt ist – beispielsweise zur Erstellung eines konsolidierten Berichts mit Aggregation an Knoten.
Die folgenden Informationen sind als Proof-of-Concept zu verstehen, da die Abfrage sehr umfangreich ist. Wenn sie jedoch in Ihrer Datenbank dominiert, sollten Sie überlegen, ähnliche Methoden anzuwenden.
Lass uns mit ein paar einfachen Aussagen beginnen:
- Einen Eintrag aus der Datenbank sollte man besser nur einmal lesen.
- Einträge aus der Datenbank lässt sich effizienter als "Batch" lesen, als einzeln.
Nun versuchen wir, die benötigte Abfrage zu konstruieren.
Schritt 1
Offensichtlich müssen wir bei der Initialisierung der Rekursion (wohin auch immer sie führt!) die Einträge der Blätter anhand einer Menge von Ausgangsidentifikatoren auslesen:
WITH RECURSIVE tree AS (
SELECT
rec -- das ist der vollständige Eintrag der Tabelle
, id::text chld -- das ist das "Set" der Eingangsblätter, die hierher geführt haben
FROM
hier rec
WHERE
id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
... Falls es jemand seltsam fand, dass das "Set" als Zeichenfolge und nicht als Array gespeichert wird, gibt es dafür eine einfache Erklärung. Für Zeichenfolgen gibt es eine integrierte aggregierende "verknüpfende" Funktion string_agg, aber für Arrays gibt es keine. Obwohl es auch .
Schritt 2
Nun möchten wir eine Menge von ID der Abschnitte erhalten, die weiter ausgelesen werden müssen. Sie werden fast immer in verschiedenen Einträgen des Ausgangssatzes dupliziert, daher sollten wir sie gruppieren, wobei wir die Informationen über die Quellblätter beibehalten.
Aber hier warten drei unangenehme Probleme auf uns:
- Der "Unterrekursive" Teil der Abfrage darf keine aggregierenden Funktionen mit
GROUP BY. - enthalten. Der Zugriff auf die rekursive "Tabelle" darf sich nicht in einer verschachtelten Unterabfrage befinden.
- Die Abfrage im rekursiven Teil darf keine CTE enthalten.
Glücklicherweise lassen sich all diese Probleme recht einfach umgehen. Lassen Sie uns mit dem Ende beginnen.
CTE im rekursiven Teil
So sollte nicht funktioniert:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Und so – funktioniert es, die Klammern lösen das Problem!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Verschachtelte Abfrage zur rekursiven "Tabelle"
Hmm… Der Zugriff auf die rekursive CTE darf sich nicht in einer verschachtelten Abfrage befinden. Aber es kann innerhalb der CTE sein! Und die verschachtelte Abfrage kann bereits auf diese CTE zugreifen!
GROUP BY innerhalb der Rekursion
Unangenehm, aber… Wir haben einen einfachen Weg, wie wir GROUP BY mit Hilfe von DISTINCT ON und Fensterfunktionen simulieren können!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- funktioniert nicht!Aber so – funktioniert es!
SELECT DISTINCT ON((rec).pid)
(rec).pid id
, string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
FROM
tree
WHERE
(rec).pid IS NOT NULLJetzt sehen wir, warum die numerische ID in Text umgewandelt wurde — damit sie durch Kommas verbunden werden können!
Schritt 3
Für das Finale bleibt uns nur noch wenig übrig:
- wir lesen die Einträge der „Abschnitte“ nach einer Gruppe von IDs aus
- wir verknüpfen die ausgelesenen Abschnitte mit den „Sätzen“ der Ausgangsblätter
- wir „entfalten“ die Satz-Reihe mit Hilfe von
unnest(string_to_array(chld, ',')::integer[])
WITH RECURSIVE tree AS (
SELECT
rec
, id::text chld
FROM
hier rec
WHERE
id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
(
WITH prnt AS (
SELECT DISTINCT ON((rec).pid)
(rec).pid id
, string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
)
, nodes AS (
SELECT
rec
FROM
hier rec
WHERE
id = ANY(ARRAY(
SELECT
id
FROM
prnt
))
)
SELECT
nodes.rec
, prnt.chld
FROM
prnt
JOIN
nodes
ON (nodes.rec).id = prnt.id
)
)
SELECT
unnest(string_to_array(chld, ',')::integer[]) leaf
, (rec).*
FROM
tree; 
Quelle: habr.com
