Задача точного распределения неделимых единиц восходит к методу Гамильтона для распределения мест в Конгрессе США, где дробные представители невозможны, и остатки должны распределяться справедливо. В 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$, и каждый промежуточный шаг поглощает предыдущие ошибки округления.
Система расчёта заработной платы должна распределить ежегодный бонусный фонд в $10,000.00 среди 150 сотрудников на основе коэффициентов производительности. Теоретическая доля каждого сотрудника вычисляется как $66.666...$ долларов, но бухгалтерская система требует целых allocation (целых центров), и сумма должна точно соответствовать бюджету в $10,000.00$ для удовлетворения контрольных требований аудита.
Один из подходов использует курсоры для итерации по сотрудникам, распределяя значение FLOOR и перенося дробный остаток на следующую строку. Это обеспечивает точность, но требует процедурного кода и плохо работает с большими наборами данных из-за обработки построчно и блокировки. Это также усложняет управление транзакциями и сценариями отката.
Другой подход вычисляет все значения FLOOR, затем пытается добавить 1 цент самым верхним $N$ сотрудникам с наибольшими дробными остатками, используя подзапрос ROW_NUMBER(). Хотя этот метод использует работу с множествами, он требует множества сканирований таблицы и сложных соединений для определения, сколько строк нуждаются в дополнительном центре (количество остатков), и испытывает трудности с разрывом привязок, когда многие сотрудники имеют идентичные дробные части.
Выбранное решение реализует метод накопительного переноса ANSI SQL. Рассчитывая текущую сумму точных долей и принимая FLOOR этого кумулятивного значения на каждом шаге, система точно определяет, сколько должно быть распределено на данный момент. Разница между последовательными кумулятивными целями дает распределение текущей строки. Это естественным образом поглощает расхождения в округлении: если первый сотрудник получает 66 центров вместо 66.666, то дефицит 0.666 переносится в кумулятивный расчёт второго сотрудника, потенциально увеличивая их кумулятивную цель с 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 для отрицательных значений в зависимости от того, предпочитает ли бизнес округление к нулю для кредитов. Надёжная реализация использует выражения 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}$, что делает последнее распределение автоматически поглощающим любой остаток от всех предыдущих строк.