- Alle Aufgaben von Advent of Code 2024 ließen sich ausschließlich mit reinem SQL lösen; der entscheidende Punkt ist, dass SQL eine andere Denkweise als die übliche Rätsellösung erzwingt
- Kleine Feld-Traversierungen lassen sich in SQL vergleichsweise natürlich abbilden – von der Eingabeanalyse über die Suche auf Basis rekursiver Abfragen bis hin zur Aggregation
- Bei Problemen wie Day 16, bei denen die Zustände stark anwachsen, lag das Problem weniger in der Darstellung als in den Auswertungskosten; für die echte Eingabe war die Ineffizienz so groß, dass mehr als 200 GB Speicher benötigt wurden
- Das Maximum-Clique-Problem aus Day 23 passt gut zum Bron-Kerbosch-Algorithmus, doch die Struktur zur Handhabung mehrerer Mengen kollidiert mit dem rekursiven SQL-Modell, das nur eine einzelne Menge weiterreicht
- Komplexe Algorithmen in SQL zu schreiben ist möglich, aber für eine praktischere Ausführung innerhalb der Datenbank wären Zustandsaktualisierungen während der Rekursion und reichhaltigere Zustandsmanipulationen nötig
Advent of Code 2024 nur mit SQL lösen
- Advent of Code 2024 wurde mit reinem SQL gelöst, und alle Aufgaben konnten ausschließlich mit SQL bewältigt werden
- Die vollständigen Lösungen sind im GitHub-Repository veröffentlicht
- Das führte zu einer anderen Sichtweise auf die Probleme, und in vielen Fällen erwies sich SQL als angenehmeres Werkzeug als erwartet
Day 11: SQL passt gut zu kleinen Traversierungsproblemen
- Die vollständige Lösung für Day 11 besteht aus einer einzigen SQL-Datei, einschließlich der Puzzle-Eingabe
- Die Eingabeverarbeitung folgt einem Ablauf, bei dem ein String schrittweise in eine Tabellenstruktur umgewandelt wird
- Die Puzzle-Eingabe wird als String behandelt
- Die Eingabe wird in einzelne Zeilen aufgeteilt
- Jedes Zeichen wird in Koordinaten und Wert umgewandelt, sodass eine Tabelle in Form eines 2D-Arrays entsteht
- Der algorithmische Teil bleibt vergleichsweise kurz
- Das Feld wird per rekursiver Abfrage traversiert
- Aus dem Traversierungsergebnis wird die Puzzle-Antwort extrahiert
- Bei solchen Traversierungen im kleinen Maßstab funktioniert SQL sehr gut
Day 16: Die Kosten der Zustandserhaltung in rekursivem SQL
- Day 16 traversiert ähnlich wie Day 11 ein Feld und berechnet für jeden besuchten Punkt die minimale Traversierungsdistanz
- In SQL lässt sich das leicht ausdrücken, aber die Auswertung ist verschwenderisch
- Bei der echten Puzzle-Eingabe wächst das Feld stark an, sodass die rekursive Abfrage viele Zustände erzeugt und vorhält
- Tatsächlich benötigt wird nur das Ergebnis der letzten Iteration der rekursiven Abfrage
- Trotzdem bleiben die meisten berechneten Tupel erhalten
- Deshalb benötigt die Ausführung dieser Abfrage mehr als 200 GB Speicher
- Mit Iterationssemantik (iteration semantic) während der Rekursion ließe sich der übermäßige Speicherverbrauch reduzieren
- Umbra kann das umsetzen
- Postgres und DuckDB unterstützen das nicht
- Daher wurde diese Funktion in der Lösung nicht verwendet
Day 23: Grenzen eines Algorithmus, der mehrere Mengen benötigt
- Day 23 verlangte das Finden einer Maximum Clique in einem dünn besetzten Graphen
- Dieses Problem lässt sich sinnvoll mit dem Bron-Kerbosch-Algorithmus berechnen
- Allerdings versucht dieser Algorithmus, mehrere Mengen gleichzeitig zu verwalten, während rekursives SQL nur eine einzelne Menge weiterreicht
- Eine Implementierung war möglich, aber der SQL-Ausdruck wurde deutlich komplexer, und auch der resultierende Code war nicht besonders sauber
Was rekursivem SQL noch fehlt
- Auch komplexe Algorithmen lassen sich in SQL schreiben, und in vielen Fällen war SQL-Code überraschend gut lesbar und schreibbar
- Mit einem Mechanismus zur Zustandsaktualisierung in rekursivem SQL könnte das effizienter und einfacher werden
- Zur Unterstützung komplexerer Kontrollflüsse in der Rekursion wird an einem Trampolin-Mechanismus geforscht; auch dieser Ansatz ist nützlich
- Es lohnt sich, zusätzlich reichhaltigere Mechanismen zur Zustandsmanipulation zu betrachten
- Schon mit wenigen zusätzlichen Funktionen könnte SQL zu einer robusten Option werden, um komplexe Algorithmen direkt innerhalb der Datenbank auszuführen
1 Kommentare
Hacker-News-Kommentare
So etwas hinzubekommen, schaffen wirklich nur außergewöhnliche Menschen. Reine Kunst, und davon gibt es in der Welt des Programmierens längst nicht genug.
Als ich diesen Titel sah, war meine Reaktion ähnlich wie beim Blick auf ein neues Menü von Taco Bell. Eine seltsame Mischung aus Verlangen, Scham und Bewunderung für die menschliche Kreativität.
Bei Problemen wie Advent of Code ist vermutlich das Parsen der Eingabe der schwierigste Teil.
Vielleicht könnte man die Zutaten herausfinden, wenn man sich durch das Tablet-Interface wühlt, aber im Moment wirkt es wie ein Glücksspiel. Im Ernst: https://www.amazon.com/Joe-Celkos-SQL-Smarties-Programming-d... ist eine hervorragende Lektion darin, extreme SQL-Handwerkskunst zu lernen.
Ich hätte gedacht, HN dreht sich insgesamt um menschliche Kreativität, und ich weiß nicht, ob man das alles so aufnehmen sollte, als würde man auf eine Taco-Bell-Speisekarte schauen.
Gut gemacht. Auf den ersten Blick wirkt es verrückt, aber ich finde, großes SQL ist eine der besten Arten, Komplexität abzubilden.
Komplex ist es, weil das Problem selbst komplex ist. SQL ist standardisiert, kompakt, sehr schnell, tatsächlich testbar und eine logische Sprache. Nicht jeder kann es sofort warten, aber das gilt genauso, wenn man in Java viele Zeilen und Funktionen schreibt.
Ich mag auch, dass SQL Tiefe hat. Es trägt seit über 40 Jahren die Datenwelt, also ist es nur natürlich, dass Leute Nischenfunktionen eingefordert haben. Die MODEL-Klausel von Oracle ist eines meiner Lieblingsfeatures, weil man damit mehrdimensionale Arrays umsetzen kann, und ein Freund hat damit Conways Game of Life in deutlich weniger Zeilen implementiert, als ich erwartet hätte.
Am Ende habe ich sie in nativen Code neu geschrieben und auf unter eine Sekunde gebracht; der Großteil der Arbeit bestand darin zu beweisen, dass das Ergebnis identisch war, und Testfälle zu schreiben und zu dokumentieren, damit die nächste Person nicht dasselbe durchmachen muss. Seitdem vermeide ich es meist, viel Business-Logik in SQL zu packen.
Meiner Meinung nach sollten komplexe Dinge sowohl manuell als auch automatisiert leicht testbar sein. SQL ist für manuelle Tests einfach, aber für automatisierte Tests schwerer als Code in einer Programmiersprache. Ein Haufen Spaghetti-Code lässt sich wenigstens weniger dicht auseinanderziehen und Stück für Stück angehen; bei verwobenen SQL-Spaghetti weiß ich gar nicht, wo man anfangen soll.
Ich stimme auch nicht völlig zu, dass mehr Zeilen automatisch ein höheres Bug-Risiko bedeuten. Nicht jede Zeile ist gleich. Eine einzelne SQL-Zeile mit 400 Zeichen ist vermutlich schwerer visuell auf Probleme zu prüfen als 400 Zeilen Java-Code, und das sage ich, obwohl ich Java aus vielen Gründen nicht mag.
Wenn du solche dekadenten Herausforderungen magst: Ich habe Advent of Code dieses Jahr in Google Sheets ausprobiert.
Ich bin nur bis Tag 6 gekommen und habe auch nicht jeden Tag beide Sterne geholt. Ich bin ziemlich sicher, dass meine Lösung für Tag 7 korrekt ist, aber bei langen Eingaben bin ich an die Zeichenbegrenzung pro Zelle gestoßen.
Viel Spaß damit. Auf Mobilgeräten sollte man es aber besser nicht öffnen. Manche Sheets bringen die App zum Absturz.
https://docs.google.com/spreadsheets/d/10FY-89y19tnRM_EAAnCd...
Ich habe im Lauf meiner Karriere mehr SQL geschrieben als jeden anderen Code-Typ. In den letzten fünf Jahren zwar weniger, sodass ich wohl vieles vergessen habe, aber früher hat es mir wirklich Spaß gemacht.
Wenn man aufhört, iterativ zu denken, und anfängt, in Mengenoperationen zu denken, wird es ziemlich natürlich und mächtig.
Wenn das Schema gut aufgebaut ist und zur Sichtweise der Business-Stakeholder passt, kann in SQL-Abfragen definierte Geschäftslogik ziemlich intuitiv sein.
Code, Frameworks, ORM, „Best Practices“, Muster und Ähnliches sind letztlich Ablenkungen. Es gibt unzählige Wege, Daten in eine Datenbank hinein- und wieder herauszubekommen, und das Verschieben von Bits an sich hat nur geringen Wert. Viele übertriebene Softwarelösungen hätten auch eine einfache Merge-Anweisung oder ein CSV-Import getan.
Ein großer Teil der Missverständnisse und schlechten Gefühle gegenüber SQL entsteht, weil man mit schmutzigen Schemas arbeiten muss. Die Sprache selbst ist wirklich stark domänenspezifisch. Wenn man solche Abfragen gar nicht erst schreiben müsste, würde man sich wohl auch nicht so sehr über schrecklich verschachtelte Abfragen und den daraus entstehenden SQL-Syntaxschmerz beschweren. Wenn man Tupel und Relationen an die Art anpasst, wie das Geschäft normalerweise spricht, kämpft man mit der Zeit weniger mit solchen Dingen. Oft kann man das Schema nicht von Anfang an refaktorisieren, aber man kann Replikate oder Views rund um ein schlechtes Schema anlegen und sie zum Ziel neuer Entwicklung und Refaktorierung machen.
Natürlich hat SQL Schwächen, auch ernste wie die Testbarkeit. Trotzdem wünschte ich mir am Ende, alle Programmierung wäre so. Der Computer entscheidet intern, wie etwas ausgeführt wird, und der Mensch konzentriert sich auf die Logik.
Ich habe versucht, als nächsten Schritt mal grob in Prolog hineinzulesen, bin bisher aber gescheitert. Ein Teil des Motivs war auch, etwas von SQL zu vergessen, um nicht zu sehr darin gefangen zu sein. Vielleicht liegt die Zukunft des Programmierens irgendwo zwischen SQL und Prolog.
Wenn man nur aus Sicht von Mengenoperationen denkt, bekommt man leicht eine Abfrage, die statt 5 Millisekunden 5 Minuten braucht. Der Denkprozess im Kopf ist fast immer eine Wiederholung von „Mit welcher Tabelle beginne ich, welche Zeilen sehe ich in welcher Reihenfolge an, womit joine ich unter welchen Bedingungen, und wie aggregiere ich das?“. Es fühlt sich eher nach einem mentalen Modell aus Schleifen und Aggregation an als nach Mengenoperationen.
Viele Leute springen zu allen möglichen irrelevanten Dingen, aber der Großteil der Softwaretechnik besteht darin, die richtigen Daten in das richtige Format zu bringen und sie zuverlässig zu bewegen.
Ich habe kürzlich eine komplexe verteilte Codebasis stark refaktoriert, und die eigentliche „Arbeit“ war fast nur die Neugestaltung des Schemas. Der Rest war viel Zeit fürs Coden, kam aber im Grunde eher einer Implementierung gleich.
Es gibt auch andere Wege, Schemas zu definieren als SQL, aber um echte Systemtechnik zu lernen, ist SQL ein perfekter Ansatz.
Ich benutze extrem viel SQL und implementiere einen großen Teil der Geschäftslogik von Stream-Processing-Anwendungen in SQL. Besonders gefällt mir der Ansatz, nicht die Daten zur Berechnung zu bringen, sondern die Berechnung zu den Daten zu bringen.
Allerdings treffe ich oft Entwickler, die diese Idee nicht mögen. Sie nehmen gewaltige I/O-Kosten in Kauf, verschieben alle Daten ins Backend und wollen die Berechnung in einer „echten“ Programmiersprache ausdrücken.
Das Konzept SQL finde ich gut, aber die Sprache SQL ist aus meiner Sicht das Problem. Es gibt zu viele unbeholfene Stellen, und nach etwa 40 Jahren ohne Konkurrenz ist das auch nicht weiter erstaunlich. Das Programmmodell im Kopf ist gut, aber um Eleganz zu sehen, muss man über die Syntax hinaus auf das Programm schauen, das man tatsächlich schreibt.
Was gebraucht wird, ist eine richtige Programmiersprache, die für bestehende Datenbanken (Postgres, MSSQL) entworfen ist und in SQL-Dialekte kompiliert. Es gibt Kandidaten, aber sie sind entweder auf bestimmte Bereiche beschränkt, wie PreQL, das keine Datenänderungen erlaubt, oder sie sind mit anderen Datenbanken gekoppelt.
Ich hätte Lust, so etwas selbst zu bauen, aber das ist zu viel Arbeit, der Weg bis zur Akzeptanz ist sehr lang, Erfolg ist nicht garantiert, und ein tragfähiges Geschäftsmodell fällt mir auch nicht ein.
Beliebte Backend-Sprachen wurden von Großunternehmen geschaffen, aber das Coden in SQL scheint in einem Teufelskreis zu stecken: Es wird herabgesetzt, bis es eine bessere Sprache gibt, und eine bessere Sprache entsteht nicht, bis es beliebter wird.
Common Table Expressions und Window Functions haben einen großen Unterschied gemacht, und besonders Window Functions verdrehen einem zwar etwas den Kopf, machen schwierige Dinge aber etwas leichter.
Ich verwende BigQuery, das Structs und Arrays unterstützt, und erst vor Kurzem wurde es möglich, Arrays zu gruppieren, aber Dinge wie Gleichheitsprüfungen fehlen noch.
BigQuery fügt langsam syntaktischen Zucker hinzu, etwa Aggregat-UDFs und polymorphe UDFs mit
ANY TYPE-Parametern. Dadurch packe ich mehr wiederverwendbare Logik in saubere Funktionen, aber persönlich würde ich mir wünschen, dass temporäre Funktionen ähnlich wie Common Table Expressions deklariert werden und einen klaren Geltungsbereich haben, damit sie sich besser mit Tools wie DBT integrieren, die gern alles in eine einzige Anweisung packen.Wenn ich eine einzelne Funktion nennen müsste, die die Produktivität am meisten erhöhen würde, dann wäre es die Möglichkeit, in
JOIN USINGdas Null-Verhalten festzulegen. In Joinsfoo.bar IS NOT DISTINCT FROM bar.barauszuschreiben, ist nicht intuitiv und sieht hässlich aus. Etwas wieUSING (bar RESPECT NULLS)wäre viel besser.Umgekehrt will man bei einer Microservices-artigen Struktur, in der kleine Services jeweils ihre eigene Datenbank besitzen und nur die Hälfte davon relationale Datenbanken sind, eher weniger komplexen Code in die Datenbank selbst legen. Der Grund ist, dass man häufig zwischen einzelnen Instanzen oder Clustern wechselt und dabei entweder nur relativ einfache Daten-Dumps mitnimmt oder nach Art des Schiffs des Theseus neue Replikate anfügt.
Dass das komplett in reinem SQL umgesetzt wurde, ist wirklich beeindruckend, aber das eigentliche Zeichen von fractured engineer energy ist wohl eher eine Blogspot-Seite, die seit 10 Jahren gepflegt wird
Schwer genau zu erklären, aber es vermittelt stark das Gefühl von „erfahrene Leute in einer Nische“. Auch ohne die Autoren zu kennen, wirkt es so, als bräuchten ein paar Leute, die 10 Jahre lang eine Blogspot-Seite namens „database architects“ betreiben, in den richtigen Communities eigentlich keine weitere Vorstellung
Zur Einordnung: Ich habe Advent of Code ein paar Tage lang mit EdgeQL gemacht, und das war eine ziemlich interessante Erfahrung
Ich habe ein paar Tweets dazu gepostet und sollte wohl einen Blogbeitrag darüber schreiben
https://x.com/1st1/status/1864069589245858083
Vergleich mit SQL: https://x.com/1st1/status/1864412869108092997
Völlig grauenhaft. Trotzdem gut gemacht
Für alle, die ihn nicht kennen: Der Autor ist einer der weltweit besten Datenbankforscher