# What's the (Big O) computational complexity of a PostgreSQL recursive common table expression?

For example, taking this StackOverflow #44620695 question, recursive path aggregation and CTE query for top-down tree postgres as an example, which uses a recursive CTE to traverse a tree structure to determine the paths from a starting node. The screenshot above shows the the input data, the recursive CTE result, and a visualization of the source data.

Recursive CTE are iterative over the preceding result -- right? (as suggested in the accepted answer here) -- so would the time complexity be something like `O(log n)`?

• My motivation for asking is that I appended some related discussion at the end of my companion blog post, PostgreSQL, Trees and Recursive CTE, and I want to be sure I understand this. – Victoria Stuart Jun 8 '18 at 19:02
• Did you run query analyzer? – Mladen Uzelac Jun 8 '18 at 20:15
• "Big O" depends entirely on the internal algorithms of execution plan operators ("Hash Join", "Recursive Union" etc.), not on the way the SQL statement looks. – mustaccio Jun 8 '18 at 22:15
• "O(log n) [i.e., less than O(1)]" O(log n) isn't "less than" O(1). – sticky bit Jun 9 '18 at 21:06
• @mladen-uzelac: please see the `EXPLAIN ANALYZE` output appended to my companion blog post. – Victoria Stuart Jun 10 '18 at 17:40

## 1 Answer

OK, I'm going to propose a solution. Using the excellent article "A Gentle Introduction to Algorithm Complexity Analysis" as a guide, I believe the worst-case complexity of the example in my question (above) is as follows.

Given this recursive CTE:

``````WITH RECURSIVE nodes(id, src, path, tgt) AS (
-- Anchor member:
SELECT id, s, concat(s, '->', t), t,
array[id] as all_parent_ids
FROM tree WHERE s = 'a'
UNION ALL
-- Recursive member:
SELECT t.id, t.s, concat(path, '->', t), t.t, all_parent_ids||t.id FROM tree t
JOIN nodes n ON n.tgt = t.s
AND t.id <> ALL (all_parent_ids)
)
-- Invocation:
SELECT path FROM nodes;
``````
1. At the Anchor member (query definition), the algorithm selects each row from the table; therefore, at this step the maximum number of iterations (`i`) and the maximum size (`n`) is the number of rows in table; `i < n`, if a starting point within the table is specified.

2. The Recursive member selects each row from the table, starting from the position specified in the anchor member, so the maximum number of iterations here once again is: `i ≤ n`.

So, with the recursive CTE above I believe that the overall complexity is `Θ(n)`.

• That's "declarative" complexity, if one can call it so, because the SQL statement declares the result, but tells you nothing about the actual algorithm. The algorithm is revealed by the query plan, and if you look at it you'll see that the complexity is more like `O(a + b + x(n + z))`, where each of `a`, `b`, `x` and `z` is no greater than `n`. This might make no difference when `n=10`, but will quickly add up on a real-life data set. – mustaccio Jun 18 '18 at 20:29