雑なクエリやインデックスは意味がない　原理を理解してB−Treeインデックスを正しく利用する

自分自身が「今さら聞けない」と思っているインデックスについて発表

橋本拓弥氏：では私、橋本から「結局インデックスってなんなんですか？」というお話をしようと思います。お願いします。

簡単に自己紹介だけさせてください。橋本と申します。株式会社サーバーワークスという、AWSのインテグレーションをやっているSI企業に所属してます。ロールは今Corporate Engineerです。

ふだんの業務ではこんな感じのことを触っています。業務フローとか、コーポレート的なことをやっていて、わりと開発寄りなところもやったりします。CRMであるSalesforceとか、あとはそれらを組み合わせる感じで、Serverless的なところをよくやっていたりします。今日のタイトルに反して、RDB（リレーショナルデータベース）的なことはあまりやっていないです。

「なんでそんなネタで登壇したねん」という話ですが。そうですね、触っている機会が少ないとはいえ「RDBの知識をきちんと勉強したいよね」という気持ちはずっと持っていて、かつ「でも日常業務では接点が少ないし、教科書から読んで入るつもりだったけど、あまり知らないよね」という、ちょっと負い目的なものがありました。それで「勉強したいよね」というところがあって。

あとはこのJuly Tech Festaのテーマでもあるのですが「今さら聞けない」というネタ。自分自身が「今さら聞けないな」と思っているネタだったので、「だったら自分でアウトプットすればええやないけ」と思った感じです。似たような感じで「インデックスようわかれへんな」という人がたぶんいるんじゃないかなと思って、応募してみたら通ったという、そんな感じでした。

あわよくば詳しい人からツッコミを頂戴しつつ、より詳しくなっていこうかなというところと。ちょっといやらしい話、締め切りに追われないと勉強できないクチなので、締め切りの力を利用して勉強しようとやらせていただいています。

なぜインデックスを使うのか

では本編にいきます。インデックスの基本というところで「なんで？」から入っていこうと思います。なぜインデックスを使うのかという話なのですが、たぶんこれはみなさんおわかりかと思います。平たく言えば、早くデータにアクセスしたいからですよね。

「早くって言われても具体的になんやねん」という話なのですが。そうですね、ここでは「何と比べて早いんですか」「どうして早くなるんですか」というところをちょっと深掘りしていきたいというプレゼンになっています。

「何と比べて」というところに関しては、たぶんフルスキャンと比べるのがわかりやすいでしょうね、というところでそれを軸にします。

「どうして早くなるんですか」というのは、実際にアクセスしにいくデータアクセスの方法を解説することで、疑問をひもといていこうと思います。

フルスキャンではレコードの件数nに比例してコストが発生する

では実際に、表形式のデータを想定して話を進めていこうと思います。「早くなる原理ってこんな感じだよね」というのを順番を追って説明をしていきます。

これ、右側に見えているのが、いわゆるユーザー情報的なテーブルですね。よくありそうなやつです。id、name、ageとか、そういったものがあって、このテーブルを、例えばid／nameで検索したいとか。あるいは年齢でフィルタリングして抽出したいとか、いわゆるB−Treeっぽいユースケースを想定しています。

では最初に、フルスキャンの話からいきます。例えば「年齢でフィルタリングして抽出したい」とした時に何が起こるかというと、これはご想像のとおりだと思います。1件読み込んで、検索条件と照合して、合っているなら抽出する、合っていなければスルーするということをレコードの数分だけ繰り返して、レコードが全体でn件あるのであれば、n件繰り返します。最終的にマッチしたレコードだけを取り出そうという動きです。

早さというところで計算コストがどんなものなのかを考えてみます。まず検索。これに関しては、レコードの件数nに比例して処理のコストがかかることが明白ですね。

他にデータを追加しようというケースも想定しておきたいですね。追加する時に何が起こるかというと、ファイルの末尾に1行分のデータを付け足す、それだけです。シンプルな話ですね。

索引的な働きをするメタデータを導入してアクセス速度を改善

ではここで、インデックスの話にいきなりいく前に、ちょっとクッションを挟んでみようと思います。このいわゆるシーケンシャルアクセスでフルスキャンをするわけですが、これだと検索するたびに、合っているか合っていないかを全件舐めないといけない（走査する必要がある）ですよね。これは効率悪いという話があります。

