ジェフリー・ウルマンのデータベース理論：高速でスケーラブルなクエリの背景

なぜウルマンは現代のデータ処理で重要か

SQLを書いたりダッシュボードを作ったり遅いクエリをチューニングしたことがある人の多くは、名前を知らなくてもジェフリー・ウルマンの仕事の恩恵を受けています。ウルマンは、データベースがデータをどう記述し、クエリをどう推論し、効率的に実行するかを定義する研究と教科書で知られる計算機科学者・教育者です。

日常ツールの背後にある静かな影響

データベースエンジンがあなたのSQLを高速に実行可能な形に変換する際には、厳密かつ適応的でなければならない多くのアイデアが使われています。ウルマンはクエリの「意味」を形式化する手法を整え（システムが安全に書き換えられるように）、データベースの考え方とコンパイラの考え方を結びつけました（クエリをパースし、最適化し、実行手順に翻訳できるようにする）。

その影響はBIツールのボタンやクラウドコンソールの目に見える機能として現れるわけではありません。現れるのは次のような形です：

• インデックスを追加したり JOIN を書き換えたりすると速くなるクエリ
• データ量に応じて別のプランを選ぶオプティマイザ
• 結果を変えずにシステムをスケールできる挙動

この記事で学べること（数式は最小限に）

本稿はウルマンの中核的な考えを案内役にして、実務で最も重要なデータベース内部の要点を説明します：SQLの下にある関係代数、書き換えが意味をどう保つか、コストベースのオプティマイザがなぜその選択をするか、そして結合アルゴリズムがジョブを数秒で終わらせるか数時間かかるかを左右する理由です。

また、パース、書き換え、プランニングといったコンパイラ風の概念も取り入れます。データベースエンジンは多くの人が思うよりずっと洗練されたコンパイラに近い振る舞いをするからです。

お約束：議論は正確に保ちつつ数学的な証明は避けます。目的は、次にパフォーマンスやスケーリング、わかりにくいクエリ挙動が現れたときに職場で使えるメンタルモデルを与えることです。

ウルマンが確立したデータベースの基礎

SQLを書いて「クエリはただ一つの意味を持つはずだ」と期待したことがあるなら、あなたはウルマンが普及・形式化したアイデアに頼っています：データの明確なモデルと、クエリが何を求めているかを正確に記述する方法です。

平易に言う関係モデル

関係モデルは本質的にデータをテーブル（リレーション）として扱います。各テーブルには行（タプル）と列（属性）があります。今では当たり前に聞こえますが、重要なのはその規律が生む利点です：

• キーが行を識別する。主キーは各レコードの「名札」です。
• 関係は外部キーを通じてテーブルを接続し、事実を一箇所に保ちながら参照できるようにします。

この枠組みにより、正しさや性能について根拠を持って考えられるようになります。テーブルが何を表現し、行がどう識別されるかがわかれば、結合が何をすべきか、重複が何を意味するか、特定のフィルタがなぜ結果を変えるのかを予測できます。

関係代数：クエリのための計算機

ウルマンの教育では、関係代数がクエリの電卓のように扱われます：ごく少数の演算（選択、射影、結合、和、差）を組み合わせて欲しい結果を表現するという考え方です。

実務でSQLとどう関係するかというと：データベースはSQLを代数形式に翻訳し、別の等価な形に書き換えます。見た目が違う2つのクエリが代数的には同じであり得る、というのがオプティマイザが結合順序を入れ替えたりフィルタを押し下げたり冗長な作業を除去したりできる理由です。

代数と計算論（大まかに）

• 関係代数はより「どうやって」：結果を計算するための操作の列。
• **関係計算（calculus）**はより「何を」：欲しい結果の記述。

SQLは大部分が「何を」寄りですが、エンジンは最適化のために代数的「どうやって」を使います。

方言を覚えるより基礎を押さえる

Postgres、Snowflake、MySQLといったSQL方言は異なりますが、基礎は不変です。キー、リレーションシップ、代数的等価性を理解していれば、クエリが論理的に間違っているのか単に遅いだけなのか、どの変更が意味を保つのかを見極められます。

関係代数：SQLの下にある隠れた言語

