← ./posts
· yuta

RDBMSを自作して学ぶ：第14章 実際のデータベースとの比較

#database#rdbms#go

前回は、これまでのコンポーネントを1つにまとめ、CLIからSQLを実行できるデータベースを完成させました。今回は、作ったデータベースをPostgreSQLやSQLite、**MySQL（InnoDB）**と比べます。自分で実装したものと、実際のデータベースの設計がどこで一致し、どこで違うのかを整理すると、実際のデータベースのドキュメントやソースコードがぐっと読みやすくなります。最後に、本シリーズで省略した機能についても解説します。

PostgreSQLとの対応

ストレージ層

PostgreSQL 本シリーズ 主な違い
共有バッファ（shared_buffers） BufferPoolManager（第4章） PostgreSQLはLRUではなく、クロックスイープで追い出すページを選ぶ
ヒープ HeapFile（第5章） PostgreSQLはテーブルごとに別のファイル（1GBごとに分割）を持ち、空き領域マップ（FSM）で空きのあるページを探す
ページ（8KB。ビルド時に変更可能） ページ（4KB） サイズ以外の考え方は同じ
行ポインタ（ItemId、4バイト） スロット（4バイト、第5章） ItemIdは位置15ビット・状態2ビット・長さ15ビットを詰め込んでいる
B-treeインデックス（nbtree） BPlusTree（第6章） PostgreSQLは葉を左右両方向にリンクし、並行アクセスに強いB-link木（Lehman & Yao）をもとにしている。任意の型をキーにできる
TOAST なし 行が約2KBを超えると、大きな値を圧縮したり別の領域に移したりする

PostgreSQLのページヘッダ（src/include/storage/bufpage.h）は次のとおりです。

typedef struct PageHeaderData
{
    PageXLogRecPtr pd_lsn;      /* このページを最後に変更したWALレコードの位置 */
    uint16      pd_checksum;    /* チェックサム */
    uint16      pd_flags;
    LocationIndex pd_lower;     /* 空き領域の先頭（行ポインタ配列の終わり） */
    LocationIndex pd_upper;     /* 空き領域の末尾（タプル領域の始まり） */
    LocationIndex pd_special;   /* 特殊領域（インデックスが使う）の先頭 */
    uint16      pd_pagesize_version;
    TransactionId pd_prune_xid; /* 刈り取り（pruning）できそうな最古のXID */
    ItemIdData  pd_linp[FLEXIBLE_ARRAY_MEMBER]; /* 行ポインタの配列 */
} PageHeaderData;

第5章のスロット付きページと見比べると、構造がほぼ同じであることがわかります。pd_lower はスロット配列の終わり、pd_upper は本シリーズの「空き領域オフセット（レコード領域の先頭）」、pd_linp はスロット配列そのものです。先頭の pd_lsn は、第12章のページLSNにあたります。

ただし、LSNの中身は少し違います。本シリーズのLSNは1から数えるレコードの通し番号ですが、PostgreSQLのLSNはWAL全体の中でのバイト位置です。どちらも単調に増えるので、「ページにどこまで反映済みか」を比べる用途では同じように使えます。

SQLエンジン

PostgreSQL 本シリーズ 主な違い
パーサ（gram.y と scan.l から、BisonとFlexで生成） 手書きの再帰下降パーサ（第7章） PostgreSQLは文法定義からパーサを自動生成する。SQLiteも独自のパーサ生成器（Lemon）を使っている
プランナ（コストベース） ルールベース（第8章） PostgreSQLは統計情報から各プランのコストを見積もって選ぶ
Seq Scan / Index Scan / Index Only Scan / Bitmap Heap Scan SeqScan / IndexScan 読み方の選択肢が多い
Nested Loop / Hash Join / Merge Join Nested Loop Join 結合方法をデータ量に応じて選ぶ
エグゼキュータ（イテレータモデル） Executor（第8章） 同じモデル

EXPLAIN の出力も、本シリーズの planner.Explain と同じく実行計画の木を表しています。例えば同じようなテーブルに対して、PostgreSQLでは次のような形になります（コストなどの数値は省略しています）。

EXPLAIN SELECT name FROM users WHERE id = 2;

 Index Scan using users_pkey on users  (cost=... rows=... width=...)
   Index Cond: (id = 2)

本シリーズの Explain は次のとおりです。

Projection NAME
  Filter (ID = 2)
    IndexScan USERS [2, 2]

PostgreSQLは、取り出すカラムの選択（Projection）をスキャンのノードの中で行い、インデックスで絞る条件を Index Cond として表示します。表現は違いますが、「主キーのインデックスで id = 2 の行を探す」という計画であることは同じです。

