불가분 단위의 정확한 할당 문제는 미국 의회 의석 배분에 사용되는 해밀턴 방법으로 거슬러 올라갑니다. 여기서는 분수 대표가 불가능하고 나머지를 공정하게 분배해야 합니다. SQL에서는 금전적 금액을 원장 항목에 분할하거나 재고를 분배할 때, SKU 수가 정수여야 할 때 이러한 문제가 발생합니다. 초기 솔루션은 커서나 프로시저 루프에 의존하여 집합 기반 패러다임을 위반하였습니다. 현대의 ANSI SQL:2003 윈도우 함수는 행별 처리가 아닌 수학적으로 정확성을 유지하는 순수 선언적 이월 알고리즘을 가능하게 했습니다.
정확한 분수 할당 $s_1, s_2, ..., s_n$ (여기서 $\sum s_i = T$)로 $n$개의 행에 총량 $T$를 나누면, 단순한 반올림으로 인한 개별 행의 합이 $\sum \text{round}(s_i) eq T$로 발생하는 누적 반올림 오류가 원인이 됩니다. 요구사항은 각 행에 대하여 $\sum a_i = T$를 정확히 만족하도록 하는 정수 $a_1, a_2, ..., a_n$를 생성하는 것이며, 각 행의 편차 $|a_i - s_i|$를 최소화해야 합니다. 이 알고리즘은 우선순위 순서(예: 연공서열, 거래 타임스탬프)를 존중하여분수 잔여물이 있는 경우 어떤 행이 올림 값을 받을 지를 결정해야 합니다.
누적 윈도우 함수를 활용하여 각 단계에서의 목표 누적 할당을 $\text{floor}(\sum_{j=1}^{i} s_j)$로 계산합니다. 행 $i$의 할당은 현재 목표 누적과 이전 목표 누적의 차이입니다: $a_i = \text{floor}(\text{cum}i) - \text{floor}(\text{cum}{i-1})$. 이는 이전 행의 반올림 부족분을 현재 행의 계산으로 가져옵니다.
WITH allocations AS ( SELECT id, priority, exact_share, SUM(exact_share) OVER (ORDER BY priority) AS cum_exact, FLOOR(SUM(exact_share) OVER (ORDER BY priority)) AS cum_target FROM distribution_queue ) SELECT id, priority, exact_share, (cum_target - COALESCE(LAG(cum_target) OVER (ORDER BY priority), 0)) AS allocated_units FROM allocations;
이것은 최종 $\text{cum_target}$이 $T$와 같도록 보장하며, 모든 중간 단계가 이전의 반올림 오류를 흡수합니다.
급여 시스템은 성과 비율에 따라 150명의 직원에게 $10,000.00의 연간 보너스 풀을 분배해야 합니다. 각 직원의 이론적인 배당은 $66.666...$달러로 계산되지만 회계 시스템은 정수 센트로 할당해야 하며 합이 $10,000.00 예산과 정확히 일치해야 합니다.
한 가지 접근법은 커서를 사용하여 직원들을 반복하며 FLOOR 값을 할당하고 나머지 분수를 다음 행으로 이월하는 것입니다. 이는 정확성을 보장하지만 절차적 코드가 필요하고 대량 데이터 세트에서 행단위 처리 및 잠금으로 인해 성능이 저하됩니다. 또한 거래 관리 및 롤백 시나리오를 복잡하게 만듭니다.
또 다른 접근법은 모든 FLOOR 값을 계산한 다음 가장 큰 분수 나머지를 가진 상위 $N$명의 직원에게 1센트를 추가하는 ROW_NUMBER() 서브쿼리를 시도합니다. 이는 집합 기반이지만 추가 센트가 필요한 행의 수(잔여 수)를 결정하기 위해 여러 테이블 스캔 및 복잡한 조인이 필요하며, 많은 직원들이 동일한 분수 부분을 공유할 때 동점 처리가 어려워집니다.
선택된 솔루션은 ANSI SQL 누적 이월 방법을 구현합니다. 정확한 배당량의 누적 합을 계산하고 각 단계에서 해당 누적 값의 FLOOR를 취하여 시스템이 그 시점까지 얼마나 분배되었어야 하는지를 결정합니다. 연속적인 누적 목표 간의 차이는 현재 행의 할당을 제공합니다. 이렇게 하면 반올림 불일치가 자연으로 흡수됩니다: 첫 번째 직원이 66.666을 대신해 66센트를 받으면 0.666의 부족이 두 번째 직원의 누적 계산으로 이월되며, 이로 인해 그들의 누적 목표가 133.333에서 133으로 변경되어 67센트를 받게 됩니다. 이 접근법은 전체 급여를 단일 집합 기반 패스로 처리하고 엄격한 ACID 준수를 유지하며 총 배분이 정확히 $10,000.00가 되도록 보장합니다.
결과적으로, 커서 방법과 비교하여 처리 시간이 95% 감소하였으며 분기 재무 감사 중 0개의 조정 오류가 발생했습니다.
왜 현재 누적 바닥에서 이전 누적 바닥을 빼는 것이 나머지를 올바르게 분배합니까?
후보들은 종종 개별 행 반올림 오류를 계산하고 이를 명시적으로 분배하려고 시도합니다. 통찰력은 **FLOOR(cumulative_exact)**가 정수 단위만 할당할 수 있다면 해당 행까지의 이상적인 총 할당을 나타낸다는 것입니다. 이러한 누적 목표 간의 차이를 내면 우리는 "이 행이 누적 총액에 도입한 새로운 전체 단위의 수는 얼마입니까?"라고 묻는 것입니다. 이전 행이 0.4의 나머지를 남겼다면, 다음 행의 0.6 분배는 누적 비율을 정수 경계를 초과하게 하여 현재 행이 이전 행이 할 수 없었던 추가 단위를 주장할 수 있습니다. 이 암묵적인 이월은 나머지를 명시적으로 추적할 필요성을 제거합니다.
이 알고리즘이 부정적인 exact_share 값에서 어떻게 작동하며 FLOOR가 그곳에서 문제가 될 수 있는 이유는 무엇입니까?
대부분의 후보들은 양수 값을 가정합니다. 부정적인 분배(예: 차감액 또는 반품)의 경우, FLOOR는 0에서 멀어지는 방식으로 반올림합니다(예: FLOOR(-1.2) = -2), 이는 부정적인 크기를 과장하게 만듭니다. 이월 로직은 여전히 수학적으로 균형을 잡지만 "우선 순위"의 비즈니스 해석이 바뀌어 부정적인 배당금이 예상치 못하게 "잔여"를 소비할 수 있습니다. 이 솔루션은 비즈니스가 크레딧을 위해 0으로 반올림하는 것을 선호하는지에 따라 부정적 값에 대해 TRUNC(0으로 향함) 또는 CEIL을 사용하는 것을 요구합니다. 강력한 구현은 CASE 표현식을 사용하여 양수에 대해 FLOOR를, 부정적에 대해 CEIL을 적용하여 절대 편차가 지속적으로 최소화되도록 합니다.
정확히 자원의 총 할당이 마지막 행의 할당이 명시적 검사를 통해 어떻게 보장됩니까?
후보들은 오프 바이 원 오류에 대해 걱정합니다. 수학적 보장은 맹렬한 수열 속성에서 기인합니다: $\sum_{i=1}^{n} (T_i - T_{i-1}) = T_n - T_0$, 여기서 $T_i = \text{FLOOR}(\sum_{j=1}^{i} s_j)$ 그리고 $T_0 = 0$. $T_n = \text{FLOOR}(\sum_{j=1}^{n} s_j) = \text{FLOOR}(T) = T$ (여기서 $T$가 정수라고 가정)임으로, 모든 차의 합은 $T$와 같아야 합니다. ANSI SQL 윈도우 프레임은 LAG 함수가 올바르게 $T_{i-1}$을 검색하도록 보장하여 마지막 할당이 자동적으로 모든 이전 행의 잔여를 흡수하게 합니다.