純粋なSQLで実装された Advent of Code 2024
(databasearchitects.blogspot.com)- 純粋なSQLだけで Advent of Code 2024 の全問題を解くことができ、SQL が一般的なパズル解法とは異なる考え方を強いる点が核心
- 小規模なフィールド探索は、入力のパースから再帰クエリベースの探索と集計まで、SQL 内で比較的自然に処理できる
- Day 16 のように状態が大きく増える問題では、表現そのものより評価コストが問題で、実際の入力では200GB超のメモリが必要になるほど非効率が大きい
- Day 23 の最大クリーク問題はBron-Kerbosch アルゴリズムと相性が良いが、複数の集合を扱おうとする構造が、単一の集合を渡す再帰 SQL モデルと衝突する
- SQL で複雑なアルゴリズムを書くことは可能だが、再帰中の状態更新とより豊かな状態操作があれば、データベース内部での実行はさらに実用的になる
Advent of Code 2024 を SQL だけで解く
- Advent of Code 2024 を純粋なSQLで解き、すべての問題を SQL だけで解決できた
- 全体の解法は GitHub リポジトリ で公開されている
- 問題を別のやり方で考えさせられ、多くの場合 SQL は予想以上に快適なツールとして機能した
Day 11: 小規模な探索問題に向く SQL
- Day 11 の全体解法は、パズル入力まで含めて 1 本の SQL で構成されている
- 入力処理は、文字列を段階的にテーブル構造へ変換していく流れになっている
- パズル入力を文字列として置く
- 入力を個々の行に分割する
- 各文字を座標と値に変換し、2D 配列形式のテーブルを作る
- アルゴリズム部分は比較的短く保たれている
- 再帰クエリでフィールドを探索する
- 探索結果からパズルの答えを抽出する
- このような小規模の探索では、SQL は十分うまく機能する
Day 16: 再帰 SQL の状態保持コスト
- Day 16 は Day 11 と似たようにフィールドを探索し、訪問した各地点の最小探索距離を計算する
- SQL で表現するのは簡単だが、評価過程は無駄が多い
- 実際のパズル入力ではフィールドが大きくなるにつれて、再帰クエリが多くの状態を生成して保持する
- 実際に必要なのは、再帰クエリの最後の反復結果だけである
- それにもかかわらず、計算されたタプルの大半が保持される
- そのため、このクエリの実行には200GBを超えるメモリが必要になる
- 再帰中に反復セマンティクス(iteration semantic)を使えば、過剰なメモリ使用を減らせる
- Umbra はこれを実行できる
- Postgres と DuckDB はこれをサポートしていない
- そのため、この機能は解法では使わなかった
Day 23: 複数の集合を必要とするアルゴリズムの限界
- Day 23 は、疎グラフで最大クリークを見つける必要がある問題だった
- この問題は Bron-Kerbosch アルゴリズム で妥当に計算できる
- しかしこのアルゴリズムは複数の集合を維持しようとする一方、再帰 SQL は単一の集合しか渡せない
- 実装は可能だったが、SQL の表現はかなり複雑になり、結果のコードもきれいとは言えない形になった
再帰 SQL にさらに必要な機能
- 複雑なアルゴリズムも SQL で書くことはでき、多くの場合 SQL コードは予想より読み書きしやすかった
- 再帰 SQL に状態更新メカニズムがあれば、より効率的で書きやすくなる可能性がある
- 再帰でより複雑な制御フローを支えるためのトランポリンメカニズムの研究が進められており、このアプローチも有用である
- より複雑な状態操作メカニズムもあわせて検討する必要がある
- 少し機能が追加されるだけでも、SQL は複雑なアルゴリズムをデータベース内部で直接実行するための堅牢な選択肢になり得る
1件のコメント
Hacker News のコメント
こういうことをやり遂げられるのは、本当にすごい人だけ。純粋な芸術で、プログラミングの世界にはこういうものがまだまだ足りない
このタイトルを見て、Taco Bell の新メニューを見たときと似た反応をした。欲望、羞恥心、そして人間の創造性への感嘆が妙に混ざった感じ
Advent of Code のような問題では、おそらく入力パースが一番難しい部分だと思う
もしかするとタブレットのインターフェースを掘れば材料が分かるのかもしれないが、今のところは運任せのゲームみたいだ。真面目な話、https://www.amazon.com/Joe-Celkos-SQL-Smarties-Programming-d... は極限の SQL 職人技を学ぶ名講義だ
HN 全体が人間の創造性に関する場所ではないかと思うし、全部を Taco Bell のメニューを見るような気分で受け止めるべきなのか、よく分からない
よくできている。最初は狂気に見えるが、大規模な SQLは複雑さを収める最良の方法の一つだと思う
複雑なのは、問題そのものが複雑だからだ。SQL は標準で、圧縮度が高く、非常に速く、実際にテスト可能で、論理的な言語だ。誰もがすぐに保守できるわけではないが、Java で大量の行と関数を書いた場合でも同じだ
SQL が奥深いのも良い。40年以上にわたってデータの世界を支えてきたのだから、人々がニッチな機能を求めてきたのは当然だ。Oracle の model 句は多次元配列を実装できるので好きな機能の一つで、友人はそれで Conway のライフゲームを予想よりずっと少ない行数で実装していた
結局ネイティブコードで書き直して1秒未満まで短縮し、作業の大半は同じ結果を出すことを証明し、次の人が同じ苦労をしないようにテストケースを書いて文書化することだった。それ以来、多くのビジネスロジックを SQL に入れるのはだいたい避けるようになった
個人的には、複雑なものは手動でも自動でも簡単にテストできるべきだと思う。SQL は手動テストは簡単だが、自動テストはプログラミング言語のコードに比べて難しい。スパゲッティコードの塊なら、もう少し疎にほどいて部分ごとに攻めることもできるが、絡み合ったSQL スパゲッティをどう扱えばいいのか途方に暮れる
行数が多いほどバグのリスクが高まるという話にも完全には同意しない。すべての行が同じではないからだ。400文字の SQL 1行は、400行の Java コードよりも目で追って問題を見つけるのが難しい可能性が高いし、Java をいろいろな理由で嫌っている立場でもそう思う
こういう種類の退廃的な挑戦が好きなら、今年の Advent of Code を Google Sheets でやってみた
6日目までしか進んでおらず、毎日星を2つとも取れたわけでもない。7日目の解法は正しいとかなり確信しているが、長い入力ではセルあたりの文字数制限に引っかかった
楽しんでほしい。ただしモバイルでは開かない方がいい。一部のシートがアプリを落とす
https://docs.google.com/spreadsheets/d/10FY-89y19tnRM_EAAnCd...
キャリアを通じて、他のどんな種類のコードよりも SQL を多く書いてきた。ここ5年はあまり書いていないのでかなり忘れているだろうが、昔は本当に楽しんでいた。
反復的に考えるのをやめて 集合演算 で考え始めると、かなり自然で強力になる。
スキーマがよく構成されていて、ビジネス関係者の視点と合っていれば、SQLクエリで定義されたビジネスロジックはかなり直感的になり得る。
コード、フレームワーク、ORM、「ベストプラクティス」、パターンなどは、結局は気を散らす要素である。データをデータベースに出し入れする方法は無数にあり、ビットを移動すること自体の価値は低い。単純なマージ文やCSVインポートで済んだはずの、大げさなソフトウェアソリューションは多い。
SQLに対する誤解や悪感情のかなりの部分は、散らかったスキーマを扱わなければならないことから生じる。言語自体は本当にドメイン特化的だ。そもそもそうしたクエリを書く必要がなければ、ひどくネストしたクエリや、それに伴うSQL構文の苦痛について、そこまで不満を言わなかっただろう。タプルとリレーションを、ビジネスが通常語るやり方に合わせれば、時間がたつにつれてこうしたものと格闘することは少なくなる。最初からスキーマをリファクタリングできない場合も多いが、悪いスキーマの周囲にレプリカやビューを置き、新規開発やリファクタリングの対象にすることはできる。
もちろんSQLには欠点があり、テスト可能性のように深刻なものもある。それでも結局、すべてのプログラミングがそのようであればいいと思う。内部でどうするかはコンピュータが決め、人間は論理に集中するやり方だ。
さらに一歩進もうとしてPrologをざっと読んでみようとしたが、まだうまくいっていない。SQLに縛られすぎないよう、一部を忘れてみる目的もあった。もしかすると SQLとPrologの間 のどこかに、プログラミングの未来があるのかもしれない。
集合演算の観点だけで考えると、5ミリ秒ではなく5分かかるクエリになりがちだ。頭の中のプロセスはほとんど常に「どのテーブルから始めるか、どの行をどの順序で見るか、何とどんな条件で結合するか、どう集計するか」の反復である。集合演算ではなく、ループと集計のメンタルモデルに近いものとして考えることになる。
多くの人はいろいろな見当違いの場所へ飛び移るが、ソフトウェア工学の大部分は、正しいデータを正しい形式に入れ、安定して移動することだ。
最近、複雑な分散コードベースを大きくリファクタリングしたが、実際の「仕事」と呼べるものはほとんどスキーマ再設計だけだった。残りは多くの時間を費やしたコーディングだったが、実際には実装に近かった。
SQL以外にもスキーマを定義する方法はあるが、本物のシステム工学を学ぶにはSQLが完璧な方法だ。
SQLを非常に多く使っており、ストリーム処理アプリケーションのビジネスロジックのかなりの部分をSQLで実装している。特に、データを計算へ移すのではなく 計算をデータ側へ持っていく方式 が本当に気に入っている。
しかし、その考えを嫌う開発者にもよく出会う。膨大な入出力コストを受け入れてすべてのデータをバックエンドへ移し、計算を「本物の」プログラミング言語で表現したがる。
SQLという概念は良いが、SQLという言語が問題だと思う。ぎこちない部分があまりに多く、40年ほど競争がなかったのだから不思議ではない。頭の中のプログラムモデルは悪くないが、優雅さを見るには、構文の向こう側で実際に使っているプログラムを見なければならない。
必要なのは、既存のデータベース（Postgres、MSSQL）を対象に設計され、SQL方言へコンパイルされる、きちんとした プログラミング言語 だと思う。候補は見えるが、データ変更を許可しないPreQLのように特定の領域に縛られていたり、別のデータベースと結合していたりする。
自分で作りたい気持ちはあるが、作業量があまりに多く、採用されるまでの道のりは長く、成功の保証もなく、思いつく収益モデルもない。
人気のあるバックエンド言語は大企業が作ったが、SQLでコーディングすることは、より良い言語が生まれるまでは軽視され、もっと人気が出るまではより良い言語が出てこないという ジレンマ に陥っているように見える。
共通テーブル式 とウィンドウ関数は大きな違いを生み、特にウィンドウ関数は少し頭をひねらせるが、難しいことを少し簡単にしてくれる。
BigQueryを使っているが、構造体と配列をサポートしており、最近になってようやく配列をグループ化できるようになった。ただし等価性検査のようなものはまだない。
BigQueryは、集計ユーザー定義関数、
ANY TYPEパラメータを使う多相ユーザー定義関数のような構文糖を少しずつ追加している。再利用ロジックをきれいな関数へより多く入れられるようになるが、個人的には一時関数が共通テーブル式のように宣言され、スコープが定められて、DBTのようにすべてを1つの文に入れたがるツールとよりよく統合されることを望んでいる。生産性を最も高めてくれる機能を1つ挙げるなら、
JOIN USINGでnullの動作を指定できるようにすることだ。結合でfoo.bar IS NOT DISTINCT FROM bar.barと書き下すのは直感的ではなく見た目も悪い。USING (bar RESPECT NULLS)のような形ならずっと良さそうだ。逆に、小さなサービスがそれぞれ自分のデータベースを所有し、そのうち半分だけがリレーショナルデータベースである マイクロサービス式 の構造ほど、データベース自体には複雑なコードをあまり置きたがらない。単一インスタンスやクラスター間を頻繁に移動し、比較的単純なデータダンプだけを持っていくか、テセウスの船のように新しいレプリカをつないでいく形だからだ。
純粋なSQLでやり遂げたのも本当に印象的だが、本物のひび割れたエンジニア・エネルギーの象徴は、10年続いているBlogspotサイトのように思える
正確に説明するのは難しいが、「ニッチ分野の熟練者」という感じが強い。著者たちを知らなくても、「database architects」というBlogspotサイトを10年にわたって維持している数人なら、しかるべきコミュニティではあえて紹介する必要もなさそうだ
ちなみに数日間、EdgeQLでAdvent of Codeをやってみたが、かなり興味深い体験だった
ツイートをいくつか残していて、ブログ記事に書くべきだと思っている
https://x.com/1st1/status/1864069589245858083
SQLとの比較: https://x.com/1st1/status/1864412869108092997
完全にひどい。それでもよくやった
知らない人のために補足すると、著者は世界最高峰のデータベース研究者の一人である