2023-09-21

SQL は嫌いだ。
(正確には、自動呼び出しされる SQL が嫌いだ。
人が都度書いて実行するためのものと見るなら、まあ、多少マシだ。)
SQL は嫌いだが、なぜか世には SQL が溢れている。
そんな嫌いな SQL についての話を徒然なるままに書こうかと思った。

私は SQL が嫌いなんだと思っていた。
しかし、この前 SQL 実装にも嫌悪感を覚えた。
結論から言うと、どうやら、多くの SQL 実装の COUNT と OFFSET の実装は欠陥品だ。
これらはいかなるインデックスを用意しても O(n) のオペレーションである。カスだ。

多くの SQL 実装のインデックスは Btree を利用している。
複数種類のインデックスがあるだろうが、原則 Btree だ。
Btree は検索木の一種であり、
順序を定義できる要素を効率的に検索できるデータ構造だ。
しかし、純粋な Btree しかないと、
「この要素が全体で何番目か」とか「何番目の要素はなにか」といった
問に答えるためには、隅から順に数える仕事が必要である。
「何番目」の数だけの要素を実際に見ないと、これらの問には答えられない。
「何番目」を n として、 O(n) の計算時間である。
これが多くの SQL 実装の COUNT と OFFSET の問題だ。

しかし、
少し考えればかんたんな工夫でこれらの問に答えることができるとわかる。
そのような工夫をした検索木を世の中では Order statistic tree と言うらしい。
日本語訳するなら、順序統計木だろうか。
この木は、各ノードがその子孫ノードが持つ要素数を記録しておくことで、
検索木の弱点を克服する。
今まで「何番目」個の要素を読み飛ばす必要があったが、
この工夫によって「目的より前にある」とわかっているサブツリーの
根が持っている「小孫数」を足し合わせる仕事になる。
この仕事量は O(log(n)) であり、実用的だ。
インデックスの更新にかかるコスト増加も、
せいぜい更新したいノードとその先祖の書き換え程度であり、やはり O(log(n)) だ。
SQL テーブルのインデックスとして問題なく機能するだろう。

悲してことに、私の見た範囲では、この機能を持つ SQL 実装は存在しない。
SQL には COUNT や OFFSET というモノがあるのに、存在しないのだ。
COUNT や OFFSET の処理を実装した人間は何を考えていたんだろう。
なぜ自分の仕事がおかしいと気づかなかったんだろう。

OFFSET や COUNT の欠陥に気づいている SQL の利用者はどのくらいいるだろう。
多くのウェブサイトが「ページ送り」の実装に「ページ番号」を利用していることから、
おそらくほとんどいないのではないかと思う。
多くの利用者は、不幸にも OFFSET や COUNT の欠陥に気づけないために、
多くの CPU 時間を無駄にしているわけだ。

利用者が実装の欠陥に気づかないのは、 SQL の設計思想の根本的な欠陥のせいだ。
すなわち、

* 抽象的な言語であるために、実際のアルゴリズムをプログラマが制御できない
* 実行時までナントカ計画を行わないものであるために、事前に処理内容を把握できない

これらの欠陥は見ようによっては実装の欠陥であり、
妥当に実装することでかなり緩和されるだろう。
しかし、そもそも SQL は使いやすい言語ではないので、 SQL は嫌いだ。