学生版 社会人版
JA EN
体系 › データベース
·無料·12分で読めます

データベース内部構造 — SQLの1行の裏側

SELECT文を投げてから結果が返るまでに、データベースの中ではパーサ・リライタ・プランナ・実行器・ストレージの5工程が動いています。なぜ同じ結果を返すのに速いプランと遅いプランがあるのか、なぜ統計が古いと突然遅くなるのかを、前提知識ゼロから実務のパラメータ名まで。

#database#sql#query-optimizer#execution-engine#storage-engine#systems
対象textタスクsystems

比喩: 注文票と厨房

レストランで「本日のおすすめを、辛さ控えめで」と注文したとき、あなたは何が欲しいかしか言っていません。どの鍋を使うか、どちらの食材を先に切るかは厨房が決めます。仕込みの状況次第で作り方も変わります。

SQLはこの注文票です。SELECT name FROM users WHERE age > 30 と書いたとき、あなたは「30歳より上の人の名前が欲しい」としか言っていない。全行を先頭から読むのか age の索引をたどるのかは一言も指定していません。それを決めるのがデータベースの内部です。

工程は5つあります。

  1. パーサ — 文字列を木に変える
  2. リライタ — 意味を変えずに形を整える
  3. プランナ — 作り方の候補から一番安いものを選ぶ
  4. 実行器 — 選ばれた作り方の通りに動く
  5. ストレージ — ディスクとメモリの間でデータを出し入れする

「同じSQLなのに昨日まで速かったのに今日は遅い」の大半は3番目で起きています。そこに至るために1から積み上げます。

SQLは命令ではなく宣言

普通のプログラミング言語は手続き的で、for を書けば書いた順にループが回ります。SQLは宣言的で、欲しい結果の性質だけを書き、手順は書きません。だから同じ結果を返す実行方法（プラン）が複数あり得る。桁違いに速いプランと遅いプランが、まったく同じ行を返します。

この自由度がデータベースに最適化の余地を与え、同時に「なぜ遅いのか分からない」の発生源にもなります。手順を人間が書いていない以上、遅いときはどんな手順が選ばれたのかを聞き出すしかありません。その道具が後で出てくる EXPLAIN です。

第1工程 パーサ — 文字列を木にする

入ってくるのはただの文字列です。まず字句解析が SELECT name FROM users … と意味のかたまりに切り分け、次に構文解析が文法規則に沿って木に組み立てます。

        SelectStmt
        /    |     \
  targets  from   where
     |       |       \
   name    users   (age > 30)

木にすれば、以降の工程は文字列を触らずに済みます。「WHERE句の中身」を取り出すのが、文字列の切り出しではなく枝をたどる操作になるからです。

この時点ではまだ users が存在するかも見ていません。それを確かめるのが続く意味解析です。データベースは自分自身の構造（どんなテーブルがあり、どんな列と型を持ち、どんな索引が張られているか）をカタログという内部テーブル群に持っており、意味解析はそれを引いてテーブル名を内部IDに、列名を位置に置き換え、型の整合を確認します。ここで落ちるのがお馴染みの「そんな列はありません」です。

第2工程 リライタ — 意味を変えずに形を整える

次に、結果を変えずに形だけ整える書き換えが入ります。代表例はビューの展開で、FROM active_users のビュー定義がその場に埋め込まれ、最初からそう書かれていたかのような木になります。

ここで大事なのは、リライタは損得を判断しないことです。どちらが速いかを考えるのは次のプランナの仕事で、リライタは「どちらでも同じ結果になる」ことだけを保証します。役割が分かれているので、プランナは意味の正しさを気にせずコスト計算に集中できます。

第3工程 プランナ — 一番安い作り方を選ぶ

心臓部です。プランナは同じ結果を返すプランを何通りも作り、それぞれにコストという見積もりを付け、最も安いものを選びます。

