Why DuckDB 2.0 is faster

Recursive CTEs: a boost for deep parent/child datasets

The DuckDB team rewrote the recursive CTE engine and claims 40x on graph reachability. Don't worry, I'll explain what that means on a table you already know.

A recursive CTE is a loop over a table. Take an employees table with two columns, manager and employee. You want to answer a simple question: who reports to whom.

manageremployeeAnaBenAnaCléaBenDevBenEliCléaFayDevGusFayHal

To do that, you start with one row: Ana, the CEO. Round one, find everyone whose manager is Ana (Ben, Cléa). Round two, find everyone whose manager is one of those people (Dev, Eli, Fay). Keep going until a round finds nobody new. Every level of the org chart is one round.

The query looks like this:

Copy code
WITH RECURSIVE team(person) AS (
    SELECT 'Ana'
  UNION
    SELECT e.employee FROM team t JOIN employees e ON e.manager = t.person
)
SELECT count(*) FROM team;

Org chart, folder tree, bill of materials, reply thread, data lineage, git history: these are all kinds of data where the table is often the same two columns, parent and child. The only thing that differs is how deep it goes, and the depth is the number of rounds for the query. An org chart is maybe eight levels. A git history is tens of thousands.

Here is the problem 1.5 had. Every round, it went back and re-read the whole table to find the next level. Eight levels mean eight full reads. Thousands of levels, thousands of full reads of the same table. In 2.0 the table is read once, a lookup on the parent column is built once, and each round only looks up the few rows it just found. The cost is now about the rows you actually touch, not rounds times table size.

Coming back to git history, that's typically where you will see the boost. Every commit points to its parent, so the table is just commit_id, parent_id, and walking the ancestry of HEAD is one round per commit. I generated a 20,000-commit repo with a few merges and walked it back to the root with a recursive CTE like this:

Copy code
WITH RECURSIVE ancestors(id) AS (
    SELECT max(id) FROM commits              
  UNION
    SELECT p.parent_id FROM ancestors a JOIN commit_parents p ON p.commit_id = a.id
)
SELECT count(*) FROM ancestors;

And the query times:

Ancestry walk, 20,000 commitsDuckDB 1.5.51.8 s to 16 s across runsDuckDB 2.0 alpha0.10 s, every run

TL;DR: if you walk deep parent/child chains (git history, lineage, reply threads, a full bill of materials), 2.0 turns a job you used to push to a graph database into a normal query. If your hierarchy is shallow, like an org chart, you won't see much. Either way, keep the hierarchy as one parent/child table with integer ids, and reach for USING KEY when the recursion carries a value like depth or cost.