Published at Nov 5, 2024
Start supercharging your PostgreSQL today.
Written by Dylan Paulus
As developers, querying in PostgreSQL for hierarchical data is difficult. SQL is a declarative programming language, but our brains are trained to think imperatively. Recursive queries using Common Table Expressions (CTE) simplify writing iterative queries and are essential in traversing hierarchical data, like tree or graph structures.
Throughout this article, we'll explore SQL recursive queries with examples, look at optimizing recursive queries, and discuss advanced techniques.
Before getting into recursive queries, let's take a step back to understand recursion. Recursion is a method of breaking down a problem into a small, repeatable solution that calls itself. Think of recursion like Russian nesting dolls. To find a specific doll, we open smaller and smaller versions of the same doll until we find the doll we want or there are no more dolls to open.
In programming, we see recursion when a function calls itself. Recursion is classically a solution to finding the Fibonacci sequence. The Fibonacci sequence is a series of numbers where each number is calculated by summing the previous two numbers starting at one (0, 1, 1, 2, 3, 5, 8, 13, and so on).
The Fibonacci Sequence mapped out
To find the Fibonacci number at a given position, we start by finding the Fibonacci number of the previous two positions. This process continues until we reach position 0 or 1, which always returns 0 or 1, respectively. It's important to remember these base cases as they form the foundation of the sequence.
For example, to find the Fibonacci number at position 5 in the sequence, we first need to find the Fibonacci number at position 4 and 3 (fibonacci(3) + fibonacci(4) = 5). To find the Fibonacci number of position 3, we then need to find the Fibonacci number at positions 1 and 2 (fibonacci(1) + fibonacci(2) = 3). This continues until we reach position 0 (since fibonacci(0) = 0) or 1 (fibonacci(1) = 1).
A graph showing calculating Fibonacci numbers at position 5
Using this approach, the solution to finding Fibonacci numbers in Python would be:
def fibonacci(number):
if number <= 1: # Base case
return number
return fibonacci(number - 1) + fibonacci(number - 2) # Recursion
Recursion can be broken down into two parts. The base case and the recursive case.
Base case: it defines the starting point of recursion, or in other words, the condition that will break out of recursion.
Recursive case: the case where we call the function we're in—this is where the "loop iterates."
Like in our favorite programming languages, recursive queries in PostgreSQL allow us to iterate through data or navigate hierarchical data, following a similar pattern and setup with a slightly different approach.
We define a base case and a recursive case by breaking down a query into small, repeatable statements. Recursive queries are defined through Common Table Expressions by starting queries with WITH RECURSIVE statements. The structure of a recursive query looks like:
WITH RECURSIVE [cte name] AS (
[base case]
UNION ALL
[recursive case]
)
[primary query]
In recursive queries, the base case is the starting point of recursion. The recursive case is what gets repeated. This happens in recursive queries by joining against the recursive query, and recursion stops when there is nothing else to join against. UNION ALL merges the results in the base case and recursive case.
Finally, outside the Common Table Expression, we have a query that ties the recursive query together. You'll generally see this as a straight SELECT * FROM [recursive_cte_name];.
Like the Python example, we can calculate Fibonacci numbers with recursive queries in PostgreSQL. The syntax looks different from the Python example, note the similarities between the base/recursive cases and the general approach to the solution.
WITH RECURSIVE fibonacci(position, current_value, next_value) AS (
-- Base case: start with position: 1, current_value: 0, and next_value: 1
SELECT
1 as position,
0 as current_value,
1 as next_value
UNION ALL
-- Recursive case: Loop through the fibonacci sequence, ending at position 4.
-- Putting the WHERE clause prevents runaway recursion (infinite loop)
SELECT
position + 1,
next_value,
current_value + next_value
FROM fibonacci -- Where we call "ourself", creating recursion
WHERE position < 5
)
-- Select the results
SELECT
position,
current_value as fibonacci_number
FROM fibonacci;
Let's say that our company monitors the electrical usage of residential homes using small IoT sensors. Each sensor is connected to another sensor to monitor voltage usage. The data is modeled in a graph since electrical runs can be split (e.g., the same power source can power lights and receptacles).
An example of a graph structure for modeling sensors in a house's electrical system
The SQL tables look like this:
CREATE TABLE sensors (
id SERIAL PRIMARY KEY,
name VARCHAR(255) NOT NULL,
previous_sensor_id INTEGER REFERENCES sensors(id)
);
CREATE TABLE events (
id SERIAL PRIMARY KEY,
sensor_id INTEGER REFERENCES sensors(id),
power_usage DECIMAL, -- Kilowatt hours
date TIMESTAMP default now()
);
INSERT INTO sensors (name, previous_sensor_id) VALUES ('Breaker', null); -- id is 1
INSERT INTO sensors (name, previous_sensor_id) VALUES ('Bedroom Recepticles', 1); -- id is 2
INSERT INTO sensors (name, previous_sensor_id) VALUES ('Bedroom Light Switch', 1); -- id is 3
INSERT INTO sensors (name, previous_sensor_id) VALUES ('Bedroom Lights', 3); -- id is 4
INSERT INTO sensors (name, previous_sensor_id) VALUES ('Bathroom Lights', 1); -- id is 5
INSERT INTO events (sensor_id, power_usage) VALUES (2, 1.05);
INSERT INTO events (sensor_id, power_usage) VALUES (4, 0.3);
INSERT INTO events (sensor_id, power_usage, date) VALUES (4, 0.2, now() - interval '1' day);
INSERT INTO events (sensor_id, power_usage, date) VALUES (4, 0.28, now() - interval '2' day);
INSERT INTO events (sensor_id, power_usage) VALUES (5, 0.13);
INSERT INTO events (sensor_id, power_usage, date) VALUES (5, 0.17, now() - interval '1' day);
We are tasked with determining the average power usage for all sensors in a given chain (e.g., Bedroom Lights -> Light Switch -> Breaker) in the past day. To make debugging easier, we will also display the path taken through each sensor.
Let's first examine the complete query and then break down each step that makes up the complete recursive query.
WITH RECURSIVE power_chain AS (
-- Base case: start with sensors who don't have children
SELECT
s.id,
s.name,
s.previous_sensor_id,
Array[e.power_usage] as power_usages,
ARRAY[s.name]::VARCHAR[] as chain
FROM sensors s
JOIN events e ON s.id = e.sensor_id
WHERE NOT EXISTS (
SELECT 1
FROM sensors child
WHERE child.previous_sensor_id = s.id
)
AND e.date >= NOW() - INTERVAL '1 day'
UNION ALL
-- Recursive case: recurse through parent sensors
SELECT
s.id,
s.name,
s.previous_sensor_id,
e.power_usage || pc.power_usages,
s.name || pc.chain
FROM sensors s
LEFT JOIN events e on s.id = e.sensor_id
JOIN power_chain pc ON s.id = pc.previous_sensor_id
)
SELECT
array_to_string(chain, ' <- ') as complete_path,
ROUND((SELECT AVG(s) FROM UNNEST(power_usages) s), 2) as power_usage
FROM power_chain
WHERE previous_sensor_id IS NULL;
The output table of running the previous recursive query
SELECT
s.id,
s.name,
s.previous_sensor_id,
Array[e.power_usage] as power_usages,
ARRAY[s.name]::VARCHAR[] as chain
FROM sensors s
JOIN events e ON s.id = e.sensor_id
WHERE NOT EXISTS (
SELECT 1
FROM sensors child
WHERE child.previous_sensor_id = s.id
)
AND e.date >= NOW() - INTERVAL '1 day'
In the base case, we define how the recursion will start. We start with the sensors that don't have children or, in other words, the root nodes. In this case, it's just the Breaker sensor. You'll notice we include two arrays in the SELECT statement: power_usages and chain. As we traverse the sensor graph, we'll add to these arrays to compute the average power_usage and the path back to the Breaking through chain.
SELECT
s.id,
s.name,
s.previous_sensor_id,
e.power_usage || pc.power_usages,
s.name || pc.chain
FROM sensors s
LEFT JOIN events e on s.id = e.sensor_id
JOIN power_chain pc ON s.id = pc.previous_sensor_id
In each recursive case, we follow the path from the breaker back through every possible path (JOIN power_chain pc ON s.id = pc.previous_sensor_id), adding the current sensor's data to power_usages and keeping track of the path in chain.
SELECT
array_to_string(chain, ' <- ') as complete_path,
ROUND((SELECT AVG(s) FROM UNNEST(power_usages) s), 2) as power_usage
FROM power_chain
WHERE previous_sensor_id IS NULL;
In the main body of the query, we'll aggregate the two arrays we created in the recursive query. First, we'll combine the chain array into a string showing the complete_path the recursive query took. Last, we take the average of the power_usages to get the average power usage through each recursive path.
The reason we stored each power_usage in an array in the previous example is that we can't use aggregate functions inside the recursive case (SUM, AVG, etc.). Give it a try. PostgreSQL will return an error that reads ERROR: aggregate functions are not allowed in a recursive query's recursive term.
We can use subqueries, build the data as we recurse (like through the array example), or use lateral joins to get around this. Lateral joins are like subqueries, except they return multiple rows, and they can reference tables in the nearby FROM clause. LATERAL can be thought of as a for-each loop.
Let's look at an example. Instead of taking the average (AVG) of the power_usage across electrical runs, let's sum up the total load. We'll accomplish this by using LATERAL in the recursive case.
WITH RECURSIVE power_chain AS (
-- Base case: start with sensors who don't have children
SELECT
s.id,
s.name,
s.previous_sensor_id,
0::float as power_usage,
ARRAY[s.name]::VARCHAR[] as chain
FROM sensors s
JOIN events e ON s.id = e.sensor_id
WHERE NOT EXISTS (
SELECT 1
FROM sensors child
WHERE child.previous_sensor_id = s.id
)
AND e.date >= NOW() - INTERVAL '1 day'
UNION ALL
-- Recursive case: recurse through parent sensors
SELECT
s.id,
s.name,
s.previous_sensor_id,
pc.power_usage + usage.total,
s.name || pc.chain
FROM sensors s
JOIN power_chain pc ON s.id = pc.previous_sensor_id,
LATERAL (SELECT SUM(e.power_usage) as total FROM events e where e.sensor_id = pc.id) as usage
)
SELECT
array_to_string(chain, ' <- ') as complete_path,
power_usage
FROM power_chain
WHERE previous_sensor_id IS NULL;
The base case in this example has mostly stayed the same. The difference is instead of using an array to gather all the power_usage's, we start with a default power_usage of 0. We'll add to this as we recurse.
The recursive case is similar to the previous example except for the addition of LATERAL. As mentioned, we can think of a lateral join as a for-each loop. Here, we are saying that for each sensor in the chain (for each recursive step), get all the events for the sensor and find the sum of the power_usage. Then, in SELECT, we add the total power_usage of the current sensor to the running total of all the sensors in the chain.
Finally, we don't need to provide any aggregate functions in the query; the recursive query has already calculated the total power_usage. We can SELECT the power_usage to get the running total.
Recursive queries shine when querying for hierarchical data in a tree or graph-like data structure. These data structures generally don't have a predefined length, and we need to know how deep we need to query ahead of time. On the flip side, using recursive queries can add a performance penalty and can be easily prone to out-of-memory issues due to logic errors in setting up recursive queries or when the dataset is huge.
Make traversing and querying hierarchical data possible
More effective than multiple self-joins
Can simplify the logic of nested SQL commands (easier to read than using many subqueries)
Misdefined recursive queries can cause runaway recursion (recursive queries that don't stop until the system crashes)
Recursive queries add a performance hit for large datasets
Complex recursive queries can be more difficult to debug
To combat the disadvantages of using recursive queries, we can take into account some optimization techniques.
Indexes are the cornerstone of all PostgreSQL query optimizations. Ensuring that the columns a recursive query joins against are indexed is a key factor in boosting performance. For instance, in the electrical system example, the columns that would benefit from indexes are previous_sensor_id and sensor_id.
In all our recursive queries, we have been using UNION ALL as the glue to combine the results of the base case and the recursive case. We have two options here, though, UNION or UNION ALL.
WITH RECURSIVE power_chain AS (
SELECT
s.name
FROM sensors s
UNION ALL -- UNION ALL
SELECT
s.name
FROM sensors s
JOIN power_chain pc ON s.id = pc.previous_sensor_id
)
SELECT
name
FROM power_chain;
WITH RECURSIVE power_chain AS (
SELECT
s.name
FROM sensors s
UNION -- UNION
SELECT
s.name
FROM sensors s
JOIN power_chain pc ON s.id = pc.previous_sensor_id
)
SELECT
name
FROM power_chain;
The difference is that UNION merges the two datasets and then deduplicates the results (like DISTINCT). UNION ALL merges the two datasets together, and that's it; there is no deduplication step. UNION has its use, but for cases where speed is a priority, use UNION ALL.
PostgreSQL has a whole range of configuration parameters] to tweak to improve the performance of queries. Updating work_mem changes the amount of memory allocated for each operation (like sorting), and updating shared_buffers will change how much memory PostgreSQL uses for its pages.
Both of these parameters will improve the efficiency of recursive queries. Directly related to recursive queries is max_stack_depth, which defines how "deep" recursion can go. Increasing max_stack_depth won't improve performance but will allow recursive queries to navigate further before erroring.
Materialized views can store the results of expensive queries in what can be thought of as a cache. When recursive queries become too slow and costly to run, we can create a materialized view of the results of the recursive query.
Querying the materialized view is fast since the recursive query doesn't need to be run on every query. Materialized views need to be updated manually. Updating the materialized view will incur the performance penalty of slow recursive queries, but refreshing the materialized view can be deferred to times of low traffic. Timescale's continuous aggregates handle refreshing automatically to get around his materialized view limitation.
As you know, PostgreSQL is a versatile tool for handling hierarchical data structures like trees or graphs. Recursive queries are just one of the many ways it can loop through iterative data, showcasing its adaptability and power.
LATERAL joins are one way to iterate over results. Another way to loop through data in SQL is to use PL/pgSQL's LOOP operation (PostgreSQL Procedural Language) inside a custom function we create. Though functions are powerful in their own right, you'll see that creating functions can be more tedious than writing a recursive query to iterate through data.
To show off loops, we'll keep the example basic by creating a function that takes in a sensor_id and prints out all the power_usage events for that sensor:
CREATE FUNCTION print_events(sensor_id_in integer) RETURNS integer AS $$
DECLARE
event RECORD;
BEGIN
FOR event IN
SELECT * from events e WHERE e.sensor_id = sensor_id_in
LOOP
RAISE NOTICE '%: %', event.sensor_id, event.power_usage;
END LOOP;
RETURN 1;
END;
$$ LANGUAGE plpgsql;
SELECT * FROM print_events(4);
There are many moving pieces in creating this simple function. First, we define the function, its name, the arguments it's going to take, and what it returns. Next is the DECLARE block, where we set up the variables we're going to use and their types. Finally, the code. This is where we define the logic of the function—in this case, looping through all events.
While this is a basic example, it effectively demonstrates the potential complexity of using functions to loop through data. Functions in PostgreSQL are adept at encapsulating functionality, but when it comes to handling hierarchical data, the true power lies in recursive queries.
As developers, navigating hierarchical data in SQL can be challenging, but recursive queries using Common Table Expressions (CTEs) make it easy.
By breaking down the problem into a base case and recursive case, we can easily traverse tree and graph data structures. While recursive queries may have some performance considerations, techniques like indexing, parameter tuning, and materialized views can help optimize their execution.
As the complexity of our data grows, the ability to effectively harness recursive queries will become increasingly essential in our toolkits as software engineers. By mastering recursive queries, we can write more efficient and maintainable code to solve the ever-evolving data challenges we face.