Σε πολύπλοκα συστήματα ERP πολλές οντότητες έχουν ιεραρχικό χαρακτήραόταν παρατάσσονται ομοιογενή αντικείμενα δέντρο των σχέσεων προγονικών-απογόνων - αυτή είναι η οργανωτική δομή της επιχείρησης (όλα αυτά τα υποκαταστήματα, τα τμήματα και οι ομάδες εργασίας), και ο κατάλογος των προϊόντων, και οι τομείς εργασίας, και η γεωγραφία των σημείων πώλησης,...
Στην πραγματικότητα, δεν υπάρχει , όπου δεν θα υπήρχε καμία ιεραρχία ως αποτέλεσμα. Αλλά ακόμα κι αν δεν εργάζεστε «για την επιχείρηση», μπορείτε να συναντήσετε εύκολα ιεραρχικές σχέσεις. Είναι τετριμμένο, ακόμη και το οικογενειακό σας δέντρο ή η κάτοψη των χώρων σε ένα εμπορικό κέντρο είναι η ίδια δομή.
Υπάρχουν πολλοί τρόποι αποθήκευσης ενός τέτοιου δέντρου σε ένα DBMS, αλλά σήμερα θα εστιάσουμε μόνο σε μία επιλογή:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Και ενώ κοιτάτε στα βάθη της ιεραρχίας, περιμένει υπομονετικά να δει πόσο [ανα]αποτελεσματικοί θα είναι οι «αφελείς» τρόποι εργασίας σας με μια τέτοια δομή.
Ας δούμε τυπικά προβλήματα που προκύπτουν, την εφαρμογή τους σε SQL και ας προσπαθήσουμε να βελτιώσουμε την απόδοσή τους.
#1. Πόσο βαθιά είναι η τρύπα του κουνελιού;
Ας δεχθούμε, βεβαίως, ότι αυτή η δομή θα αντικατοπτρίζει την υποταγή των τμημάτων στη δομή του οργανισμού: τμήματα, τμήματα, τομείς, κλάδοι, ομάδες εργασίας... - όπως και να τα ονομάσετε.
Αρχικά, ας δημιουργήσουμε το «δέντρο» μας των 10K στοιχείων
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;Ας ξεκινήσουμε με την απλούστερη εργασία - την εύρεση όλων των εργαζομένων που εργάζονται σε έναν συγκεκριμένο τομέα ή όσον αφορά την ιεραρχία - βρείτε όλα τα παιδιά ενός κόμβου. Θα ήταν επίσης ωραίο να πάρουμε το “βάθος” του απογόνου... Όλα αυτά μπορεί να είναι απαραίτητα, για παράδειγμα, για την κατασκευή κάποιου είδους .
Όλα θα ήταν καλά αν υπάρχουν μόνο δύο επίπεδα από αυτούς τους απογόνους και ο αριθμός είναι μέσα σε μια ντουζίνα, αλλά εάν υπάρχουν περισσότερα από 5 επίπεδα και υπάρχουν ήδη δεκάδες απόγονοι, μπορεί να υπάρχουν προβλήματα. Ας δούμε πώς γράφονται (και λειτουργούν) οι παραδοσιακές επιλογές αναζήτησης κάτω από το δέντρο. Αλλά πρώτα, ας προσδιορίσουμε ποιοι κόμβοι θα είναι οι πιο ενδιαφέροντες για την έρευνά μας.
Το περισσότερο "βαθύς" υποδέντρα:
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}
...Το περισσότερο "πλατύς" υποδέντρα:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Για αυτά τα ερωτήματα χρησιμοποιήσαμε το τυπικό αναδρομικό JOIN:
Προφανώς, με αυτό το μοντέλο αιτήματος ο αριθμός των επαναλήψεων θα ταιριάζει με τον συνολικό αριθμό των απογόνων (και υπάρχουν αρκετές δεκάδες από αυτά), και αυτό μπορεί να πάρει αρκετά σημαντικούς πόρους και, ως αποτέλεσμα, χρόνο.
Ας δούμε το «πλατύτερο» υποδέντρο:
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;
Όπως ήταν αναμενόμενο, βρήκαμε και τους 30 δίσκους. Αλλά ξόδεψαν το 60% του συνολικού χρόνου σε αυτό - επειδή έκαναν επίσης 30 αναζητήσεις στο ευρετήριο. Είναι δυνατόν να κάνουμε λιγότερα;
Μαζική διόρθωση κατά ευρετήριο
Χρειάζεται να κάνουμε ξεχωριστό ερώτημα ευρετηρίου για κάθε κόμβο; Αποδεικνύεται ότι όχι - μπορούμε να διαβάσουμε από το ευρετήριο χρησιμοποιώντας πολλά πλήκτρα ταυτόχρονα σε μία κλήση μέσω = ANY(array).
Και σε κάθε τέτοια ομάδα αναγνωριστικών μπορούμε να πάρουμε όλα τα αναγνωριστικά που βρέθηκαν στο προηγούμενο βήμα ανά "κόμβους". Δηλαδή, σε κάθε επόμενο βήμα θα το κάνουμε αναζήτηση για όλους τους απογόνους ενός συγκεκριμένου επιπέδου ταυτόχρονα.
Μόνο που εδώ είναι το πρόβλημα, σε αναδρομική επιλογή, δεν μπορείτε να αποκτήσετε πρόσβαση σε ένα ένθετο ερώτημα, αλλά πρέπει με κάποιο τρόπο να επιλέξουμε μόνο ό,τι βρέθηκε στο προηγούμενο επίπεδο... Αποδεικνύεται ότι είναι αδύνατο να γίνει ένθετο ερώτημα για ολόκληρη την επιλογή, αλλά για το συγκεκριμένο πεδίο της είναι δυνατό. Και αυτό το πεδίο μπορεί επίσης να είναι ένας πίνακας - που είναι αυτό που πρέπει να χρησιμοποιήσουμε ANY.
Ακούγεται λίγο τρελό, αλλά στο διάγραμμα όλα είναι απλά.
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;
Και εδώ το πιο σημαντικό δεν είναι καν κερδίστε 1.5 φορές στο χρόνο, και ότι αφαιρέσαμε λιγότερα buffer, αφού έχουμε μόνο 5 κλήσεις στο ευρετήριο αντί για 30!
Ένα επιπλέον μπόνους είναι το γεγονός ότι μετά την τελική αφαίρεση, τα αναγνωριστικά θα παραμείνουν ταξινομημένα ανά "επίπεδα".
Σημάδι κόμβου
Η επόμενη σκέψη που θα βοηθήσει στη βελτίωση της απόδοσης είναι − Τα «φύλλα» δεν μπορούν να κάνουν παιδιά, δηλαδή για αυτούς δεν χρειάζεται καθόλου να κοιτάζουν «κάτω». Στη διατύπωση της αποστολής μας, αυτό σημαίνει ότι αν ακολουθήσαμε την αλυσίδα των τμημάτων και φτάσαμε σε έναν υπάλληλο, τότε δεν χρειάζεται να κοιτάξουμε περαιτέρω κατά μήκος αυτού του κλάδου.
Ας μπούμε στο τραπέζι μας πρόσθετος boolean-πεδίο, που θα μας πει αμέσως αν η συγκεκριμένη καταχώρηση στο δέντρο μας είναι «κόμβος» – δηλαδή αν μπορεί να έχει καθόλου απογόνους.
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 мс.Εξαιρετική! Αποδεικνύεται ότι μόνο λίγο περισσότερο από το 30% όλων των στοιχείων του δέντρου έχουν απογόνους.
Τώρα ας χρησιμοποιήσουμε έναν ελαφρώς διαφορετικό μηχανικό - συνδέσεις με το αναδρομικό τμήμα μέσω LATERAL, που θα μας επιτρέψει να έχουμε άμεση πρόσβαση στα πεδία του αναδρομικού «πίνακα» και να χρησιμοποιήσουμε μια συνάρτηση συγκεντρωτικών στοιχείων με συνθήκη φιλτραρίσματος που βασίζεται σε έναν κόμβο για να μειώσουμε το σύνολο των κλειδιών:
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;
Καταφέραμε να μειώσουμε μία ακόμη κλήση ευρετηρίου και κέρδισε περισσότερες από 2 φορές σε όγκο διορθώνω τυπογραφικά δοκίμια.
#2. Ας επιστρέψουμε στις ρίζες
Αυτός ο αλγόριθμος θα είναι χρήσιμος εάν χρειάζεται να συλλέξετε εγγραφές για όλα τα στοιχεία "πάνω στο δέντρο", διατηρώντας ταυτόχρονα πληροφορίες σχετικά με το φύλλο προέλευσης (και με ποιους δείκτες) προκάλεσε τη συμπερίληψή του στο δείγμα - για παράδειγμα, για τη δημιουργία μιας συνοπτικής αναφοράς με συνάθροιση σε κόμβους.
Αυτό που ακολουθεί θα πρέπει να ληφθεί αποκλειστικά ως απόδειξη της ιδέας, καθώς το αίτημα αποδεικνύεται πολύ δυσκίνητο. Αλλά αν κυριαρχεί στη βάση δεδομένων σας, θα πρέπει να σκεφτείτε να χρησιμοποιήσετε παρόμοιες τεχνικές.
Ας ξεκινήσουμε με μερικές απλές δηλώσεις:
- Η ίδια εγγραφή από τη βάση δεδομένων Είναι καλύτερο να το διαβάσετε μόνο μία φορά.
- Εγγραφές από τη βάση δεδομένων Είναι πιο αποτελεσματικό να διαβάζετε σε παρτίδεςπαρά μόνος.
Τώρα ας προσπαθήσουμε να κατασκευάσουμε το αίτημα που χρειαζόμαστε.
Βήμα 1
Προφανώς, κατά την αρχικοποίηση της αναδρομής (πού θα ήμασταν χωρίς αυτήν!) θα πρέπει να αφαιρέσουμε τις εγγραφές των ίδιων των φύλλων με βάση το σύνολο των αρχικών αναγνωριστικών:
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
...
Αν φάνηκε περίεργο σε κάποιον ότι το "σύνολο" αποθηκεύεται ως συμβολοσειρά και όχι ως πίνακας, τότε υπάρχει μια απλή εξήγηση για αυτό. Υπάρχει μια ενσωματωμένη λειτουργία "κόλλησης" συνάθροισης για χορδές string_agg, αλλά όχι για πίνακες. Αν και αυτή .
Βήμα 2
Τώρα θα λάβαμε ένα σύνολο αναγνωριστικών ενοτήτων που θα πρέπει να διαβάσετε περαιτέρω. Σχεδόν πάντα θα αντιγραφούν σε διαφορετικούς δίσκους του αρχικού σετ - έτσι θα κάναμε ομαδοποιήστε τα, διατηρώντας παράλληλα πληροφορίες σχετικά με τα φύλλα πηγής.
Αλλά εδώ μας περιμένουν τρία προβλήματα:
- Το "υποδρομικό" τμήμα του ερωτήματος δεν μπορεί να περιέχει συγκεντρωτικές συναρτήσεις με
GROUP BY. - Μια αναφορά σε έναν αναδρομικό "πίνακα" δεν μπορεί να βρίσκεται σε ένθετο υποερώτημα.
- Ένα αίτημα στο αναδρομικό μέρος δεν μπορεί να περιέχει CTE.
Ευτυχώς, όλα αυτά τα προβλήματα είναι αρκετά εύκολο να επιλυθούν. Ας ξεκινήσουμε από το τέλος.
CTE σε αναδρομικό μέρος
Εδώ όχι έργα:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Και έτσι λειτουργεί, οι παρενθέσεις κάνουν τη διαφορά!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Ένθετο ερώτημα σε αναδρομικό "πίνακα"
Χμ... Δεν είναι δυνατή η πρόσβαση σε ένα αναδρομικό CTE σε ένα δευτερεύον ερώτημα. Αλλά θα μπορούσε να είναι μέσα στο CTE! Και ένα ένθετο αίτημα μπορεί ήδη να έχει πρόσβαση σε αυτό το CTE!
ΟΜΑΔΑ ΑΝΑ εσωτερική αναδρομή
Είναι δυσάρεστο, αλλά... Έχουμε έναν απλό τρόπο μίμησης GROUP BY χρησιμοποιώντας DISTINCT ON και λειτουργίες παραθύρου!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Και έτσι λειτουργεί!
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Τώρα βλέπουμε γιατί το αριθμητικό αναγνωριστικό μετατράπηκε σε κείμενο - έτσι ώστε να μπορούν να ενωθούν χωρισμένα με κόμματα!
Βήμα 3
Για τον τελικό δεν μας μένει τίποτα:
- διαβάζουμε εγγραφές «τμημάτων» με βάση ένα σύνολο ομαδοποιημένων αναγνωριστικών
- Συγκρίνουμε τα αφαιρούμενα τμήματα με τα «σύνολα» των αρχικών φύλλων
- "επεκτείνετε" τη συμβολοσειρά set χρησιμοποιώντας
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;
Πηγή: www.habr.com