In komplexen ERP-Systemen Viele Entitäten sind hierarchischer Naturwenn homogene Objekte aneinandergereiht sind Baum der Vorfahren-Nachkommen-Beziehungen - Dies ist die Organisationsstruktur des Unternehmens (alle diese Niederlassungen, Abteilungen und Arbeitsgruppen), der Warenkatalog und die Arbeitsbereiche sowie die Geographie der Verkaufsstellen.
Tatsächlich gibt es keine , wo es dadurch keine Hierarchie gäbe. Aber auch wenn Sie nicht „für das Unternehmen“ arbeiten, kann es leicht zu hierarchischen Beziehungen kommen. Es ist banal, sogar Ihr Stammbaum oder der Grundriss der Räumlichkeiten in einem Einkaufszentrum hat die gleiche Struktur.
Es gibt viele Möglichkeiten, einen solchen Baum in einem DBMS zu speichern, aber heute konzentrieren wir uns nur auf eine Option:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Und während Sie in die Tiefen der Hierarchie blicken, warten Sie geduldig darauf, wie [in]effektiv Ihre „naive“ Art und Weise, mit einer solchen Struktur zu arbeiten, sein wird.
Schauen wir uns typische auftretende Probleme, ihre Implementierung in SQL und versuchen, ihre Leistung zu verbessern.
#1. Wie tief ist das Kaninchenloch?
Nehmen wir zur Klarstellung an, dass diese Struktur die Unterordnung der Abteilungen in der Organisationsstruktur widerspiegelt: Abteilungen, Abteilungen, Sektoren, Niederlassungen, Arbeitsgruppen ... – wie auch immer Sie sie nennen.
Lassen Sie uns zunächst unseren „Baum“ aus 10 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 in einem bestimmten Sektor oder in Bezug auf die Hierarchie arbeiten – Finden Sie alle Kinder eines Knotens. Es wäre auch schön, die „Tiefe“ des Nachkommens zu erfahren... All dies kann beispielsweise notwendig sein, um etwas zu bauen .
Alles wäre in Ordnung, wenn es nur ein paar Ebenen dieser Nachkommen gäbe und die Zahl innerhalb eines Dutzends läge, aber wenn es mehr als 5 Ebenen gibt und es bereits Dutzende von Nachkommen gibt, kann es zu Problemen kommen. Schauen wir uns an, wie herkömmliche Down-the-Tree-Suchoptionen geschrieben sind (und funktionieren). Aber zunächst wollen wir bestimmen, welche Knoten für unsere Forschung am interessantesten sind.
Am meisten "tief" 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}
...Am meisten "breit" Teilbäume:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Für diese Abfragen haben wir das typische verwendet rekursiver JOIN:
Offensichtlich mit diesem Anfragemodell Die Anzahl der Iterationen entspricht der Gesamtzahl der Nachkommen (und davon gibt es mehrere Dutzend), und dies kann erhebliche Ressourcen und damit auch Zeit in Anspruch nehmen.
Schauen wir uns den „breitesten“ Teilbaum an:
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 erwartet haben wir alle 30 Datensätze gefunden. Dafür haben sie aber 60 % der Gesamtzeit aufgewendet – denn sie haben auch 30 Suchanfragen im Index durchgeführt. Ist es möglich, weniger zu tun?
Massenkorrekturlesen nach Index
Müssen wir für jeden Knoten eine separate Indexabfrage durchführen? Es stellt sich heraus, dass nein – wir können aus dem Index lesen Verwendung mehrerer Tasten gleichzeitig in einem Anruf über = ANY(array).
Und in jeder dieser Bezeichnergruppen können wir alle im vorherigen Schritt gefundenen Bezeichner als „Knoten“ verwenden. Das heißt, wir werden es bei jedem nächsten Schritt tun Suche nach allen Nachkommen einer bestimmten Ebene auf einmal.
Nur hier ist das Problem, Bei der rekursiven Auswahl können Sie in einer verschachtelten Abfrage nicht auf sich selbst zugreifen, aber wir müssen irgendwie nur das auswählen, was auf der vorherigen Ebene gefunden wurde... Es stellt sich heraus, dass es unmöglich ist, eine verschachtelte Abfrage für die gesamte Auswahl durchzuführen, aber für sein spezifisches Feld ist es möglich. Und dieses Feld kann auch ein Array sein – was wir verwenden müssen ANY.
Es klingt ein wenig verrückt, aber im Diagramm ist alles einfach.
WITH RECURSIVE T AS (
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$, '{}') <> '{}' -- условие выхода из цикла - пустой массив
)
SELECT
unnest(id$) id
FROM
T;
Und hier ist das Wichtigste nicht einmal Gewinne 1.5 Mal rechtzeitig, und dass wir weniger Puffer abgezogen haben, da wir nur 5 Aufrufe an den Index statt 30 haben!
Ein zusätzlicher Bonus ist die Tatsache, dass die Identifikatoren nach der endgültigen Verschachtelung weiterhin nach „Ebenen“ geordnet bleiben.
Knotenzeichen
Die nächste Überlegung, die zur Verbesserung der Leistung beiträgt, ist – „Blätter“ können keine Kinder haben, das heißt, für sie besteht überhaupt keine Notwendigkeit, „nach unten“ zu schauen. In der Formulierung unserer Aufgabenstellung bedeutet dies: Wenn wir der Abteilungskette gefolgt sind und einen Mitarbeiter erreicht haben, ist es nicht erforderlich, in diesem Zweig weiter zu suchen.
Lassen Sie uns in unsere Tabelle eintreten zusätzlich boolean-Feld, was uns sofort sagt, ob dieser bestimmte 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
);
-- Запрос успешно выполнен: 3033 строк изменено за 42 мс.Großartig! Es stellt sich heraus, dass nur etwas mehr als 30 % aller Baumelemente Nachkommen haben.
Lassen Sie uns nun eine etwas andere Mechanik verwenden – Verbindungen zum rekursiven Teil durch LATERAL, wodurch wir sofort auf die Felder der rekursiven „Tabelle“ zugreifen und eine Aggregatfunktion mit einer Filterbedingung basierend auf einem Knoten verwenden können, um den Schlüsselsatz zu reduzieren:
WITH RECURSIVE T AS (
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 Indexaufruf reduzieren und gewann mehr als das Zweifache an Volumen Korrekturlesen.
#2. Gehen wir zurück zu den Wurzeln
Dieser Algorithmus ist nützlich, wenn Sie Datensätze für alle Elemente „oben im Baum“ sammeln müssen und gleichzeitig Informationen darüber beibehalten müssen, welches Quellblatt (und mit welchen Indikatoren) dazu geführt hat, dass es in die Stichprobe aufgenommen wurde – beispielsweise um einen zusammenfassenden Bericht zu erstellen mit Aggregation in Knoten.
Das Folgende ist lediglich als Proof-of-Concept zu verstehen, da sich die Anfrage als sehr umständlich erweist. Wenn es jedoch Ihre Datenbank dominiert, sollten Sie über die Verwendung ähnlicher Techniken nachdenken.
Beginnen wir mit ein paar einfachen Aussagen:
- Derselbe Datensatz aus der Datenbank Es ist am besten, es nur einmal zu lesen.
- Datensätze aus der Datenbank Es ist effizienter, stapelweise einzulesenals allein.
Versuchen wir nun, die von uns benötigte Anfrage zu erstellen.
Schritt 1
Offensichtlich müssen wir bei der Initialisierung der Rekursion (was wären wir ohne sie!) die Datensätze der Blätter selbst basierend auf der Menge der Anfangsbezeichner subtrahieren:
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
...
Wenn es jemandem seltsam vorkommt, dass die „Menge“ als String und nicht als Array gespeichert wird, dann gibt es dafür eine einfache Erklärung. Es gibt eine integrierte aggregierende „Klebe“-Funktion für Strings string_agg, aber nicht für Arrays. Obwohl sie .
Schritt 2
Jetzt würden wir eine Reihe von Abschnitts-IDs erhalten, die weiter gelesen werden müssen. Fast immer werden sie in verschiedenen Datensätzen des Originalsatzes dupliziert – so würden wir es auch tun gruppieren Sie sie, während Informationen über die Quellblätter erhalten bleiben.
Aber hier erwarten uns drei Probleme:
- Der „subrekursive“ Teil der Abfrage darf keine Aggregatfunktionen enthalten
GROUP BY. - Ein Verweis auf eine rekursive „Tabelle“ darf nicht in einer verschachtelten Unterabfrage enthalten sein.
- Eine Anfrage im rekursiven Teil darf keinen CTE enthalten.
Glücklicherweise lassen sich all diese Probleme recht einfach umgehen. Fangen wir am Ende an.
CTE im rekursiven Teil
Folgendermaßen nicht funktioniert:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Und so funktioniert es, die Klammern machen den Unterschied!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Verschachtelte Abfrage für eine rekursive „Tabelle“
Hmm ... Auf einen rekursiven CTE kann in einer Unterabfrage nicht zugegriffen werden. Aber es könnte innerhalb des CTE liegen! Und eine verschachtelte Anfrage kann bereits auf diesen CTE zugreifen!
GROUP BY innerhalb der Rekursion
Es ist unangenehm, aber ... Wir haben eine einfache Möglichkeit, GROUP BY mithilfe von zu emulieren DISTINCT ON und Fensterfunktionen!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Und 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 getrennt miteinander verbunden werden konnten!
Schritt 3
Für das Finale bleibt uns nichts übrig:
- Wir lesen „Abschnitt“-Datensätze basierend auf einer Reihe gruppierter IDs
- Wir vergleichen die subtrahierten Abschnitte mit den „Sätzen“ der Originalblätter
- „erweitern“ Sie den Set-String mit
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;
Source: habr.com