PostgreSQL Recursive Queries for Hierarchies: Trees, Access Scopes and Cycles

To read a hierarchy stored as parent_id columns in PostgreSQL, use WITH RECURSIVE: an anchor query selects the starting row, and a recursive step joins the table to the rows found so far, until no new rows appear.

Hierarchies are everywhere in business software, and they often decide who may see what. PCB Dashboard, a platform I work on, is designed around a pollution control board’s structure — a state head office, zonal offices, regional offices and, below them, the industries they regulate — and every user’s access is scoped to their part of that tree. This article uses a small version of that structure to show the queries, a planner trap that appears at realistic sizes, and how a cycle in the data turns into an access-control bug.

Every query, plan and result below was run on PostgreSQL 14.18 on 25 October 2026.

The table: one parent per row

The simplest way to store a tree is an adjacency list: every row points at its parent.

CREATE TABLE offices (
  id        bigint PRIMARY KEY,
  parent_id bigint REFERENCES offices (id),
  kind      text   NOT NULL CHECK (kind IN ('state', 'zone', 'region')),
  name      text   NOT NULL,
  CHECK (parent_id IS DISTINCT FROM id)
);

CREATE TABLE industries (
  id        bigint PRIMARY KEY,
  office_id bigint NOT NULL REFERENCES offices (id),
  name      text   NOT NULL
);

CREATE INDEX ON offices (parent_id);
CREATE INDEX ON industries (office_id);

Walk down: everything under one node

WITH RECURSIVE subtree AS (
  SELECT id, parent_id, name, 0 AS depth, ARRAY[name] AS path
  FROM offices
  WHERE id = 2                                   -- the anchor: where the walk starts
  UNION ALL
  SELECT o.id, o.parent_id, o.name, s.depth + 1, s.path || o.name
  FROM offices o
  JOIN subtree s ON o.parent_id = s.id           -- the recursive step: children of rows found so far
)
SELECT id, depth, array_to_string(path, ' > ') AS path
FROM subtree
ORDER BY path;

 id | depth |         path
----+-------+-----------------------
  2 |     0 | North zone
  4 |     1 | North zone > Region A
  5 |     1 | North zone > Region B

How it runs:

1. The anchor (the query before UNION ALL) runs once and returns the starting row.
2. The recursive step runs against the rows produced by the previous round only, here finding their children.
3. Rounds repeat until a round produces no rows. In a tree, that happens when you reach the leaves.

UNION ALL keeps every row the recursive step produces. UNION would also remove duplicates, which costs a comparison on every round and hides problems you would rather see — such as the cycle later in this article. Use UNION ALL unless you need deduplication. depth is useful for indenting a tree in a user interface, and sorting by path lists each node directly after its parent.

Walk up: breadcrumbs

To go from a node to the root, join the other way round — each round finds the parent of the previous row:

WITH RECURSIVE up AS (
  SELECT id, parent_id, name, 0 AS distance FROM offices WHERE id = 5
  UNION ALL
  SELECT o.id, o.parent_id, o.name, up.distance + 1
  FROM offices o
  JOIN up ON o.id = up.parent_id
)
SELECT name FROM up ORDER BY distance DESC;   -- Head office, North zone, Region B

Scope access with the tree

An officer attached to an office may see the industries under that office and every office below it:

SELECT i.name, o.name AS office
FROM industries i
JOIN offices o ON o.id = i.office_id
WHERE i.office_id IN (
  WITH RECURSIVE scope AS (
    SELECT id FROM offices WHERE id = 2
    UNION ALL
    SELECT o.id FROM offices o JOIN scope s ON o.parent_id = s.id
  )
  SELECT id FROM scope
)
ORDER BY i.name;

This is correct, and on small data it is fast. On larger data it has a trap.

The planner can’t see inside a recursive CTE

To test it at a realistic size, I filled the tables with 1 head office, 10 zones, 100 regions and 125,000 industries spread evenly over the regions, with the indexes above.

PostgreSQL cannot know in advance how many rows a recursive CTE will produce, so it guesses. For a single region’s scope it estimated 1,001 rows when the scope actually contained 1 office. Planning for a thousand offices, it chose to read all 125,000 industries and hash-join them — the index on office_id went unused:

The fix is to resolve the scope to a list of office ids first — once per request, or cached per user — and pass it as an array parameter. With node-postgres:

import pg from "pg";

const pool = new pg.Pool();

/** Every office id at or below `officeId`. Resolve once per request, or cache it per user. */
async function officeScope(officeId) {
  const { rows } = await pool.query(
    `WITH RECURSIVE scope AS (
       SELECT id FROM offices WHERE id = $1
       UNION ALL
       SELECT o.id FROM offices o JOIN scope s ON o.parent_id = s.id
     )
     SELECT id FROM scope`,
    [officeId],
  );
  return rows.map((row) => row.id);
}

