For example, there is a perfect ten-fork tree of height 6 and size 1000001, with a root node whose value is {parent_id: -1, id: 0}:

CREATE TABLE tree (
  pid     INT,
  id      INT,
  is_leaf INT,
  PRIMARY KEY (pid, id)
);

WITH
  digit(n) AS (
    VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
  ),
  
  number(n) AS (
    SELECT a.n*100000 + b.n*10000 + c.n*1000 + d.n*100 + e.n*10 + f.n
      FROM digit a, digit b, digit c, digit d, digit e, digit f
  )

INSERT INTO tree (pid, id, is_leaf)
SELECT -1, 0, FALSE
 UNION ALL
SELECT n / 10, n + 1, n >= 100000
  FROM number;

And now I need to calculate the sum of the ids of all descendant nodes of the root node.

At first, I used recursive cte:

WITH RECURSIVE
  descendant(id, is_leaf) AS (
    SELECT id, is_leaf
      FROM tree
     WHERE pid = 0
     UNION ALL
    SELECT b.id, b.is_leaf
      FROM descendant a
     CROSS JOIN tree b ON b.pid = a.id
     WHERE NOT a.is_leaf
  )

SELECT SUM(id)
  FROM descendant;

But then I realized that, it would be faster if I joined the table manually:

WITH
  lv1(id, is_leaf) AS (SELECT id, is_leaf FROM tree WHERE pid = 0),
  lv2(id, is_leaf) AS (SELECT b.id, b.is_leaf FROM lv1 a CROSS JOIN tree b ON NOT a.is_leaf AND b.pid = a.id),
  lv3(id, is_leaf) AS (SELECT b.id, b.is_leaf FROM lv2 a CROSS JOIN tree b ON NOT a.is_leaf AND b.pid = a.id),
  lv4(id, is_leaf) AS (SELECT b.id, b.is_leaf FROM lv3 a CROSS JOIN tree b ON NOT a.is_leaf AND b.pid = a.id),
  lv5(id, is_leaf) AS (SELECT b.id, b.is_leaf FROM lv4 a CROSS JOIN tree b ON NOT a.is_leaf AND b.pid = a.id),
  lv6(id, is_leaf) AS (SELECT b.id, b.is_leaf FROM lv5 a CROSS JOIN tree b ON NOT a.is_leaf AND b.pid = a.id),
  lv7(id, is_leaf) AS (SELECT b.id, b.is_leaf FROM lv6 a CROSS JOIN tree b ON NOT a.is_leaf AND b.pid = a.id),
  
  descendant(id) AS (
    SELECT id FROM lv1 UNION ALL SELECT id FROM lv2 UNION ALL
    SELECT id FROM lv3 UNION ALL SELECT id FROM lv4 UNION ALL
    SELECT id FROM lv5 UNION ALL SELECT id FROM lv6 UNION ALL SELECT id FROM lv7
  )
  
SELECT SUM(id)
  FROM descendant;

The following table shows the time used for the above methods:

Why is recursive CTE so slow? Is it because sqlite recurses only one line at a time?

I reproduced your test on my hardware, and got this:

populate
Run Time: real 9.557 user 8.576036 sys 0.312179

prime the cache with SELECT * FROM tree; into /dev/null
Run Time: real 3.289 user 3.286377 sys 0.000000

Calculate the sum of the ids of all descendant nodes of the root node.

Recursive cte:
500000500000
Run Time: real 7.704 user 7.555815 sys 0.139559

Manual join:
500000500000
Run Time: real 3.946 user 3.836644 sys 0.109949

And I thought: hey, all descendants? That is all rows excluding the root. No need to walk the tree.

SELECT SUM(id) FROM tree WHERE id;
500000500000
Run Time: real 0.552 user 0.551928 sys 0.000026

Granted, this only solves the special case of "all descendants of root", and does not solve "all descendants of a specific node".

So, maybe i should add a smiley?

-- 
Regards,
Kees Nuyt

Talking about closure…

You could try to benchmark your use-case against the pre-CTE solution, I.e. < https://sqlite.org/src/file/ext/misc/closure.c>