Calculate the Depth of a Hierarchy using Postgres recursive query

Published February 11, 2023

In this tutorial, you will learn about PostgreSQL recursive queries that use recursive common table expressions (CTEs) to generate the depth of a hierarchy.

Introduction to the PostgreSQL Recursive Query

PostgreSQL includes the WITH statement, which allows you to create auxiliary statements for use in queries. These statements are frequently referred to as common table expressions, or CTEs, and are similar to temporary tables that exist only during the query’s execution. Many situations benefit from recursive queries, such as querying hierarchical data such as product categories or family trees, employee and manager.

The syntax of a recursive CTE is illustrated below:

WITH RECURSIVE cte_name AS(
    CTE_query_definition -- non-recursive term
    UNION [ALL]
    CTE_query definion  -- recursive term
) SELECT * FROM cte_name;

A recursive CTE has three elements:

Non-recursive term: the non-recursive term is a CTE query definition that forms the base result set of the CTE structure.
Recursive term: the recursive term is one or more CTE query definitions joined with the non-recursive term using the UNION or UNION ALL operator. The recursive term references the CTE name itself.
Termination check: the recursion stops when no rows are returned from the previous iteration.

PostgreSQL executes a recursive CTE in the following sequence:

Execute the non-recursive term to create the base result set (R0).
Execute the recursive term with Ri as an input to return the result set Ri+1 as the output.
Repeat step 2 until an empty set is returned (termination check).
Return the final result set that is a UNION or UNION ALL of the result set R0, R1, … Rn.

Example: Use Recursive to calculate employee dept

In this example, we’ll take a look at how to use a recursive query to calculate the depth of nodes in an employee table in PostgreSQL.

Setting Up the Employee Table

We’ll start by setting up a simple employee table in PostgreSQL.

CREATE TABLE employees (
  id serial PRIMARY KEY,
  name varchar(100) NOT NULL,
  manager_id integer REFERENCES employees (id)
);

Next, we’ll populate the table with some sample data.

INSERT INTO employees (name, manager_id)
VALUES ('John', NULL), ('Jane', 1), ('Jim', 1), ('Jack', 2), ('Jill', 4);

The NULL value in the manager_id column indicates that the employee has no manager, i.e., they are at the top of the hierarchy.

Calculating the Depth of Nodes

With the sample data in place, we can now calculate the depth of each node in the hierarchy. We’ll use a recursive query to achieve this.

WITH RECURSIVE employee_hierarchy (id, name, manager_id, depth) AS (
  SELECT id, name, manager_id, 1
  FROM employees
  WHERE manager_id IS NULL
  UNION ALL
  SELECT e.id, e.name, e.manager_id, eh.depth + 1
  FROM employees e
  JOIN employee_hierarchy eh ON e.manager_id = eh.id
)
SELECT id, name, manager_id, depth
FROM employee_hierarchy
ORDER BY depth, id;

The query makes use of the WITH clause to define a recursive query named employee_hierarchy. The UNION ALL clause combines the results of two separate SELECT statements.

The first SELECT statement selects employees who have no manager (i.e., those at the top of the hierarchy) and sets their depth to 1.

The second SELECT statement selects all other employees and increments their depth by 1 based on the depth of their manager.

The final SELECT statement returns the results of the employee_hierarchy query.

Query Results

The results of the recursive query are as follows:

id | name  | manager_id | depth
---|-------|------------|-------
1  | John  | NULL       | 1
2  | Jane  | 1          | 2
4  | Jack  | 2          | 3
5  | Jill  | 4          | 4
3  | Jim   | 1          | 2

Conclusion

In conclusion, understanding how to use recursive queries in PostgreSQL can be a valuable tool in solving hierarchical data problems. We were able to simply calculate the depth of each node in a tables by using a recursive query, demonstrating the versatility and power of recursive queries in PostgreSQL.
Whether you’re working on a database for an organizational chart (org chart) or any other hierarchical data structure, recursive queries can be a useful tool to have in your toolkit.