Common Table Expressions (CTEs) & Recursive Hierarchies: SQL Graph Traversals

Created: 2026-11-08  ·  Last updated: 2026-11-08  ·  Nejat Hakan

Executive Summary: Highly nested subqueries obscure business logic, hinder query readability, and often force application developers into slow "N+1" procedural database calls. Common Table Expressions (WITH clauses) solve this by transforming complex queries into sequential, readable pipelines. Beyond formatting, WITH RECURSIVE elevates relational SQL engines into graph traversal systems capable of exploring organizational hierarchies, network topologies, and dependency trees in a single database round-trip with built-in cycle detection.

• Modular Query Pipelines

  ---

  Decompose multi-layered subqueries into readable, testable stages; control execution with MATERIALIZED vs. NOT MATERIALIZED hints.

• Recursive Graph Traversals

  ---

  Traverse arbitrary-depth hierarchies (filesystem trees, network routing hops, category breadcrumbs) in pure set-based SQL.

• Loop & Cycle Detection

  ---

  Prevent runaway queries on cyclic graphs using PostgreSQL 14+ standard CYCLE syntax or array path tracking.

• Data-Modifying CTEs

  ---

  Perform atomic, zero-downtime data archival: combine DELETE ... RETURNING and INSERT in a single concurrent transaction.

---

1. Standard Common Table Expressions (WITH)

A Common Table Expression defines a temporary, named result set that exists strictly within the execution scope of a primary statement (SELECT, INSERT, UPDATE, or DELETE).

-- Pipeline readability: Top 5 spenders among enterprise customers
WITH enterprise_customers AS (
    SELECT customer_id, company_name, email
    FROM customers
    WHERE company_name ILIKE '%Corp%' OR company_name ILIKE '%Enterprise%'
),
customer_spending AS (
    SELECT 
        o.customer_id,
        COUNT(o.order_id) AS order_count,
        SUM(oi.quantity * oi.unit_cents) AS total_spent_cents
    FROM orders o
    INNER JOIN order_items oi ON oi.order_id = o.order_id
    WHERE o.status = 'PAID'
    GROUP BY o.customer_id
)
SELECT 
    ec.company_name,
    ec.email,
    cs.order_count,
    ROUND(cs.total_spent_cents / 100.0, 2) AS total_spent_eur
FROM enterprise_customers ec
INNER JOIN customer_spending cs ON cs.customer_id = ec.customer_id
ORDER BY cs.total_spent_cents DESC
LIMIT 5;

Optimizer Semantics: MATERIALIZED vs. NOT MATERIALIZED

In early versions of PostgreSQL, CTEs acted as optimization fences: the engine always evaluated the CTE completely into an in-memory temporary table before executing the outer query. Since PostgreSQL 12+, the query planner can inline CTEs (treating them identically to subqueries) to push down WHERE clauses and leverage indexes.

Engineers can explicitly control this behavior:

-- Force the engine to evaluate the CTE once into a temporary buffer:
WITH expensive_calculation AS MATERIALIZED (
    SELECT heavy_function(x) AS val FROM large_table
)
SELECT * FROM expensive_calculation WHERE val > 100;

-- Force the engine to push down predicates and inline into outer joins:
WITH customer_lookup AS NOT MATERIALIZED (
    SELECT customer_id, email FROM customers
)
SELECT * FROM orders o JOIN customer_lookup c ON c.customer_id = o.customer_id;

---

2. WITH RECURSIVE: Mechanics of Hierarchical SQL

A recursive CTE consists of three core components: an Anchor Member, a Recursive Member combined via UNION ALL, and a Termination Condition.

%%{init: {'flowchart': {'wrappingWidth': 600}}}%%
flowchart TB
    ANCHOR["1. Anchor Member<br/>Initial Query Evaluates Root Rows<br/>Seeds Intermediate Working Table"]
    RECUR["2. Recursive Member<br/>Joins Working Table against Child Rows<br/>Produces New Working Batch"]
    DEC{"Working Batch<br/>Empty?"}
    FINAL["3. Final Result Set<br/>Unions all traversed levels into<br/>single unified relation"]

    ANCHOR --> RECUR
    RECUR --> DEC
    DEC -->|No: Has Rows| RECUR
    DEC -->|Yes: 0 Rows| FINAL

The Engine's Internal Execution Loop

1. Initialize Working Table: The engine executes the Anchor query and inserts the resulting rows into both the final output and an internal Working Table.
2. Execute Recursive Query: The engine runs the Recursive query, substituting the CTE name with the contents of the Working Table.
3. Swap & Append: If the recursive step returns new rows, they are appended to the final output, the Working Table is replaced with the new rows, and the loop repeats.
4. Termination: When the recursive step returns zero rows, the execution loop terminates.

---

3. Hands-on Lab: Traversing Network Infrastructure Topology