関係代数はSQLの“下の数学”です：欲しい結果を記述する少数の演算子群。ウルマンの業績はこの演算子の見方を明確にしやすくし、今でも多くのオプティマイザが使うメンタルモデルとなっています。

中核的な演算子（とその意味）

データベースのクエリは少数の構成要素のパイプラインとして表現できます：

• 選択（σ）：行をフィルタする（SQLの WHERE に相当）
• 射影（π）：特定の列を残す（SQLの SELECT col1, col2 に相当）
• 結合（⋈）：条件に基づいてテーブルを結合する（JOIN ... ON ...）
• 和（∪）：同じ形の結果を積み重ねる（UNION）
• 差（−）：AにあってBにない行（多くの方言での EXCEPT のようなもの）

集合が小さいため、等価性の議論がしやすくなります：もし2つの代数式が同値なら、どんな有効なデータベース状態でも同じ表を返します。

SQLが代数にどうマップされるか（概念的に）

馴染みのあるクエリを例に取ると：

SELECT c.name
FROM customers c
JOIN orders o ON o.customer_id = c.id
WHERE o.total > 100;

概念的には、これは：

1. customers と orders の結合を始める：customers ⋈ orders

2. o.total > 100 のみを残すように 選択（σ） を適用：σ(o.total > 100)(...)

3. 取り出したい列だけを 射影（π）：π(c.name)(...)

これは全てのエンジンが内部で使う正確な表記ではないかもしれませんが、正しい考え方です：SQLは演算子ツリーになります。

等価性：最適化への入口

多くの異なるツリーが同じ結果を意味することがあります。例えば、フィルタはしばしばより早い段階に押し下げられ（σ を先に適用）、射影は不要な列を早めに落とすことができます（π を先に適用）。

これらの等価規則があることで、データベースはクエリを書き換えても意味を変えずにより安価なプランに変換できます。クエリを代数として見ると、最適化は魔法ではなくルールに基づく安全な形の変形になります。

SQLからクエリプランへ：意味を保つ書き換え

SQLを書いたとき、データベースはそれを「書いた通り」に実行するわけではありません。文をクエリプランに翻訳します：実行すべき作業の構造化された表現です。

良いメンタルモデルは演算子の木です。葉はテーブルやインデックスを読み、内部ノードは行を変換・結合します。一般的な演算子には scan、filter（選択）、project（射影）、join、group/aggregate、sort などがあります。

論理プラン vs 物理プラン（何を vs どうやって）

データベースは通常、計画を2層に分けます：

• 論理プラン：抽象的な演算子（フィルタ、結合、集約）で表現される「何を」計算するか。
• 物理プラン：実際のストレージとハードウェア上で「どう」実行するか（インデックス走査 vs フルスキャン、ハッシュ結合 vs ネストループ結合、並列実行 vs 単一スレッド）。

ウルマンの影響は、意味を保つ変換を重視する点に現れます：論理プランを様々な方法で並び替えても答えは変わらないと保証した上で、効率的な物理戦略を選びます。

作業量を減らすルールベースの書き換え

最終的な実行戦略を選ぶ前に、オプティマイザは代数的な“掃除”ルールを適用します。これらの書き換えは結果を変えませんが、不必要な作業を減らします。

一般的な例：

• 選択の押し下げ（selection pushdown）：可能な限り早くフィルタを適用して後段へ流れる行を減らす。
• 射影の削減（projection pruning）：必要な列だけを残してI/Oとメモリを減らす。
• 結合順序の入れ替え：安全な範囲で小さい中間結果を先に作るように結合順序を変える。

単純な書き換えの例

ユーザがある国にいる注文を取りたい場合：

SELECT o.order_id, o.total
FROM users u
JOIN orders o ON o.user_id = u.id
WHERE u.country = 'CA';

素朴に解釈すると 全ユーザ と 全注文 を結合してからカナダのフィルタを適用するかもしれません。意味を保つ書き換えはフィルタを押し下げ、結合する行数を減らします：

• country = 'CA' でユーザを先に絞る
• その後で絞ったユーザと注文を結合する
• 最後に order_id と total を射影する

プラン的には次のように変えようとします：

Join(Users, Orders) → Filter(country='CA') → Project(order_id,total)

を

Filter(country='CA') on Users → Join(with Orders) → Project(order_id,total)

に近い形にする。答えは同じで、作業量は少なくなります。