/** Filter by a concrete array of ids, so the planner can use the index on office_id. */
async function industriesInScope(officeIds, { limit = 50 } = {}) {
  const { rows } = await pool.query(
    "SELECT id, name FROM industries WHERE office_id = ANY ($1::bigint[]) ORDER BY id LIMIT $2",
    [officeIds, limit],
  );
  return rows;
}

node-postgres returns bigint columns as strings, which is fine here because the ids go straight back into the next query. Office hierarchies change rarely, so a resolved scope is a good thing to cache — for example in Redis, keyed by user, and cleared when the hierarchy changes (how to clear such keys without blocking Redis).

Planner estimates differ between PostgreSQL versions and data, so check your own queries with EXPLAIN (ANALYZE) on realistic data.

Cycles: when a data bug becomes a permission bug

Suppose a bad update makes the head office report to one of its own regions:

UPDATE offices SET parent_id = 4 WHERE id = 1;

The head office is now a child of Region A, so the North zone’s scope query walks down into it — and from there into the South zone and its regions. A North-zone officer can suddenly see industries elsewhere in the state.

A depth limit (WHERE s.depth < 20 in the recursive step) stops the query from running forever, but hides the problem: in the test it returned 40 rows of repeats instead of an error. PostgreSQL 14 added a CYCLE clause that marks the repeat instead:

WITH RECURSIVE subtree AS (
  SELECT id, parent_id, name FROM offices WHERE id = 2
  UNION ALL
  SELECT o.id, o.parent_id, o.name FROM offices o JOIN subtree s ON o.parent_id = s.id
) CYCLE id SET is_cycle USING visited
SELECT id, name, is_cycle FROM subtree;

Refuse the bad write

Better still, never store a cycle. This trigger walks up from the new parent and rejects the change if the walk reaches the row being changed:

CREATE OR REPLACE FUNCTION offices_no_cycle() RETURNS trigger LANGUAGE plpgsql AS $$
BEGIN
  -- Serialise hierarchy edits; without this, two concurrent edits can create a cycle (see below).
  PERFORM pg_advisory_xact_lock(hashtext('offices hierarchy'));
  IF NEW.parent_id IS NULL THEN RETURN NEW; END IF;
  IF EXISTS (
    WITH RECURSIVE up AS (
      SELECT id, parent_id FROM offices WHERE id = NEW.parent_id
      UNION
      SELECT o.id, o.parent_id FROM offices o JOIN up ON o.id = up.parent_id
    )
    SELECT 1 FROM up WHERE id = NEW.id
  ) THEN
    RAISE EXCEPTION 'office % cannot report to office %: that would create a cycle', NEW.id, NEW.parent_id;
  END IF;
  RETURN NEW;
END $$;

CREATE TRIGGER offices_no_cycle BEFORE INSERT OR UPDATE OF parent_id ON offices
  FOR EACH ROW EXECUTE FUNCTION offices_no_cycle();

ERROR:  office 1 cannot report to office 4: that would create a cycle

(This walk uses UNION on purpose: if the stored data already contains a cycle, deduplication lets the check finish instead of looping.)

Why the trigger needs the lock

Each transaction’s check sees only committed data. I tested two transactions running at the same time: one moved Zone A under Zone B, the other moved Zone B under Zone A. Each move is legal on its own. Without the advisory lock, both checks passed, both transactions committed, and the table ended up with a cycle.

With pg_advisory_xact_lock at the start of the trigger, the second transaction waited for the first to commit, then saw its change, and was rejected with the cycle error. The lock is released automatically at the end of each transaction. This relies on PostgreSQL’s default isolation level, READ COMMITTED, where each query in the trigger sees the latest committed data. Under REPEATABLE READ or SERIALIZABLE, the check sees the transaction’s snapshot, which can predate the other edit, so the lock alone is not enough; run hierarchy edits at READ COMMITTED. Edits to an office hierarchy are rare, so making them wait for each other costs nothing in practice.

Alternatives to an adjacency list

For a hierarchy that changes rarely but is read on every request, the adjacency list is enough: keep the writes simple and safe, and resolve each user’s scope once and cache it. Consider ltree or a closure table when you need fast ancestor and descendant queries across many different nodes and can afford more complicated writes.

Checklist

1. Store the tree with parent_id, and index parent_id and every foreign key that points into the tree.
2. Use UNION ALL with a clear anchor and recursive step.
3. Resolve an access scope to an array of ids before using it to filter large tables.
4. Prevent cycles on write, and serialise hierarchy edits so concurrent changes can’t form one.
5. Use CYCLE (PostgreSQL 14+) when reading data you don’t fully trust.
6. Check plans with EXPLAIN (ANALYZE) on realistic data, not on ten rows.