In Linux operations, infrastructure dependencies form hierarchical directed trees. Consider this lab mapping physical servers, virtual machines, and containerized services:

-- File: /opt/db-ops/infrastructure_tree_lab.sql
BEGIN;

CREATE TABLE infra_topology (
    node_id         INT PRIMARY KEY,
    parent_node_id  INT REFERENCES infra_topology(node_id),
    node_name       VARCHAR(64) NOT NULL,
    role            VARCHAR(32) NOT NULL
);

INSERT INTO infra_topology (node_id, parent_node_id, node_name, role) VALUES
    (1, NULL, 'core-spine-01',   'Datacenter Switch'),
    (2, 1,    'leaf-tor-01',     'Top-of-Rack Switch'),
    (3, 2,    'hv-kvm-node01',   'Debian 12 Hypervisor'),
    (4, 3,    'vm-db-primary',   'PostgreSQL 17 VM'),
    (5, 4,    'pg-tenant-app1',  'Application Database'),
    (6, 2,    'hv-kvm-node02',   'Compute Hypervisor'),
    (7, 6,    'vm-ingress-01',   'Nginx Edge Gateway');

-- Traverse the tree from root to leaf with depth levels and path trace
WITH RECURSIVE topology_tree AS (
    -- 1. Anchor Member: Find top-level datacenter root
    SELECT
        node_id,
        parent_node_id,
        node_name,
        role,
        1 AS depth_level,
        node_name::TEXT AS path_trace
    FROM infra_topology
    WHERE parent_node_id IS NULL

    UNION ALL

    -- 2. Recursive Member: Join children to their parents
    SELECT
        child.node_id,
        child.parent_node_id,
        child.node_name,
        child.role,
        parent.depth_level + 1,
        parent.path_trace || ' → ' || child.node_name
    FROM infra_topology child
    INNER JOIN topology_tree parent ON parent.node_id = child.parent_node_id
)
SELECT 
    depth_level,
    REPEAT('  ', depth_level - 1) || '└─ ' || node_name AS tree_view,
    role,
    path_trace
FROM topology_tree
ORDER BY path_trace;

COMMIT;

Query Output

 depth_level | tree_view                        | role                  | path_trace
-------------+----------------------------------+-----------------------+-----------------------------------------------------------
           1 | └─ core-spine-01                 | Datacenter Switch     | core-spine-01
           2 |   └─ leaf-tor-01                 | Top-of-Rack Switch    | core-spine-01 → leaf-tor-01
           3 |     └─ hv-kvm-node01             | Debian 12 Hypervisor  | core-spine-01 → leaf-tor-01 → hv-kvm-node01
           4 |       └─ vm-db-primary           | PostgreSQL 17 VM      | core-spine-01 → leaf-tor-01 → hv-kvm-node01 → vm-db-primary
           5 |         └─ pg-tenant-app1        | Application Database  | ... → vm-db-primary → pg-tenant-app1
           3 |     └─ hv-kvm-node02             | Compute Hypervisor    | core-spine-01 → leaf-tor-01 → hv-kvm-node02
           4 |       └─ vm-ingress-01           | Nginx Edge Gateway    | ... → hv-kvm-node02 → vm-ingress-01

---

4. Preventing Infinite Loops: Graph Cycle Detection

If data contains cyclic references (A → B → C → A), standard recursive queries enter an infinite loop, consuming CPU and disk space until the statement times out or exhausts memory.

Standard PostgreSQL 14+ CYCLE Syntax

PostgreSQL provides native cycle detection syntax conforming to modern SQL standards:

WITH RECURSIVE graph_walk AS (
    SELECT node_id, parent_node_id, node_name
    FROM infra_topology
    WHERE node_id = 1

    UNION ALL

    SELECT c.node_id, c.parent_node_id, c.node_name
    FROM infra_topology c
    JOIN graph_walk p ON p.node_id = c.parent_node_id
)
CYCLE node_id SET is_cycle USING path_history
SELECT * FROM graph_walk WHERE NOT is_cycle;

---

5. Data-Modifying CTEs: Atomic Archival

CTEs can contain DELETE, UPDATE, or INSERT statements with a RETURNING clause. This allows moving rows between tables in a single atomic SQL statement without locking tables across multiple round-trips:

-- File: /opt/db-ops/atomic_log_archival.sql
-- Atomically purge processed logs older than 30 days and move to cold storage
WITH purged_logs AS (
    DELETE FROM audit_logs_hot
    WHERE created_at < NOW() - INTERVAL '30 days'
      AND processed = TRUE
    RETURNING log_id, event_type, payload, created_at
)
INSERT INTO audit_logs_cold (log_id, event_type, payload, archived_at)
SELECT log_id, event_type, payload, NOW()
FROM purged_logs;