これらの書き換えはあなたが明示的にタイプするものではないため見落としがちですが、同じSQLがあるデータベースで速く、別のデータベースで遅い主因はここにあります。

ジャーゴンなしのコストベース最適化

SQLを実行するとき、データベースは同じ答えを返す複数の方法を検討し、最も安そうな方法を選びます。これがコストベース最適化であり、ウルマン風の理論が日常的なパフォーマンスに現れる最も実践的な場所の一つです。

「コストモデル」とは何か

コストモデルは、オプティマイザが代替プランを比較するための採点システムです。ほとんどのエンジンは次のような主要リソースでコストを推定します：

• 処理される行数（各ステップを通るデータ量に比例して作業が増える）
• I/O（ディスク／SSDからのページ読み取り、キャッシュ効果）
• CPU（フィルタ、ハッシュ、ソート、集約にかかる計算）
• メモリ（操作がRAMに収まるかスピルするか）

モデルは完璧である必要はなく、十分にしばしば方向性が正しければ良いのです。それで良いプランを選べます。

平易に言うカードィナリティ推定

プランを評価する前に、オプティマイザは各ステップで「どれだけの行が出るか」を推測します。これがカードィナリティ推定です。

WHERE country = 'CA' のようなフィルタならテーブルのどれだけの割合が該当するかを推定します。顧客と注文を結合するなら、結合キーでどれだけペアができるかを推定します。これらの行数予測が、インデックス走査を選ぶか全表走査を選ぶか、ハッシュ結合を選ぶかネストループを選ぶか、ソートが小さいか巨大かを決めます。

統計が重要な理由（欠如するとどうなるか）

オプティマイザの推測は統計に依存します：件数、値の分布、NULL率、列間の相関などです。

統計が古かったり欠如していると、オプティマイザは行数を桁違いに誤推定します。紙上では安そうに見えたプランが実行では高コストになることがあり、典型的な症状はデータ増加後の突然の遅延、突発的なプラン変化、結合が予期せずディスクにスピルすることです。

避けられないトレードオフ：精度 vs 計画時間

より良い推定は、より詳しい統計やサンプリング、より多くの候補プランの探索など追加の作業を必要とすることがあります。しかしプラン作成自体にも時間がかかるため、特に複雑なクエリでは計画時間とのトレードオフになります。

したがってオプティマイザは二つの目的のバランスを取ります：

• インタラクティブなワークロードでは十分に速くプランを作ること
• 惨事を避けるために十分に賢くプランを作ること

EXPLAIN 出力を解釈するとき、このトレードオフを理解しておくとオプティマイザは「賢く振る舞おうとしている」のではなく「限られた情報で予測可能に正しくあろうとしている」と見なせます。

結合アルゴリズムとクエリ性能の核心

ウルマンの仕事は、SQLが「実行される」のではなく「実行計画に翻訳される」ことを広める助けになりました。結合ほどそれが明白に現れる部分はありません。同じ行を返す二つのクエリでも、エンジンが選ぶ結合アルゴリズムや結合順序によって実行時間は大きく異なります。

ネストループ、ハッシュ、マージ：どれがいつ効くか

ネストループ結合は概念的に単純です：左の各行について右側のマッチする行を探します。左側が小さく、右側に有効なインデックスがあるときに速くなります。

ハッシュ結合は一方の入力（通常は小さい方）でハッシュ表を作り、もう一方で探します。等価条件（例：A.id = B.id）の大きな未ソート入力に向いていますが、メモリを必要とし、スピルが発生すると利点が失われます。

マージ結合は二つの入力をソート順で順に走査します。両方が既に秩序付けられている場合（インデックスが結合キー順に行を提供できるなど）に非常に適しています。

結合順序が性能を支配する理由

3つ以上のテーブルがあると可能な結合順序は爆発的に増えます。大きなテーブル同士を先に結合すると巨大な中間結果ができて残りが遅くなります。より良い順序は通常、最も選択度の高いフィルタ（行が少ない）から始め、中間結果を小さく保って外側に広げます。

インデックスは選べるプランを変える

インデックスは単にルックアップを速くするだけでなく、特定の結合戦略を可能にします。結合キーにインデックスがあれば、高価なネストループを「行ごとのシーク」に変えられることがあります。逆にインデックスがないとエンジンはハッシュ結合や大規模なソートに頼らざるを得ないかもしれません。