トランザクション

PostgreSQL 本シリーズ 主な違い
MVCC（行の複数の版とスナップショット） テーブル単位の厳格2PL（第11章） PostgreSQLでは、読み取りと書き込みが互いを待たない
テーブルロック（8種類のモード）と行ロック テーブルロック（S/X） 行ロックの情報は、タプルのヘッダ（xmax）に書き込まれる
デッドロック検出（deadlock_timeout（既定1秒）待った後に検査） ロックを待つたびに検査 PostgreSQLは、デッドロックはまれという前提で、しばらく待ってから調べる
SERIALIZABLEはSSIで実現。既定の分離レベルはREAD COMMITTED 常にSERIALIZABLE
WAL LogManager（第12章） PostgreSQLは、チェックポイント後にページを初めて変更するときにページ全体をWALに書く（full_page_writes）
リカバリはREDOのみ REDO + UNDO 下で説明
ファジーチェックポイント 静止チェックポイント PostgreSQLはトランザクションを止めずにチェックポイントを取る
VACUUM なし 不要になった行の版を回収する

注目したいのは、PostgreSQLのリカバリにはUNDOがないことです。PostgreSQLはMVCCを採用しているので、未コミットのトランザクションが挿入した行も、ヒープにそのまま残ってかまいません。行には「どのトランザクションが作ったか（xmin）」が記録されていて、そのトランザクションがコミットしたかどうかは別の場所（pg_xact）で管理されています。クラッシュしたトランザクションはコミット済みにならないので、その行は誰からも見えず、後でVACUUMが片付けます。そのため、ログから変更を取り消す必要がないのです。本シリーズはヒープの行を直接見せる設計なので、第12章でUNDOを実装する必要がありました。

full_page_writes は、第12章では扱わなかった**破損ページ（torn page）**への対策です。ページの書き込みの途中で電源が落ちると、ページの前半だけが新しく、後半が古い、という壊れた状態になることがあります。こうなると、ページLSNとログを比べても正しく復元できません。PostgreSQLは、チェックポイントの後で各ページを初めて変更するときに、ページ全体の内容をWALに残しておき、リカバリではそれを土台に変更を再実行します。本シリーズの実装は、この破損ページには対応していません。

SQLiteの設計思想

組み込み型データベース

SQLiteは、PostgreSQLとはまったく違う方針で作られたデータベースです。

観点 SQLite PostgreSQL 本シリーズ
動作形態 アプリケーションのプロセス内で動くライブラリ 独立したサーバープロセス ライブラリ + CLI
ファイル データベースは1ファイル（＋ジャーナルかWALファイル） 多数のファイル データファイル・カタログ・WALの3ファイル
テーブルの格納 B+木（rowidをキーとする） ヒープ ヒープ
同時に書き込めるトランザクション 常に1つ 複数 テーブルごとに1つ
ページサイズ 512〜65536バイト（既定4096） 8KB 4KB

サーバーを立てる必要がなく、ファイル1つをコピーすればデータベースを持ち運べる手軽さから、スマートフォンのアプリやWebブラウザ、組み込み機器などで広く使われています。

テーブルもB+木に格納する

本シリーズとSQLiteの大きな違いは、テーブルのデータの持ち方です。本シリーズはPostgreSQLと同じく、テーブルのデータをヒープに置き、インデックスは「キー → RID」を引くための別の構造にしています。SQLiteは、テーブルのデータそのものを、rowid（行番号）をキーとするB+木の葉に格納します。

本シリーズ・PostgreSQL:                  SQLite:
  インデックス: キー → RID                テーブル: rowid → 行全体（B+木の葉）
  ヒープ:       RID → 行全体              インデックス: キー → rowid

SQLiteでは、INTEGER PRIMARY KEY として宣言したカラムはrowidそのものになるので、主キーで引けばテーブルのB+木を1回たどるだけで行に届きます。それ以外のインデックスで検索する場合は、インデックスのB+木でrowidを求めてから、テーブルのB+木をもう一度たどります。

MySQLのInnoDBも、テーブルを主キーをキーとするB+木（クラスタ化インデックス）として格納します。主キーの範囲検索では、行が主キーの順に並んでいるので効率よく読めます。一方、主キー以外のインデックス（セカンダリインデックス）は「キー → 主キー」を持つので、行を読むにはB+木を2回たどる必要があります。ヒープ方式とクラスタ化インデックス方式には、それぞれ得意・不得意があるのです。

ロールバックジャーナルとWALモード

SQLiteには、クラッシュからデータを守る方式が2つあります。

