용량 제한 배치에 순차 항목을 분할하는 방법을 엄격하게 ANSI SQL을 사용하여 지정하십시오. 각 배치는 누적 임계값을 초과할 때까지 연속 항목을 집계하며, 이는 재귀적 계산을 필요로 합니다.

질문에 대한 답변

질문의 역사

빈 패킹 및 배치 집계의 문제는 관계형 데이터베이스보다 이전에 발생하였으며, 이는 운영 연구 및 물류 최적화에서 유래하였습니다. ANSI SQL에서 이 문제는 전통적으로 PL/SQL 또는 T-SQL 커서와 같은 절차적 확장이 없이는 해결할 수 없었습니다. 표준 집합 기반 작업은 창 프레임 내에서 "재설정된 실행 총합"을 참조하는 능력이 부족하기 때문입니다. SQL:1999에서 재귀적 CTE의 도입은 반복적인 집계를 위한 이론적 기초를 제공하였지만, 많은 구현은 초기에는 대량 데이터세트에서 성능 제한을 겪었습니다. 현대 쿼리 최적화기는 재귀 실행 계획을 개선하여 제조 배치 제어 및 금융 거래 그룹화를 위한 효율적인 솔루션을 가능하게 했습니다. 이 패턴은 절차적 알고리즘을 선언적 ANSI SQL 논리로 변환하는 기본적인 테스트로 남아 있습니다.

문제 설명

우리는 각각의 무게 또는 값을 가진 정렬된 항목 시퀀스를 처리하고, 각 배치의 누적 총합이 미리 정의된 용량을 초과하지 않도록 순차 배치에 할당해야 합니다. 다음 항목을 추가하면 임계값을 초과하게 될 경우 새로운 배치가 시작됩니다. 이는 조건부로 재설정되는 실행 집계를 유지해야 하며, 이 상태 기반 작업은 단순한 창 함수 집계로는 처리할 수 없습니다. 재설정 경계는 최근 재설정 이후 모든 이전 항목의 동적 합계에 따라 달라지기 때문입니다. 솔루션은 개별 용량을 초과하는 항목(오류 또는 단일 항목 초과 배치) 및 빈 입력을 포함한 엣지 케이스를 처리해야 하며, 공급자별 절차적 확장 없이 엄격하게 ANSI SQL 내에서 운영되어야 합니다.

솔루션

우리는 정렬된 시퀀스를 순회하는 재귀적 CTE를 사용하여 현재 배치 번호와 해당 배치의 누적 무게를 전달합니다. 앵커 멤버는 첫 번째 항목을 배치 1로 초기화하고, 해당 무게를 현재 합계로 설정합니다. 재귀 멤버는 다음 순차 항목에 조인하여 그 무게를 추가할 경우 용량을 초과하는지 계산합니다. 만약 초과하면 배치 번호를 증가시키고 누적기를 새 항목의 무게로 재설정합니다. 그렇지 않으면 현재 배치를 유지하고 누적기에 추가합니다. 우리는 **ROW_NUMBER()**를 사용하여 엄격한 탐색 순서를 설정하고 깊이 카운터를 필터링하거나 단지 다음 행과만 조인하여 무한 재귀를 방지합니다. 마지막으로, 우리는 필요에 따라 distinct 배치 할당 또는 집계 결과를 선택합니다.

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의 엄격한 중량 제한을 가진 배송 용기에 그룹화해야 합니다. 각 주문은 가변 무게를 가집니다. 시스템은 각 항목이 도착함에 따라 인쇄해야 할 container 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 재귀가 중간 결과를 물질화하여, 대규모 배치에 대해 상당한 메모리를 소비할 수 있다는 점을 이해하는 것입니다. 후보자들은 수백만 개의 행에 대해 순수 재귀보다는 더 작은 청크로 처리하거나 반복 배치 처리로 최적화하는 것을 언급해야 합니다.