De uitdaging van bin packing en batch accumulatie dateert van vóór relationele databases en is ontstaan in de operations research en logistiek optimalisatie. In ANSI SQL was dit probleem historisch onoplosbaar zonder procedurele extensies zoals PL/SQL of T-SQL cursors, omdat standaard set-gebaseerde bewerkingen niet de mogelijkheid bieden om "lopende totalen met reset" binnen vensterframes te refereren. De introductie van recursieve CTE's in SQL:1999 bood de theoretische basis voor iteratieve accumulatie, hoewel veel implementaties aanvankelijk leed onder prestatiebeperkingen bij grote datasets. Moderne query-optimalisaties hebben recursieve uitvoeringsplannen verbeterd, waardoor efficiënte oplossingen voor productie batchcontroles en financiële transactie-groepering mogelijk zijn. Dit patroon blijft een fundamentele test van het vertalen van procedurele algoritmen naar declaratieve ANSI SQL logica.
We moeten een geordende reeks van items verwerken—elk met een gewicht of waarde—en deze toewijzen aan sequentiële batches zodat de cumulatieve totalen van elke batch een vooraf gedefinieerde capaciteit niet overschrijden. Wanneer het toevoegen van het volgende item de drempel zou overschrijden, begint een nieuwe batch. Dit vereist het bijhouden van een lopende accumulator die conditioneel opnieuw wordt ingesteld, een stateful bewerking die eenvoudige vensterfunctie aggregatie tart omdat de resetgrens afhankelijk is van de dynamische som van alle voorgaande items sinds de laatste reset, en niet slechts van een vaste rij-offset. De oplossing moet randgevallen afhandelen, waaronder items die de individuele capaciteit overschrijden (fout of enkele item overflow batch) en lege invoer, met strikt gebruik binnen ANSI SQL zonder vendor-specifieke procedurele extensies.
We maken gebruik van een recursieve CTE die door de geordende reeks iterereert, waarbij het huidige batchnummer en het verzamelde gewicht van die batch worden doorgegeven. Het ankerlid initialiseert het eerste item met batch 1 en het gewicht als de huidige som. Het recursieve lid voegt zich bij het volgende sequentiële item en berekent of het toevoegen van zijn gewicht de capaciteit overschrijdt; als dat het geval is, verhoogt het het batchnummer en reset het de accumulator naar het gewicht van het nieuwe item, anders behoudt het de huidige batch en voegt het toe aan de accumulator. We gebruiken ROW_NUMBER() om een strikte volgorde van doorgang te waarborgen en eindeloze recursie te voorkomen door te filteren op een diepte-teller of door alleen samen te voegen met daaropvolgende rijen. Uiteindelijk selecteren we de onderscheidende batch-toewijzingen of aggregeren we resultaten zoals vereist.
WITH RECURSIVE ordered_items AS ( SELECT item_id, weight, ROW_NUMBER() OVER (ORDER BY sequence_order) AS rn FROM items ), batch_accumulator AS ( -- Anker: eerste item begint batch 1 SELECT item_id, weight, rn, 1 AS batch_number, weight AS current_batch_sum FROM ordered_items WHERE rn = 1 UNION ALL -- Recursief: verwerk het volgende item 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;
Context: Automatisering van verpakking in een magazijn voor een e-commerce fulfillment centrum.
Probleemomschrijving: Het geautomatiseerde transportsysteem verwerkt bestellingen sequentieel, maar moet deze groeperen in verzendcontainers met een strikte limiet van 20 kg. Elke bestelling heeft een variabel gewicht. Het systeem moet weten welke container-ID op elk verzendlabel moet worden afgedrukt terwijl de items op de lijn binnenkomen, zonder te pauzeren om groepen batchgewijs te verwerken. Vroege pogingen met toepassing-laagcode veroorzaakten knelpunten en race-omstandigheden tijdens drukke perioden.
Verschillende oplossingen overwogen:
Oplossing 1: Batching in de applicatielaag met tijdelijke tabellen. De applicatie zou items ophalen, lopende totalen in een lus berekenen en batches in de database invoegen. Deze aanpak introduceerde aanzienlijke netwerklatentie en transactie-overhead, waardoor meerdere rondreizen tussen de applicatieserver en de database nodig waren. Dit bemoeilijkte ook de gelijktijdige controle wanneer meerdere verpakkingslijnen gelijktijdig werkzaam waren, leidend tot tabelvergrendelingsconflicten.
Oplossing 2: Pure vensterfunctie benadering met SUM() OVER (ORDER BY ...) met modulo-aritmetiek. Dit probeerde batches te creëren door de onbegrensde lopende som door de capaciteit te delen. Echter, dit wijst items onjuist aan batches toe op basis van absolute positie in plaats van de dynamische resetdrempel, wat resulteert in batches die consequent de capaciteit overschrijden wanneer individuele items variabele gewichten hebben. De modulo-benadering werkt alleen voor items van vaste grootte, waardoor het ongeschikt is voor de vereiste variabele gewichten.
Oplossing 3: Recursieve CTE geïmplementeerd binnen ANSI SQL. Deze oplossing voert alle berekeningen server-side uit in een enkele query-uitvoering, wat netwerkoverhead elimineert. Het behandelt correct de stateful accumulatie- en resetlogica door de geordende stroom iteratief te verwerken. Hoewel er grenzen zijn aan de recursiediepte in sommige databaseconfiguraties, zorgden de operationele beperkingen van het magazijn (batches die zelden 100 items overschrijden) ervoor dat dit de platformlimits niet zou overschrijden. Deze aanpak werd geselecteerd vanwege de atomiciteit, consistentie en eliminatie van applicatiestatusbeheer.
Resultaat: De query verwerkte met succes 50.000 items per uur met sub-seconde latentie, waarbij correct container-ID's werden toegewezen terwijl gewichtslimieten werden gerespecteerd. De oplossing elimineerde race-omstandigheden en reduceerde de infrastructuurkosten door de noodzaak voor een aparte batching-microservice te verwijderen.
1. Hoe ga je correct om met het eerste item wanneer het individueel de batchcapaciteit overschrijdt?
Veel kandidaten gaan ervan uit dat alle items binnen de capaciteit passen. Wanneer het gewicht van een individueel item de batchdrempel overschrijdt, moet de recursieve logica of een fout aanduiden of het in een geïsoleerde overflow batch plaatsen. De juiste implementatie voegt een CASE-verklaring toe in het ankerlid om de initiële capaciteit te controleren, en in het recursieve lid om dwingend een nieuwe batch te creëren wanneer oi.weight > capacity, ongeacht de huidige som. Zonder dit kan het systeem proberen om te grote items aan bestaande batches toe te voegen of eindeloze recursies te creëren door te proberen items te splitsen.
2. Waarom riskeert het samenvoegen op rn = rn + 1 eindeloze recursie, en hoe voorkom je dit?
Kandidaten gebruiken vaak oi.rn = ba.rn + 1 waarbij ze veronderstellen dat er strikte sequentialiteit is, maar als de brontekstgaten bevat of de ROW_NUMBER()-ordening duplicaten produceert door niet-unieke sorteersleutels, kan de join cycli creëren of rijen overslaan. Bovendien, als de gegevens circulaire verwijzingen bevatten in de sequentie-definitie, eindigt de recursie nooit. De oplossing vereist dat sequence_order deterministisch en uniek is, en een diepte-tellerkolom die toeneemt met elk niveau van recursie, inclusief een CHECK-beperking of WHERE-clausule depth < 1000 om te voorkomen dat exploderende queries worden uitgevoerd tijdens gegevenscorruptie.
3. Wat zijn de prestatie-implicaties van recursiediepte versus -breedte in dit algoritme?
Junior ontwikkelaars beschouwen recursieve CTE's vaak als iteratieve lussen, zonder te beseffen dat elk niveau van recursie alle beschikbare rijen op dat niveau verwerkt (breedte-eerst). Ze missen dat zonder de juiste indexering op rn, de join oi.rn = ba.rn + 1 resulteert in geneste lusbewerkingen die kwadratisch schalen. De juiste aanpak vereist ervoor te zorgen dat de sequenciekolom geïndexeerd is en te begrijpen dat ANSI SQL recursie tussenresultaten materialiseert, wat mogelijk aanzienlijk geheugen verbruikt voor grote batches. Kandidaten zouden moeten vermelden dat ze optimaliseren door in kleinere brokken te verwerken of door iteratieve batchverwerking voor miljoenen rijen te gebruiken in plaats van pure recursie.