実務的チェックリスト：悪い結合プランの兆候

• データ量が少し増えただけで実行時間が劇的に増える（中間結果が膨れ上がっている可能性）。
• プランに推定行数と実行後行数の大きな差が表示される（カードィナリティ推定の失敗）。
• 大きなソートやハッシュのスピルが見られる（メモリ不足やインデックス不足）。
• 小さく絞られるべきテーブルが遅れて結合されている（フィルタが早期に適用されていない）。
• 結合述語が等価条件でなく型が合っていない（効率的なハッシュ／マージが使えない）。

データベースエンジンに潜むコンパイラ的発想

データベースは単にSQLを“実行する”のではなく、それをコンパイルします。ウルマンの影響はデータベース理論とコンパイラ的思考の両方に及び、この結びつきがあるためクエリエンジンはプログラム言語のツールチェーンのように振る舞います：翻訳し、書き換え、最適化してから実行するのです。

パースと構文木：SQLの読み取り方

クエリを送ると最初のステップはコンパイラのフロントエンドのようです。エンジンはキーワードと識別子をトークン化し、文法をチェックして**構文木（parse tree）**を作ります（しばしば抽象構文木に簡略化されます）。ここで基本的なエラーが検出されます：カンマの欠落、曖昧な列名、無効なGROUP BYなど。

有用なメンタルモデル：SQLは「ループの代わりにデータ関係を記述するプログラム」であるプログラミング言語に似ています。

構文木から論理演算子への変換

コンパイラが構文を中間表現（IR）に変換するのと同様に、データベースはSQL構文を論理演算子に変換します。例えば：

• 選択（フィルタ）
• 射影（列選択）
• 結合（テーブル結合）
• 集約（GROUP BY）

その論理形はSQLテキストより関係代数に近く、意味と等価性を議論しやすくなります。

なぜオプティマイザはコンパイラ最適化に似るのか

コンパイラ最適化はプログラムの結果を同じに保ちながら実行コストを下げます。データベースオプティマイザも同様で、次のようなルールを使います：

• フィルタを早く押し下げる（作業を早期に減らす）
• 結合順序を変える（同じ結果をより安価に得る）
• 冗長な計算を取り除く

これは「デッドコード削除」と同じ哲学で、手法は異なっても「意味を保持してコストを減らす」という点で一致します。

デバッグ：コンパイル済みコードのようにプランを読む

クエリが遅いときはSQLだけを見つめないでください。実際にエンジンが選んだものを示すクエリプランを見てください。プランは結合順序、インデックス使用、時間を要する箇所を示します。

実務的な結論：EXPLAINの出力を性能の「アセンブリ一覧」として読む習慣をつけましょう。推測ではなく証拠に基づくチューニングが可能になります。詳しい習慣作りは /blog/practical-query-optimization-habits を参照してください。

実際の性能に影響するスキーマ設計理論

良いクエリ性能はしばしばSQLを書く前に始まります。ウルマンのスキーマ設計理論（特に正規化）は、データを正しく、予測可能に、効率的に保つための設計法を与えます。

正規化の目的（なぜ存在するか）

正規化は次を目指します：

• 異常の削減（例えば顧客住所を5箇所更新して1箇所漏らすようなことを防ぐ）
• 一貫性の向上：各事実を一つの“ホーム”に置くこと
• 制約を表現可能にする：キーや外部キーでエンジンにルールを任せられるようにする

これらの正しさの利点は後の性能向上にもつながります：重複フィールドが減り、インデックスが小さくなり、高価な更新が減ります。

正規形を平易に説明すると

証明を覚える必要はありませんが、考え方は簡単です：

• 1NF：列の値は原子であること（カンマ区切りリストを避ける）。これによりフィルタやインデックスが扱いやすくなる。
• 2NF：複合キーのテーブルでは非キー列はキー全体に依存すべきで、部分依存を避ける。これにより属性の重複を防ぐ。
• 3NF：非キー列はキーにのみ依存し、他の非キー列に依存しないようにする。隠れた重複を防ぐ。
• BCNF：ほぼ一意の列が微妙な重複を生む場合に有用な、3NFより厳しい形。

デノーマライズが合理的なとき

