Die Herausforderung des Bin-Packing und der Batch-Akkumulation ist älter als relationale Datenbanken und stammt aus der Betriebsforschung und der Logistikoptimierung. In ANSI SQL war dieses Problem historisch ohne prozedurale Erweiterungen wie PL/SQL oder T-SQL-Cursors nicht lösbar, da standardisierte set-basierte Operationen nicht in der Lage sind, "laufende Summen mit Zurücksetzung" innerhalb von Fensterrahmen zu referenzieren. Die Einführung rekursiver CTEs in SQL:1999 lieferte die theoretische Grundlage für die iterative Akkumulation, obwohl viele Implementierungen anfangs unter Leistungsbeschränkungen bei großen Datensätzen litten. Moderne Abfrageoptimierer haben rekursive Ausführungspläne verbessert und ermöglichen effiziente Lösungen für die Steuerung von Fertigungsbatches und die Gruppierung von Finanztransaktionen. Dieses Muster bleibt ein fundamentaler Test für die Übersetzung prozeduraler Algorithmen in deklarative ANSI SQL-Logik.
Wir müssen eine geordnete Sequenz von Elementen verarbeiten – jedes mit einem Gewicht oder Wert – und sie in sequenzielle Chargen einteilen, sodass die kumulierte Gesamtsumme jeder Charge ein vordefiniertes Limit nicht überschreitet. Wenn das Hinzufügen des nächsten Elements den Schwellenwert überschreiten würde, beginnt eine neue Charge. Dies erfordert die Aufrechterhaltung eines laufenden Akkumulators, der bedingt zurückgesetzt wird, eine zustandsbehaftete Operation, die eine einfache Aggregation von Fensterfunktionen widerspricht, da die Rücksetzgrenze von der dynamischen Summe aller vorherigen Elemente seit dem letzten Zurücksetzen abhängt, nicht nur von einem festen Zeilenversatz. Die Lösung muss Randfälle behandeln, einschließlich Elemente, die die individuelle Kapazität überschreiten (Fehler oder Einzelstück-Überlauf-Charge) und leere Eingaben, und zwar ausschließlich innerhalb von ANSI SQL ohne vendor-spezifische prozedurale Erweiterungen.
Wir verwenden ein rekursives CTE, das die geordnete Sequenz durchläuft und die aktuelle Chargennummer und das angesammelte Gewicht dieser Charge weitergibt. Das Ankermitglied initialisiert das erste Element mit Charge 1 und seinem Gewicht als aktuelle Summe. Das rekursive Mitglied verbindet sich mit dem nächsten sequenziellen Element und berechnet, ob das Hinzufügen seines Gewichts die Kapazität überschreitet; wenn ja, erhöht es die Chargennummer und setzt den Akkumulator auf das Gewicht des neuen Elements zurück, andernfalls behält es die aktuelle Charge bei und fügt den Akkumulator hinzu. Wir verwenden ROW_NUMBER(), um eine strenge Traversierungsreihenfolge festzulegen und eine unendliche Rekursion zu verhindern, indem wir auf einen Tiefenzähler filtern oder nur mit nachfolgenden Zeilen verknüpfen. Schließlich wählen wir die unterschiedlichen Chargenzuweisungen oder aggregieren die Ergebnisse nach Bedarf aus.
WITH RECURSIVE ordered_items AS ( SELECT item_id, weight, ROW_NUMBER() OVER (ORDER BY sequence_order) AS rn FROM items ), batch_accumulator AS ( -- Anker: erstes Element startet Charge 1 SELECT item_id, weight, rn, 1 AS batch_number, weight AS current_batch_sum FROM ordered_items WHERE rn = 1 UNION ALL -- Rekursiv: nächstes Element verarbeiten SELECT oi.item_id, oi.weight, oi.rn, CASE WHEN ba.current_batch_sum + oi.weight > 100 THEN ba.batch_number + 1 ELSE ba.batch_number END AS batch_number, CASE WHEN ba.current_batch_sum + oi.weight > 100 THEN oi.weight ELSE ba.current_batch_sum + oi.weight END AS current_batch_sum FROM batch_accumulator ba JOIN ordered_items oi ON oi.rn = ba.rn + 1 ) SELECT item_id, batch_number, weight FROM batch_accumulator ORDER BY rn;
Kontext: Automatisierung der Verpackung in einem E-Commerce-Logistikzentrum.
Problembeschreibung: Das automatisierte Fördersystem verarbeitet Bestellungen sequenziell, muss sie jedoch in Versandbehälter mit einem strengen Gewichtslimit von 20 kg gruppieren. Jede Bestellung hat ein variables Gewicht. Das System muss wissen, welche Container-ID auf jedem Versandetikett gedruckt werden soll, während die Artikel an der Linie ankommen, ohne eine Pause zur Batchverarbeitung von Gruppen einzulegen. Frühe Versuche, Anwendungs-Code zu verwenden, führten zu Engpässen und Wettbewerbskonflikten während stark frequentierter Zeiten.
Verschiedene Lösungen in Betracht gezogen:
Lösung 1: Batching auf Anwendungsebene mit temporären Tabellen. Die Anwendung würde Elemente abrufen, laufende Summen in einer Schleife berechnen und Chargen in die Datenbank einfügen. Dieser Ansatz führte zu erheblichem Netzwerkverzug und Transaktionsüberhead, was mehrere Rundreise zwischen dem Anwendungsserver und der Datenbank erforderte. Es komplizierte auch die Steuerung der Gleichzeitigkeit, wenn mehrere Verpackungslinien gleichzeitig betrieben wurden, was zu Tabellenblockierungswettbewerb führte.
Lösung 2: Reine Fensterfunktionsmethode mit SUM() OVER (ORDER BY ...) unter Verwendung von Modulo-Arithmetik. Dies versuchte, Chargen zu erstellen, indem die unbegrenzte laufende Summe durch die Kapazität dividiert wurde. Dies ordnete jedoch Elemente fälschlicherweise Chargen basierend auf ihrer absoluten Position zu, anstatt dem dynamischen Rücksatzschwellenwert, was zu Chargen führte, die konsequent die Kapazität überschritten, wenn einzelne Elemente unterschiedliche Gewichte hatten. Der Modulo-Ansatz funktioniert nur für festelemente, was ihn für das variable Gewicht unbrauchbar macht.
Lösung 3: Rekursives CTE, das innerhalb von ANSI SQL implementiert wird. Diese Lösung führt alle Berechnungen serverseitig in einer einzigen Abfrageausführung durch und beseitigt Netzwerküberhead. Es verarbeitet die zustandsbehaftete Akkumulation und die Zurücksetzlogik korrekt, indem es den geordneten Stream iterativ verarbeitet. Während in einigen Datenbankkonfigurationen Grenzen für die Rekursionstiefe bestehen, gewährleisteten die operativen Einschränkungen des Lagers (Chargen überschreiten selten 100 Elemente), dass dies die Plattformgrenzen nicht überschreiten würde. Dieser Ansatz wurde aufgrund seiner Atomarität, Konsistenz und der Beseitigung der Anwendungszustandsverwaltung ausgewählt.
Ergebnis: Die Abfrage verarbeitete erfolgreich 50.000 Elemente pro Stunde mit Sub-Sekunden-Latenz und wies korrekt Container-IDs zu, während die Gewichtsbeschränkungen beachtet wurden. Die Lösung beseitigte Wettbewerbskonflikte und reduzierte die Infrastrukturkosten durch die Beseitigung des Bedarfs an einem separaten Batch-Microservice.
1. Wie gehen Sie mit dem ersten Element um, wenn es einzeln die Chargenkapazität überschreitet?
Viele Kandidaten gehen davon aus, dass alle Elemente innerhalb der Kapazität liegen. Wenn das Gewicht eines einzelnen Elements den Chargenschwellenwert überschreitet, muss die rekursive Logik entweder einen Fehler melden oder es in eine isolierte Überlaufcharge stellen. Die korrekte Implementierung fügt im Ankerteil eine CASE-Anweisung hinzu, um die anfängliche Kapazität zu überprüfen, und im rekursiven Teil, um eine neue Charge zu erzwingen, wenn oi.weight > capacity, unabhängig von der aktuellen Summe. Andernfalls könnte das System versuchen, Übergewichtige zu bestehenden Chargen hinzuzufügen oder eine unendliche Rekursion versuchen, indem es versucht, Artikel zu teilen.
2. Warum birgt das Verknüpfen von rn = rn + 1 das Risiko einer unendlichen Rekursion, und wie verhindern Sie das?
Kandidaten verwenden häufig oi.rn = ba.rn + 1, in der Annahme strikter Sequenzialität. Wenn jedoch die Quelldaten Lücken enthalten oder die ROW_NUMBER()-Anordnung aufgrund nicht eindeutiger Sortierschlüssel Duplikate erzeugt, kann der Join Zyklen erzeugen oder Zeilen überspringen. Wenn die Daten zudem zirkuläre Verweise in der Sequenzdefinition enthalten, endet die Rekursion nie. Die Lösung erfordert, dass die sequence_order deterministisch und eindeutig ist, und das Hinzufügen einer Tiefenzäulen, die mit jeder Rekursionsebene inkrementiert wird, einschließlich einer CHECK-Bedingung oder WHERE-Klausel depth < 1000, um ausgefallene Abfragen während einer Datenbeschädigung zu verhindern.
3. Was sind die Leistungsimplikationen der Rekursionstiefe gegenüber der Breite in diesem Algorithmus?
Junior-Entwickler behandeln rekursive CTEs oft als iterative Schleifen und erkennen nicht, dass jede Rekursionsebene alle berechtigten Zeilen auf dieser Tiefe (breit zuerst) verarbeitet. Sie übersehen, dass ohne ordnungsgemäße Indizierung auf rn der Join oi.rn = ba.rn + 1 zu verschachtelten Schleifen führt, die quadratisch skalieren. Der korrekte Ansatz erfordert die Gewährleistung, dass die Sequenzspalte indiziert ist, und das Verständnis, dass ANSI SQL-Rekursion Zwischenresultate materialisiert, die signifikanten Speicherbedarf für große Chargen verursachen können. Kandidaten sollten erwähnen, dass die Verarbeitung in kleineren Mengen oder die Verwendung iterativer Batchverarbeitung für Millionen von Zeilen anstelle reiner Rekursion optimiert werden sollte.