EXPLAIN EXTENDED

In one of the previous articles I wrote about using hierarchical queries in MySQL:

• Hierarchical queries in MySQL

PostgreSQL has a contrib module to implement the same functionality.

However, it's not always possible to install and use contribs. Same is true for procedural languages.

Fortunately, this functionality can be implemented using a plain SQL function.

Let's create a sample table and see how it works:

CREATE TABLE t_hierarchy (
        id INT NOT NULL PRIMARY KEY,
        parent INT NOT NULL,
        value VARCHAR(50) NOT NULL
);

CREATE INDEX ix_hierarchy_parent ON t_hierarchy (parent);

BEGIN TRANSACTION;
INSERT
INTO    t_hierarchy (id, parent, value)
SELECT  s, s / 5, 'Value ' || s
FROM    generate_series(1, 1000) s;

COMMIT;

ANALYZE t_hierarchy;

This table of 1,000 rows has a hierarchical structure, with parent always being equal to id / 5.

This gives us 5 children per node.

To select a tree representation, we need to traverse the tree in the correct order: select the next sibling of a node only after the node's children had been selected.

This can be done using recursive rowset returning functions.

For each node, this function should build a list of its children interleaved with recursive calls to itself that would return the grandchildren etc.

To do this, we will join each list of nodes with a dummy rowset of INT's indicating what should we return on the current step.

If the rowset's value is 1, we return the node; if 2, we invoke the function for the node.

We will create a complex type to return from the function.

This type will contain the whole table row along with level pseudocolumn.

Here's the type and the function:

CREATE TYPE tp_hierarchy AS (node t_hierarchy, level INT);

CREATE OR REPLACE FUNCTION fn_hierarchy_connect_by(INT, INT)
RETURNS SETOF tp_hierarchy
AS
$$
        SELECT  CASE
                WHEN node = 1 THEN
                        (t_hierarchy, $2)::tp_hierarchy
                ELSE
                        fn_hierarchy_connect_by((q.t_hierarchy).id, $2 + 1)
                END
        FROM    (
                SELECT  t_hierarchy, node
                FROM    (
                        SELECT  1 AS node
                        UNION ALL
                        SELECT  2
                        ) nodes,
                        t_hierarchy
                WHERE   parent = $1
                ORDER BY
                        id, node
                ) q;
$$
LANGUAGE 'sql';

And here's what it returns:

SELECT  REPEAT('  ', (q.h).level) || ((q.h).node).id,
        ((q.h).node).parent,
        ((q.h).node).value,
        (q.h).level
FROM    (
        SELECT  fn_hierarchy_connect_by(0, 1) AS h
        ) AS q

Subquery Scan q  (cost=0.00..0.28 rows=1 width=32)
  ->  Result  (cost=0.00..0.26 rows=1 width=0)

The tree structure is just as it should be.

Note the ORDER BY clause inside the function query.

First ordering condition (id in our case) defines what Oracle calls ORDER SIBLINGS BY: that is order in which nodes of same level are returned.

Second ordering condition (node) defines that the nodes and recursive calls are always interleaved. This is required to build correct tree structure.

The filtering condition uses an index on parent, that's why this query is very fast.