次のような場合、デノーマライズは有効な選択です：

• 分析向けのテーブル（幅広いファクトテーブル、レポーティング）を作るとき
• 結合がボトルネックで、制御された冗長性を受け入れられるとき
• 読み取り速度を最適化し、更新は夜間再構築などで賄えるとき

重要なのは、デノーマライズを意図的に行い、重複を同期するプロセスを持つことです。

スキーマ選択がオプティマイザとスケーリングに与える影響

スキーマ設計はオプティマイザのできることを形作ります。明確なキーと外部キーはより良い結合戦略、安全な書き換え、より正確な行数推定を可能にします。一方で過度の重複はインデックスを肥大化させ書き込みを遅くし、複数値列は効率的な述語を阻害します。データ量が増えるにつれて、初期のモデリング決定は単一クエリのマイクロ最適化より重要になることが多いです。

システムがスケールするとき理論がどう現れるか

システムが「スケールする」とき、それは単に大きなマシンを追加するだけではありません。同じクエリの意味を保ちながら、非常に異なる物理戦略を選んで実行時間を予測可能にする必要が出てくることが多いです。ウルマンの等価性の重視は、結果を変えずに戦略を変えられることを可能にします。

スケールは多くの場合、物理配置＋プランの選択である

小さな規模では多くのプランが「動作する」ことがあります。スケールすると、テーブルをスキャンするかインデックスを使うか、事前計算された結果を使うかの違いが秒と数時間の差になります。理論の側面が重要になるのは、オプティマイザが答えを変えずに安全に適用できる書き換えルール群（フィルタ押し下げ、結合の並べ替え等）を持っている必要があるからです。

パーティショニングはSQLが同じでも実行するクエリを変える

日付や顧客、リージョンでのパーティショニングは論理的には1つのテーブルを物理的に複数の断片に分けます。これがプランに与える影響は：

• スキップできるパーティション（パーティションプルーニング）
• 結合がパーティション内で完結するかノード間でシャッフルが必要か
• 集約がローカルでできるかどうか

SQLテキストは変わらなくても、最適なプランは行がどこにあるかに依存します。

マテリアライズドビュー：代数的なショートカットとしての事前計算

マテリアライズドビューは基本的に「保存された部分式」です。エンジンがクエリを保存済み結果と同値（または書き換えで同値にできる）だと証明できれば、高価な結合や集計を繰り返し計算する代わりに高速なルックアップで置き換えられます。これは関係代数的思考の実践例です：等価性を認識して再利用する。

キャッシュ：助けにはなるが形の悪い作業は直せない

キャッシュは繰り返し読み取りの速度を上げますが、スキャンすべきデータが多すぎるクエリや巨大な中間結合が必要なクエリの根本的な問題は解決しません。スケールの問題が出たら、多くの場合は：触るデータ量を減らす（配置／パーティショニング）、繰り返し計算を減らす（マテリアライズドビュー）、あるいはプランを変えることが正解で、単なるキャッシュ追加ではないことが多いです。

ウルマンに触発された実践的な最適化習慣

ウルマンの影響は単純なマインドセットに現れます：遅いクエリを「意図の声明」として扱い、データベースがどう書き換えたかを検証することです。理論家になる必要はありません。繰り返し可能なルーチンがあれば恩恵を受けられます。

1) EXPLAINプランを読む：まず何を見るか

まず実行時間を支配することが多い部分を見る：

• アクセス方法：期待したインデックスルックアップではなくテーブル全体をスキャンしていないか？
• 推定行数 vs 実行行数（データベースが両方を表示する場合）：大きな差は遅さの原因になることが多い。
• 結合順序：どのテーブルが結合を駆動しているか？最も選択的なフィルタから始まっているか？
• 高コストの演算子：ソート、ハッシュビルド、大きなネストループなどがどこにあるか。

一つだけやるなら、行数が爆発的に増える最初の演算子を特定してください。多くの場合そこが根本原因です。

2) オプティマイザを敗北させる一般的なアンチパターン

書きやすく意外に高コストなもの：

• インデックス列に関数を適用する：WHERE LOWER(email) = ... はインデックス利用を阻害する。代わりに正規化列や関数インデックスを使う。
• 必要な述語の欠落：日付範囲やテナントフィルタを忘れるとターゲットのクエリが全表スキャンになる。
• 意図しないクロス結合：結合条件の欠落で行数が掛け算され大きな中間結果を生む。

