Wyzwanie dokładnego przydziału z niepodzielnymi jednostkami sięga metody Hamiltona przydzielania miejsc w Kongresie USA, gdzie ułamkowe przedstawicielstwo jest niemożliwe, a reszty muszą być sprawiedliwie rozdzielane. W SQL manifestuje się to, gdy dzieli się kwoty pieniężne między wpisami w księdze rachunkowej lub rozdziela zapasy, gdzie liczby SKU muszą być liczbami całkowitymi. Wczesne rozwiązania polegały na kursorach lub pętlach proceduralnych, łamiąc paradygmat oparte na zbiorach. Nowoczesne funkcje okien w ANSI SQL:2003 umożliwiły czysto deklaratywne algorytmy przeniesienia, które zachowują precyzję matematyczną bez przetwarzania wiersz po wierszu.
Podczas dzielenia całkowitej ilości $T$ na $n$ wierszy z dokładnymi ułamkowymi udziałami $s_1, s_2, ..., s_n$ (gdzie $\sum s_i = T$), proste zaokrąglanie poszczególnych wierszy daje $\sum \text{round}(s_i) eq T$ z powodu nagromadzonych błędów ułamkowych. Wymagana jest produkcja liczb całkowitych $a_1, a_2, ..., a_n$ takie, że $\sum a_i = T$ dokładnie, minimalizując odchylenie $|a_i - s_i|$ dla każdego wiersza. Algorytm musi szanować określoną kolejność priorytetów (np. seniorność, znacznik czasu transakcji), aby deterministycznie zdecydować, które wiersze otrzymują wartość sufitową, gdy istnieją ułamkowe reszty.
Wykorzystaj kumulacyjne funkcje okien, aby obliczyć docelowy kumulacyjny przydział na każdym etapie jako $\text{floor}(\sum_{j=1}^{i} s_j)$. Przydział dla wiersza $i$ to różnica między aktualnym docelowym kumulacyjnym a poprzednim docelowym kumulacyjnym: $a_i = \text{floor}(\text{cum}i) - \text{floor}(\text{cum}{i-1})$. To skutecznie przenosi wszelkie deficyty zaokrągleń z wcześniejszych wierszy do obliczenia bieżącego wiersza.
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;
To zapewnia, że końcowe $\text{cum_target}$ równa się $T$, a każdy etap pośredni absorbuje wcześniejsze błędy zaokrągleń.
System płacowy musi rozdzielić pulę premii rocznej $10,000.00 pomiędzy 150 pracowników na podstawie współczynników wydajności. Teoretyczny udział każdego pracownika oblicza się na wartości takie jak $66.666...$ dolarów, ale system księgowy wymaga całkowitych alokacji (całkowitych centów), a suma musi dokładnie odpowiadać budżetowi $10,000.00, aby spełnić wymogi audytowe.
Jednym z podejść jest użycie kursora do iteracji przez pracowników, alokując wartość FLOOR i przenosząc ułamkową resztę do następnego wiersza. To zapewnia dokładność, ale wymaga kodu proceduralnego i słabo działa z dużymi zestawami danych z powodu przetwarzania wiersz po wierszu i blokowania. Utrudnia to również zarządzanie transakcjami i scenariusze wycofywania.
Inne podejście oblicza wszystkie wartości FLOOR, a następnie stara się dodać 1 centa do najlepszych $N$ pracowników z największymi ułamkowymi resztami za pomocą podzapytania ROW_NUMBER(). Choć jest oparte na zbiorach, wymaga wielu skanów tabel i złożonych złączy, aby określić, ile wierszy potrzebuje dodatkowego centa (liczba reszt), i ma problemy z łamaniem remisu, gdy wielu pracowników dzieli identyczne części ułamkowe.
Wybrane rozwiązanie implementuje metodę przeniesienia przewidywaną w ANSI SQL. Obliczając bieżącą sumę dokładnych udziałów i biorąc FLOOR tej kumulacyjnej wartości na każdym kroku, system dokładnie określa, ile powinno być rozdzielone do tego momentu. Różnica między kolejnymi docelowymi kumulacyjnymi daje przydział dla bieżącego wiersza. To naturalnie absorbuje nieścisłości w zaokrągleniu: jeśli pierwszy pracownik otrzymuje 66 centów zamiast 66.666, deficyt 0.666 przenosi się do kumulacyjnego obliczenia drugiego pracownika, potencjalnie przesuwając ich kumulacyjny cel z 133.333 do 133, dając im 67 centów. To podejście przetwarza cały budżet płac w jednym przejściu opartym na zbiorach, utrzymuje ścisłą zgodność z ACID i gwarantuje, że całkowity przydział wynosi dokładnie $10,000.00.
Efekt był 95% redukcji czasu przetwarzania w porównaniu z metodą kursorową i zero błędów uzgodnienia podczas kwartalnego audytu finansowego.
Dlaczego odejmowanie poprzedniego kumulacyjnego floor od aktualnego kumulacyjnego floor poprawnie przydziela resztę?
Kandydaci często próbują obliczyć błędy zaokrągleń poszczególnych wierszy, a następnie rozdzielić je explicite. Wnikliwość polega na tym, że FLOOR(cumulative_exact) reprezentuje idealny całkowity przydział do tego wiersza, gdybyśmy mogli tylko przydzielać całe jednostki. Poprzez różnicowanie tych kumulacyjnych celów, skutecznie pytamy "ile nowych całkowitych jednostek ten wiersz wprowadza do kumulacyjnego całkowitego?" Jeśli wcześniejsze wiersze zostawiły 0.4 resztę, udział 0.6 następnego wiersza przesuwa kumulacyjną frakcję poza granicę całkowitą, pozwalając bieżącemu wierszowi zgarnąć dodatkową jednostkę, której poprzedni wiersz nie mógł. To niejawne przeniesienie eliminuje potrzebę śledzenia reszt explicite.
Jak zachowuje się ten algorytm przy ujemnych wartościach exact_share i dlaczego FLOOR może być problematyczny w tym przypadku?
Większość kandydatów zakłada wartości dodatnie. W przypadku ujemnych udziałów (np. debety lub zwroty), FLOOR zaokrągla w stronę zera (np. FLOOR(-1.2) = -2), co nadmiernie zwiększa ujemną wielkość. Logika przeniesienia wciąż matematycznie się równoważy, ale interpretacja biznesowa „priorytetu” się zmienia - ujemne alokacje mogą nieoczekiwanie konsumować „resztę”. Rozwiązanie wymaga użycia TRUNC (w kierunku zera) lub CEIL dla wartości ujemnych, w zależności od tego, czy biznes woli zaokrąglanie w kierunku zera dla kredytów. Solidna implementacja używa wyrażeń CASE, aby zastosować FLOOR dla wartości dodatnich i CEIL dla wartości ujemnych, zapewniając, że całkowite odchylenie jest niezawodnie minimalizowane.
Co zapewnia, że przydział ostatniego wiersza dokładnie wyczerpuje całkowity zasób bez explicite sprawdzania?
Kandydaci martwią się o błędy o jeden. Matematyczna gwarancja pochodzi z właściwości serii teleskopowej: $\sum_{i=1}^{n} (T_i - T_{i-1}) = T_n - T_0$, gdzie $T_i = \text{FLOOR}(\sum_{j=1}^{i} s_j)$ i $T_0 = 0$. Ponieważ $T_n = \text{FLOOR}(\sum_{j=1}^{n} s_j) = \text{FLOOR}(T) = T$ (zakładając, że $T$ jest liczbą całkowitą), suma wszystkich różnic musi równać się $T$. Ramka okna ANSI SQL zapewnia, że funkcja LAG poprawnie pobiera $T_{i-1}$, co sprawia, że ostatni przydział automatycznie absorbuje wszelkie pozostałe reszty ze wszystkich wcześniejszych wierszy.