バンパッキングとバッチ集積の課題は、リレーショナルデータベースよりも前に存在し、オペレーションリサーチや物流最適化に起源を持ちます。ANSI SQLにおいて、この問題は、標準的なセットベースの操作が「リセットされるランニングトータル」をウィンドウフレーム内で参照する能力を欠いていたため、歴史的に手続き的拡張（例：PL/SQLやT-SQLカーソル）なしでは解決できませんでした。SQL:1999での再帰CTEの導入は、反復的な集積の理論的基盤を提供しましたが、多くの実装は当初、大規模データセットに対する性能制限に悩まされていました。現代のクエリオプティマイザは再帰的実行プランを改善し、製造バッチの制御や金融取引のグループ化のための効率的なソリューションを可能にしました。このパターンは、手続き的アルゴリズムを宣言的な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;
文脈：eコマースのフルフィルメントセンターの倉庫パッケージング自動化。
問題の説明：自動コンベヤーシステムは、注文を順次処理しますが、厳密な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の再帰が中間結果を具現化することを理解し、大規模なバッチに対しては重要なメモリを消費する可能性があることを理解する必要があります。候補者は、純粋な再帰よりも数百万行を処理するために小さなチャンクで処理したり、反復的なバッチ処理を使用することで最適化することを言及すべきです。