データベースの迷宮

よくその体を表した名前をつけること
RDBが提供する外部キーやCHECK制約などの機能を適切に使うこと
そしてリレーショナルモデルに基づいた分かりやすい設計を意識すること
技術的負債は早めに返していくこと

この章は開発全般に広く言えるものもあるこのような原則が、RDBにもそのまま言えることを述べた章だと感じました。

思うに、開発者が関わる技術的な対象--今回で言えばRDB--の提供する機能を適切に使うことで一貫性のある挙動を守ることができます。RDBの機能で言えば上で書いた通り外部キーやCHECK制約、さらに言えばNOT NULL制約などの種々の制約が挙げられるでしょう。また、例えば様々なプログラミング言語に備わっている定数は変数と比べて定数への再代入を防ぐ機能を持ちますが、これもメモリに格納された値に関してある程度¹一貫性のある挙動を提供するものと言えるでしょう。

失われた事実

この章ではRDBに履歴データを保持しないと起こることが述べられています。結論からいうと基本的にはトラブル対応時などに後から事実を遡れなくなってしまうので履歴データを保存した方が良いです（と私は解釈しました）。

しかしだからといって履歴データを保存することが常に正解であるとも言えません。この辺りが考慮ポイントになります。

テーブルサイズが増えるのでインフラコストに跳ね返ること
集計が単純な主キー検索ではなくなるので、テーブルサイズが増えるとパフォーマンスが劣化すること

レポート表示などのユースケースでパフォーマンスの懸念が気になる場合はマテビューを設けたり集計済みテーブルを用意したりすることもできます。

RDBに履歴を保存しない場合には

また、RDBに履歴を保存しない選択をする場合に検討する手段として以下のようなものがあります。

ElasticSearchなどにアプリケーションログとして保存する
遅延レプリケーションを使う

ElasticSearchとかならインフラコストやパフォーマンスの問題もクリアできるのか？あるいはRDBが性能面でその辺りを既に十分カバーしているのか？我々はデータとその計算の謎を明らかにするためアマゾンの奥地へと向かった...。

やり過ぎたJOIN

RDBによる演算結果はJOINのそれも含め全てリレーション、つまり二次元表の形で得られる。今年度、今の会社に入社してからJOINをたくさん書くようになった私は、RDBのその一貫した挙動に感動し感謝したものでした。

しかしながらJOINは複数の異なる表同士を結合する操作であるという点で、1つの表に対する射影(SELECT)よりもパフォーマンス面で注意が必要になります。この章ではMySQLとPostgreSQLを例とするそれぞれのRDBのJOINの挙動や、JOINとINDEXの関係について述べられています。

JOINの問題点

JOIN回数に対して負荷が増えやすい

JOIN操作は結局「対象となる表同士の共通部分を取る操作」です。以下のクエリのように複数のJOINを1つのクエリでやろうとすると、「まずusersとordersの共通部分を取って、次にusersとorder_itemsの共通部分を取って...」というように調べるべきテーブルの組み合わせの数が増えます。1つ1つの組み合わせについて共通部分を調べて最後にそれらをガッチャンコすることで求めたい共通部分を調べているのです。調べるべきテーブルの組み合わせの数はクエリ中に登場するテーブルの数を$n$とすると${}_n C_2$と表せるので、JOIN回数に対して負荷が増えやすいことは想像できるのではないかと思います。

SELECT
    u.id AS user_id,
    u.name AS user_name,
    o.order_id,
    o.order_date,
    p.product_name,
    c.category_name
FROM
    users u
JOIN
    orders o ON u.id = o.user_id
JOIN
    order_items oi ON o.order_id = oi.order_id
JOIN
    products p ON oi.product_id = p.product_id
JOIN
    categories c ON p.category_id = c.category_id
WHERE
    u.id = 1;

テーブルサイズに対して負荷が増えやすい

