问题的答案

问题历史

箱包问题和批量累积的挑战早于关系数据库，起源于运筹学和物流优化。在 ANSI SQL 中，这个问题在没有过程扩展（如 PL/SQL 或 T-SQL 游标）时历史上是无法解决的，因为标准的集合操作缺乏引用“带重置的运行总数”的能力。递归 CTE 在 SQL:1999 中的引入为迭代累积提供了理论基础，尽管许多实现最初在大型数据集上性能有限。现代查询优化器改善了递归执行计划，使制造批次控制和金融交易分组的高效解决方案成为可能。这一模式仍然是将过程算法转换为声明式 ANSI SQL 逻辑的基本测试。

问题描述

我们需要处理有序的项目序列——每个项目都有一个重量或价值——并将它们分配到顺序批次，使每个批次的累计总数不超过预定义的容量。当添加下一个项目会突破阈值时，新的批次开始。这需要维护一个有条件重置的运行累加器，这是一种状态操作，违反了简单窗口函数聚合的原则，因为重置边界取决于上一次重置以来所有先前项目的动态总和，而不仅仅是固定的行偏移。解决方案必须处理包括超出单项容量的项目（错误或单一项溢出批次）和空输入的边缘情况，严格在 ANSI SQL 以内操作，而不使用特定于供应商的过程扩展。

解决方案

我们采用递归 CTE 在有序序列中迭代，向前传递当前批次编号和该批次的累计重量。锚定成员用批次 1 初始化第一个项目及其重量作为当前总和。递归成员连接下一个顺序项目，计算添加其重量是否超过容量；如果是，则递增批次编号并将累加器重置为新项目的重量，否则保留当前批次并将其添加到累加器。我们使用 ROW_NUMBER() 来建立严格的遍历顺序，并通过过滤深度计数器或仅连接后续行来防止无限递归。最后，我们根据需要选择不同的批次分配或聚合结果。

WITH RECURSIVE ordered_items AS (
    SELECT 
        item_id, 
        weight, 
        ROW_NUMBER() OVER (ORDER BY sequence_order) AS rn
    FROM items
),
batch_accumulator AS (
    -- 锚定：第一个项目开始批次 1
    SELECT 
        item_id, 
        weight, 
        rn, 
        1 AS batch_number, 
        weight AS current_batch_sum
    FROM ordered_items
    WHERE rn = 1
    
    UNION ALL
    
    -- 递归：处理下一个项目
    SELECT 
        oi.item_id,
        oi.weight,
        oi.rn,
        CASE 
            WHEN ba.current_batch_sum + oi.weight > 100 THEN ba.batch_number + 1 
            ELSE ba.batch_number 
        END AS batch_number,
        CASE 
            WHEN ba.current_batch_sum + oi.weight > 100 THEN oi.weight 
            ELSE ba.current_batch_sum + oi.weight 
        END AS current_batch_sum
    FROM batch_accumulator ba
    JOIN ordered_items oi ON oi.rn = ba.rn + 1
)
SELECT item_id, batch_number, weight
FROM batch_accumulator
ORDER BY rn;

生活中的情况

背景：电子商务履行中心的仓库包装自动化。

问题描述：自动化输送系统按顺序处理订单，但必须将它们分组到具有严格 20kg 重量限制的运输容器中。每个订单具有可变的重量。系统需要知道在每个运输标签上打印哪个容器 ID，以便在物品到达生产线时识别，而不需要暂停以批量处理组。在高流量期间，早期使用应用程序层代码的尝试造成了瓶颈和竞争条件。

考虑的不同解决方案：

解决方案 1：使用临时表进行应用层批处理。应用程序会获取项目，在循环中计算运行总数，并将批次插入到数据库中。这种方法引入了显著的网络延迟和事务开销，需要在应用服务器和数据库之间进行多次往返。此外，当多个打包线同时运作时，它还使并发控制复杂化，导致表锁争用。

解决方案 2：使用 SUM() OVER (ORDER BY ...) 的纯窗口函数方法，结合模运算。这试图通过将无限运行总和除以容量来创建批次。然而，这种方法不正确地根据绝对位置而不是动态重置阈值将项目分配到批次，导致当单个项目具有不同重量时，批次持续超过容量。模运算方法仅适用于固定大小的项目，因此不适合可变重量的要求。

解决方案 3：在 ANSI SQL 中实现递归 CTE。此解决方案在单个查询执行中执行所有计算，消除了网络开销。它通过迭代处理有序流正确处理状态累积和重置逻辑。虽然某些数据库配置中存在递归深度限制，但仓库的操作约束（批次很少超过 100 项）确保不会超出平台限制。此方法因其原子性、一致性和消除了应用程序状态管理而被选中。

结果：该查询以每小时处理 50,000 项的速度成功运行，延迟低于一秒，正确分配容器 ID，同时遵守重量限制。该解决方案消除了竞争条件，并通过消除对单独批处理微服务的需求降低了基础设施成本。

候选人常常遗漏的内容

1. 如何正确处理第一个项目，当它单独超过批次容量时？

许多候选人假设所有项目都符合容量。当单个项目的重量超过批次阈值时，递归逻辑必须标记错误或将其放入一个孤立的溢出批次。正确的实现需要在锚定成员中添加一个 CASE 语句，以检查初始容量，并在递归成员中强制在 oi.weight > capacity 时创建一个新批次，不管当前总和如何。如果没有这一点，系统可能会尝试将超重项目添加到现有批次中，或者通过尝试拆分项目来创建无限递归。

2. 为什么在 rn = rn + 1 上连接存在无限递归的风险，以及如何防止它？

候选人经常使用 oi.rn = ba.rn + 1 假设严格的顺序性，但如果源数据存在间隙，或者 ROW_NUMBER() 排序由于非唯一排序键而产生重复项，连接可能会创建循环或跳过行。此外，如果数据在序列定义中包含循环引用，递归将永远无法终止。解决方案需要确保 sequence_order 是确定且唯一的，并添加一个深度计数器列，该列在每一递归级别上递增，包括 CHECK 约束或 WHERE 子句 depth < 1000 以防止在数据损坏期间查询失控。

3. 这种算法的递归深度与广度的性能影响是什么？

初级开发人员往往将递归 CTE 视为迭代循环，而未认识到每个递归级别处理该深度下所有适用行（广度优先）。他们忽略了在没有对 rn 进行适当索引的情况下，连接 oi.rn = ba.rn + 1 会导致嵌套循环操作，导致性能呈二次方扩展。正确的方法需要确保序列列被索引，并理解 ANSI SQL 递归会生成中间结果，这可能在处理大批次时消耗大量内存。候选人应该提到通过处理较小的块或使用迭代批处理来优化数百万行，而不是纯递归。