データベース基礎

そもそもデータベースは速いのか? SELECT文の内部動作#01

サービスやシステムを構築・運用するときの要件として「性能」があります。

性能というのは重要な要件で、仮にどんな素晴らしい機能を実装していたとしても、性能が悪ければサービスは使われなくなります。

たとえば、10分経ってもツイートが表示されなかったらtwitterを使うこと自体をやめてしまうと思いますし、株価チャートを1時間遅れで表示する証券会社は倒産するでしょう。

そんな重要な「性能」について、データベースにおける性能を出すための仕組みや、そのための留意点について考えてみたいと思います。

そもそもデータベースは速いのか

まず、そもそも論として、データベースは速いのでしょうか。

昔話になりますが、僕が業務アプリ屋だったころ、データベースの遅延問題に巻き込まれたことがあります。要件では8秒以内と定義した検索結果が5分以上返って来ない状況でした。

そのとき「データベースが遅い!遅い!使えない!」と言われ続け、ゴーゴーと空調機が鳴り響くサーバールームに閉じ込められたトラウマから「データベースを使うと遅くなるものなんだ・・・」と思っていた時期が僕にもありました。(ちなみに、そのときの原因は行連鎖・行移行によるフラグメント化でした)

しかし、データベースを学び始めてからはそういった偏見が徐々になくなり、最近ではむしろ「データベースを使わずにどうやって性能を出すの?」と思えるようになりトラウマを克服しつつあります(笑)

具体的にデータベースがどれくらい速いかは環境や設計に依存するのでなんともいえませんが、実体験として、数十億件レベルのデータを扱ったときには、ファイル検索に比べて数百倍とか数千倍といった規模で高速化したこともあります。

では、なぜデータベースは速いのでしょうか。

結論から言えば、オプティマイザ機構や、バッファキャッシュ機構などの仕組みがあるからだと考えています。といっても、「ぜんぜん分からん」だと思いますので、少し深堀りしてみたいと思います。

SELECT文を受けたときのデータベースの動き

なぜデータベースは速いのかを考えるにあたり、内部動作を見てみます。

データベースに対してSELECT文(データを参照するための命令)を発行したときの内部動作はおおよそ以下となります。

  1. サーバプロセスがSQL文をパースして実行計画を作る
  2. データファイルからバッファにデータを読み込む
  3. データを加工(ソートなど)して結果を返す

各要素の用語はプロダクトごとにバラバラですので、代表的なプロダクトであるOracle用語で記載しています。概念自体はMySQLやPostgreSQLでもおおよそ同じです。

順を追って考えてみます。

サーバプロセスがSQL文をパースして実行計画を作成する

データベースに命令する言語をSQLと呼びます。

SQLには様々な命令文がありますが、最も使われるのがデータを参照する命令であるSELECT文です。「従業員表の全データを、給与順にソートして出して」は以下のように記述します。

SELECT * FROM 従業員 ORDER BY 給与 ;

SQLは不思議な言語です。

通常のプログラミング言語では「how」を記述します。たとえば、ソートはバブルソートが速いのか、それともクイックソートが速いのかなどの「how」をプログラマが自身で判断しますが、SQLでは「how」を記載せずに「what」のみを記述します。

つまり「どんなアルゴリズムでもいいから、これが欲しい」とだけ記述します。クセは強いですが考え方自体は簡単でいいのではないかと思います。

SQL文を投げると、オプティマイザがパースして「実行計画」を作成します。

パースとは、まあ、コンパイルです。SQL文自体は人間は理解できる形式ですが、機械には理解できないので、機械が理解できる形式に変換します。

「実行計画」とは、データベースでは実行可能なプログラムファイルのような概念です。計画というとなんだかプロジェクトマネジメント的な何かなイメージを受けますが、英語でいうとexecution planとか、query planとかいうらしいです。

実行計画を作るときに重要になるのがオプティマイザ統計情報です。

オプティマイザ統計情報とは、表が何件あるかなどを管理しているデータです。オプティマイザは、この統計情報をもとに、当該SQLが最も速く動作するであろう方法(アクセスパス)を自動で判別し、そのアクセスパスを考慮した形で実行計画を作成します。

データベースが速い理由のひとつがココにあります。

もし、「 “oracle” という英単語の意味を英和辞書で調べろ」と言われたらどういう調べ方をするでしょうか。おそらく、最初のページからパラパラめくって “oracle” という単語を探していくのではなく、目次を使って”o”からはじまる単語のページを開いてから探していくのではないかと思います。

データベースの中ではこれと同じような探索をしています。

  • 辞書のページ数が多ければ、目次から単語を探す
  • 辞書のページ数が少なければ、頭から単語を探す

辞書のページ数に該当するものがオプティマイザ統計情報となります。

オプティマイザは統計情報の件数などをもとに探索方法(アクセスパス)を決定しますので、統計情報の管理がズサンだと酷い目にあいます。というか、統計情報の管理がズサンで性能問題を出しまくるのはデータベースあるあるです。どうすれば適切に管理できるかについては、やや深い話になるので、別エントリで考えたいと思います。

目次から単語を探す方法をインデックススキャンと呼びます。

データベースの中にインデックスと呼ばれる目次を作っておき、目次をもとにデータを探索します。このアクセスパスを取ることで、あたかも辞書から単語を引くように、超大量のデータがあったとしても最小アクセスで目的のデータにたどり着くことができます。別の言い方をすれば、計算量がO(log(n))とかになります。

一方、頭から単語を探す方法をフルスキャンと呼びます。

なんだか効率が悪そうなアクセスパスですが、バッチ処理や統計演算(平均・合計・最大・最小など)に代表されるような、全件データを参照するSQL文のときなどは頭から読み込んでいったほうが速くなります。

データベースは日々探索方法を最適化している

データベースが速い理由のひとつは、管理しているデータの特性を見て、常にアクセスパスを最適化していることにあります。

このアクセスパスの最適化は、インデックスキャン・フルスキャンの判断だけではなく、表の結合方法(ネスティッドループ結合やハッシュ結合など)といったその他の処理も同様に最適化を行っています。

とはいえ、この仕組みは諸刃の剣でもあり、キチンと動作概要を理解して、適切なオプティマイザ統計情報や実行計画の管理をすれば恩恵を受けられますが、ズサンな管理をすると全く性能がでずに動かないコンピュータを作ることになってしまいます。

ちょっと長くなってきたので、ここで一旦切ろうと思います。

つづく。