Repository navigation
this recursive CTE SQL runs slower than SQLite #1805
Description
s="""
WITH RECURSIVE
input(sud) AS (
VALUES('....754..........8.8.19....3....1.6........34....6817.2.4...6.39......2.53.2.....'),
('3.........5.7.3..8....28.7.7......43...........39.41.54..3..8..1...4....968...2..')
),
digits(z, lp) AS (
VALUES('1', 1)
UNION ALL SELECT
CAST(lp+1 AS TEXT) as z, lp+1 as lp FROM digits WHERE lp<9
),
x(s, ind) AS (
SELECT sud, instr(sud, '.') FROM input
UNION ALL
SELECT
substr(s, 1, ind-1) || z || substr(s, ind+1),
instr( substr(s, 1, ind-1) || z || substr(s, ind+1), '.' )
FROM x, digits AS d
WHERE ind>0
AND NOT EXISTS (
SELECT 1
FROM digits AS lp
WHERE d.z = substr(s, ((ind-1)/9)*9 + lp, 1)
OR d.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)
OR d.z = substr(s, (((ind-1)/3) % 3) * 3
+ ((ind-1)/27) * 27 + lp
+ ((lp-1) / 3) * 6, 1)
)
)
SELECT s FROM x WHERE ind=0;
"""
import time
from datafusion import SessionContext
ctx = SessionContext()
t=time.time();print(ctx.sql(s));print(time.time()-t)+-----------------------------------------------------------------------------------+
| s |
+-----------------------------------------------------------------------------------+
| 387419526259763418641528379716285943594631782823974165472396851135842697968157234 |
| 693875412145632798782194356357421869816957234429368175274519683968743521531286947 |
+-----------------------------------------------------------------------------------+
7.106393575668335
SQLite-3.54 memory-> .read sudomid3.sql
╭─────────────────────────────────────────────────────────────────────────────────────╮
│ s │
╞═════════════════════════════════════════════════════════════════════════════════════╡
│ '693875412145632798782194356357421869816957234429368175274519683968743521531286947' │
│ '387419526259763418641528379716285943594631782823974165472396851135842697968157234' │
╰─────────────────────────────────────────────────────────────────────────────────────╯
Run Time: real 1.201766 user 1.156250 sys 0.031250
Activity
mohamd764 commentedon Oct 28, 2026
I ran this on datafusion 55.0.0 (Python 3.13, 8 cores) and got about 11-12s, while Python's sqlite3 (3.46.1) took about 2s on the same machine.
Looking at the EXPLAIN output, most of the time seems to go into the
digitsCTE. It's recursive too, and it gets inlined twice into the recursive step ofx(once asdand once inside the NOT EXISTS), so it looks like it's re-run on every iteration ofxinstead of being computed once.When I replaced it with a plain list, keeping everything else the same:
the query dropped to about 1.6-2s with the same two solutions, so roughly on par with SQLite. Setting target_partitions to 1 only made a small difference compared to that.
The fix probably belongs in DataFusion core (materializing a CTE that's referenced more than once, or at least a recursive one used inside another recursive CTE), but the VALUES rewrite works as a workaround for now.