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

Question

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)?

Answer 1

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).

Answer 2

(From your companion blog)
The query returns these 13 rows:

 a->b
 a->b->a
 a->b->c
 a->b->d
 a->b->c->e
 a->b->d->e
 a->b->c->h
 a->b->d->e->f
 a->b->c->e->f
 a->b->c->e->f->g
 a->b->d->e->f->g
 a->b->d->e->f->g->h
 a->b->c->e->f->g->h

The execution plan ( aka explain plan / query plan):

CTE Scan on nodes  (cost=322.86..356.54 rows=1684 width=32) (actual time=0.027..0.120 rows=13 loops=1)
   CTE nodes
     ->  Recursive Union  (cost=4.18..322.86 rows=1684 width=132) (actual time=0.025..0.110 rows=13 loops=1)
           ->  Bitmap Heap Scan on tree  (cost=4.18..12.65 rows=4 width=132) (actual time=0.024..0.024 rows=1 loops=1)
                 Recheck Cond: (s = 'a'::text)
                 Heap Blocks: exact=1
                 ->  Bitmap Index Scan on tree_s_t_key  (cost=0.00..4.18 rows=4 width=0) (actual time=0.005..0.005 rows=1 loops=1)
                       Index Cond: (s = 'a'::text)
           ->  Hash Join  (cost=1.30..27.65 rows=168 width=132) (actual time=0.009..0.012 rows=2 loops=6)
                 Hash Cond: (t.s = n.tgt)
                 Join Filter: (t.id <> ALL (n.all_parent_ids))
                 Rows Removed by Join Filter: 0
                 ->  Seq Scan on tree t  (cost=0.00..18.50 rows=850 width=68) (actual time=0.001..0.002 rows=10 loops=6)
                 ->  Hash  (cost=0.80..0.80 rows=40 width=96) (actual time=0.001..0.001 rows=2 loops=6)
                       Buckets: 1024  Batches: 1  Memory Usage: 9kB
                       ->  WorkTable Scan on nodes n  (cost=0.00..0.80 rows=40 width=96) (actual time=0.000..0.001 rows=2 loops=6)

Execution plans are read innermost-indent to outermost, from bottom to top. Aligned indented operations belong to a parent operation located above them, that has less indentation.

There are 2 sets of brackets after the operations, the first is an estimated cost so I will ignore that and talk about the actual costs.

• The "Anchor" part of the CTE corresponds to the Bitmap Index Scan ( and Bitmap Heap Scan after it which is really the second stage of the same scan) and it shows actual rows = 1 and loops = 1 so we can simplify and assume that whole operation would be O(1)

• The "Recursive" part of the CTE corresponds to the Hash Join. A hash is created on a WorkTable, an in-memory structure that it has reserved 9kB of memory for, and uses a hash function with 1024 possible buckets - which it deems enough for the query. How does initializing the WorkTable contribute to the complexity? Should it be ignored because it's an implementation detail or is it significant?

• The WorkTable has 2 rows and is looped over 6 times, but each time it is scanned does the WorkTable have the same contents? How could it since the array is accumulating and arrows are being concatenated to the previous iteration's s & t? It must be modified or rebuilt on each loop. So is that 6 rebuilds of 2 rows plus 6 scans of 2 rows? There are implementation details that are not surfaced by the execution plan so hard to say without profiling the Postgres C source code.

• That WorkTable is used as the Hash to probe the other table in the hash-join. That other table is tree and there is a Sequential Scan (Seq Scan) on tree that contains 10 rows, and it loops 6 times, 10 * 6 = 60. So yes i <= N as stated in your answer, but I don't think it is right to say the complexity is the same as i, it is i * n because each iteration is a sequential scan over the full tree table, not just one row.

• The final query results (the CTE Scan in the very first line of the plan) says there are 13 rows and 1 loop. That 13 consists of the 1 anchor row plus the 2 * 6 = 12 rows returned by the Hash Join. Does that count as another 13? I would say yes because the step takes more than zero time; the Recursive Union finishes at 0.110 and the CTE Scan at 0.120.

So adding it all up

1 (anchor)
? ( Initialize WorkTable, contributes some small unknown time complexity)
12 ( worktable scan 2 rows * 6 loops)
12 ( hash 2 rows * 6 loops)
60 ( sequential scan of 10 rows of `tree` table * 6 loops)
12 ( hash join of 2 rows * 6 loops -  is this double or triple counting?)
13 ( Final CTE Scan)

= 110

---

If N = 10 (rows) then this is more like O(n^2)

Quadratic complexity, similar to a nested-loop operation, which is a reasonable comparison. A hash join is not a nested-loop join, it's an optimisation, but in the context of recursion it's not just doing it once.

I notice at the end of your blog you mention

while embedding complex graphs in a RDB (arguably) is not a good idea, given that recursive CTE appear to be an efficient algorithmic approach to determining paths in trees/graphs, that is not one of the reasons

I would have to disagree. Recursive CTE's are not efficient, they are effectively explicit loops and loops are usually bad news in SQL. There are some situations where they can't be avoided but should be if possible. I would agree about using cypher/gremlin/ some other graph specific language or graph database for this use case though. It's not so much they have better algorithms for this but rather that have some good tricks for pre-calculating and caching paths, ancestors and descendants & storing redundant data structures at graph-build-time in order to speed up run-time queries.