コストは秒数ではなく、「ディスクからページを1枚順番に読む手間」を1とした相対点数です。PostgreSQLならざっくりこの形です。

C=cseq⋅Pseq+crand⋅Prand+ccpu⋅NC = c_{\text{seq}} \cdot P_{\text{seq}} + c_{\text{rand}} \cdot P_{\text{rand}} + c_{\text{cpu}} \cdot N
(1)

読み下すと、「順番に読むページ数」「飛び飛びに読むページ数」「処理する行数」に、それぞれの単価を掛けて足したものです。単価 cc は設定値で、既定は順読み seq_page_cost = 1.0、ランダム読み random_page_cost = 4.0、1行あたりの処理 cpu_tuple_cost = 0.01。ランダム読みが4倍高いのは、回転する円盤でヘッド移動が高くつくという前提から来ています。SSDではこの差はずっと小さいので、実務ではこの値を下げるのが定番の調整です。この1つの数字が、索引をたどるか全部読むかを左右します。

何行返るかを当てる — 選択率

式には NN（処理する行数）が入っていますが、プランナは実行前にこれを知りません。そこで各列の統計情報（値の分布のヒストグラム、頻出値、異なる値の個数）から、条件を通過する行の割合＝選択率を推定します。

N^=Ntotal×s1×s2×⋯\hat{N} = N_{\text{total}} \times s_1 \times s_2 \times \cdots
(2)

つまり総行数に、各条件の通過率を掛け算していく。sis_i は ii 番目の条件の選択率で0〜1です。

掛け算しているということは、各条件が互いに無関係だと仮定しているということです。「都道府県=東京」かつ「市区町村=渋谷区」のように条件が強く相関していると、この積は行数を極端に少なく見積もります。プランナは数行のつもりで索引を選び、実際には数十万行が返ってその全部にランダム読みが走る——遅いクエリの典型です。

結合順序の組み合わせ爆発

テーブルが増えると話は急に難しくなります。nn 個を結合するときどの順に組み合わせるかの選択肢は n!n! のオーダーで増え、3個なら6通り、10個なら300万通りを超えます。

FIG 1結合するテーブルが1つ増えるたび、候補となる結合順序は掛け算で増える。10個を超えたあたりから、素直に全部試す方法は現実的でなくなる

順序が違うだけで速度は桁で変わります。10行の表と1000万行の表を結合するとき、先に絞ってから進むのと、大きい表同士を先に結合するのとでは、途中で抱える行数がまるで違うからです。

全部試さずに済ませる — 動的計画法

古典的なプランナ（IBMのSystem Rに始まる方式）は動的計画法を使います。1テーブル単位の最良の読み方を求め、次に2テーブルの組ごとの最良を求め、それを使って3テーブルを組み立てる——という積み上げです。鍵は、大きな組み合わせの最良解を、その部分集合の最良解から作れること。同じ部分問題を解き直さずに済むので、n!n! が 2n2^n 個の部分集合を1回ずつ埋める作業に落ちます。

FIG 2部分問題の答えを表に残して使い回す動的計画法。図は編集距離の例だが、「小さい組み合わせの最良解から大きい組み合わせを組み立てる」という埋め方は、プランナの結合順序探索とまったく同じ

考え方そのものは動的計画法を1から解説で扱っています。それでも 2n2^n は指数関数なので、PostgreSQLは結合対象が geqo_threshold（既定12）以上になると厳密解を諦め、遺伝的アルゴリズムでの探索に切り替えます。ここを超えると実行のたびにプランが変わり得ます。

第4工程 実行器 — 木を上から引っ張る

決まったプランは演算子の木です。葉がテーブルの読み取り、上に絞り込み・結合・集約・並べ替えが乗り、根が最終結果になります。古典的なイテレータモデルでは、どの演算子も open / next / close という同じ3つの入口を持ちます。