これを全件舐めなくても結果が返せるようにするためにはどうしたらいいだろうか。ここでいわゆる索引的なデータをメタデータとして導入するというアイデアが出てきます。これはまだインデックスの話ではないです。インデックス的なものなのですが、インデックスではないです。

索引的な働きをするメタデータを導入しました。これで、テーブルが2つに増えました。新しいのが上のほうですね。何やっているのかというと、これは年齢で検索することを想定しています。これをageで、昇順で並べたメタデータを用意します。ソート済みです。この横に書いてあるbyte offsetとは何か、平たく言うと、実際の実データ、データファイルに対するポインタです。

例えばこの青枠で囲ってある、ageが19のやつ、これはだいぶ省略しているのですが、offsetが「id2のoffsetを見てます」と言っています。要するにこれは「id＝2の列を見てます」ということです。こういったものをすべてのレコードに対して年齢で持っておきます。

こうすることによって何が起こるかというと、例えばage＝19のデータを探したいですとなった時に、先にメタデータのほうを挟み撃ちするかたちで舐めていって、例えば一致であれば「19のレコードが一致したね」と。じゃあこれを取り出そうということで、19のageに対するoffset、要するにid＝2のレコードのポインタがわかりましたと。

データベースとしては「id＝2のところをoffset byteで見にいって、ランダムアクセスできますね」ということになるので、フルスキャンしなくてもこの索引のメタデータを作ることで、アクセスの速度が改善されるであろうというところです。

ここまでの話で見ていくと「これでどうやらn件見ることにはならないだろうね」ということはなんとなくわかると思います。

まず検索です。n件全部見にいく必要はないです。ただし、基本的には順番に上から下から舐めていくかたちになるので、基本的に検索のコストはレコード件数nに比例します。フルスキャンよりはマシという程度ですね。

また、実際メタデータを使った時にマッチする件数多かったらという問題があるのですが、これは後でお話しします。

メタデータ追加でインデックス自体を舐めていくコストが発生する

次に、データ追加。まず実データの下のほうのテーブルに関して。これは末尾に追記するだけなので簡単です。さっきと同じです。ただこれ、メタデータを併せて管理し始めたので「メタデータのほうも更新しなきゃあかんですね」という話が出ます。「じゃあこれどうやって更新するねん」というところに問題があるので、その話をします。

これは、メタデータのテーブルをちょっと広げて表示したものになります。ageとbyte offsetというところで見てますね。まず、age＝30のデータが追加されたというシーンを想定しています。

どうやって追加するのかというと、ageが昇順でソートされているので、順番に上から見ていって、age＝30になる行を探します。探して「ここにデータを挿入する必要がある」と判断します。たぶん後続のデータをずらす必要もあると思うので、実際にはたぶん挿入するのは1個の処理ではないと思うのですが、挿入します。

こんな流れで索引データ側をメンテナンスするわけですが、ここでちょっと気になることがあります。何かというと1番目、age＝30となる行を探すという処理です。これを見てもらうと、上から順番に見ているんですよね。さっきのフルスキャンとかなり似たようなことが起きています。これは効率がいいんですかというと、よくないですね。

順番に探していったら効率は悪くないですかという話があります。これは、新しいデータが追加された時に、この索引データを更新するための処理としても探す部分がネックになっていました。実際に更新じゃなくて、探す場合でも、上から順番に見ていく限りネックになっちゃいますよね。

メタデータ追加したことで、n件見なくて済むようになったけど、このインデックス自体を舐めていくコストが掛かっちゃう。つまり、このインデックスというソート済みのデータを、効率よく参照できて、かつ、更新できないといけないということが今ここでは課題になりました。今の話が、その索引となるメタデータを簡単に導入してみた結果になります。

ソート済みのデータをレンジで分割するB−Treeで見るべき範囲を削減

次に、B−Treeの話に入ってきます。どうすればより早く索引のメタデータを更新できるか、検索できるかと考えた時に、ソート済みのデータを、いくつかのレンジに分割してあげるというアイデアが考えられます。