JOINはイメージ的にはテーブル同士の掛け算です。
100行と100行のテーブル同士をJOINしたら10000行のテーブルスキャンになりますが、1000行と1000行のテーブルスキャンでは1,000,000行のテーブルスキャンになります。

JOINのアルゴリズムの種類

この本の著者であるsoudaiさんの知見の深さが光ります。私はJOINされるテーブルを外部表、JOINするテーブルを内部表（または駆動表）と呼ぶことすら知らなかった...。

Nested Loop Join(NLJ)

最もナイーブなアルゴリズムだと感じました。要するに総当たりです。外部表の１行に対して内部表の全行をループしながら外部表のレコードを１行ずつ調べていきます。外部表のループに内部表のループがネストされているみたいに見えるのでNested Loop Joinと呼ばれてるわけですね。

Hash Join

JOINに使う小さい方のテーブルを全件読み取って「ハッシュ値をキー、レコードを値」とするハッシュ表を作成しそれを元に結合を行うアルゴリズムです。ハッシュ表ができたら、大きい方のテーブルも同様に1行ずつ結合キーをハッシュ化してハッシュ表を検索していきます。ハッシュ値がヒットした行同士を結合するという仕組みです。

Sort Merge Join

外部表と内部表の両方を結合キーでソートした上で、上から順に結合キーを比較して結合を行っていくアルゴリズムです。

アルゴリズム同士の比較

// 3章はこれ以降書き差し(P57

Nested Loop JoinとHash Joinの比較

ハッシュ値で検索を行うので結合自体は非常に高速ですが、ハッシュ表の作成と保存ができるだけの十分なメモリが必要です。

NLJと比べるとHash Joinは「各テーブルの読み取りが1回ずつで良い」

Hash JoinとSort Merge Joinの比較

MySQL vs. PostgreSQL

PostgreSQLは上で挙げた3つのアルゴリズムを全てサポートしていますが、MySQLはNLJしかサポートしていないのです。よってPostgreSQLはMySQLに比べて大きな表のJOIN(Hash Join)や不等号を使ったJOIN(Sort Merge Join)が得意と言えるでしょう。

ただしMySQLがPostgreSQLに関してJOIN性能がカスかといえばそういうわけではなく、外部表が小さくて索引のある内部表と等号で結合する場合は非常に高速に処理できます。要するにNLJの仕組みを慮った設計にするとMySQLはJOINにおいて性能を大きく発揮してくれるというわけです。

効かないINDEX

小規模なアプリケーションではINDEXに気を使わなくても十分なユーザー体験を提供できてしまいます。そのためINDEXの存在は知っていてもその仕組みや種類について把握する機会やモチベはなかったりしてゆるゆるな認識になりがちです。私もそうでした。

INDEX is 何

INDEXはテーブルからデータを高速に取り出すための仕組みです。INDEXを作成し、さらにそれを検索時に利用することでクエリの高速化ができます。そしてINDEXはMySQLとPostgreSQLの間でも実装方法が異なります。

B-Tree INDEX

MySQLもPostgreSQLも実装方法は多少違えど考え方は同じB-Tree INDEXです。B-Tree INDEX自体の説明は他の記事に譲りますが、要するに二分探索的にレコードを絞り込んでいって目的のレコードに早く辿り着けるというものです。仮にINDEXがない場合はフルスキャンするしかなくなり、テーブルサイズに対して重い処理になります。

// p73から

WHERE狙いのキー、INDEX狙いのキー

カーディナリティが低くても

十分に少ないデータを検索するならINDEX使ってくれるのでは？

フラグの闇

