質問への回答

質問の歴史

不可分単位の正確な配分の課題は、ハミルトン法のアポーションメントが米国議会の議席で使用されていたことにさかのぼります。ここでは、分数の代表者は不可能で、余剰は公正に分配されなければなりません。SQL では、これは元帳エントリ全体で金額を分割したり、在庫を分配する際に SKU 数を整数でなければならない場合に現れます。初期の解決策は、カーソルや手続き的なループに依存していましたが、これはセットベースのパラダイムに違反しています。現代の ANSI SQL:2003 のウィンドウ関数を使用することで、行ごとの処理なしに数学的な精度を維持する純粋な宣言的キャリーオーバーアルゴリズムを可能にしました。

問題

合計数量 $T$ を $n$ 行に分配するとき、正確な分数シェア $s_1, s_2, ..., s_n$ （ここで $\sum s_i = T$）に対して、個々の行の単純な四捨五入は $\sum \text{round}(s_i) eq T$ となり、蓄積された分数の誤差が生じます。求められるのは、整数 $a_1, a_2, ..., a_n$ を生成することで、$\sum a_i = T$ になるようにしつつ、各行に対して $|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 の予算に正確に一致しなければなりません。

1つのアプローチでは、カーソルを使用して従業員を反復処理し、FLOOR 値を配分し、余剰を次の行に持ち越します。これにより正確性は保証されますが、手続き的コードを必要とし、大規模データセットでは行ごとの処理およびロックによりパフォーマンスが低下します。また、トランザクション管理およびロールバックシナリオを複雑にします。

別のアプローチは、すべての FLOOR 値を計算し、次に余剰が最も大きい上位 $N$ 人の従業員に1セントを追加しようとするサブクエリを使用します。このアプローチはセットベースですが、追加のセントを必要とする行数を決定するために複数のテーブルスキャンおよび複雑な結合が必要で、多くの従業員が同じ分数部分を共有している場合にはブレークポイントで苦労します。

選択された解決策は、ANSI SQL の累積キャリーオーバーメソッドを実装します。正確なシェアの累計を計算し、各ステップでその累積値の FLOOR を取得することにより、システムはその時点で何が正確に配分されるべきかを決定します。連続する累積目標間の差が現在の行の配分を示します。これにより自動的に四捨五入の不一致が吸収されます：最初の従業員が66セントを受け取る場合、0.666の不足が2番目の従業員の累積計算に持ち込まれ、彼らの累積目標を133.333から133に変更し、67セントを与える可能性があります。このアプローチは、給与全体を単一のセットベースのパスで処理し、厳密な ACID 準拠を維持し、配分された合計が正確に $10,000.00$ に等しいことを保証します。

その結果、カーソル方式と比較して処理時間が95%短縮され、四半期の財務監査での調整エラーはゼロになりました。

候補者が見落としがちなこと

なぜ前の累積フロアを現在の累積フロアから引くことで余りを正しく分配できるのか？

候補者はしばしば個々の行の四捨五入誤差を計算し、これを明示的に配分しようとします。この洞察は、FLOOR(cumulative_exact) がその行までの理想的な配分を表すということです。これらの累積目標の差分を取ることにより、「この行が累積合計に何個の新しい全単位を追加するか？」ということを実際に尋ねます。前の行が0.4の余りを残している場合、次の行の0.6のシェアが整数の境界を越え、現在の行が前の行が取得できなかった余分な単位を請求することを可能にします。この暗黙のキャリーオーバーにより、余りを明示的に追跡する必要がなくなります。

このアルゴリズムは負のexact_share値に対してどのように動作し、なぜFLOORがそこでは問題になる可能性があるのか？

ほとんどの候補者は正の値を想定します。負のシェア（例えば、デビットや返品）に対しては、FLOOR がゼロから離れるように丸め（例えば、FLOOR(-1.2) = -2）、負の大きさを誇張します。キャリーオーバーのロジックは数学的にはバランスの取れていますが、「優先順位」のビジネス解釈が変わります—負の配分は予期せぬ「余り」を消費する可能性があります。この解決策では、ビジネスがクレジットに対してゼロへ丸めたい場合を考慮し、TRUNC（ゼロに向かって）またはCEILを負の値に使用する必要があります。堅牢な実装は、正の値にはFLOORを適用し、負の値にはCEILを適用するためにCASE式を使用し、絶対的な偏差を一貫して最小限に抑えます。

最終行の配分が明示的なチェックなしで合計リソースを正確に消費することを保証するのは何ですか？

候補者はオフバイワンエラーを心配します。数学的な保証は、テレコーピング級数の特性から来ます：$\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}$ を正しく取得することを保証し、最終配分がすべての前の行からの残余余りを自動的に吸収することを可能にします。