WALモードでは、書き込み中でも読み取りがデータベースファイルと確定済みのWALを見ればよいので、読み取りと書き込みが互いを待たなくなります。ただし、同時に書き込めるのは常に1つだけです。

SQLiteのWALはページ全体の内容を記録する方式で、読み取りのたびにWALも参照します。本シリーズのWALは、ページへの操作（INSERTなど）をレコード単位で記録し、読み取りはバッファプールとデータファイルだけを見ます。名前は同じWALでも、本シリーズの設計はPostgreSQLに近いものです。

バイトコードで動く実行エンジン

第8章で触れたとおり、SQLiteはSQLを仮想マシン（VDBE: Virtual Database Engine）のバイトコードにコンパイルして実行します。SQLiteのCLIで EXPLAIN SELECT ... を実行すると、PostgreSQLのような計画の木ではなく、バイトコードの命令列が表示されます。

本シリーズで省略した機能

MVCC（多版型同時実行制御）

本シリーズでは、テーブルにロックをかけることで分離性を実現しました。この方式では、書き込みをしているトランザクションがあると、そのテーブルを読みたいトランザクションは待たされます。

PostgreSQLやMySQL（InnoDB）が採用しているMVCCは、行を更新するときに古い版を残したまま新しい版を作り、それぞれのトランザクションに「自分が見るべき版」を見せる方式です。PostgreSQLの場合、各行の版には次の情報が付いています。

トランザクションは、開始時（またはSQL文の実行時）にスナップショットを取ります。スナップショットは「その時点でコミット済みのトランザクションはどれか」を表す情報です。ある版が見えるのは、「xminのトランザクションがスナップショットの時点でコミット済み」かつ「xmaxが空か、xmaxのトランザクションがスナップショットの時点でまだコミットしていない」場合です。

UPDATE users SET name = 'Bob' WHERE id = 1   （TX 200 が実行してコミット）

版1: xmin=100, xmax=200, name='Alice'  ← TX 200のコミット前に取ったスナップショットからは、こちらが見える
版2: xmin=200, xmax=空,  name='Bob'    ← TX 200のコミット後に取ったスナップショットからは、こちらが見える

読み取りはロックを取らずに自分のスナップショットで見える版を読むので、書き込みと互いを待ちません。その代わり、誰からも見えなくなった古い版を片付ける仕組みが必要になります。PostgreSQLではVACUUMがこれを担います。InnoDBは古い版を別の領域（undoログ）に持ち、不要になったらパージします。

観点 テーブル単位の2PL（本シリーズ） MVCC
読み取りと書き込み 互いを待つ 互いを待たない
古い版の管理 不要 必要（VACUUM・パージ）
実装の複雑さ 低い 高い

コストベースのクエリオプティマイザ

本シリーズのPlannerは、「WHERE句に主キーの条件があればIndexScan」という決まったルールで実行計画を選びます。実際のオプティマイザは、次のような手順で計画を選びます。

  1. 統計情報を集める: テーブルの行数、各カラムの値の分布（ヒストグラム）、値の種類の数など（PostgreSQLでは ANALYZE で収集する）
  2. コストを見積もる: 条件に合う行がどれくらいあるかを推定し、ディスクの読み込み回数やCPUの処理量から各計画のコストを計算する。例えばPostgreSQLの既定では、シーケンシャルなページの読み込みのコストを1.0、ランダムな読み込みを4.0として見積もる
  3. 最も安い計画を選ぶ: 結合するテーブルが多いと組み合わせが爆発するので、動的計画法や、テーブル数が多い場合は遺伝的アルゴリズム（PostgreSQLのGEQO）で探索を絞る

条件に合う行が多い場合は、インデックスを使わずにSeqScanで全件読んだほうが速いこともあります。コストベースのオプティマイザは、そうした判断をデータの実際の分布に基づいて行います。

インデックスの種類

本シリーズで実装したのは、整数キーのB+木だけです。PostgreSQLには、用途に応じた複数のインデックスがあります。

インデックス 得意な用途
B-tree 等値検索・範囲検索・ソート（標準）
Hash 等値検索のみ
GiST 図形・範囲型・全文検索など、多様なデータ型の検索
SP-GiST 四分木や基数木（トライ）のように、空間を重なりのない領域に分割して探すデータ（点データ、文字列の前方一致など）
GIN 配列・JSONB・全文検索（1つの行が複数のキーを持つデータ）
BRIN 物理的な並び順と値に相関があるカラム（時系列データのタイムスタンプなど）の範囲検索

その他の省略した機能

まとめ

次章はシリーズの最終回です。さらに学ぶための書籍や論文、OSSのソースコードを読むときのコツ、分散データベースへの道筋を紹介します。