--- title: "Recursive Query in SQL" description: "Learn what SQL recursive queries are and how you can write them in PostgreSQL with examples. A practical guide for PostgreSQL and TimescaleDB developers." section: "Postgres guides" --- > **TimescaleDB is now Tiger Data.** *Written by *[*Dylan Paulus*](https://www.timescale.com/blog/author/dylan/)* * 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](https://www.timescale.com/learn/how-to-use-common-table-expression-sql) (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.  ## What Is Recursion? 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](https://en.wikipedia.org/wiki/Matryoshka_doll). 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." ## Recursive Queries 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; ` ## Real-World Example Using Recursive Queries 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* ### Base case `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`. ### Recursive case `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`. #### Query `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. ## Using Lateral Joins The reason we stored each `power_usage` in an array in the previous example is that we can't use [aggregate functions](https://www.timescale.com/learn/understanding-sql-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;  ` ### Base case 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. ### Recursive case 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.  #### Query 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. ## When to Use Recursive Queries 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. ### Advantages of using recursive queries: - 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) ### Disadvantages of using recursive queries: - 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 ## Optimizing Recursive Queries To combat the disadvantages of using recursive queries, we can take into account some optimization techniques.  ### Indexes [Indexes are the cornerstone of all PostgreSQL](https://www.timescale.com/learn/database-indexes-in-postgres) 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`. #### UNION vs. UNION ALL 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`. ## Configure PostgreSQL Parameters [PostgreSQL has a whole range of configuration parameters](https://www.timescale.com/learn/postgresql-performance-tuning-key-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 [Materialized views](https://www.timescale.com/blog/creating-a-fast-time-series-graph-with-postgres-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. [T](https://docs.timescale.com/use-timescale/latest/continuous-aggregates/)[imescale's continuous aggregates](https://docs.timescale.com/use-timescale/latest/continuous-aggregates/) handle refreshing automatically to get around his materialized view limitation. ## Alternatives to Recursive Queries 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. ## Conclusion 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. ### Read more - [How to Use a Common Table Expression (CTE) in SQL](https://www.timescale.com/learn/how-to-use-common-table-expression-sql) - [PostgreSQL Performance Tuning: Key Parameters](https://www.timescale.com/learn/postgresql-performance-tuning-key-parameters) - [PostgreSQL Performance Tuning: Optimizing Database Indexes](https://www.tigerdata.com/learn/postgresql-performance-tuning-optimizing-database-indexes) - [Postgres Materialized Views, The Timescale Way ](https://www.timescale.com/blog/materialized-views-the-timescale-way/)