DuckDB递归SQL无限循环问题：带重置条件的累积求和优化

问题描述 #

我在DuckDB中编写递归SQL，计算带重置条件（当前一次累积和≥30时重置，或当前val≥30时重置）的累积和：

• Code 1实现了功能，但处理数千条记录时速度极慢；
• 尝试Code 2做批量递归优化，却出现无限循环（或运行时间远超预期）；
  Code 2的思路是：

1. 过滤ref表，排除已加入CTE的行；
2. 对剩余行计算累积和，筛选出前n-1行累积和≤30的记录；
3. 将符合条件的行合并到CTE，重复操作。
   单独调试各子查询均正常，但整体运行异常。

相关代码 #

library(data.table)
library(duckdb)

ref <- data.table(
  idx  = c(1:20)
  ,val = c(1,2,5,5,5,15,15,15,31,3,25,10,29,0,0,9,4,8,8,10)
)

con <- dbConnect(duckdb())
dbWriteTable(con, "ref", ref, overwrite=T)

### Code 1：逐行递归实现（功能正确但性能差）
code_1 <- dbGetQuery(con, paste0("
    WITH 
      RECURSIVE cte as (
                          SELECT
                            idx
                            ,val
                            ,val AS c_val
                          FROM
                            ref
                          WHERE
                            idx = 1
    
                          UNION ALL
    
                          SELECT
                            ref.idx
                            ,ref.val
                            ,(CASE WHEN ref.val + cte.c_val >= 30 + ref.val THEN ref.val
                                                                            ELSE ref.val + cte.c_val
                              END) AS c_val
                          FROM
                            cte
                            JOIN
                            ref ON ref.idx = cte.idx + 1
                       )
      SELECT * FROM cte
 "))

### Code 2：批量递归尝试（出现无限循环/逻辑错误）
code_2 <- dbGetQuery(con, paste0("
    WITH 
      RECURSIVE cte as (
        SELECT
           0 AS idx
          ,0 AS val
          ,0 AS c_val

        UNION ALL

        SELECT
           idx
          ,val
          ,c_val
        FROM
          (
            SELECT
              *
            FROM
              (
                SELECT
                  * 
                  ,SUM(val) OVER (ORDER BY idx) AS c_val
                  ,c_val-val                    AS c_val_adj
                FROM
                  (
                    SELECT
                       idx
                      ,val
                    FROM
                      ref
                    WHERE
                      idx NOT IN (SELECT idx FROM cte)
                  )
              )
            WHERE
              c_val_adj <= 30
          )
     )
                       
  SELECT * FROM cte
 "))

Code 2无限循环/性能问题的原因 #

1. 累积和逻辑错误：
   窗口函数SUM(val) OVER (ORDER BY idx)计算的是剩余所有行的全局累积和，而非从重置点开始的局部累积和，导致c_val结果不符合预期，同时每次递归都需要重新计算剩余行的全局累积，性能没有提升。
2. 递归次数过多：
   每次递归仅筛选出部分符合条件的行，当数据量较大时，递归次数会呈线性增长，导致运行时间极长，看起来像无限循环。
3. 初始行冗余：
   初始CTE行(0,0,0)没有实际作用，反而增加了筛选逻辑的复杂度。

高效替代方案：非递归窗口函数实现 #

对于带重置的累积和，无需使用递归，通过计算重置分组ID即可高效实现，性能远优于递归：

WITH reset_groups AS (
    SELECT
        idx,
        val,
        -- 计算每个位置的重置分组：每次前一次累积和≥30或当前val≥30时，分组ID递增
        SUM(CASE WHEN COALESCE(LAG(c_val) OVER (ORDER BY idx), 0) >= 30 OR val >=30 THEN 1 ELSE 0 END) 
        OVER (ORDER BY idx ROWS UNBOUNDED PRECEDING) AS group_id
    FROM (
        -- 先计算带重置的累积和，用于下一行判断
        SELECT
            idx,
            val,
            CASE 
                WHEN COALESCE(LAG(raw_c_val) OVER (ORDER BY idx), 0) >=30 OR val>=30 
                THEN val 
                ELSE raw_c_val - COALESCE(SUM(CASE WHEN LAG(raw_c_val) OVER (ORDER BY idx)>=30 THEN val ELSE 0 END) OVER (ORDER BY idx), 0)
            END AS c_val,
            SUM(val) OVER (ORDER BY idx) AS raw_c_val
        FROM ref
    ) t
)
-- 每个分组内计算累积和，得到最终结果
SELECT
    idx,
    val,
    SUM(val) OVER (PARTITION BY group_id ORDER BY idx) AS c_val
FROM reset_groups
ORDER BY idx;

批量递归的正确写法（可选） #

如果坚持使用递归，可改为每次批量处理一个完整的重置组，减少递归次数：

WITH RECURSIVE cte AS (
    -- 初始组：从第一个idx开始，计算累积和直到需要重置
    SELECT
        idx,
        val,
        val AS c_val,
        idx AS last_idx
    FROM ref
    WHERE idx = 1

    UNION ALL

    -- 下一个组：从上一个组的最后idx+1开始，计算累积和直到需要重置
    SELECT
        ref.idx,
        ref.val,
        SUM(ref.val) OVER (ORDER BY ref.idx) AS c_val,
        MAX(ref.idx) OVER () AS last_idx
    FROM ref
    JOIN cte ON ref.idx > cte.last_idx
    WHERE SUM(ref.val) OVER (ORDER BY ref.idx ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) < 30 
          AND ref.val < 30
)
SELECT idx, val, c_val FROM cte ORDER BY idx;

内容的提问来源于stack exchange，提问作者ohwaitwhatohok