Die Herausforderung der genauen Verteilung mit unteilbaren Einheiten geht auf die Hamilton-Methode der Verteilung zurück, die für die US-Kongresssitze verwendet wird, wo fraktionale Vertreter unmöglich sind und Reste fair verteilt werden müssen. In SQL zeigt sich dies, wenn Geldbeträge über Buchungseinträge aufgeteilt oder Bestände verteilt werden, wo SKU-Zahlen ganze Zahlen sein müssen. Frühe Lösungen beruhten auf Cursors oder prozeduralen Schleifen, die das set-basierte Paradigma verletzten. Moderne ANSI SQL:2003 Fensterfunktionen ermöglichten rein deklarative Übertragungsalgorithmen, die mathematische Präzision ohne zeilenweise Verarbeitung aufrechterhalten.
Wenn eine Gesamtsumme $T$ auf $n$ Zeilen mit genauen Bruchteilen $s_1, s_2, ..., s_n$ (wo $\sum s_i = T$) verteilt wird, ergeben einfache Rundungen der einzelnen Zeilen $\sum \text{round}(s_i) eq T$ aufgrund angesammelter fraktionaler Fehler. Die Anforderung ist, ganze Zahlen $a_1, a_2, ..., a_n$ zu produzieren, sodass $\sum a_i = T$ genau, während die Abweichung $|a_i - s_i|$ für jede Zeile minimiert wird. Der Algorithmus muss eine definierte Prioritätsreihenfolge (z.B. Dienstalter, Transaktionszeitstempel) respektieren, um determiniert zu entscheiden, welche Zeilen den Deckungswert erhalten, wenn fraktionale Überreste vorhanden sind.
Verwenden Sie kumulative Fensterfunktionen, um die angestrebte kumulative Zuweisung bei jedem Schritt als $\text{floor}(\sum_{j=1}^{i} s_j)$ zu berechnen. Die Zuweisung für Zeile $i$ ist die Differenz zwischen der aktuellen Zielkumulativen und der vorherigen Zielkumulativen: $a_i = \text{floor}(\text{cum}i) - \text{floor}(\text{cum}{i-1})$. Dies trägt effektiv jedes Rundungsdefizit von vorherigen Zeilen in die Berechnung der aktuellen Zeile voran.
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;
Dies garantiert, dass das endgültige $\text{cum_target}$ gleich $T$ ist und jeder Zwischenschritt vorherige Rundungsfehler absorbiert.
Ein Gehaltsabrechnungssystem muss einen jährlichen Bonuspool von $10,000.00 unter 150 Mitarbeitern basierend auf Leistungsquoten verteilen. Der theoretische Anteil jedes Mitarbeiters wird auf Werte wie $66.666...$ Dollar berechnet, aber das Buchhaltungssystem erfordert die Zuweisung ganzer Cents (ganzzahlige Cents), und die Summe muss genau dem Budget von $10,000.00 entsprechen, um die Prüfungsanforderungen zu erfüllen.
Ein Ansatz verwendet einen Cursor, um durch die Mitarbeiter zu iterieren, wobei der FLOOR-Wert zugewiesen wird und der fraktionale Rest zur nächsten Zeile übertragen wird. Dies gewährleistet Genauigkeit, erfordert jedoch prozeduralen Code und schneidet bei großen Datensätzen aufgrund der zeilenweise Verarbeitung und Sperrung schlecht ab. Es kompliziert auch das Transaktionsmanagement und Rückschraubszenarien.
Ein anderer Ansatz berechnet alle FLOOR-Werte und versucht dann, 1 Cent den $N$ Mitarbeitern mit den größten fraktionalen Resten hinzuzufügen, indem eine ROW_NUMBER()-Unterabfrage verwendet wird. Obwohl set-basiert, erfordert dies mehrere Tabellen-Scans und komplexe Joins, um zu bestimmen, wie viele Zeilen den zusätzlichen Cent benötigen (die Restanzahl), und hat Probleme mit dem Brechen von Unentschieden, wenn viele Mitarbeiter identische fraktionale Teile haben.
Die gewählte Lösung implementiert die ANSI SQL kumulative Übertragungsmethode. Durch die Berechnung der laufenden Summe der genauen Anteile und der Anwendung des FLOOR dieser kumulierten Werte bei jedem Schritt wird genau bestimmt, wie viel bis zu diesem Punkt verteilt werden sollte. Die Differenz zwischen den aufeinanderfolgenden kumulierten Zielen ergibt die Zuweisung der aktuellen Zeile. Dies absorbiert natürlich Rundungsdiskrepanzen: Wenn der erste Mitarbeiter 66 Cent anstelle von 66.666 erhält, wird das 0.666-Defizit in die kumulative Berechnung des zweiten Mitarbeiters übertragen, wodurch dessen kumulatives Ziel von 133.333 auf 133 verschoben wird, was ihm 67 Cent gibt. Dieser Ansatz verarbeitet die gesamte Gehaltsabrechnung in einem einzigen set-basierten Durchlauf, hält strikte ACID-Konformität aufrecht und garantiert, dass die insgesamt verteilte Summe genau $10,000.00 beträgt.
Das Ergebnis war eine Reduzierung der Verarbeitungszeit um 95 % im Vergleich zur Cursor-Methode und null Abstimmungsfehler während der vierteljährlichen finanziellen Prüfung.
Warum verteilt das Subtrahieren des vorherigen kumulierten Bodens vom aktuellen kumulierten Boden den Rest korrekt?
Kandidaten versuchen oft, individuelle Zeilenrundungsfehler zu berechnen und diese dann explizit zu verteilen. Der Einblick ist, dass FLOOR(kumulative_exact) die ideale Gesamterfassung bis zu dieser Zeile darstellt, wenn wir nur ganze Einheiten zuweisen könnten. Durch die Differenzierung dieser kumulierten Ziele fragen wir effektiv: "Wie viele neue ganze Einheiten führt diese Zeile in die kumulierte Summe ein?" Wenn vorherige Zeilen einen Rest von 0.4 hinterlassen, schiebt der 0.6-Anteil der nächsten Zeile die kumulierte Fraktion über die ganze Zahl, sodass die aktuelle Zeile die zusätzliche Einheit beanspruchen kann, die die vorherige Zeile nicht konnte. Dieser implizite Vorlauf eliminiert die Notwendigkeit, Überreste explizit zu verfolgen.
Wie verhält sich dieser Algorithmus bei negativen genau Anteile Werten, und warum könnte FLOOR problematisch sein?
Die meisten Kandidaten gehen von positiven Werten aus. Bei negativen Anteilen (z.B. Lastschriften oder Rückgaben) rundet FLOOR von null weg (z.B. FLOOR(-1.2) = -2), was die negative Größe übertreibt. Die Übertragungslogik bleibt mathematisch im Gleichgewicht, aber die geschäftliche Interpretation von "Priorität" ändert sich - negative Zuweisungen könnten den "Rest" unerwartet verbrauchen. Die Lösung erfordert die Verwendung von TRUNC (zur Null hin) oder CEIL für negative Werte, je nachdem, ob das Unternehmen eine Rundung zur Null für Gutschriften bevorzugt. Eine robuste Implementierung verwendet CASE-Ausdrücke, um FLOOR für positive und CEIL für negative Werte anzuwenden, wodurch sichergestellt wird, dass die absolute Abweichung konstant minimiert wird.
Was gewährleistet, dass die Zuweisung der letzten Zeile genau die gesamte Ressource ohne eine explizite Überprüfung erschöpft?
Kandidaten machen sich Sorgen über Off-by-One-Fehler. Die mathematische Garantie ergibt sich aus der Eigenschaft der Teleskopreihe: $\sum_{i=1}^{n} (T_i - T_{i-1}) = T_n - T_0$, wobei $T_i = \text{FLOOR}(\sum_{j=1}^{i} s_j)$ und $T_0 = 0$. Da $T_n = \text{FLOOR}(\sum_{j=1}^{n} s_j) = \text{FLOOR}(T) = T$ (vorausgesetzt, $T$ ist integer), muss die Summe aller Differenzen gleich $T$ sein. Der ANSI SQL Fensterrahmen stellt sicher, dass die LAG-Funktion $T_{i-1}$ korrekt abruft, wodurch die endgültige Zuweisung automatisch alle verbleibenden Reste aus allen vorhergehenden Zeilen absorbiert.