【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 (id integer);
create table t2 (id integer);テーブルt1とt2があります。id列があり、数値またはNullが入ります。
3値論理における等価性
データベースでは3値論理が採用されているそうです。
「a = b」の結果が true になるのは、a と b がともに NULL でなく、かつ同じ値であるときに限ります。
これをTypeScriptのコードで表すと以下のようになります。
type Id = number | null;
const eq = (id1: Id, id2: Id): boolean => {
if (id1 === null) return false;
if (id2 === null) return false;
return id1 === id2;
};JOINのアルゴリズムを想像する
INNER JOIN
さきほどのeqを使って、INNER JOINは以下のように表せます。
type Ids = Id[];
type QueryResult = { t1_id: Id; t2_id: Id }[];
const innerJoin = (t1: Ids, t2: Ids): QueryResult => {
let res: QueryResult = [];
for (const id1 of t1) {
for (const id2 of t2) {
if (eq(id1, id2)) {
res.push({ t1_id: id1, t2_id: id2 });
}
}
}
return res;
};2つのテーブルをとって1つの結果のテーブルを返す演算です。
t1のidをid1、t2のidをid2とおきます。各id1について、各id2が等しければ結果として取り出します。
ここで、Nullは何とも等しないことに注意すると、結果にNullが現れないこともわかります。
LEFT OUTER JOIN
INNER JOINと似ていますが、各id1が結果として取り出されなかったときに、id2をNullとして取り出すところが違います。
const leftOuterJoin = (t1: Ids, t2: Ids): QueryResult => {
let res: QueryResult = [];
for (const id1 of t1) {
let selected = false;
for (const id2 of t2) {
if (eq(id1, id2)) {
res.push({ t1_id: id1, t2_id: id2 });
selected = true; }
}
if (!selected) res.push({ t1_id: id1, t2_id: null }); }
return res;
};id1は、すべて結果に含まれることになります。id1と等しいid2があれば取り出されますし、なければid2をNullとして取り出されるからです。
FULL OUTER JOIN
LEFT OUTER JOINに加えて、各id2が結果として取り出されなかったときに、id1をNullとして取り出します。
const fullOuterJoin = (t1: Ids, t2: Ids): QueryResult => {
let res: QueryResult = [];
let t1Selected = new Map<number, boolean>();
let t2Selected = new Map<number, boolean>();
for (const [idx1, id1] of t1.entries()) {
for (const [idx2, id2] of t2.entries()) {
if (eq(id1, id2)) {
res.push({ t1_id: id1, t2_id: id2 });
t1Selected.set(idx1, true);
t2Selected.set(idx2, true);
}
}
}
for (const [idx1, id1] of t1.entries())
if (t1Selected.get(idx1) === undefined)
res.push({ t1_id: id1, t2_id: null });
for (const [idx2, id2] of t2.entries())
if (t2Selected.get(idx2) === undefined)
res.push({ t1_id: null, t2_id: id2 });
return res;
};Mapを使って取り出されたid1とid2を覚えておき、処理の最後で取り出されていないid1とid2について、相手をNullとして取り出します。
PostgreSQLの動作と比較
これまで作成した関数に対して、実際にPostgreSQLに接続して動作するバージョンを作成します。
例えばINNER JOINについては以下のようになります。
import { Client } from "pg";
const client = new Client({
// ...
});
const innerJoinNaive = async (t1: Ids, t2: Ids): Promise<QueryResult> => {
const res = await client.query(`
${resetTable("t1", t1)}
${resetTable("t2", t2)}
select
t1.id as t1_id,
t2.id as t2_id
from
t1
inner join t2 on t1.id = t2.id;
`);
return extractQueryResult(res as unknown as PGResult);
};そして、ランダムなテーブルを生成する関数も作ります。
長さが0〜4で、値が1、2、nullのいずれかであるIdの列を生成します。
const generateTestIds = (): Ids => {
const values = [1, 2, null];
const length = Math.floor(Math.random() * 5);
return [...Array(length).keys()].map(
() => values[Math.floor(Math.random() * values.length)]
);
};
// 生成例
// []
// [ 1 ]
// [ 1, 1 ]
// [ null, 1 ]
// [ null, 2, null, 2 ]
// [ null, 1, 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初心者なので間違っている点があれば教えてください。
ありがとうございました。