例えばレンジ1、2、3と書いてあるのですが、1は19歳から22歳みたいなかたちで、レンジごとに含まれてる値の範囲が決まってるわけですね。そういった概念を導入してあげます。これをやることによって、少ない回数でより絞り込めるという利点が生まれます。

下のほうにexampleと極端な例を書いているのですが、例えばこの10億件のレコードがあって、年齢順でソートされてるとします。このレンジを例えば1億件ずつ10個のレンジに分かれたとする。この中から例えば30歳以上を探そうとした場合どうなるか。

さっきのレンジという概念を入れていなかったら、上から全部見ていく必要があるので、30歳以上を抽出するためには、結局n件の処理がかかっちゃうわけですね。コストがかかっちゃいます。これは、あまり意味ないですね。

このレンジという概念を導入するとどうなるかというと、まず「30歳以上が含まれてるレンジはどれですか」というのを、10個のレンジに対してそれぞれチェックしにいきます。これが10回のチェック処理ですね。

そこで例えば「2つのレンジが30歳以上含んでます」という結果を返したとします。そうなるとその時点でレンジ2個分、つまり2億件分ですね、2億件分の分を舐めればそれでいいということにできます。

なので、全体で10億件あるとなっていたのですが、レンジというものを導入することによって、見るべき範囲を2億件にまで削減できました。

結局順番に見にいかなければいけないというコストは発生するのですが、見る対象を10個のレンジに対するチェックという、10回の操作で効率的に絞ることができました。

素早く検索する、ひいては素早くこのソートされたメタデータを更新することにつながるアイデアがあるんですね。

今の話をもうちょっと細かく簡略化してみました。値と書いてあるボックスがさっきの表だと思ってください。それらの横にレンジでまとめたものがあって、もうちょっと数増やしてみました、という図です。

さっきは極端な例として10億件という数を挙げたのですが「10億件を10分割してもまだ1億件あるじゃん、多いじゃん」という話がありますね。だったら、「じゃあレンジのレンジという感じでもう1階層増やしてあげれば効率いいんじゃね？」ということが言えそうですね。

例えば10分割したものをさらに10分割して、もう1個レンジのレンジを作ってあげるみたいなことをやると、それだけ絞る数が、要はかける10で減っていくので、より効率がいいでしょうということで、こう増やしていきます。レンジのレンジという概念を積み重ねていくことができます。

最終的にはこいつらを親玉として束ねる親がいます。こんな感じの構造に発展することができます。これでだいぶB−Treeという木構造に見た目が近づいてきましたよね。

なのでここらへんでちょっと整理をすると、ソート済みのデータをレンジで分割して、もともと多数の値があった状態から、効率よく絞り込んで検索できる状態、目当ての値をもう絞り込めるような状態に適した木構造をもってます。これがB−Treeのアイデアである、やりたいことであると言えます。

これまでの話のまとめ

ここでいったん小休止でちょっとまとめを入れます。まずフルスキャンの話をしました。フルスキャンで検索すると、レコード数に比例して検索のコストかかります。これ、シーケンシャルアクセス、順次アクセスしているからかかるコストです。

それは効率悪いので、どう改善しましょうかという話が出た時に、検索用のメタデータを用意して、ピンポイントでアクセスするようにしてあげれば、効率がよくなるんじゃないかというアイデアがあります。

ただ、それだけだとメタデータ自身の参照コスト、更新コストかかってしまいます。なので、B−Treeのようなソート済みのデータを木構造にまとめることで、まず検索の処理というところを軽くして、結果的にランダムアクセスを素早くできるようにしてあげましょうとしているんですね。

なので、そのレンジ分割して木構造でまとめるというところがB−Treeのやりたいところになります。

たぶん細かい実装とかデータ構造とかに関しては、いろいろ正確ではない部分があるとは思いますが、おおよそこんな感じのことをやりたいんだよねというところで納得いただければと思います。

雑なクエリやインデックスは意味がない

では、さっきスルーしてた話を掘り起こそうと思います。メタデータ、ここではB−Treeと言ってしまいますが、B−Treeを導入しました。ageでインデックス作りました。そうなった時に「マッチするレコードが多い場合に問題あるんじゃないの？」というお話をしていました。これが何かをお話しします。