class Filter:
    def __init__(self, child, pred):
        self.child, self.pred = child, pred

    def next(self):
        while (row := self.child.next()) is not None:
            if self.pred(row):
                return row          # 条件を満たす1行だけ返す
        return None                 # 子が尽きたら終わり

根の next() が子を呼び、その子がさらに下を呼び……と伝わって、1行が下から上へ運ばれます。必要な分だけ下から引っ張るので、LIMIT 10 のときに1000万行を読み切らずに済み、中間結果を全部メモリに置く必要もありません。

弱点は1行ごとに関数呼び出しが何段も走ることです。1億行なら呼び出しも1億回×段数になり、実際の計算より呼び出しの手間が上回ります。そこで現代のデータベースは1000行の塊で受け渡しするベクトル化実行や、プランをその場で機械語にコンパイルする方式を採ります。狙いは計算量と実測が食い違うときで扱った「CPUキャッシュと分岐予測に優しい形にする」ことです。

結合の3つの作り方

「突然遅くなった」の多くは、行数の見積もりがずれてハッシュ結合が入れ子ループ結合に化けたケースです。数行のつもりのループが数十万行回ります。

第5工程 ストレージ — ページとログ

一番下では、データはページ（多くのデータベースで8KBや16KBの固定長ブロック）単位で扱われます。1バイト読みたくてもページ丸ごと読む。ディスクがその単位でしか動かないからです。読んだページはバッファプールというメモリ上のキャッシュに残り、次は行かずに済みます（PostgreSQLの shared_buffers）。性能の大半は、必要なページがここに載っているかで決まります。

書き込みには順序の問題があります。ページを書き換えている途中で電源が落ちればデータは壊れる。そこで先行書き込みログ（WAL）を使い、「これから何をするか」を先に順次追記のログへ確定させ、実ページの更新は後回しにします。落ちてもログを読み直せば復旧でき、ログは順番に書くだけなので安く済みます。

読んでいる最中の書き換えには、多くのデータベースがMVCC（多版同時実行制御）で対処します。行を上書きせず新しい版を作るので、読み手は自分のトランザクション開始時点の版を見続け、書き手と待ち合わせません。代償は古い版がたまることで、回収役（PostgreSQLの VACUUM）が要ります。

ページをどう木に組み、どう更新するかは姉妹記事のB木とLSM木が担当します。

現場ではこう使う

誰がいつ。 アプリ開発者が「この画面だけ妙に重い」と言われたとき、SREがDBのCPU急上昇を追うとき、データ基盤担当が夜間バッチが朝までに終わらないとき。共通するのは遅いのはSQLではなくプランだという視点です。

最初に打つコマンド。 PostgreSQLなら EXPLAIN (ANALYZE, BUFFERS) <クエリ>。ANALYZE を付けると実際に実行して推定行数と実測行数の両方が出ます。見るべきは1点、rows=1000 に対し actual rows=800000 のような桁のずれ。ずれている演算子から上のプランは、全部その誤りの上に建っています。MySQLは EXPLAIN ANALYZE、SQL Serverは実行プランの表示が対応します。

触るパラメータ。 work_mem（並べ替えやハッシュ表に使えるメモリ。足りないとディスクに溢れる）、random_page_cost（SSDでは既定4.0を下げるのが定番）、shared_buffers、default_statistics_target（ヒストグラムの細かさ・既定100）、effective_cache_size。統計更新は ANALYZE、遅いクエリの発見は pg_stat_statements。

知らないと事故になる落とし穴。

面接で問われる形。 「索引があるのに使われないのはなぜか」——筋道は4つ。①条件が列を加工していて索引の形と一致しない、②選択率が高すぎて全表走査のほうが安いとプランナが判断した、③統計が古く選択率の推定を誤った、④型が合わず暗黙変換が起きている。EXPLAIN の推定行数と実測行数の比較で切り分けます。

まとめ

次は第5工程の内側——ページをどう木に組んで検索と更新を両立させるのか——をB木とLSM木で分解します。

コメント

コメントにはログインが必要です