【SQL】JOINが覚えられないのでアルゴリズムを想像してみる
2024/10/20
こんにちは、SQL初心者のsititou70です。
INNER JOIN、LEFT OUTER JOIN、FULL OUTER JOINがなかなか覚えられないので、具体的なアルゴリズムを考え、それをPostgreSQLの動作と比較してみる試みです。
今回は、2つのテーブルを=の条件で結合する単純なケースを考えます。
リポジトリ：https://github.com/sititou70/join-play
テーブル構造
create table t1 (val integer);
create table t2 (val integer);テーブルt1とt2があります。val列があり、数値またはNullが入ります。
3値論理における等価性
データベースでは3値論理が採用されているそうです。
「a = b」の結果が true になるのは、a と b がともに NULL でなく、かつ同じ値であるときに限ります。
これをTypeScriptのコードで表すと以下のようになります。
type Value = number | null;
const eq = (val1: Value, val2: Value): boolean => {
if (val1 === null) return false;
if (val2 === null) return false;
return val1 === val2;
};JOINのアルゴリズムを想像する
INNER JOIN
さきほどのeqを使って、INNER JOINは以下のように表せます。
const innerJoin = (t1: [Value][], t2: [Value][]): [Value, Value][] => {
let res: [Value, Value][] = [];
for (const [val1] of t1) {
for (const [val2] of t2) {
if (eq(val1, val2)) {
res.push([val1, val2]);
}
}
}
return res;
};2つのテーブルをとって1つの結果のテーブルを返す演算です。
t1のvalをval1、t2のvalをval2とおきます。各val1について、各val2が等しければ結果として取り出します。
ここで、Nullは何とも等しないことに注意すると、結果にNullが現れないこともわかります。
LEFT OUTER JOIN
INNER JOINと似ていますが、各val1が結果として取り出されなかったときに、val2をNullとして取り出すところが違います。
const leftOuterJoin = (t1: [Value][], t2: [Value][]): [Value, Value][] => {
let res: [Value, Value][] = [];
for (const [val1] of t1) {
let selected = false;
for (const [val2] of t2) {
if (eq(val1, val2)) {
res.push([val1, val2]);
selected = true; }
}
if (!selected) res.push([val1, null]); }
return res;
};val1は、すべて結果に含まれることになります。val1と等しいval2があれば取り出されますし、なければval2をNullとして取り出されるからです。
FULL OUTER JOIN
LEFT OUTER JOINに加えて、各val2が結果として取り出されなかったときに、val1をNullとして取り出します。
const fullOuterJoin = (t1: [Value][], t2: [Value][]): [Value, Value][] => {
let res: [Value, Value][] = [];
let selectedT1Val = new Set<number>();
let selectedT2Val = new Set<number>();
for (const [idx1, [val1]] of t1.entries()) {
for (const [idx2, [val2]] of t2.entries()) {
if (eq(val1, val2)) {
res.push([val1, val2]);
selectedT1Val.add(idx1);
selectedT2Val.add(idx2);
}
}
}
for (const [idx1, [val1]] of t1.entries())
if (!selectedT1Val.has(idx1)) res.push([val1, null]);
for (const [idx2, [val2]] of t2.entries())
if (!selectedT2Val.has(idx2)) res.push([null, val2]);
return res;
};Setを使って取り出されたval1とval2を覚えておき、処理の最後で取り出されていないval1とval2について、相手をNullとして取り出します。
PostgreSQLの動作と比較
これまで作成した関数に対して、実際にPostgreSQLに接続して動作するバージョンを作成します。
例えばINNER JOINについては以下のようになります。
import { Client } from "pg";
const client = new Client({
// ...
});
const innerJoinNaive = async (
t1: [Value][],
t2: [Value][]
): Promise<[Value, Value][]> => {
const res = await client.query(`
${resetTable("t1", t1)}
${resetTable("t2", t2)}
select
t1.val as t1_val,
t2.val as t2_val
from
t1
inner join t2 on t1.val = t2.val;
`);
return extractQueryResult(res as unknown as PGResult);
};そして、ランダムなテーブルを生成する関数も作ります。
長さが0〜4で、値が1、2、nullのいずれかであるIdの列を生成します。
const generateRandomTable = (): [Value][] => {
const vals = [1, 2, null];
const length = Math.floor(Math.random() * 5);
return [...Array(length).keys()].map(() => [
vals[Math.floor(Math.random() * vals.length)],
]);
};
// 生成例
// [ [ 1 ], [ 2 ], [ 2 ] ]
// [ [ 1 ], [ 1 ], [ 1 ] ]
// [ [ 1 ] ]
// [ [ 1 ], [ null ], [ 2 ], [ 1 ] ]
// [ [ 2 ] ]
// [ [ null ], [ 2 ] ]
// [ [ 1 ], [ 1 ] ]ランダムに生成されたt1とt2について、innerJoin(t1, t2)とinnerJoinNaive(t1, t2)の結果は一致するはずです。
今回は、結果の行の順番が並び変わっているだけなら同じ結果であると判定します。
テスト結果
適当に生成した1,000件のテストケースについて、innerJoin、leftOuterJoin、fullOuterJoinはPostgreSQLの動作と一致しました。
テストは約7秒で完了しました。
まとめ
少なくとも今回想定したテストケースの範囲では、想像したJOINのアルゴリズムは正しそうなことが確かめられました。
これらのアルゴリズムは、DB内部の実際の動作とは違います。DBでは、場合に応じてもっと最適化された動作（Merge JoinとかHash Joinとか？）をしているはずです。
ただ、心の中にあるJOINの動作として理解しておくと、実際の業務で混乱することが少なくなるのではないでしょうか。
SQL初心者なので間違っている点があれば教えてください。
ありがとうございました。
