In complex ERP systems many entities have a hierarchical nature, when homogeneous objects are arranged in a tree of relationships 'parent — child' — this includes both the organizational structure of the enterprise (all its branches, departments, and work groups), as well as a product catalog, work sections, and the geography of sales points,…
In fact, there is hardly any , where some hierarchy does not exist as a result. But even if you are not working 'for business', you can still easily encounter hierarchical relationships. For instance, even your family tree or the floor plan of a shopping center is a similar structure.
There are many ways to store such a tree in a DBMS, but today we will focus on just one option:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- let’s not forget that FK does not imply automatic index creation, unlike PK
And while you are scrutinizing the depth of the hierarchy, it patiently awaits to see how 'inefficient' your 'naive' ways of working with such structure will turn out to be.
Let’s break down the typical tasks that arise, their implementation in SQL, and try to improve their performance.
#1. Насколько глубока кроличья нора?
Let us, for clarity, assume that this structure will reflect the subordination of departments in an organization: departments, divisions, sectors, branches, work groups,… — however you want to name them.
First, we will generate our 'tree' with 10K elements
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;Let’s start with the simplest task — finding all employees who work within a particular sector, or in hierarchical terms — finding all descendants of the node. Also, it would be nice to get the 'depth' of the descendant… All of this may be necessary, for example, for building some .
Everything would be fine if there were only a couple of descendant levels and limited to a few dozen, but if the levels exceed 5 and the descendants already number in the dozens — there could be problems. Let's look at how the traditional methods of searching "down the tree" are written (and work). But first, let's determine which nodes will be most interesting for our research.
The most “deep” subtrees:
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}
...The most “wide” subtrees:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
For these queries, we used a typical recursive JOIN.:
Clearly, with this query model, the number of iterations will match the total number of descendants (which are several dozen), and this can take quite significant resources and, consequently, time.
Let's check on the most "wide" subtree:
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; 
As we expected, we found all 30 records. But we spent 60% of the total time on this — because we also performed 30 index searches in the process. Can we do better?
Bulk reading by index
And is it necessary for each node to make a separate request to the index? It turns out, no — we can read from the index immediately by several keys in one query using = ANY(array).
And for each such group of identifiers, we can take all the IDs found in the previous step by the "nodes." This means that at each subsequent step we will be looking for all descendants at a certain level at once..
However, there's a catch: in the recursive selection, you cannot refer to itself in the nested query, and we need to filter out exactly what was found at the previous level… It turns out, making a nested query over the entire selection is not allowed, but it is possible to do so over a specific field of it. And this field can even be an array — which is what we need for utilization. ANY.
It sounds somewhat bizarre, but on the diagram — it’s all quite simple.
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$, '{}') '{}' -- exit condition for the loop - empty array
)
SELECT
unnest(id$) id
FROM
T; 
The most important point here is not even the 1.5 times gain in time, but that we accessed fewer buffers, since we have only 5 index accesses instead of 30!
An additional bonus is the fact that after the final unnest, the identifiers will remain ordered by 'levels'.
Node indicator
Another consideration that will help improve performance is that leaves cannot have children, meaning there is no need to search 'down' for them at all. In the context of our task, this means that if we have traversed the chain of departments and reached an employee, there is no point in searching further down this branch.
Let's introduce an additional -field boolean, which will immediately tell us whether this particular record in our tree is a 'node' — that is, whether it can have descendants.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 ); -- Query executed successfully: 3033 rows changed in 42 ms.
Great! It turns out that only a little over 30% of all tree elements have descendants.Now let's apply a different mechanism — joining with the recursive part through
, which will allow us to immediately access the fields of the recursive 'table', while using an aggregate function with a filter condition based on the node indicator to reduce the key set: generate_seriesWITH 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;
We managed to reduce one more index access and 
gained more than twice the volume of data read. This algorithm will be useful if you need to gather records for all elements 'up the tree', while preserving information about which original leaf (and with what metrics) triggered its inclusion in the selection — for example, to create a summary report aggregated at the nodes.
#2. Вернемся к корням
This algorithm will be helpful if you need to gather records for all "up the tree" elements while retaining information about which original leaf (and with which metrics) triggered its inclusion in the sample — for example, for generating a summary report with aggregation at the nodes.
The following should be perceived solely as a proof of concept, as the query becomes quite cumbersome. However, if it dominates your database, it’s worth considering the use of similar methods.
Let's start with a couple of simple statements:
- The same record from the database is better read only once.
- Records from the database are more efficiently read "in batches", rather than one at a time.
Now let's try to construct the query we need.
Step 1
It is obvious that at the initialization of recursion (where would we be without it!) we have to read the records of the leaves based on a set of initial identifiers:
WITH RECURSIVE tree AS (
SELECT
rec -- this is the complete record of the table
, id::text chld -- this is the "set" of the initial leaves that led here
FROM
hier rec
WHERE
id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
... If anyone finds it strange that the "set" is stored as a string instead of an array, there is a simple explanation for that. There is a built-in aggregate "concatenation" function for strings string_agg, but there isn't one for arrays. Although it's not difficult to implement it yourself. .
Step 2
group them , while retaining information about the source leaves.But here we are faced with three unpleasant issues:
"Subrecursive" parts of the query cannot contain aggregate functions with
- A reference to the recursive "table" cannot be in a nested subquery.
GROUP BY. - The query in the recursive part cannot contain CTE.
- Fortunately, all these problems are quite easy to circumvent. Let's start from the end.
CTE in the recursive part
works:
That's it do not WITH RECURSIVE tree AS ( ... UNION ALL WITH T (...) SELECT ... )
And this works — parentheses solve it!WITH RECURSIVE tree AS ( ... UNION ALL ( WITH T (...) SELECT ... ) )
A nested query to the recursive "table"Hmm… A reference to the recursive CTE cannot be in a nested query. But it can be inside the CTE! And the nested query can already refer to this CTE!
GROUP BY within recursion
It's unpleasant, but… We have a simple way to simulate GROUP BY using
DISTINCT ON and window functions! SELECT (rec).pid id , string_agg(chld::text, ',') chld FROM tree WHERE (rec).pid IS NOT NULL GROUP BY 1 -- does not work!
But this way — it works!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
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 NULLNow we see why the numeric ID was converted to text — so they could be concatenated with a comma!
Step 3
We have just a little left for the finale:
- we summarize the records of the 'sections' by the set of grouped IDs
- we match the summarized sections with the 'sets' of the source sheets
- we 'unfold' the set string using
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
