Le défi de l'empaquetage et de l'accumulation de lots remonte à avant les bases de données relationnelles, originaire de la recherche opérationnelle et de l'optimisation logistique. Dans ANSI SQL, ce problème était historiquement insoluble sans extensions procédurales comme PL/SQL ou des curseurs T-SQL car les opérations basées sur des ensembles standard manquent de la capacité à référencer "totaux cumulés réinitialisés" dans les fenêtres. L'introduction des CTE récursifs dans SQL:1999 a fourni la base théorique pour une accumulation itérative, bien que de nombreuses implémentations souffrent initialement de limitations de performance sur de grands ensembles de données. Les optimiseurs de requêtes modernes ont amélioré les plans d'exécution récursifs, permettant des solutions efficaces pour le contrôle des lots de fabrication et le regroupement des transactions financières. Ce modèle reste un test fondamental pour traduire des algorithmes procéduraux en logique déclarative ANSI SQL.
Nous devons traiter une séquence ordonnée d'éléments, chacun possédant un poids ou une valeur, et les assigner à des lots séquentiels de sorte que le total cumulatif de chaque lot ne dépasse pas une capacité prédéfinie. Lorsque l'ajout de l'élément suivant franchirait le seuil, un nouveau lot commence. Cela nécessite de maintenir un accumulateur courant qui se réinitialise conditionnellement, une opération d'état qui défie l'agrégation simple des fonctions de fenêtre car la limite de réinitialisation dépend de la somme dynamique de tous les éléments précédents depuis la dernière réinitialisation, et non d'un simple décalage de ligne fixe. La solution doit gérer les cas particuliers, y compris les éléments dépassant la capacité individuelle (erreur ou lot de débordement d'un seul élément) et les entrées vides, fonctionnant strictement dans ANSI SQL sans extensions procédurales spécifiques au fournisseur.
Nous employons un CTE récursif qui itère à travers la séquence ordonnée, transportant le numéro de lot actuel et le poids accumulé de ce lot. Le membre d'ancrage initialise le premier élément avec le lot 1 et son poids comme la somme courante. Le membre récursif se joint à l'élément séquentiel suivant, calculant si l'ajout de son poids dépasse la capacité ; si c'est le cas, il incrémente le numéro de lot et réinitialise l'accumulateur au poids du nouvel élément, sinon il conserve le lot actuel et ajoute à l'accumulateur. Nous utilisons ROW_NUMBER() pour établir un ordre de traversée strict et éviter la récursion infinie en filtrant sur un compteur de profondeur ou en se joignant uniquement aux lignes suivantes. Enfin, nous sélectionnons les affectations de lot distinctes ou agrégons les résultats selon les besoins.
WITH RECURSIVE ordered_items AS ( SELECT item_id, weight, ROW_NUMBER() OVER (ORDER BY sequence_order) AS rn FROM items ), batch_accumulator AS ( -- Ancre : le premier élément commence le lot 1 SELECT item_id, weight, rn, 1 AS batch_number, weight AS current_batch_sum FROM ordered_items WHERE rn = 1 UNION ALL -- Récursif : traiter l'élément suivant 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;
Contexte: Automatisation de l'emballage en entrepôt pour un centre de distribution de commerce électronique.
Description du problème: Le système de tapis roulant automatisé traite les commandes séquentiellement mais doit les regrouper dans des conteneurs d'expédition avec une limite de poids stricte de 20 kg. Chaque commande a un poids variable. Le système doit savoir quel ID de conteneur imprimer sur chaque étiquette d'expédition à mesure que les éléments arrivent sur la ligne, sans s'arrêter pour traiter des groupes. Les premières tentatives utilisant du code au niveau de l'application ont créé des goulets d'étranglement et des conditions de course durant les périodes de forte affluence.
Différentes solutions considérées:
Solution 1: Batching au niveau de l'application avec des tables temporaires. L'application récupérait les éléments, calculait des totaux cumulés dans une boucle, et insérait des lots dans la base de données. Cette approche a introduit une latence réseau significative et des frais de transaction, nécessitant plusieurs allers-retours entre le serveur d'application et la base de données. Cela compliquait également le contrôle de la concurrence lorsque plusieurs lignes d'emballage fonctionnaient simultanément, entraînant une contention des verrous de table.
Solution 2: Approche pure fonction de fenêtre utilisant SUM() OVER (ORDER BY ...) avec arithmétique modulaire. Cela tentait de créer des lots en divisant la somme cumulée illimitée par la capacité. Cependant, cela attribue incorrectement des éléments à des lots basés sur une position absolue plutôt que sur le seuil de réinitialisation dynamique, résultant en des lots qui dépassent systématiquement la capacité lorsque les éléments individuels ont des poids variables. L'approche modulaire ne fonctionne que pour des éléments de taille fixe, rendant cette méthode inappropriée pour l'exigence de poids variable.
Solution 3: CTE récursif mis en œuvre dans ANSI SQL. Cette solution effectue tous les calculs côté serveur en une seule exécution de requête, éliminant les frais de réseau. Elle gère correctement la logique d'accumulation et de réinitialisation d'état en traitant itérativement le flux ordonné. Bien que des limites de profondeur de récursion existent dans certaines configurations de base de données, les contraintes opérationnelles de l'entrepôt (les lots dépassant rarement 100 éléments) ont garanti que cela ne violerait pas les limites de plate-forme. Cette approche a été sélectionnée pour son atomicité, sa cohérence et l'élimination de la gestion d'état de l'application.
Résultat: La requête a réussi à traiter 50,000 éléments par heure avec une latence de moins d'une seconde, attribuant correctement des IDs de conteneur tout en respectant les contraintes de poids. La solution a éliminé les conditions de concurrence et réduit les coûts d'infrastructure en supprimant la nécessité d'un microservice de batching séparé.
1. Comment gérez-vous le premier élément correctement lorsqu'il dépasse individuellement la capacité du lot ?
De nombreux candidats supposent que tous les éléments rentrent dans la capacité. Lorsque le poids d'un élément individuel dépasse le seuil du lot, la logique récursive doit soit signaler une erreur, soit le placer dans un lot de débordement isolé. L'implémentation correcte ajoute une CASE dans le membre d'ancrage pour vérifier la capacité initiale, et dans le membre récursif pour forcer un nouveau lot lorsque oi.weight > capacity, indépendamment de la somme actuelle. Sans cela, le système pourrait tenter d'ajouter des éléments surdimensionnés aux lots existants ou créer une récursion infinie en essayant de diviser les éléments.
2. Pourquoi le join sur rn = rn + 1 risque-t-il une récursion infinie, et comment l'évitez-vous ?
Les candidats utilisent fréquemment oi.rn = ba.rn + 1 en supposant une strict séquentialité, mais si les données sources contiennent des lacunes ou si l'ordre ROW_NUMBER() produit des doublons en raison de clés de tri non uniques, le join pourrait créer des cycles ou sauter des lignes. De plus, si les données contiennent des références circulaires dans la définition de séquence, la récursion ne se termine jamais. La solution nécessite de s'assurer que sequence_order est déterministe et unique, et d'ajouter une colonne de compteur de profondeur qui s'incrémente à chaque niveau de récursion, y compris une contrainte CHECK ou clause WHERE depth < 1000 pour prévenir les requêtes runaway en cas de corruption des données.
3. Quelles sont les implications de performance de la profondeur de récursion par rapport à la largeur dans cet algorithme ?
Les développeurs juniors traitent souvent les CTE récursifs comme des boucles itératives, ne reconnaissant pas que chaque niveau de récursion traite toutes les lignes éligibles à cette profondeur (largeur d'abord). Ils manquent que sans un bon indexage sur rn, le join oi.rn = ba.rn + 1 résulte en des opérations de boucle imbriquée qui scalent quadratiquement. L'approche correcte nécessite de s'assurer que la colonne de séquence est indexée et de comprendre que la récursion ANSI SQL matérialise des résultats intermédiaires, consommant potentiellement une mémoire significative pour de grands lots. Les candidats devraient mentionner l'optimisation en traitant en morceaux plus petits ou en utilisant un traitement de lots itératif pour des millions de lignes plutôt que de la pure récursion.