SQLと手続き型言語 － JOIN を手続き型で書いてみる
SQL と手続き型言語（オブジェクト指向言語）は最終的には同じです。
今回は、JOIN を手続き型言語（Javaっぽく）書いてみます。
目次
オプティマイズについて
SQL を実行する前に手続き型のソースに変換されます。この処理をオプティマイズと言い、その処理を行う機能はオプティマイザと呼ばれています。
単純に SQL と手続き型に１対１で変換することをルールベースオプティマイズと言います。
SQL を変換するときテーブルのレコード数やインデックスを考慮し、どのインデックスを使うか、あるいは、何を外部表とするかまで統計情報を使って判断してから変換する方式を、コストベースオプティマイズと言います。
1990年代は、「将来、コストベースになります」というアナウンスはなされていましたが、ルールベースが主流でした。現在はコストベースが主流になっています。
もちろん、設定でルールベースに切り替えることはできますが、現在もルールベースで利用されているのは SQLite ぐらいじゃないかと思います。
２つの表をJOINしたSQL
以下の SQL を代表的な４つのアルゴリズムで Javaっぽく書いています。
SELECT *
FROM 外部表
INNER JOIN 内部表
ON句の条件
WHERE
外部表のWHERE句の条件
AND 内部表のWHERE句の条件
;
単純なネスティッドループ（NESTED LOOP）
JOIN にインデックスを使えないときに選択されます。
HASH JOIN のアルゴリズムを持っている RDBMS であればこのアルゴリズムが選択されることはまずなく、ハッシュジョインが選択されるはずです。
HASH JOIN がない MySQL ではよく見られます。「MySQL は JOIN が遅い」と言われる理由でもある。
foreach ( row外部 : 外部表 ) {
if ( ! 外部表のWHERE句の条件 ) { // ネストを減らすため否定形
continue; // WHERE句の条件に合わなかったら飛ばす。
}foreach ( row内部 : 内部表 ) {
if ( ON句の条件、内部表のWHERE句の条件 ) {
result.Add(row外部, row内部);
}
}
}
インデックスを使ったネスティッドループ（NESTED LOOP）
オーソドックスな JOIN です。
「外部表のWHERE句の条件」で十分に絞り込める。とオプティマイザが判断したときによく選択されます。
foreach( row外部 : 外部表 )
if( ! 外部表のWHERE句の条件 ) {
continue; // WHERE句の条件に合わなかったら飛ばす。
}
wrkIndexs = 内部表.IndexRangeScan(row外部.内部のキー)
foreach ( wrkIndex : wrkIndexs ) {
if ( インデックス以外のON句の条件 ) {
resultRow = 内部表.GetRowByIndex(wrkIndex);
if( resultRow を使ったWHEREの条件 ){
result.Add(row外部, resultRow );
}
}
}
}
ハッシュジョイン（HASH JOIN）
内部表（マスタ類など）を一旦、メモリー上のハッシュテーブルに入れて処理する形です。「外部表のWHERE句の条件」で絞り込んだ結果が多くなると判断されたとき、選択されることが多いアルゴリズムです。
foreach( row内部 : 内部表){ // 内部表を全件読んでいる
hash内部.put(row内部);
}
foreach(row外部 : 外部表){
if ( ! 外部表のWHERE句の条件 ) { // ネストを減らすため否定形
continue; // WHERE句の条件に合わなかったら飛ばす。
}
row内部s = hash内部.get(row外部.キー); // 1件とは限らない
foreach(row内部 : row内部s){
if( ON句の条件、内部表のWHERE 条件 ){
result.Add(row外部, row内部);
}
}
}
ソートマージジョイン（SORT MERGE JOIN）
HASH JOIN の方が速くなるため、現在では選択されることはほとんどありませんが、両方のキーにインデックスがあるとき、あるいは、FULL OUTER JOINなどのときに選択されることがあります。
外部表.Sort(キー); // これが遅いからあまり選択されない内部表.Sort(キー); // これが遅いからあまり選択されない
i = 0;
j = 0;
while ( i < 外部表.Count ){
if ( ! 外部表のWHERE句の条件 ) { // ネストを減らすため否定形
continue; // WHERE句の条件に合わなかったら飛ばす。
}
while ( j < 内部表.Count ){
if ( 外部表(i).キー = 内部表(j).キー ) {
if ( 外部表のWHERE句の条件 ) {
result.Add(外部表(i), 内部表(j));
}
} else if ( 外部表(i).キー < 内部表(j).キー ) {
break;
} // else なしを嫌う人もいるけど
j++;
}
i++;
}
少なくとも４種類考えられる
２つの表を JOIN しただけの単純な SQL でも上のように少なくとも４種類は考えられ、それぞれに、「外部表のWHERE句の条件」、「内部表のWHERE句の条件」について、インデックスを使った方が良いかの判断が行われ、使われるケースと使われないケースがあります。
それぞれのパターンを考えると、昨今、「センサーの状況で少し分岐した処理をする」という機能を持った家電に「AI搭載（似非AI）」と謳っている広告が多いですが、それ以上のレベルの機能は30年ほど前には確立され、20年前には十分に実用レベルになっていた訳です。
ちなみに、私も手続き型言語（オブジェクト指向言語）からキャリアをスタートさせていますから、SQL を考えるとき先に手続き型で考えています。
上に書いたことの逆の思考をしているのです。
なぜ ORM を目の敵にするか
ORM からは、RDBMS の内部にある統計情報を見る手段がありません。
よしんば見れたとしても、大量のデータキャッシュを保持している RDBMS のインプロセスで処理した方が圧倒的に効率的です。
統計情報が見れないのであれば、理論上、ORM は RDBMS が備えるオプティマイザを超えない訳です。
そもそも、ORM は、「SQLを書きたくない。手続き型で全部処理したい」という欲求から生まれています。
「その欲求がそもそも勘違いである」
というのが私の主張で、
手続き型（ORM） → 非手続き型（SQL）→ 手続き型（実行計画）
という流れは、典型的な車輪の再開発です。
通常、批判される車輪の再開発は開発期間だけの無駄なのですが、この流れは実行時にも毎回同じことが繰り返されることが重要です。あり得ないレベルでの車輪の再開発なのです。
車輪の再開発が起きるのは、車輪の機能を正しく理解してないからです。
つまり、ORM を作ったり、使ったりしてしまうのは、それだけで SQL、RDBMS の理解が足りてないと証明されてしまいます。
もちろん、正しく理解されてない時代が長いため、最新の言語と比べると SQL の不便さが際立ってしまっているところもあります。しかし、ここ20年間に大量のリソースを「車輪の再開発」に費やしてきました。
その間に、
「ORM が良い」
「否、SQL を書くべき」
という議論は、何度も起きては消えしてきました。
その間に、消えて行った ORM はいくつもありますが、「消える」と言われた SQL は消えていません。理論上、ORM は、SQL を超えないからです。
私は、「SQL を正しく理解して SQL の不便さを解消する」という方向に向かうべきで、今からでも遅くないと考えています。
次回は、NoSQL と SQL について書きます。
