Tracking: Recursive CTE result may be random

[KKould]

Search before asking

• I had searched in the issues and found no similar issues.

Version

bff4f81

What's Wrong?

The jobs where the problem occurred:

• https://github.com/databendlabs/databend/actions/runs/21581558958/job/62182108377 2026/02/02
• https://github.com/databendlabs/databend/actions/runs/21617417183/job/62300995492 2026/02/03
• https://github.com/databendlabs/databend/actions/runs/21629058211/job/62339470706 2026/02/03

This issue only started after #19373

It was first discovered in #19212, where it was believed to have been fixed. However, in recent CI runs, the problem of occasional non-deterministic (random) results still persists.

This issue is currently difficult to reproduce locally and via CI. A pull request attempted to reproduce it but failed: #19391

How to Reproduce?

No response

Are you willing to submit PR?

• Yes I am willing to submit a PR!

[l1t1]

I run the sql in duckdb, it reports

WITH RECURSIVE aoc10_input(i) AS (SELECT '\n89010123\n78121874\n87430965\n96549874\n45678903\n32019012\n01329801\n10456732\n'), lines(y, line, rest) AS (SELECT 0::UInt64, substr(i, 1, position('\n' IN i) - 1), substr(i, position('\n' IN i) + 1) FROM aoc10_input UNION ALL SELECT y + 1::UInt64, substr(rest, 1, position('\n' IN rest) - 1), substr(rest, position('\n' IN rest) + 1) FROM lines WHERE position('\n' IN rest) > 0), field(x, y, v) AS (SELECT x::UInt64 AS x, y, (ascii(substr(line, x::Int64, 1)) - 48)::UInt64 AS v FROM (SELECT * FROM lines l WHERE line <> '') s, LATERAL generate_series(1, length(line)) g(x)), paths(x, y, v, sx, sy) AS (SELECT x, y, 9::UInt64, x, y FROM field WHERE v = 9 UNION ALL SELECT f.x, f.y, f.v, p.sx, p.sy FROM field f JOIN paths p ON f.v = p.v - 1 AND p.v > 0 AND ((f.x = p.x AND abs(f.y - p.y) = 1) OR (f.y = p.y AND abs(f.x - p.x) = 1))), results AS (SELECT * FROM paths WHERE v = 0), part1 AS (SELECT DISTINCT * FROM results) SELECT (SELECT count(*) FROM part1) AS part1, (SELECT count(*) FROM results) AS part2;
--duckdb
--Out of Range Error:
--Overflow in subtraction of UINT64 (3 - 4)!

[l1t1]

If replace all '\n to E'\n, and then replace all abs with case when expression, it works

WITH RECURSIVE aoc10_input(i) AS (SELECT E'\n89010123\n78121874\n87430965\n96549874\n45678903\n32019012\n01329801\n10456732\n'), 
lines(y, line, rest) AS (
  SELECT 0::UInt64, substr(i, 1, position(E'\n' IN i) - 1), substr(i, position(E'\n' IN i) + 1) FROM aoc10_input 
   UNION ALL 
  SELECT y + 1::UInt64, substr(rest, 1, position(E'\n' IN rest) - 1), substr(rest, position(E'\n' IN rest) + 1) FROM lines WHERE position(E'\n' IN rest) > 0), 
field(x, y, v) AS (SELECT x::UInt64 AS x, y, (ascii(substr(line, x::Int64, 1)) - 48)::UInt64 AS v FROM (SELECT * FROM lines l WHERE line <> '') s, LATERAL generate_series(1, length(line)) g(x)), 
paths(x, y, v, sx, sy) AS (SELECT x, y, 9::UInt64, x, y FROM field WHERE v = 9 
   UNION ALL
 SELECT f.x, f.y, f.v, p.sx, p.sy FROM field f JOIN paths p ON f.v = p.v - 1 AND p.v > 0 AND ((f.x = p.x AND case when f.y >= p.y then f.y - p.y else p.y - f.y end = 1) OR (f.y = p.y AND case when f.x >= p.x then f.x - p.x else p.x - f.x end = 1))), 
results AS (SELECT * FROM paths WHERE v = 0), 
part1 AS (SELECT DISTINCT * FROM results) 
SELECT (SELECT count(*) FROM part1) AS part1, (SELECT count(*) FROM results) AS part2;

[KKould]

What you're actually describing is part of this SQL issue: checking for uint64 overflow, but it's not the core problem of this issue. This issue can now be fixed, but you could try submitting another pull request to align with DuckDB's behavior.
BTW, thank you for the correction. @l1t1