- リレーショナルデータベースの inner join は単なるSQL構文を超え、参照・ネストループ・論理モデル・型検査・代数の観点から同じ構造を異なる形で解釈できる
- 正規化されたテーブルでは、結合は参照をたどって 重複なく保存された情報 を再結合する最も実用的なツールになる
- 実装の観点では、行の組を走査して条件を満たす組み合わせだけを残す方法として、またはカラムのドメイン上で両方の関係に存在する値の組み合わせだけを選ぶ方法として見られる
- プログラミングモデルでは、
flatMap、SQLの LATERAL、ORMの N+1問題 の解決、Rust trait ベースの型検査、Setモナドの andThen で結合を説明できる
- 数学的には、グラフの経路、最小モデル、最大の許容関係、半順序における 最小上界、関係式の環積がいずれも結合の同じ性質を示している
正規化されたデータでは結合は参照になる
- 結合は最も実用的には、ある値を 参照 したり、既存データに重複した情報を付け加えたりする操作として見られる
- 例は
user、country、country_code を1つのテーブルに保存する方式から始まる
- 同じ
country の値ごとに country_code が繰り返され、重複 が生じる
- 値が頻繁に変わるデータなら、すべての場所を一緒に更新する必要があり、誤りや非効率が大きくなる
- 正規化された形では、
country と country_code の関係を別テーブルに分離し、ユーザーテーブルは country_id だけを参照する
users と countries を country_id で INNER JOIN すると、元の user、country、country_code の形を再び得られる- 以降の説明では、同名のカラムを基準に暗黙的に結合すると仮定しつつ、細かなSQL構文には厳密にこだわらない
実装の観点: 行とカラムを走査する結合
- 2つの集合
R、S と述語 p があるとき、結合はすべての r ∈ R、s ∈ S を走査したあと p(r, s) が真の場合だけを出力する
- 2つのコレクションの デカルト積 が可能なすべての行の連結だとすれば、結合はその中で条件を満たす部分集合である
- カラム中心に見ると、各カラムの ドメイン を可能な値の集合とし、カラム値の組み合わせを走査する
R(a, b) と S(b, c) があれば、a、b、c のドメインを走査する(a, b) が R にあり、(b, c) が S にあるときだけ [a, b, c] を出力する
互換性のある代替現実として見る結合
- John と Sally の例は、互いに一部の情報しか持っていない状況で、互換性のある現実 だけを残す方法として結合を説明する
- John は自分の pet と stray 動物のあり得る組み合わせを知っており、Sally も自分の pet と stray 動物のあり得る組み合わせを持っている
- John が dog を飼っているとき stray が dog である場合や、Sally が cat を飼っているとき stray が mouse である場合は同時に真ではあり得ない
- 2人が同じ stray を観測していなければならないためだ
- 2つのテーブルを
stray 基準で結合すると、John の pet・stray・Sally の pet の組み合わせのうち、互いに矛盾しない場合だけが残る
プログラミングモデルにおける結合
flatMap は元の配列の各要素に対して新しい配列を作り、その結果を連結する関数であり、結合の実装に使える
SELECT * FROM r INNER JOIN s ON p は r.flatMap(x => s.filter(y => p(x, y))) と表現できる- SQL の一部方言にある
LATERAL 構文は、結合を flatMap の形に変える
LATERAL の右辺が左辺のカラムを参照しなければ、デカルト積 と等価である
- クエリの decorrelation は、右辺のカラム参照を連続的な書き換えで除去する方法に依存する
- ORM でよくある N+1問題 も結合で説明できる
- 結果集合の各行ごとに追加クエリを実行すると、Postgres のようにコネクションを使うデータベースでは個々のクエリの固定コストが大きい
- データベースに「これらの参照をすべて実行してほしい」と依頼した結果が
users INNER JOIN countries のような結合である
- Sqlite のような in-process データベースではこの問題は小さい
グラフの経路と論理モデル
- 関係は2つの集合を「関連付ける」ものなので、グラフとして見られる
users テーブルはユーザー名の集合と country_id の集合を結び付けるcountry_id と2文字の国コードを結び付ける関係も別のグラフとして表せる
- 最初のグラフの右側の集合と、2番目のグラフの左側の集合が同じ vertex set を共有していれば、1つにまとめて見られる
- 左側の集合から始まり、中央の vertex を経由して右側の集合へ行くすべての経路を列挙すると、2つの関係の結合になる
- 形式論理では、関係を 述語 と見なし、文の集合を真にする事実の集合をモデルと見る
users(A, B) と countries(B, C, D) が真なら Q(A, B, C, D) が真であるという含意を置く- この条件を満たすモデルは複数あり得る
- 標準的な結果を得るため、条件を満たすモデルのうち 最小のモデル を選ぶ
- この最小モデルは
users と country の結合結果に等しい
型検査として見る結合
- MLスタイルの型システムは Prolog や Datalog に強く似ているため、結合に近い形で表現できる
- Rust の例では、関係を trait として定義する
Users と CountryCode が関係の役割を果たすSmudge、Sissel、Petee、Canada、UnitedStates、CA、US は具体的な型として定義される
(Smudge, Canada): Users、(Canada, CA): CountryCode のような trait 実装が関係の行に対応する(A, B, C) が結合に含まれるには、(A, B): Users かつ (B, C): CountryCode でなければならないtest::<(Smudge, _, CA)>() は型検査に成功するが、test::<(Smudge, _, US)>() は (Canada, US): CountryCode が実装されていないため失敗する
Setモナド演算として見る結合
- JavaScript の
Some と None の例は、optional record を結合する方法から始まる
- 2つの record が同じ
country を持てば、マージして Some を返す
- 互換性がないか値がなければ
None を返す
andThen は optional 値の中身を取り出して結合関数を適用する- 同じ
combine 関数を保ったままコンテナを Rel に変えると、関係集合を扱える
Rel.map はすべての行に関数を適用するRel.andThen は各行から得られた関係を flatMap で連結する
users 関係と countries 関係に同じ combine を実行すると、Smudge、Sissel、Petee に国コードが付いた結合結果が得られる
最大の許容関係と半順序の join
- 2つの関係
R、S のすべてのカラムを持つ3つ目の関係 T が新しい情報を発明しないなら、許容可能 だと定義する
T のある行を R のカラムに制限したとき、その行が R に存在しなければならない- 同様に
S のカラムに制限したときも、その行は S に存在しなければならない
- たとえば
Smudge, Canada, US は許容されない
country、country_code だけを見ると Canada, US になるが、これは S に存在しない行だからだ
- 空の関係も許容可能だが、最大の許容関係は
Smudge-Canada-CA、Sissel-Canada-CA、Petee-United States-US を含む
- この 最大の許容関係 が2つの関係の結合である
- 半順序の観点では、
R ≤ Q を次のように定義する
Q が R のすべてのカラムを含むQ の各行を R のカラムに制限すると R の行になる
- この半順序で、2つの関係
R、S の最小上界である R ∨ S が存在し、これがリレーショナル結合と同じ意味の join である
環積として見る結合
- 関係を代数的に表現することもできる
- 1つの行はカラムと値の組の 積 で表す
- 1つの関係は複数の行の 和 で表す
- たとえば
user = Smudge と country_id = 1 を掛けた項が1つの行になる
- 式を単純化するための規則が追加される
- Idempotence:
[x = y][x = y] = [x = y]
- Contradiction:
[x = y][x = z] = 0 if y ≠ z
- ユーザー関係
R と国の lookup 関係 S を掛け、分配法則と交換法則で展開すると、矛盾する項は消え、互換性のある項だけが残る
- 残る式は
Smudge-1-Canada-CA、Sissel-1-Canada-CA、Petee-2-United States-US で、これはまさに2つの関係の結合である
- この方法は tensor contraction として見ることもできる
1件のコメント
Hacker Newsのコメント
JOINを空間次元として考え始めると、かなり理解しやすくなった
Dim_X、Dim_Y、Dim_Zのように各次元を別テーブルにして、同じEntityIdで結び付ければ、1つのエンティティの3次元位置を構成するものとして見られる3つの次元を作るには少なくとも2つの内部結合が必要で、時間のような非空間的な次元にも同じやり方で拡張できる
特定の時間に制限しなければ、あるエンティティが時間に応じて存在したすべての位置を含むレポートになる
他の結合タイプも、スキーマを頭の中で「回転」できるくらい概念をつかむと、この変形として理解しやすくなる
https://dbdb.io/db/hyperdex
EntityPosition(EntityId, X, Y, Z)のようなテーブルにするはずただし、複数次元の断片を組み合わせて集計を扱うという点では、データウェアハウス方面を連想する
JOIN、INNER JOINのような構文をなぜ使うのか、いつも疑問に思う。FROMにテーブルを並べて、WHERE句に結合条件を方程式のように書くほうがずっと明確に見える複雑な
FROM句に複数のJOINが混ざると読みにくく、等価な条件式をWHEREで読むほうが直感的だ0番目の観点は、「結合は 関係代数 の演算子だ」ということ
https://en.m.wikipedia.org/wiki/Relational_algebra
自然結合
R ⋈ Sは、共通する属性名が同じタプルの組み合わせの集合であり、論理的なANDに対応する関係演算だ⋈は、結果に入ってはいけない行を述語で取り除くデカルト積と見なせて、SQL の多くの部分がこの観点からうまく理解できる数日前から クエリ実行/プラン実装 の資料を探しているが、述語・既存インデックス・JOIN といった実装寄りの資料がなかなか見つからない
Google の検索結果は使い方の資料に汚染されている
今のところ見つけたのは CMU Database Group の資料だけで、それは素晴らしい
https://pi3.informatik.uni-mannheim.de/~moer/querycompiler.p...
TUM の “Database Systems on Modern CPU Architectures” 講義も役に立つかもしれず、2020年の資料には講義動画一式がある
https://db.in.tum.de/teaching/ss20/moderndbs/?lang=en
https://www.sqlite.org/optoverview.html
https://www.sqlite.org/queryplanner.html
https://www.postgresql.org/docs/current/planner-optimizer.ht...
クエリ実行とクエリ計画は、実際にはほとんど別物に近い
JOIN 最適化の論文としては、元祖の Selinger 論文が今でも最良だと思う
https://courses.cs.duke.edu/compsci516/cps216/spring03/paper...
外部結合をサポートしておらず、より効率的な手法も出てきているが、System R 系の最適化器を見る人には今でもなじみ深く読める
Postgres の
src/backend/optimizer/READMEにも、他ではなかなか見られない内容が多いCMU の Andy Pavlo の講義は、オンラインでこの内容を説明してくれるほぼ唯一の資料に近く、“Building Query Compilers” の PDF は不完全ではあるが、Moerkotte らの中核論文を収めているので、現代的な実装をするなら見る価値がある
適用可能なインデックスを見つけるのは、通常 sargable predicate があるかを見ればよいので難しくないが、選択度推定は難しく、JOIN をまたいだ選択度推定は最適化器で最も難しい問題に近い
たとえば
A=x AND B=y AND C=zがあり、(A,B)、(B,C)インデックスの選択度/カーディナリティ情報しかないとき、3条件全体の選択度をどう推定するかという問題も簡単ではないこれを解くために、「2次錐計画法」のソルバーを要求する論文まである
query planningを検索してみたら、ざっと見ただけでも実装寄りの結果がかなり増えた14番目の方式は多重結合で、「最悪ケース最適結合」とも呼ばれるが、名前はいまひとつだと思う。
テーブルを2つずつ結合して中間結果を作り続ける代わりに、3つ以上のテーブルを中間結果なしでまとめて結合するという意味だ。
関連するブログ記事と短い動画は https://relational.ai/blog/dovetail-join にあり、元論文は https://dl.acm.org/doi/pdf/10.1145/3180143 にある。
RelationalAIで働いているが、学術界で10年ほど研究されてきたこの新しい結合アルゴリズムを、私たちや他のいくつかの新興データベース企業が市場に持ち込みつつある。
https://justinjaffray.com/a-gentle-ish-introduction-to-worst...
ANDはNORになり、Tetrisはこの点を活用している。最悪ケース境界はステートレス／ストリーミングWCOJより厳しくはならないが、実データではずっと小さなボックス証明書を持つことが多い。
Dovetail joinが再帰クエリ、つまり出力関係だけを指定し中間関係はエンジンが自動で処理する任意の datalog をサポートするのかは見たことがない。
そうしたクエリをサポートするのか気になる。
関係モデルの微妙さを主にアプリケーションレベルの開発者に示すこの種の記事は、もっと増えるべきだ。
関数型プログラミングの観点からの説明と考察も簡潔で説得力がある。
N+1問題を教えるまたとない機会を逃したように思う。
クラスタ化されていないインデックスへの結合も依然としてN+1であり、ネットワークやディスクをまたぐN+1ではなく、ディスク上のN+1であるだけだ。
内部結合は条件付きのデカルト積だ。
等値結合条件を持つ内部結合は条件を直接生成し、不等値結合条件は実際の評価が必要になる。
良い説明だ。「正しいやり方はテーブルを正規化することだ」という話はトランザクションデータベースでは正しいが、データウェアハウスではある程度の非正規化が広く受け入れられている。
正規化の例を見て、昔は文字列より数値の主キーのほうが速いと思ってテーブルを設計していた頃を思い出した。
すると意味のない
idが生まれ、実際に欲しい一意の値を得るには結合が必要だった。ある日、2つのテーブルで同じ一意キーを使えば結合を減らせると気づき、単純だが効果は大きかった。
idフィールドを置くのは好きだ。ログ記録に役立つし、複数フィールドからなる「本当の」キーを気にしなくて済む。その代わり文字列の値には一意インデックスを置き、さらに重要なのは整合性制約をそちらにかけることだ。
意味のある文字列で埋まったテーブルは、数値の
idや UUID で埋まったテーブルよりずっと読みやすい。