рдЬрдЯрд┐рд▓ рдИрдЖрд░рдкреА рдкреНрд░рдгрд╛рд▓реАрдВрдордзреНрдпреЗ рдЕрдиреЗрдХ рд╕рдВрд╕реНрдерд╛рдВрдирд╛ рд╢реНрд░реЗрдгреАрдмрджреНрдз рд╕реНрд╡рд░реВрдк рдЕрд╕рддреЗрдЬреЗрд╡реНрд╣рд╛ рдПрдХрд╕рдВрдз рд╡рд╕реНрддреВ рдЖрдд рдпреЗрддрд╛рдд рдкреВрд░реНрд╡рдЬ-рд╡рдВрд╢рдЬ рд╕рдВрдмрдВрдзрд╛рдВрдЪреЗ рдЭрд╛рдб - рд╣реА рдПрдВрдЯрд░рдкреНрд░рд╛рдЗрдЭрдЪреА рд╕рдВрд╕реНрдерд╛рддреНрдордХ рд░рдЪрдирд╛ рдЖрд╣реЗ (рдпрд╛ рд╕рд░реНрд╡ рд╢рд╛рдЦрд╛, рд╡рд┐рднрд╛рдЧ рдЖрдгрд┐ рдХрд╛рд░реНрдп рдЧрдЯ), рдЖрдгрд┐ рд╡рд╕реНрддреВрдВрдЪреА рдХреЕрдЯрд▓реЙрдЧ, рдЖрдгрд┐ рдХрд╛рдорд╛рдЪреА рдХреНрд╖реЗрддреНрд░реЗ рдЖрдгрд┐ рд╡рд┐рдХреНрд░реА рдмрд┐рдВрджреВрдВрдЪреЗ рднреВрдЧреЛрд▓, ...
рдЦрд░рдВ рддрд░, рдПрдХрд╣реА рдирд╛рд╣реА
рдбреАрдмреАрдПрдордПрд╕рдордзреНрдпреЗ рдЕрд╕реЗ рдЭрд╛рдб рд╕рдВрдЪрдпрд┐рдд рдХрд░рдгреНрдпрд╛рдЪреЗ рдмрд░реЗрдЪ рдорд╛рд░реНрдЧ рдЖрд╣реЗрдд, рдкрд░рдВрддреБ рдЖрдЬ рдЖрдореНрд╣реА рдлрдХреНрдд рдПрдХрд╛ рдкрд░реНрдпрд╛рдпрд╛рд╡рд░ рд▓рдХреНрд╖ рдХреЗрдВрджреНрд░рд┐рдд рдХрд░реВ:
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
рдпрд╛ рдкреНрд░рд╢реНрдирд╛рдВрд╕рд╛рдареА рдЖрдореНрд╣реА рдард░рд╛рд╡рд┐рдХ рд╡рд╛рдкрд░рд▓реЗ рдЖрд╡рд░реНрддреА рд╕рд╛рдореАрд▓ рд╡реНрд╣рд╛:
рдЕрд░реНрдерд╛рдд, рдпрд╛ рд╡рд┐рдирдВрддреА рдореЙрдбреЗрд▓рд╕рд╣ рдкреБрдирд░рд╛рд╡реГрддреНрддреАрдЪреА рд╕рдВрдЦреНрдпрд╛ рд╡рдВрд╢рдЬрд╛рдВрдЪреНрдпрд╛ рдПрдХреВрдг рд╕рдВрдЦреНрдпреЗрд╢реА рдЬреБрд│реЗрд▓ (рдЖрдгрд┐ рддреНрдпрд╛рдкреИрдХреА рдЕрдиреЗрдХ рдбрдЭрди рдЖрд╣реЗрдд), рдЖрдгрд┐ рдпрд╛рд╕рд╛рдареА рдмрд░реАрдЪ рдорд╣рддреНрддреНрд╡рдкреВрд░реНрдг рд╕рдВрд╕рд╛рдзрдиреЗ рдЖрдгрд┐ рдкрд░рд┐рдгрд╛рдореА рд╡реЗрд│ рд▓рд╛рдЧреВ рд╢рдХрддреЛ.
рдЪрд▓рд╛ "рд╕рд░реНрд╡рд╛рдд рд░реБрдВрдж" рдЙрдкрд╡реГрдХреНрд╖ рддрдкрд╛рд╕реВрдпрд╛:
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 рд╡реЗрд│рд╛ рдЬрд┐рдВрдХрд╛, рдЖрдгрд┐ рдЖрдореНрд╣реА рдХрдореА рдмрдлрд░ рд╡рдЬрд╛ рдХреЗрд▓реЗ, рдХрд╛рд░рдг рдЖрдордЪреНрдпрд╛рдХрдбреЗ 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 рдкреЗрдХреНрд╖рд╛ рдЬрд╛рд╕реНрдд рд╡реЗрд│рд╛ рдЬрд┐рдВрдХрд▓реЗ рдкреБрд░рд╛рд╡рд╛
#реи. рдЪрд▓рд╛ рдореБрд│рд╛рдВрдХрдбреЗ рдкрд░рдд рдЬрд╛рдКрдпрд╛
рд╣реЗ рдЕрд▓реНрдЧреЛрд░рд┐рджрдо рдЙрдкрдпреБрдХреНрдд рдард░реЗрд▓ рдЬрд░ рддреБрдореНрд╣рд╛рд▓рд╛ рд╕рд░реНрд╡ рдШрдЯрдХрд╛рдВрд╕рд╛рдареА тАЬрдЭрд╛рдбрд╛рдЪреНрдпрд╛ рд╡рд░тАЭ рдиреЛрдВрджреА рдЧреЛрд│рд╛ рдХрд░рд╛рдпрдЪреНрдпрд╛ рдЕрд╕рддреАрд▓ рддрд░, рдХреЛрдгрддреНрдпрд╛ рд╕реНрддреНрд░реЛрдд рдкрддреНрд░рдХрд╛рдореБрд│реЗ (рдЖрдгрд┐ рдХреЛрдгрддреНрдпрд╛ рдирд┐рд░реНрджреЗрд╢рдХрд╛рдВрд╕рд╣) рддреЗ рдирдореБрдиреНрдпрд╛рдд рд╕рдорд╛рд╡рд┐рд╖реНрдЯ рдХреЗрд▓реЗ рдЧреЗрд▓реЗ рдпрд╛рдмрджреНрджрд▓ рдорд╛рд╣рд┐рддреА рд░рд╛рдЦреВрди рдареЗрд╡рдд рдЕрд╕реЗрд▓ - рдЙрджрд╛рд╣рд░рдгрд╛рд░реНрде, рд╕рд╛рд░рд╛рдВрд╢ рдЕрд╣рд╡рд╛рд▓ рддрдпрд╛рд░ рдХрд░рдгреНрдпрд╛рд╕рд╛рдареА рдиреЛрдбреНрд╕рдордзреНрдпреЗ рдПрдХрддреНрд░реАрдХрд░рдгрд╛рд╕рд╣.
рдкреБрдвреАрд▓ рдЧреЛрд╖реНрдЯреА рдХреЗрд╡рд│ рд╕рдВрдХрд▓реНрдкрдиреЗрдЪрд╛ рдкреБрд░рд╛рд╡рд╛ рдореНрд╣рдгреВрди рдШреНрдпрд╛рд╡реНрдпрд╛рдд, рдХрд╛рд░рдг рд╡рд┐рдирдВрддреА рдЦреВрдк рдЕрд╡рдШрдб рдЖрд╣реЗ. рдкрд░рдВрддреБ рдЬрд░ рддреЗ рддреБрдордЪреНрдпрд╛ рдбреЗрдЯрд╛рдмреЗрд╕рд╡рд░ рд╡рд░реНрдЪрд╕реНрд╡ рдЧрд╛рдЬрд╡рдд рдЕрд╕реЗрд▓ рддрд░ рддреБрдореНрд╣реА рддрддреНрд╕рдо рддрдВрддреНрд░реЗ рд╡рд╛рдкрд░рдгреНрдпрд╛рдЪрд╛ рд╡рд┐рдЪрд╛рд░ рдХреЗрд▓рд╛ рдкрд╛рд╣рд┐рдЬреЗ.
рдЪрд▓рд╛ рдХрд╛рд╣реА рд╕реЛрдкреНрдпрд╛ рд╡рд┐рдзрд╛рдирд╛рдВрд╕рд╣ рдкреНрд░рд╛рд░рдВрдн рдХрд░реВрдпрд╛:
- рдбреЗрдЯрд╛рдмреЗрд╕рдордзреВрди рд╕рдорд╛рди рд░реЗрдХреЙрд░реНрдб рдПрдХрджрд╛рдЪ рд╡рд╛рдЪрдгреЗ рдЙрддреНрддрдо.
- рдбреЗрдЯрд╛рдмреЗрд╕рдордзреВрди рд░реЗрдХреЙрд░реНрдб рдмреЕрдЪрдордзреНрдпреЗ рд╡рд╛рдЪрдгреЗ рдЕрдзрд┐рдХ рдХрд╛рд░реНрдпрдХреНрд╖рдо рдЖрд╣реЗрдПрдХрдЯреНрдпрд╛рдкреЗрдХреНрд╖рд╛.
рдЖрддрд╛ рдЖрдкрд▓реНрдпрд╛рд▓рд╛ рдЖрд╡рд╢реНрдпрдХ рдЕрд╕рд▓реЗрд▓реА рд╡рд┐рдирдВрддреА рддрдпрд╛рд░ рдХрд░рдгреНрдпрд╛рдЪрд╛ рдкреНрд░рдпрддреНрди рдХрд░реВрдпрд╛.
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 рдкрд╛рдКрд▓
рдЕрдВрддрд┐рдо рдлреЗрд░реАрд╕рд╛рдареА рдЖрдордЪреНрдпрд╛рдХрдбреЗ рдХрд╛рд╣реАрд╣реА рд╢рд┐рд▓реНрд▓рдХ рдирд╛рд╣реА:
- рдЖрдореНрд╣реА рдЧрдЯрдмрджреНрдз рдЖрдпрдбреАрдЪреНрдпрд╛ рд╕рдВрдЪрд╛рд╡рд░ рдЖрдзрд╛рд░рд┐рдд "рд╡рд┐рднрд╛рдЧ" рд░реЗрдХреЙрд░реНрдб рд╡рд╛рдЪрддреЛ
- рдЖрдореНрд╣реА рд╡рдЬрд╛ рдХреЗрд▓реЗрд▓реНрдпрд╛ рд╡рд┐рднрд╛рдЧрд╛рдВрдЪреА рддреБрд▓рдирд╛ рдореВрд│ рд╢реАрдЯреНрд╕рдЪреНрдпрд╛ "рд╕реЗрдЯ" рд╕реЛрдмрдд рдХрд░рддреЛ
- рд╡рд╛рдкрд░реВрди рд╕реЗрдЯ-рд╕реНрдЯреНрд░рд┐рдВрдЧ тАЬрд╡рд┐рд╕реНрддрд╛рд░рд┐рдд рдХрд░рд╛тАЭ
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