Advent of Code 2024 implémenté en SQL pur
(databasearchitects.blogspot.com)- Tous les problèmes d’Advent of Code 2024 ont pu être résolus uniquement en SQL pur, et le point essentiel est que SQL impose une manière de penser différente de celle des résolutions d’énigmes classiques
- Pour les parcours de grille de petite taille, de l’analyse de l’entrée jusqu’à l’exploration et l’agrégation basées sur des requêtes récursives, tout se traite de façon relativement naturelle dans SQL
- Sur des problèmes comme le Day 16, où le nombre d’états augmente fortement, le problème venait moins de l’expression que du coût d’évaluation, avec une inefficacité telle que l’entrée réelle nécessitait plus de 200 Go de mémoire
- Le problème de clique maximale du Day 23 correspond bien à l’algorithme de Bron-Kerbosch, mais une structure qui cherche à manipuler plusieurs ensembles entre en conflit avec le modèle du SQL récursif, qui transmet un seul ensemble
- Écrire des algorithmes complexes en SQL est possible, mais pour rendre leur exécution directement dans la base de données plus pratique, il faudrait des mises à jour d’état en cours de récursion et des manipulations d’état plus riches
Résoudre Advent of Code 2024 uniquement avec SQL
- Advent of Code 2024 a été résolu en SQL pur, et tous les problèmes ont pu être traités uniquement avec SQL
- L’ensemble des solutions est disponible dans le dépôt GitHub
- Cela a conduit à penser les problèmes autrement, et dans de nombreux cas SQL s’est révélé être un outil plus agréable que prévu
Day 11 : SQL fonctionne bien sur les petits problèmes de parcours
- La solution complète du Day 11, y compris l’entrée du puzzle, tient dans un seul script SQL
- Le traitement de l’entrée suit un flux qui transforme progressivement une chaîne en structure tabulaire
- l’entrée du puzzle est conservée sous forme de chaîne
- l’entrée est découpée en lignes individuelles
- chaque caractère est converti en coordonnées et en valeur pour créer une table sous forme de tableau 2D
- La partie algorithmique reste relativement courte
- une requête récursive parcourt la grille
- la réponse du puzzle est extraite à partir du résultat du parcours
- Sur ce type de petits parcours, SQL fonctionne tout à fait correctement
Day 16 : le coût de conservation de l’état en SQL récursif
- Day 16 parcourt une grille de manière similaire au Day 11 et calcule la distance minimale de parcours pour chaque point visité
- C’est facile à exprimer en SQL, mais l’évaluation est coûteuse et gaspille des ressources
- Avec l’entrée réelle du puzzle, la grille devient grande et la requête récursive génère et conserve de nombreux états
- en pratique, seul le résultat de la dernière itération de la requête récursive est nécessaire
- malgré cela, la plupart des tuples calculés sont conservés
- À cause de cela, l’exécution de cette requête nécessite plus de 200 Go de mémoire
- L’utilisation d’une sémantique d’itération pendant la récursion permettrait de réduire cette consommation mémoire excessive
- Umbra sait le faire
- Postgres et DuckDB ne le prennent pas en charge
- cette fonctionnalité n’a donc pas été utilisée dans la solution
Day 23 : les limites d’un algorithme qui exige plusieurs ensembles
- Le Day 23 consistait à trouver la clique maximale dans un graphe creux
- Ce problème peut se calculer de manière raisonnable avec l’algorithme de Bron-Kerbosch
- Mais cet algorithme cherche à maintenir plusieurs ensembles, alors que le SQL récursif n’en transmet qu’un seul
- L’implémentation était possible, mais l’expression en SQL est devenue assez complexe, et le code obtenu a pris une forme peu élégante
Ce qu’il manque encore au SQL récursif
- Même des algorithmes complexes peuvent être écrits en SQL, et dans bien des cas le code SQL s’est révélé plus simple à lire et à écrire qu’attendu
- Si le SQL récursif disposait d’un mécanisme de mise à jour d’état, il pourrait devenir plus efficace et plus facile à utiliser
- Des recherches sont en cours sur un mécanisme de trampoline pour prendre en charge des flux de contrôle plus complexes dans la récursion, et cette approche est elle aussi utile
- Il faudrait également examiner des mécanismes de manipulation d’état plus complexes
- Avec seulement quelques fonctionnalités supplémentaires, SQL pourrait devenir une option robuste pour exécuter directement des algorithmes complexes à l’intérieur de la base de données
1 commentaires
Commentaires de Hacker News
Seules des personnes vraiment exceptionnelles peuvent réussir ce genre de chose. C’est de l’art pur, et il n’y en a pas assez comme ça dans le monde de la programmation
En voyant ce titre, j’ai eu une réaction assez similaire à celle que j’ai quand je vois un nouveau menu chez Taco Bell. Un mélange étrange de désir, de honte et d’admiration pour la créativité humaine
Pour des problèmes comme Advent of Code, la partie la plus difficile est probablement le parsing de l’entrée
Peut-être qu’en fouillant dans l’interface de la tablette, on pourrait connaître les ingrédients, mais pour l’instant ça ressemble à un jeu de hasard. Plus sérieusement, https://www.amazon.com/Joe-Celkos-SQL-Smarties-Programming-d... est un excellent cours pour apprendre l’artisanat SQL extrême
Il me semble que HN, dans son ensemble, parle de créativité humaine, et je ne suis pas sûr qu’il faille tout recevoir comme si on regardait un menu de Taco Bell
C’est bien fait. Au début, ça a l’air dément, mais je pense que le gros SQL est l’une des meilleures façons de contenir la complexité.
Si c’est complexe, c’est parce que le problème lui-même est complexe. SQL est un standard, concis, très rapide, réellement testable et logique. Tout le monde ne peut pas le maintenir immédiatement, mais c’est pareil quand c’est écrit en Java avec beaucoup de lignes et de fonctions.
J’aime aussi la profondeur de SQL. Il soutient le monde des données depuis plus de 40 ans, donc il est normal que les gens aient demandé des fonctionnalités de niche. La clause model d’Oracle est l’une de mes fonctionnalités préférées, car elle permet d’implémenter des tableaux multidimensionnels, et un ami s’en est servi pour implémenter le jeu de la vie de Conway en beaucoup moins de lignes que prévu
Au final, je l’ai réécrite en code natif et je l’ai ramenée à moins d’une seconde ; l’essentiel du travail a consisté à prouver qu’elle produisait le même résultat, puis à écrire et documenter des cas de test pour éviter que la personne suivante subisse la même galère. Depuis, j’évite généralement de mettre beaucoup de logique métier dans SQL
Personnellement, je pense que ce qui est complexe doit pouvoir être testé facilement, à la main comme automatiquement. SQL est facile à tester manuellement, mais les tests automatisés y sont plus difficiles que pour du code dans un langage de programmation. Un tas de spaghetti code peut au moins être déroulé de façon moins dense pour s’attaquer aux morceaux un par un, mais je ne vois pas bien comment traiter un spaghetti SQL entremêlé.
Je ne suis pas non plus totalement d’accord avec l’idée que plus il y a de lignes, plus le risque de bugs augmente. Toutes les lignes ne se valent pas. Une ligne SQL de 400 caractères a probablement plus de chances d’être difficile à parcourir visuellement pour y trouver un problème que 400 lignes de Java, et je dis ça tout en détestant Java pour plusieurs raisons
Si vous aimez ce genre de défi décadent, j’ai fait l’Advent of Code de cette année dans Google Sheets.
Je ne suis allé que jusqu’au jour 6, et je n’ai pas obtenu les deux étoiles tous les jours. Je suis assez sûr que ma solution du jour 7 est correcte, mais avec l’entrée longue, je me suis heurté à la limite du nombre de caractères par cellule.
Amusez-vous bien. Évitez toutefois de l’ouvrir sur mobile : certaines feuilles font planter l’app.
https://docs.google.com/spreadsheets/d/10FY-89y19tnRM_EAAnCd...
Au cours de ma carrière, j’ai écrit plus de SQL que n’importe quel autre type de code. Ces cinq dernières années, j’en ai moins fait, donc j’en ai sans doute beaucoup oublié, mais à l’époque j’aimais vraiment ça.
Quand on arrête de penser de façon itérative et qu’on commence à raisonner en opérations ensemblistes, cela devient assez naturel et puissant.
Si le schéma est bien structuré et aligné avec le point de vue des parties prenantes métier, la logique métier définie par des requêtes SQL peut être assez intuitive.
Le code, les frameworks, les ORM, les « bonnes pratiques », les patterns, etc., finissent par être des sources de distraction. Il existe un million de façons de faire entrer et sortir des données d’une base, et déplacer des bits n’a en soi que peu de valeur. Beaucoup de solutions logicielles surdimensionnées auraient pu être de simples instructions de fusion ou des imports CSV.
Une grande partie des malentendus et des ressentiments autour de SQL vient du fait qu’il faut composer avec des schémas désordonnés. Le langage lui-même est vraiment spécifique au domaine. Si l’on n’avait pas besoin d’écrire ce genre de requêtes au départ, on ne se plaindrait pas autant des requêtes atrocement imbriquées et des douleurs syntaxiques SQL qui en découlent. Si l’on aligne les tuples et les relations sur la manière dont le métier s’exprime habituellement, on finit avec le temps par moins se battre avec ces choses. Il est souvent impossible de refactorer un schéma depuis zéro, mais on peut placer des répliques ou des vues autour d’un mauvais schéma et en faire la cible du nouveau développement et du refactoring.
Bien sûr, SQL a des défauts, dont certains sérieux, comme la testabilité. Mais au fond, j’aimerais que toute la programmation fonctionne ainsi : l’ordinateur décide comment faire en interne, et les humains se concentrent sur la logique.
J’ai essayé de lire rapidement Prolog pour aller un cran plus loin, mais je n’y suis pas encore arrivé. L’objectif était aussi d’oublier une partie de SQL pour ne pas rester trop enfermé dedans. Peut-être que l’avenir de la programmation se trouve quelque part entre SQL et Prolog.
Si l’on raisonne uniquement en termes d’opérations ensemblistes, on obtient facilement une requête qui prend 5 minutes au lieu de 5 millisecondes. Le processus mental est presque toujours une itération du type : « par quelle table commencer, quelles lignes regarder et dans quel ordre, avec quoi joindre et sous quelles conditions, comment agréger ». On finit par penser avec un modèle mental de boucles et d’agrégations plutôt qu’en opérations ensemblistes.
Beaucoup de gens sautent vers toutes sortes de distractions, mais l’essentiel du génie logiciel consiste à mettre les bonnes données dans le bon format et à les déplacer de manière fiable.
J’ai récemment refactoré en profondeur une base de code distribuée complexe, et ce qui compte vraiment comme le « travail » réalisé, c’est presque uniquement la refonte du schéma. Le reste a représenté beaucoup d’heures de code, mais relevait en réalité davantage de l’implémentation.
Il existe d’autres manières que SQL de définir des schémas, mais SQL est une façon parfaite d’apprendre la véritable ingénierie des systèmes.
J’utilise énormément SQL, et j’implémente en SQL une bonne partie de la logique métier d’applications de traitement de flux. J’aime particulièrement l’idée de rapprocher le calcul des données, plutôt que de déplacer les données vers le calcul.
Mais je rencontre souvent des développeurs qui détestent cette idée. Ils préfèrent accepter un énorme coût d’entrées-sorties, déplacer toutes les données vers le backend, puis exprimer le calcul dans un « vrai » langage de programmation.
Le concept de SQL est bon, mais je pense que le problème, c’est le langage SQL lui-même. Il a trop d’aspects maladroits, ce qui n’est pas surprenant après environ 40 ans sans concurrence. Le modèle de programme que l’on a en tête est correct, mais pour en voir l’élégance, il faut regarder au-delà de la syntaxe, vers le programme que l’on est réellement en train d’écrire.
Ce qu’il faudrait, à mon avis, c’est un vrai langage de programmation conçu pour cibler les bases de données existantes (Postgres, MSSQL) et compiler vers des dialectes SQL. On voit quelques candidats, mais ils sont soit cantonnés à un domaine spécifique, comme PreQL qui n’autorise pas les modifications de données, soit couplés à une autre base de données.
J’aimerais le créer moi-même, mais cela représente trop de travail, le chemin vers l’adoption serait très long, il n’y a aucune garantie de succès et aucun modèle économique évident ne me vient à l’esprit.
Les langages backend populaires ont été créés par de grandes entreprises, mais coder en SQL semble pris dans une impasse : ce sera dévalorisé tant qu’un meilleur langage n’existera pas, et aucun meilleur langage n’émergera tant que cette pratique ne sera pas plus populaire.
Les expressions de table communes et les fonctions de fenêtre ont fait une grande différence, et les fonctions de fenêtre en particulier, même si elles tordent un peu le cerveau, rendent des choses difficiles un peu plus faciles.
J’utilise BigQuery, qui prend en charge les structures et les tableaux ; ce n’est que récemment qu’il est devenu possible de grouper des tableaux, mais il n’y a toujours pas de test d’égalité, par exemple.
BigQuery ajoute progressivement du sucre syntaxique, comme les fonctions d’agrégation définies par l’utilisateur et les fonctions définies par l’utilisateur polymorphes avec des paramètres
ANY TYPE. Cela permet de mettre davantage de logique réutilisable dans des fonctions propres, mais personnellement, j’aimerais que les fonctions temporaires soient déclarées et scopées comme des expressions de table communes, afin de mieux s’intégrer avec des outils comme DBT qui veulent tout mettre dans une seule instruction.Si je devais citer une seule fonctionnalité qui améliorerait le plus la productivité, ce serait la possibilité de spécifier le comportement vis-à-vis des valeurs nulles dans
JOIN USING. Déplierfoo.bar IS NOT DISTINCT FROM bar.bardans une jointure n’est ni intuitif ni élégant. Quelque chose commeUSING (bar RESPECT NULLS)serait bien mieux.À l’inverse, dans une architecture de type microservices, où de petits services possèdent chacun leur propre base de données et où seulement la moitié d’entre elles sont relationnelles, on souhaite moins mettre de code complexe dans la base elle-même. C’est parce qu’on migre souvent entre instances uniques ou clusters, en emportant seulement des dumps de données relativement simples, ou en rattachant de nouvelles répliques à la manière du bateau de Thésée.
Le fait que ce soit réalisé en pur SQL est déjà vraiment impressionnant, mais le vrai signe d’une énergie d’ingénieur complètement fissuré, c’est surtout le site Blogspot maintenu depuis 10 ans, je trouve.
C’est difficile à expliquer précisément, mais ça dégage fortement une impression de « spécialiste chevronné d’un domaine de niche ». Même sans connaître les auteurs, quelques personnes qui maintiennent pendant 10 ans un site Blogspot intitulé « database architects » n’ont sans doute pas besoin d’être présentées dans la bonne communauté.
Pour info, j’ai essayé Advent of Code en EdgeQL pendant quelques jours, et c’était une expérience assez intéressante.
J’ai posté quelques tweets, et il faudrait probablement que j’en fasse un billet de blog.
https://x.com/1st1/status/1864069589245858083
Comparaison avec SQL : https://x.com/1st1/status/1864412869108092997
Absolument horrible. Mais bien joué quand même.
Pour ceux qui ne le sauraient pas, l’auteur est l’un des meilleurs chercheurs en bases de données au monde.