The challenge of bin packing and batch accumulation predates relational databases, originating in operations research and logistics optimization. In ANSI SQL, this problem was historically unsolvable without procedural extensions like PL/SQL or T-SQL cursors because standard set-based operations lack the ability to reference "running totals with reset" within window frames. The introduction of recursive CTEs in SQL:1999 provided the theoretical foundation for iterative accumulation, though many implementations initially suffered from performance limitations on large datasets. Modern query optimizers have improved recursive execution plans, enabling efficient solutions for manufacturing batch controls and financial transaction grouping. This pattern remains a fundamental test of translating procedural algorithms into declarative ANSI SQL logic.
We need to process an ordered sequence of items—each possessing a weight or value—and assign them to sequential batches such that each batch's cumulative total does not exceed a predefined capacity. When adding the next item would breach the threshold, a new batch begins. This requires maintaining a running accumulator that resets conditionally, a stateful operation that defies simple window function aggregation because the reset boundary depends on the dynamic sum of all previous items since the last reset, not just a fixed row offset. The solution must handle edge cases including items exceeding individual capacity (error or single-item overflow batch) and empty inputs, operating strictly within ANSI SQL without vendor-specific procedural extensions.
We employ a recursive CTE that iterates through the ordered sequence, carrying forward the current batch number and the accumulated weight of that batch. The anchor member initializes the first item with batch 1 and its weight as the current sum. The recursive member joins to the next sequential item, calculating whether adding its weight exceeds capacity; if so, it increments the batch number and resets the accumulator to the new item's weight, otherwise it retains the current batch and adds to the accumulator. We use ROW_NUMBER() to establish a strict traversal order and prevent infinite recursion by filtering on a depth counter or by joining only to subsequent rows. Finally, we select the distinct batch assignments or aggregate results as required.
WITH RECURSIVE ordered_items AS ( SELECT item_id, weight, ROW_NUMBER() OVER (ORDER BY sequence_order) AS rn FROM items ), batch_accumulator AS ( -- Anchor: first item starts batch 1 SELECT item_id, weight, rn, 1 AS batch_number, weight AS current_batch_sum FROM ordered_items WHERE rn = 1 UNION ALL -- Recursive: process next item 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;
Context: Warehouse packaging automation for an e-commerce fulfillment center.
Problem description: The automated conveyor system processes orders sequentially but must group them into shipping containers with a strict 20kg weight limit. Each order has a variable weight. The system needs to know which container ID to print on each shipping label as items arrive on the line, without pausing to batch process groups. Early attempts using application-layer code created bottlenecks and race conditions during high-traffic periods.
Different solutions considered:
Solution 1: Application-layer batching with temporary tables. The application would fetch items, calculate running totals in a loop, and insert batches into the database. This approach introduced significant network latency and transaction overhead, requiring multiple round-trips between the app server and database. It also complicated concurrency control when multiple packing lines operated simultaneously, leading to table lock contention.
Solution 2: Pure window function approach using SUM() OVER (ORDER BY ...) with modulo arithmetic. This attempted to create batches by dividing the unbounded running sum by the capacity. However, this incorrectly assigns items to batches based on absolute position rather than the dynamic reset threshold, resulting in batches that consistently exceed capacity when individual items have varying weights. The modulo approach only works for fixed-size items, making it unsuitable for the variable-weight requirement.
Solution 3: Recursive CTE implemented within ANSI SQL. This solution performs all calculation server-side in a single query execution, eliminating network overhead. It correctly handles the stateful accumulation and reset logic by iteratively processing the ordered stream. While recursion depth limits exist in some database configurations, the warehouse's operational constraints (batches rarely exceeding 100 items) ensured this would not breach platform limits. This approach was selected for its atomicity, consistency, and elimination of application state management.
Result: The query successfully processed 50,000 items per hour with sub-second latency, correctly assigning container IDs while respecting weight constraints. The solution eliminated race conditions and reduced infrastructure costs by removing the need for a separate batching microservice.
1. How do you handle the first item correctly when it individually exceeds the batch capacity?
Many candidates assume all items fit within capacity. When an individual item's weight exceeds the batch threshold, the recursive logic must either flag an error or place it in an isolated overflow batch. The correct implementation adds a CASE statement in the anchor member to check initial capacity, and in the recursive member to force a new batch when oi.weight > capacity, regardless of current sum. Without this, the system might attempt to add oversized items to existing batches or create infinite recursion by trying to split items.
2. Why does joining on rn = rn + 1 risk infinite recursion, and how do you prevent it?
Candidates frequently use oi.rn = ba.rn + 1 assuming strict sequentiality, but if the source data contains gaps or the ROW_NUMBER() ordering produces duplicates due to non-unique sort keys, the join might create cycles or skip rows. Additionally, if the data contains circular references in the sequence definition, recursion never terminates. The solution requires ensuring sequence_order is deterministic and unique, and adding a depth counter column that increments with each recursion level, including a CHECK constraint or WHERE clause depth < 1000 to prevent runaway queries during data corruption.
3. What are the performance implications of recursion depth versus breadth in this algorithm?
Junior developers often treat recursive CTEs as iterative loops, not recognizing that each recursion level processes all eligible rows at that depth (breadth-first). They miss that without proper indexing on rn, the join oi.rn = ba.rn + 1 results in nested loop operations that scale quadratically. The correct approach requires ensuring the sequence column is indexed and understanding that ANSI SQL recursion materializes intermediate results, potentially consuming significant memory for large batches. Candidates should mention optimizing by processing in smaller chunks or using iterative batch processing for millions of rows rather than pure recursion.