EXPLAIN EXTENDED

How to create fast database queries

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 POLYGON instead of a BOX since 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 on all ancestors (not by much); performs reasonably well on all descendants up to a certain level on 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

View query details

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

View query details

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

View query details

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

View query details

, 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

View query details

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.

Written by Quassnoi

March 1st, 2010 at 11:00 pm

Posted in PostgreSQL

Leave a Reply