3) 代数的思考で仮説を立てる

関係代数は次の実用的な動きを促します：

• フィルタを早く適用する：可能なら結合前に WHERE を適用して入力を小さくする。
• 列を早めに削減する：結合前に必要な列だけを残してメモリ・I/O を節約する。

良い仮説の例：「この結合が高コストなのは結合入力が多すぎるからだ。orders を直近30日で先に絞れば結合入力が減るはずだ。」

4) インデックス、書き換え、またはスキーマ変更か？

単純な判断ルール：

• インデックス追加：クエリが正しく、選択性が高く、繰り返し実行される場合。
• クエリ書き換え：EXPLAIN が不要な作業（不必要な結合、遅いフィルタ、非SARGableな述語）を示す場合。
• スキーマ変更：ワークロードが安定していて同じボトルネックと戦い続ける場合（事前集計、デノーマライズ、時間/テナントでのパーティショニングなど）。

目標は“賢いSQL”ではなく、予測可能で小さい中間結果を作ることです—これこそウルマンの等価性の考え方が見せてくれる価値です。

実際のプロダクト構築でこれらをどう適用するか

これらの概念はDB管理者だけのものではありません。アプリを出荷するなら、スキーマの形状、キーの選択、クエリパターン、データアクセス層といった決定を通して、すでにクエリ計画に影響を与えています。

もしあなたが vibe-coding ワークフローを使っていて（たとえばチャットインターフェースで Koder.ai から React + Go + PostgreSQL アプリを生成するような場合）、ウルマン流のメンタルモデルは実用的な保険になります：生成されたスキーマをキーとリレーションシップの観点でレビューし、アプリが頼るクエリを点検し、本番化前に EXPLAIN で性能を検証できます。"クエリ意図 → プラン → 修正" のサイクルを速く回せるほど、加速された開発から得られる価値は大きくなります。

もっと学ぶ場所と職場での応用方法

“理論を別に勉強する”ことを趣味にする必要はありません。ウルマン流の基礎から得られる最速の利点は、クエリプランを自信を持って読めるようになることで、そのために学ぶべき最小限を実地で練習することです。

入門向けの参考リソース

次の本や講義トピックを探してみてください（いずれも広く引用されている出発点です）：

• “A First Course in Database Systems” (Ullman & Widom) — 実用的な枠組みで学べる入門書。
• “Principles of Database and Knowledge-Base Systems” (Ullman) — より厳密な理論を学びたい場合。
• “Compilers: Principles, Techniques, and Tools” (Aho, Lam, Sethi, Ullman) — 「なぜオプティマイザはコンパイラに似ているのか」を理解するために。
• 検索トピック：関係代数、クエリ書き換え、結合順序、コストベース最適化、インデックスと選択性、パースとクエリ言語。

軽めの学習パス

小さく始めて、各ステップを観察可能なことに結びつけましょう：

1. 関係代数：選択、射影、結合、等価規則を学ぶ。
2. プラン：プランノード（走査の種類、フィルタ、結合、ソート、集約）を読む。
3. 結合：ネストループ、ハッシュ、マージの特性を理解する。
4. コストモデル：決定を左右する主要入力（行数、選択性、I/OとCPU）を把握する。

すぐ効果が出る小さな演習

実際の2〜3件のクエリを取り、次を繰り返してください：

• 書き換え：IN と EXISTS の比較、フィルタの前倒し、不要列の削除、結果の比較。
• プラン比較："前/後" のプランを取得して何が変わったか（結合順序、結合型、走査の種類）を記録。
• インデックス操作：インデックスを一つずつ追加・削除して推定行数と実行行数の変化を観察。

チームへの報告方法

プランに基づいた明確な言葉を使って説明します：

• 「フィルタが選択的になったため、プランが全表走査からインデックス走査に切り替わった」
• 「推定行数が100倍ずれていたため、オプティマイザが間違った結合順序を選んだ」
• 「この書き換えは等価（結果は同じ）だが、述語の押し下げを可能にし結合に入る行数を減らす」

これがウルマンの基礎がもたらす実務上の利点です：推測ではなく共有できる語彙で性能を説明できます。