もう1回、実際にデータを想定してみます。テーブルが2つあります。右側は実データ、左側はインデックス、いわゆるメタデータ側ですね。ここで「ユーザーがage＝30のデータが欲しいです」とクエリを投げた状態を想定しています。どうなるか。

まずはこのインデックスのファイルを見にいって、age＝30に合致するレコードはどれかを探しにいきます。今回は1件だけ見つかりました。これによれば「id＝3のoffsetを見にいけばいい」とポインタが書かれてました。

次に、見つけたものをもとに実データのoffset、ポインタを見にいって、無事id3のレコードだけがランダムアクセスによって取得できました。これで順番にフルスキャンして舐めていく必要なくなりました、幸せですね。となります。

では次です。マッチするレコードが多かった場合。30歳以上のageを抽出しようとやってみます。こうなると、インデックス側はソート済みのデータなので、30歳以上のデータは全部引っ掛かっちゃいます。

それで、B−Treeインデックスを検索して、それぞれランダムアクセスでこのoffsetというところを、ポインタで見にいこうとしちゃいます。要するにマッチする結果が、例えばm件であるならば、m回のランダムアクセスが発生します。

パッと見イケてなさそうな雰囲気がすると思うんですよ。実際そのとおりで「フルスキャンより効率が悪くない？」という疑問が出てきます。実際そうなんですよね。

もちろん、絞り込まれた件数にもよるのですが、インデックス経由で見にいって、ワンクッション置いている分だけ、手数としては増えているんですよね。たくさん引っ掛かれば引っ掛かるほど、インデックスの旨味が活きてこないんですよ。

ここで言える話が「雑なクエリやインデックスは意味がないよね」という話です。さっきのように、ほとんど検索条件でデータが絞れていない場合、インデックスは意味がありません。

インデックスというワンクッションを置いて見にいっているランダムアクセスなので「だったら最初からフルスキャンでバッと舐めて順番に見ていったほうが早くない？」となっちゃうわけですね。

これがなんで起こるのかというところは、例えばさっきみたいな30歳以上という緩い条件でクエリ投げてばかりだと効率は悪いです。

データの分布の偏りによりインデックスの有効性がなくなる

もう1つ、データそのものの分布が偏っている場合。例えばソシャゲ（ソーシャルゲーム）のサービスでいろいろなユーザーが登録しているけども、ユーザーの90パーセントは20代です。そんな時に、20代だけ取り出しましょうというクエリを投げたら、たぶん同じこと起こりますよね。50代のクエリ投げたらたぶん同じことが起きないんですよ。データの分布によっても発生します。クエリの投げ方や、データの分布によって、インデックスが有効に効かない場面が発生し得ます。

ここで唐突ですが、カーディナリティという言葉をインデックスとセットでみなさん1回ぐらいは聞いたことあるんじゃないかなと思います。カーディナリティといったらこのへんの話です。きちんと散らばっているデータなら、ある程度クエリした時に絞り込んでくれるだろうという、そんな感じの話をしているんですね。

データの分布の偏りに関しては、ポスグレ（PostgreSQL）であれば部分インデックスというものを使用することで緩和できる場合もあるので、DBエンジンによってそういったものも使えるかもしれないねという話です。

「とりあえずインデックス貼ってみましょう」はやめるべき

また、実際にはクエリオプティマイザが実行計画を立てているので、インデックスは使わんほうがいいなと判断される場合もあります。一概に、そのまま投げられるというわけではないですよ、というところが一応注意が必要です。

あとはアレですね。インデックスは、結局作れば作るだけ更新する時にコストがかかってしまいます。さっき言ったように、木構造のノードに新しいデータ追加しなければいけなくて、それにコストがかかります。

あとはレコード数が増えて、さっきのあの木の階層ですね、あれを増やしたくなったらけっこう大規模なメンテナンス作業になっちゃうじゃないですかというところ。実際どんな仕組みで追加しているのか、ポスグレではどうなのかというところ、すみません、私はそのへんあまりきちんと調べられていないのですが、少なくともそういったところもインデックスのメンテナンス作業です。

あとは削除することによって空き領域が発生しましたみたいな話があって、それを掃除してキレイにしてあげるという、いわゆるバキュームと呼ばれるポスグレの話もありますが、そういったものもインデックスのメンテナンスに相当します。