(From your companion blog)
The query returns these 13 rows:
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)
-> 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?
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.
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
? ( 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)
If N = 10 (rows) then this is more like
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
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.