削除フラグを始め会員ステータス・痩身ステータスなど、RDBに状態を持たせる設計はクエリの複雑化を招きやすいアンチパターンの1つです。しかしながら入門者が触りがちなLaravelを始めとするWebフレームワークではこの削除フラグの存在を前提とした便利メソッドが提供されています。そのため「とりあえず削除フラグつけとけば安全で良いよね」という認識になりやすいのですが、この章では冷静に別の視点を提供してくれています。端的に言って、RDBは状態ではなく事実を記録する場所なのです。一度記録した事実が消えることはあり得ないのです。ちなみに@t_wada氏のSQLアンチパターン幻の第26章「とりあえず削除フラグ」も大変参考になるのでぜひご一読を。

何が問題か

クエリの複雑化
カーディナリティが低くなる

クエリの複雑化

有効なレコードを検索するために常にis_deleted = falseを書かなければならなくなります。検索するテーブルが1つのうちはまだ良いでしょうが複数のテーブルをJOINしたくなるとクエリは一気に肥大し複雑になっていきます。クエリを見ると分かりやすいです。例えばXのようなサービスで有効なポストを検索するクエリは以下のようになるでしょう。

SELECT * FROM posts WHERE is_deleted = false

ここでユーザが複数の投稿を持っているというリレーションシップがあると仮定して、削除されていないユーザの投稿を検索したくなったとします。クエリはこんな感じになるでしょう。

SELECT posts.* FROM posts 
INNER JOIN users ON users.id = posts.user_id AND users.is_deleted = false 
WHERE posts.is_deleted = false

もしここに「実は投稿にはカテゴリが紐づいていて、まだ削除されていないカテゴリを考慮したクエリにしてくれ」と言われたらさらにcategoriesテーブルのJOINにも削除フラグの条件文が必要になります。

このように「とりあえず削除フラグ」はクエリに関連するテーブル全てに影響を及ぼし、「条件文付け忘れてないっけ」と開発時に意識を割かなければならないところが増えます。1つでも付け忘れたら正しい結果が取得できません。

また、物理削除にしておけば有効な投稿を取得するのにpostsテーブルの読み取りだけで済んだのに論理削除にすると幾つものテーブルをJOINしないといけなくなっています。これでは例えばpostsテーブルに紐づくテーブルが増えるなどの仕様変更時にpostsをFROM句に取る全てのクエリにJOINを追加する修正が必要になり、バグを埋め込みやすくなります。

カーディナリティが低くなる

INDEXはカーディナリティが低くなってくると効かなくなります。言わずもがな削除フラグは「削除されたかそうでないか」の2種類の値しか取らないのでカーディナリティが極端に低いデータで、INDEXが使われにくいです。しかもどのクエリにも必ず削除フラグが入ってくるので、データの規模が大きくなってくるとINDEXの使われないスロークエリが散乱している...という事態を簡単に招きます。

事実のみを保存せよ

テーブルに状態を持たせてはいけません。

削除されたリソースのテーブルを用意する

削除フラグを使う代わりに、deleted_postsのような削除されたリソース用のテーブルを用意して削除済のリソースはそこへ移すようにします。元のリソーステーブルからは物理削除するのです。実装に際してはアプリケーションで頑張るのも良いですがトリガーを使う手もあります。しかし、トリガーはカラム追加などの仕様変更に弱いので採用にあたってはよく検討してください。

Viewを用意する

既に削除フラグが存在する場合には有効なリソースを取得するViewを定義するのも手です。アプリケーションからの参照はViewに一本化できますし、テーブルの追加時にもViewの修正だけで済みます。しかし、Viewは参照されるたびに再実行されるのでパフォーマンスが気になるかもしれません。その場合はサマリーテーブル（MySQL）やマテビュー（PostgreSQL）などの実体を用意してやるのも良いでしょう。
ただ、筆者によればPostgreSQLのマテビューは差分更新ではない（更新時に毎回０から作り直す）のでデータが増えてくると更新がボトルネックになってくるでしょう。

// 3種の参考文献をあたる

ある程度としているのは、例えばTypeScriptでは定数があくまで再代入を防ぐだけで、フィールドの変更などは防いでくれないためです。 ↩