1行の SELECT が PostgreSQL の中をどう進むのか。パーサ・プランナ・エグゼキュータ、8KB ページと ctid、B-tree が1億行から一瞬で探せる理由、共有バッファ、そして UPDATE・MVCC・WAL から見た ACID まで、順を追って解説します。
アプリが SELECT * FROM users WHERE id = 10000; という1行を送ると、データベースの中では何が起きているのでしょうか。ふだん私たちは結果だけを受け取りますが、その裏では「文字列を読み解く」「探し方を決める」「ディスクのどこを読むか決める」「見つけた行を返す」という手順が、きっちり順番に進んでいます。
このアニメモでは PostgreSQL を題材に、その道のりを順に追います。前半は読む側(SELECT)の流れと、1億行あっても一瞬で目的の行にたどり着ける理由。後半は書く側(UPDATE)の流れと、途中で電源が落ちてもデータが壊れない理由(ACID)です。
図は左がアプリ、中央が PostgreSQL、右がデータを置くディスク。SQL はこの左から右へ、結果は右から左へ流れます。
PostgreSQL を起動すると、まず postmaster という親プロセスが待ち受けます。アプリが接続してくると、postmaster は自分の分身(バックエンドプロセス)を1つ fork して、その接続専属の担当者にします。以後、その接続から届く SQL はすべてこの担当者が処理します。接続が 100 本あれば担当者も 100 人いる、という構造です。
SQL は届いた時点ではただの文字列です。担当者はこれを4つの工程に順番に通していきます。パーサ(読み解く)、リライタ(書き換える)、プランナ(探し方を決める)、エグゼキュータ(実際に探す)。この4工程が、どんな SQL でも必ず通る共通の道です。
最初の工程はパーサです。やることはプログラミング言語のコンパイラと同じで、文字列を単語(トークン)に切り、文法に照らして木構造に組み立てます。SELECT * FROM users WHERE id = 10000 なら、「SELECT 文」という根の下に、「何を取り出すか(*)」「どこから(users)」「どんな条件で(id = 10000)」という枝がぶら下がった形になります。これをパースツリーと呼びます。
ここで見ているのは文法だけです。users というテーブルが本当にあるのか、id が数値なのかはまだ知りません。SELCT のようなつづり間違いや括弧の閉じ忘れは、この段階で構文エラーとして突き返されます。
次に、木に出てくる名前の正体をシステムカタログで調べます。カタログとは PostgreSQL が自分自身の構造を記録しているテーブル群で、「users という名前のテーブルは内部番号 16384」「その id 列の型は integer」といった情報が入っています。定数の 10000 も integer として扱うと決まり、木は意味の確定した「クエリツリー」に変わります。存在しない列名を書くとエラーになるのはこの段階です。
続くリライタは、ルールに従って木を書き換えます。いちばん身近なのはビューです。ビューに対する SELECT は、ここで元のテーブルへの問い合わせに展開されます。行レベルセキュリティの条件が WHERE に足されるのもここです。
ここが RDBMS のいちばん賢い部分です。SQL には「id が 10000 の行がほしい」としか書いてありません。どうやって探すかは書いていないので、プランナが決めます。
候補はたとえば2つ。案Aは Seq Scan、テーブルを頭から全部読んで条件に合う行を拾う方法。案Bは Index Scan、id 列に作られた B-tree 索引で直接たどる方法。プランナは「テーブルは約1億行」「id は重複なし」といった統計情報(ANALYZE で集めたもの)を元に、それぞれが読むページ数と CPU の手間を数値(コスト)で見積もり、いちばん安い案を選びます。この例では案Bが圧倒的に安い。
SQL の前に EXPLAIN を付けると、プランナが選んだ計画とコストをそのまま見ることができます。遅い SQL を調べるときの出発点です。
選ばれた計画は、実行ノードの木として渡されます。今回は「users_pkey という索引を使って id = 10000 を探し、見つかった行を取り出す」という1つのノードだけ。エグゼキュータはこの木を上から順に「次の1行をくれ」と呼び出していき、ノードは要求されるたびに1行ずつ返します。JOIN や ORDER BY があれば、ノードが積み重なって、下から上へ行が流れていく形になります。
ここから先は「実際にディスクのどこを読むか」の話です。その前に、テーブルのデータがディスク上でどんな形をしているかを見ておきます。
テーブルの中身は、ディスク上では1つのファイルとして置かれています(ヒープファイル)。ファイルは先頭から 8KB ずつの「ページ」に区切られ、各ページの中に行(タプル)が詰め込まれています。1行が 60 バイト程度なら、1ページに 100 行ちょっと。1億行なら約 83 万ページ、6.7GB ほどになります。
大事なのは、「10000 行目」という番号はどこにも存在しないことです。行の住所は ctid と呼ばれ、「何ページ目の何番目か」の組で表されます(図の (0,1) など)。行はテーブルに入れた順に空いているページへ置かれ、更新や削除で場所も変わります。だから id = 10000 の行がどのページにあるかは、読んでみるか、別に「住所録」を持っていないと分かりません。
索引(住所録)がなければ、選択肢は Seq Scan しかありません。ページ0から順に 8KB ずつ読み込み、ページの中の行を1つずつ見て、id が 10000 かどうか比べます。見つかっても止まれません。id に重複がないという保証がなければ、最後のページまで読み切る必要があるからです。
1億行なら約 83 万ページ、6.7GB を全部読むことになります。SSD でも数秒から数十秒。これが「索引のない検索は遅い」の正体です。読む量がテーブルの大きさに比例するので、テーブルが 10 倍になれば時間も 10 倍かかります。
そこで PostgreSQL は、id 列に対して B-tree という索引を作ります(主キーを付けると自動で作られます)。これは「キーの値 → その行の ctid」という対応表を、木の形に整理したものです。
木の節(ノード)も、やはり 8KB のページです。いちばん上のルートには「7000 まではこっちの子、14000 まではこっちの子」という境目の値が並び、その下の内部ノードがさらに細かく区切り、いちばん下の葉(リーフ)にキーの値と ctid が昇順に並んでいます。1ページには数百個のキーが入るので、1段下がるごとに候補がおよそ数百分の1に絞られます。葉どうしは横にもつながっていて、「id が 10000 以上 20000 以下」のような範囲も、葉を横にたどるだけで取れます。
id = 10000 を探すときの動きはこうです。まずルートのページを読み、「10000 は 7000 以上 14000 未満」と比べて真ん中の子へ進みます。その内部ノードを読み、「9000 以上 11000 未満」の葉へ進みます。葉のページを読むと、キー 10000 の隣に ctid = (83, 7) が書いてあります。「83 ページ目の 7 番目の行」という住所です。
ここまでに読んだページは3枚。あとはヒープファイルの 83 ページ目を1枚読んで、7 番目の行を取り出せば終わりです。ページの中での比較は二分探索なので、数百個のキーがあっても 10 回足らずで決まります。
速さの理由は「読むページの数」にあります。全走査は約 83 万ページを読みました。B-tree なら、1段で数百分の1に絞られるので、1億行でも木の高さは3〜4段。読むページは 4〜5 枚です。しかも上のほうの段は全部の検索で通るので、メモリにキャッシュされていて、実際にディスクまで行くのは葉と、ヒープの1ページくらいです。
テーブルが 100 倍の 100 億行になっても、木は1段増えるだけ。読むページが 1 枚増えるだけです。これが「対数時間」という言葉の意味で、索引が効く検索は、データが増えてもほとんど遅くなりません。
逆に言えば、WHERE に書いた列に索引がない、あるいは WHERE lower(name) = ... のように索引が使えない形で書いてしまうと、プランナは全走査に戻ります。
エグゼキュータが「83 ページ目をくれ」と頼む相手は、ディスクではなくバッファマネージャです。PostgreSQL は共有バッファと呼ばれるメモリ領域にページのコピーを溜めていて、頼まれたページがそこにあればディスクには触れません。なければディスクから 8KB を読み込んで共有バッファに置き、以後の問い合わせはそれを使います。
よく使われるページ(B-tree の上の段、人気のあるテーブルの一部)はほぼ常にメモリにあります。ディスクの読み出しはメモリの数千倍以上遅いので、「どれだけバッファで済ませられるか」が実際の速さを決めます。EXPLAIN (ANALYZE, BUFFERS) を付けると、ヒットした枚数とディスクから読んだ枚数が見えます。
ヒープページの 7 番目の行を取り出したら、エグゼキュータはそれを「見えていい行か」確認し(この話は後半で)、列の並びを整えて、接続を通じてアプリに返します。索引から「次の行」を求めても、キー 10000 はもう無いので、ここで終了。アプリには1行が届きます。
ここまでが SELECT の一生です。文字列を木にし、意味を確かめ、探し方を選び、索引で住所を引き、メモリ経由でページを読み、行を返す。どれも一瞬ですが、どこかの手順が重くなる(索引がない、統計が古い、バッファに乗らない)と、SQL は急に遅くなります。
後半は書く側です。UPDATE users SET name = 'Sora' WHERE id = 10000 が来たとき、探すところまでは SELECT と同じです。違うのはその後で、PostgreSQL は見つけた行を上書きしません。古い行はそのまま残し、新しい内容の行を同じページ(または別のページ)に追加します。
各行には、それを作ったトランザクションの番号(xmin)と、消したトランザクションの番号(xmax)が隠し列として付いています。更新とは「古い行の xmax に自分の番号を書き、新しい行の xmin に自分の番号を書く」ことです。この仕組みを MVCC(多版型同時実行制御)と呼びます。
なぜこんな回りくどいことをするか。同じ瞬間に別の接続がこの行を読んでいるかもしれないからです。古い行を残しておけば、読んでいる側は「自分が始まった時点ではまだ 612 番は終わっていない」と判断して古い行を見続けられ、書く側は誰も待たせずに進めます。読みは書きを待たず、書きは読みを待たない。これが PostgreSQL の同時実行の基本です。不要になった古い行は、あとで VACUUM が回収します。
変更したページはまずメモリ(共有バッファ)の上で書き換えられます。この時点ではディスク上の本体ファイルは古いままです。ここで電源が落ちたら変更は消えてしまいそうですが、そうはなりません。PostgreSQL は、ページを書き換えると同時に「何をどう変えたか」を WAL(先行書き込みログ)という別のファイルに追記し、COMMIT のときにその WAL をディスクに確実に書き切って(fsync)から、アプリに「コミットしました」と返すからです。
WAL は末尾に追記するだけなので速く、本体ファイルのあちこちに書きに行くより圧倒的に安く済みます。書き換えたページ本体は、後からチェックポイントという節目でまとめてディスクに書かれます。もし途中でクラッシュしても、再起動時に WAL を先頭から再生すれば、コミット済みの変更はすべて本体に反映し直せます。
RDBMS が守る性質を ACID と呼びます。ここまでの部品に対応づけると、それぞれが何で実現されているかが見えてきます。
原子性(Atomicity)は「全部やるか、何もしないか」。トランザクションの変更は複数ページに散らばっても、WAL に COMMIT の記録が書かれたかどうかの一点で決まります。記録の前に落ちれば、再起動後は未コミットとして全部なかったことになります。
一貫性(Consistency)は「決めたルールを破らない」。主キーの重複禁止、外部キー、CHECK 制約などを、書き込みのたびにその場で検査します。破れば文全体がエラーになり、原子性によって巻き戻ります。
分離性(Isolation)は「同時に動く他人の途中経過が見えない」。MVCC のスナップショットで、各トランザクションは自分が始まった時点で確定していた版だけを見ます。
永続性(Durability)は「コミットしたら消えない」。WAL の fsync が完了してから返事をする、という順序が守っています。
最後に、SQL というものの理解の仕方です。SQL は手順を書く言語ではなく、「どんな行がほしいか」を書く宣言型の言語です。どの順で、どの索引で、どのページを読むかは、プランナが統計情報から毎回決めます。だから同じ SQL でも、データ量や索引の有無で動き方が変わります。
実務で効くのは次の3点です。WHERE や JOIN に使う列には索引があるか。遅いときは EXPLAIN (ANALYZE, BUFFERS) で、プランナがどの案を選び、何ページ読んだかを見る。そして書き込みは「上書きではなく追記」なので、更新の多いテーブルは VACUUM と索引の肥大化を気にかける。
アプリから見れば1行の SQL と1行の結果ですが、その間では、字句解析・カタログ参照・コスト計算・B-tree の探索・バッファ管理・WAL への追記が、毎回この順番で動いています。
