PostgreSQL: nested sets and R-Tree
Comments enabled. I *really* need your comment
A feedback on one of my previous articles comparing adjacency list and nested sets models for PostgreSQL.
Jay writes:
In your series on adjacency lists vs nested sets, you discuss geometric types and R-Tree indexes in MySQL, but you don't discuss them when discussing the same subject with PostgreSQL, which also has geometric types and R-Tree indexing (mostly available through GiST indexes).
To make it simple I added the following line after the data insertion part of the script at Nested Sets - Postgresql:
ALTER TABLE t_hierarchy ADD COLUMN sets POLYGON; UPDATE t_hierarchy SET sets = POLYGON(BOX(POINT(-1,lft), POINT(1, rgt)));It needed to be a
POLYGONinstead of aBOXsince there is a@>(POLYGON,POLYGON)function but no@>(BOX,BOX)function, and the polygon was cast from the box to create the rectangle shape required.It outperforms the adjacency list on
all descendants; outperforms it onall ancestors(not by much); performs reasonably well onall descendants up to a certain levelon items with few descendants (e. g. 31415) and badly on items with many descendants (e. g. 42).It still completes in less than 20 seconds though, which is an improvement over 1 minute.
PostgreSQL does support R-Tree indexes indeed (through GiST interface), and they can be used to improve the efficiency of the nested sets model.
Let's create a sample table and try some of the queries that Jay proposed:
Table creation details
To make the management of the table easier, I didn't create an additional column with the geometric representation of the nested sets, but instead just defined an index on a derived expression, so that updating lft and rgt columns would be enough to update the set.
Now, let's see how these queries perform.
All descendants
SELECT SUM(LENGTH(hc.stuffing)), COUNT(*) FROM t_hierarchy hp JOIN t_hierarchy hc ON POLYGON(BOX(POINT(-1, hc.lft), POINT(1, hc.rgt))) <@ POLYGON(BOX(POINT(-1, hp.lft), POINT(1, hp.rgt))) WHERE hp.id = 42
Quite fast, 213 ms.
All ancestors
SELECT hc.id, hc.lft, hc.rgt, hc.parent FROM t_hierarchy hp JOIN t_hierarchy hc ON POLYGON(BOX(POINT(-1, hc.lft), POINT(1, hc.rgt))) @> POLYGON(BOX(POINT(-1, hp.lft), POINT(1, hp.rgt))) WHERE hp.id = 42
Extremely fast: only 10 ms.
All descendants up to a certain level
SELECT hc.id, hc.lft, hc.rgt, hc.parent
FROM t_hierarchy hp
JOIN t_hierarchy hc
ON POLYGON(BOX(POINT(-1, hc.lft), POINT(1, hc.rgt))) <@ POLYGON(BOX(POINT(-1, hp.lft), POINT(1, hp.rgt)))
WHERE hp.id = 42
AND
(
SELECT COUNT(*)
FROM t_hierarchy hcp
WHERE POLYGON(BOX(POINT(-1, hc.lft), POINT(1, hc.rgt))) <@ POLYGON(BOX(POINT(-1, hcp.lft), POINT(1, hcp.rgt)))
) -
(
SELECT COUNT(*)
FROM t_hierarchy hpp
WHERE POLYGON(BOX(POINT(-1, hp.lft), POINT(1, hp.rgt))) <@ POLYGON(BOX(POINT(-1, hpp.lft), POINT(1, hpp.rgt)))
) <= 2
This, exactly as was mentioned by Jay, is much faster than using a B-Tree index but still too slow: 20 seconds.
Analysis
The nested sets model, improved by using the R-Tree indexes, provides a way to tell if two records are in the same ancestry chain.
However, even with the R-Tree, the model provides no simple means to tell how deep is a record nested.
To check it, an R-Tree index scan should be made which would return all of the record's ancestors, the the number of the ancestors is to be compared with that of the parent node.
For a record with lots of ancestors (which was the case for the record 42 we used in the test queries), this means that thousands of records should be checked in a nested loop, out of which only a dozen will be returned.
Ironically, for the real-world models, this type of query is most often used, and used against the records with lots of descendants it is.
Usually, when hierarchical data are stored in a database, they are presented to a user in the form of a tree view. When the user opens the catalog, the first-level entries are show; when the user clicks on expand
button of an entry, all immediate children of the entry should be shown.
Since users usually start browsing from the beginning, clicking the expand buttons on the first-level or second-level entries is what happens most often. And, unfortunately, it takes the most time to execute these queries.
Adjacency list model provides a constant time solution to this problem, since fetching all immediate children requires a single index scan. This is extremely fast on showing the immediate children.
A user can also click on expand all
which should just return all children of the given entry.
However, clicking on expand all
on a high-level entry will return too many records, so a time to download them or represent them in the GUI will be much more than that required to fetch them out of the table. A properly written GUI usually limits the level of the records returned so that GUI remains responsive, which, it its turn, implies the same problem of filtering on level.
The low-level entries (for which it makes sense to implement expand all
without any limitations) can be queried for their descendants with the R-Tree query in the nested sets model or with a recursive query in the adjacency list model almost equally fast, since low-level entries contain few records.
The same applies to selecting all ancestors. Despite the fact that the nested sets model outperforms slightly the adjacency list model on this type of query, the absolute numbers are very small and the times that both queries take are almost imperceptible to the bare eye. A hierarchy is seldom more than a dozen levels deep, and fetching each ancestor even with a recursive query requires but one unique index scan per ancestor.
However, one may still be forced to use the nested tree model. This may be the way an ORM stores its data in the database; a heavily used legacy schema too old and scary to touch; or just some obscure model which mostly requires fetching all descendants fast with an occasional need to filter on the level.
Here are some methods to deal with it.
Analytic functions
Though there is no efficient way to filter all descendants on the level, there still is a way to fetch all immediate children of a record.
If we select all records within lft and rgt of a given entry and order them by lft, the first record will be the first immediate child of the entry.
All descendants of the first child will be returned before the second child and have rgt less than that of the first child.
This means that if we record the MAX(rgt) fetched so far, it will be that of the last immediate child of the entry fetched so far:
| id | lft | rgt | MAX(rgt) |
|---|---|---|---|
| 2 | 2 | 11 | 11 |
| 3 | 3 | 4 | 11 |
| 4 | 5 | 8 | 11 |
| 5 | 6 | 7 | 11 |
| 6 | 9 | 10 | 11 |
| 7 | 12 | 15 | 15 |
| 8 | 13 | 14 | 15 |
This means that each value of MAX(rgt) will correspond to exactly one immediate child; and the first entry in the recordset holding the value of MAX(rgt) will be that first child.
Several method exist to select records holding group-wise maximum in PostgreSQL. In this case, is will be best to use PostgreSQL's DISTINCT ON.
Here's the query:
SELECT DISTINCT ON (MAX(hc.rgt) OVER (ORDER BY hc.lft)) hc.id, hc.lft, hc.rgt
FROM t_hierarchy hp
JOIN t_hierarchy hc
ON hc.lft > hp.lft
AND hc.lft < hp.rgt
WHERE hp.id = 42
ORDER BY
MAX(hc.rgt) OVER (ORDER BY hc.lft), hc.lft
, which is reasonably fast (only 160 ms).
Using PostgreSQL 8.4 recursive abilities, this approach can be extended to select the descendants up to any level (provided as a parameter to the query).
Here's the query to select all children and grandchildren:
WITH RECURSIVE
q AS
(
SELECT id, lft, rgt, 1 AS lvl
FROM t_hierarchy
WHERE id = 42
UNION ALL
SELECT *
FROM (
SELECT DISTINCT ON (MAX(hc.rgt) OVER (PARTITION BY q.id ORDER BY hc.lft)) hc.id, hc.lft, hc.rgt, lvl + 1
FROM q
JOIN t_hierarchy hc
ON hc.lft > q.lft
AND hc.lft < q.rgt
WHERE lvl <= 2
ORDER BY
MAX(hc.rgt) OVER (PARTITION BY q.id ORDER BY hc.lft), hc.lft
) q2
)
SELECT *
FROM q
This is also reasonably fast, only 432 ms. It is slower than the same adjacency list query (which completes in several milliseconds), but still is much faster than R-Tree and of course the least efficient B-Tree solutions involving COUNT(*) and can ease your life if you have to deal with a nested sets model.
To be continued.
Subscribe in a reader