筆者は40才近くになってから初めてこのソフトウェア業界に足を突っ込んだし、もともと技術屋ではなかったので本当の理論とかは正直なところよくわからない。

けれど、大体そんなもんじゃないの?っとタカをくくって仕事を続けてる(汗)
そんな適当漢がDBが検索するってことについて考えてみる...

まず、第1回目はインデックスについて考えてみる。

DBにかかわってる方なら、テーブルにインデックスを付与すると検索が早くなるってのは常識として持ってる話なんだが、じゃなんでインデックスを付けると早くなるんだろ?

これ、人間が物を探すときのことを思い浮かべると意外と「そうなんだぁ~」ってことになるって知ってた?
例えば辞書で何かを探すことを考えてみよう。

そーだなぁ...「金字塔」の意味を探すとしよう!

もし、辞書に目次が無く、コンテンツも「あいうえお順」ではなかったらどうやって探そうか?そう、最初のページから1ページずつめくっていって「金字塔」って文字が出てくるまで頑張るしかない。いわゆる全捜査ってやつでこれがテーブルにインデックスがない状態と同じ。DBも人間と何ら変わらず全部のデータをひとつづつ探してるわけで、データが100件ぐらいならすぐ見つかるだろうけど数100万件のデータとかになるとデータが増えるに従って見つけるのに時間がかかるということになる。しかも、早々に見つかるか?データの最後の方で見つかるか?はまさに神のみぞ知るってやつで検索ヒットする時間も推定することすらできない。

じゃ、辞書に目次があってコンテンツも「あいうえお順」に並んでたらどうやって探すかな?そう、「きんじとう」だから「き」が始まるページを目次で探して、「く」までの間のページだけを探せばよいってことになる。実に効率的だよねぇ。これは、本屋とか図書館の本棚とかもそうだよね。かなり大雑把な例えと理論だけど、これがDBのインデックス。つまり、データがそれを格納しているオブジェクトの大体どの辺に集まっているかをデータとは別に生成して保持しておくって仕組みなんだな。

でも昨今はビックデータとか言っちゃってデータ量もかなり大量なものを扱うのが当たり前。さっきの例えで「き」~「く」の間が1万ページあったらどうだろうか?「えー、1万ページは全部めくってかなきゃいけないの?」ってことになるでしょ(汗)

ってことで...

PCでこーんなファイル管理してる人いませんか?
例えば日付のフォルダ作成してその下にその日のファイルを格納したり、カテゴリ分けしたフォルダの下に更に細分化したフォルダを作ってファイル管理とか...

それを「金字塔」を探すのに仮に最適化してみたのがこれ。

「き」「ん」「し」「と」「う」とフォルダを追いかけていき、最後は「う」フォルダの中だけを全捜査すれば済むのでめっちゃ効率いいですな(嬉)まあ、かなり強引な例えではあるけれど、これが「B木」とか「Bツリー」とかいわれてるDBのインデックスの正体。(実は目次の例もDB的には、ほんとはB木なんですが...多めに見てね 汗)

実際にDBでは「あ」「い」「う」「え」「お」とかではなくデータをハッシュ化などしてその値を利用しているわけなんだが理屈はおんなじ。人間が探しやすいって思う目印を付けてやることでDBも同じように検索効率が上がるってことなんですな。

他にも、男と女とかデータを思いっきり大きくカテゴリ分けできるものであればビットマップインデックスとか、同じようなデータを同じページ(物理的データの格納場所)に配置するクラスタリングとか色々な方式のインデックスがあったりするんだけれど、どれも要は最終的に見ていかなければいけないものを如何に少なくするかを考えてデータの配置場所をどうするかとか、配置した場所をどう覚えておくかってことを頭のいい人たちが一生懸命考えてるんだね。(データ分布と統計学だね)

じゃ、インデックスさえ付ければもう怖いものなしってことになるのかといえば、そうは問屋が卸さない。インデックス君にだって色々あるのさ(笑)

「B木」の例では文字列を構成するひらがなでデータのありかを標したけれど、実際のデータは何文字あるかもわからないし、こんな詳細なインデックスを作ってたらインデックスが必要とする領域が馬鹿にならない。(実際問題、最近ではデータ領域よりもインデックスの領域が大きいDBを何度も経験してるけど)また、仮に領域問題が解決したとして以下のような問題にぶち当たる。

  • インデックスの作成に時間がかかりデータの登録が遅くなる。
  • 折角インデックスを作成しても、データ分布が思い切り偏っていて効果が出ない。
  • 実はデータの格納が終わって全データが集まってからでないと本当の意味で効率の良いインデックスを作成できない。

インデックス君も実に大変だよな(汗)

そんなわけで、DBではインデックスとは別にデータの分布を統計情報として作成してそれを元に、「このテーブルのデータはこんな偏りがあるので、インデックスはこうしよう」とか、「複数のテーブルを一緒に検索する際(ジョイン時)にはどのテーブルから探し始めるのが効率いいかな?」とか、パラレル実行(同時に複数のスレッドで捜査をおこなう)とかインデックス君を助けてあげる仕組みが色々と織り込まれていたりもする。(この辺はDBベンダの謳い文句になるので色んな志向がありますが)

最後に我々がインデックス君を助けてあげられることはというと...

  • テーブルに作成するデータの性質と分布からそれに合ったインデックスの方式を選んであげる。
  • トランザクション系だとインサート時に自動的に作成されるのに任せっぱなしだが、大量のデータを保持するデータウェア的なDBの場合はインデックスを作成するタイミングを検討する。
  • DB領域見積もりの時からインデックスの領域をきちんと算出し、後になって「もうインデックスつける領域が足りないよ~!」ってなことにならないようにする。
  • もう一度立ち返って、辞書でこの単語を探すにはどうなってた方がいいかなぁ?とか、図書館でこの本を探すにはどんな配置になっていれば探しやすいのか?ってのを考える。

...ってな感じですかね(-。-)y-゜゜゜