BASE開発チームブログ

Eコマースプラットフォーム「BASE」( https://thebase.in )の開発チームによるブログです。開発メンバー積極募集中! https://www.wantedly.com/companies/base/projects

SQLアンチパターンとBtreeインデックスの関連性

この記事は、「BASE Advent Calendar 2018」の9日目の記事です。

devblog.thebase.in

前日は id:match_1 でした。こんにちは、10日ほど前にデータベース移行についての記事を書かせていただいた植木です。 今回はインデックスとBtreeのパフォーマンスチューニング系のお話をしたいと思います。

概要

Btreeの構造などを説明している資料は他にもあるし、SQLのアンチパターンもある程度あるけど、何故アンチパターンになるのかなど構造を理解しながらの説明が無いように思っていました。今回はBtreeの構造を説明しながら、どのように動いてパフォーマンスに影響しているのかを説明しようかと思います。SQLのパフォーマンスチューニングはBtreeの構造を理解しているかどうかで全く違うものになります。構造を意識しつつ、誤解しやすいところや何故この処理でインデックスが効くのかなど考えてみましょう。

Btreeの仕組み

Btreeとは

情報処理試験などで出ますから知ってるよって人も多いですよね。ソート処理と木構造によって検索の高速化をするアルゴリズムとなります。このBtree構造がDBのインデックスの内部構造となります。弊社だとMySQL系ですので若干カスタマイズしたB+treeとなります。

下の図を見てほしいのですが、データを格納する単位であるノード内にはインデックス対象のキー値とそれ以外にリーフには実データへのポインタ情報(MySQLだとPK)が入っています。木構造を使った分岐で対象のリーフノードを選択したらポインタ経由で実テーブルにアクセスしてデータを取得します。

f:id:kingyokkun:20181207191659p:plain

B+treeがBtreeと違う点はリーフノードにもブランチノードと同じ情報が入る事とリーフノードに次のリーフのポインタが入る事になります。これらの対応をする事で範囲検索やorder by、group by等の対応がしやすくなります。今回はこのB+treeを使っての説明をいたします。以降、Btreeと書いているものはB+treeです。

今回はわかりやすくしたいのでノード内に1データしか入らないと仮定してキー値に1−10のデータを入れた場合を想定します。実際にはノードに複数レコードが入りますが、ノードの先頭データと末尾データを使って同じような構造と比較をします。

また、参考に普通のBtreeだとこうなります。

f:id:kingyokkun:20181207191718p:plain

何故この構造にデータを並べると早いの?

例えば、今回のように1〜10まであるデータの中で6を探したいと思った場合、通常なら10回6という数字と格納データとを比較する必要があります。ユニーク制約をつける事ができたとしても6回です。それに対して、木構造にしておけば、まずルートノードの5と比較して大きいので右のブランチへ行き、7と比較して小さいので左に行けばもう目当てのデータに辿りつきます。

インデックスをつけない状態なら検索はデータ量に比例した処理時間が必要ですが、木構造にする事で必要な時間はデータ量の対数に比例します。

実際のSQLでよくある問題などなど

範囲検索

下記のような検索をした場合に認識を誤解している方がいます。

where id between 6 and 8

この時、Btree上で6と8の位置を検索してその間のデータを全て取るなんて器用な事はできません。今回の上図データだとおそらくDBが6を選んで検索し、6以降のデータを取得して一つずつ8より小さくないかを比較します。また、その際に6と8どちらかの数字を選択するかを判断するには統計情報を使います。

likeでインデックスが効く場合

ここで少しBtree構造がわかった事だと思うので、前方一致ならlike検索でもインデックスが効く事を説明してみます。例えば、yamada、tanaka、suzuki、yamakawaさんがいた場合にBtreeの構造にしたらsuzuki、tanaka、yamada、yamakawaの順番になりますね。この時に下記のような条件で検索すればyamadaさんの直前の位置まで木構造の動きで辿りつく事ができ、それ以降のデータを取得する動きができるという事になります。「%yama%」のような中間一致や後方一致では、Btreeのソート順が活かせないためBtree検索はできません。

where name like 'yama%'

検索キーに関数や演算を使うとインデックスが効かない

Btreeはデータをソートしている事が重要な訳ですが、例えば、下記のように関数を使った場合、ソート順が変わる可能性があります。

where date(update_time)='2018-01-01'

もっとわかりやすくreverse関数を使えばソート順は真逆になります。一つ一つの関数や演算の特徴までDBは把握しきれないためインデックスを利用できません。

複合インデックスの構造

続いて複合インデックスの場合のBtree構造です。購入などの情報をイメージしてもらえると良いかと思います。今回はユーザーと購入日をイメージしてみます。(user_id,update_dt)にインデックスをつけてuser_idが0001〜0004の人が1/1から1/3まで何らかの操作をした場合、インデックス内部のBtreeはこのような並びになります。

f:id:kingyokkun:20181207191808p:plain

ここで下記のように検索すれば木構造の動きで(0003,2018-01-02)まで到達します(黄色塗り)。

where user_id='0003' and update_dt>='2018-01-02'

後はそれ以降の第一キーが0003のリーフを取得すればいいわけです。(本当はINSERT順考えたらこの木構造にはならないけど、今回は気にしない)

f:id:kingyokkun:20181207191834p:plain

複合インデックスの順番誤り

日付とキーの順番を逆にしている場合がよくあります。(update_dt,userid)でインデックスをつけているわけです。そうなるとこういった構造になります。

f:id:kingyokkun:20181207192007p:plain

この状態で先ほどと同じく「user_id='0003' and update_dt>='2018-01-02'」を検索しても、第一キーであるupdate_dtが'2018-01-02'の先頭(黄色塗り)を検索して、それ以降の8つのデータを全て取得し、user_idが0003と同じかを比較するという処理になります。このようにキーの順番を間違えると非効率な処理となります。

f:id:kingyokkun:20181207192029p:plain

キー飛ばし

ソート順が重要なので、基本的に第一キーを飛ばして第二キーのみを指定したクエリを実行してもインデックスは機能しません。第三キーまであるインデックスを作ってwhere句で第二キーを指定しない場合は第一キーまでのソート順が利用できるため第一キーだけのインデックスと同じ動きとなります。

最適な複合インデックスの順番づけ

そんなものはありません。まず、=で検索するキーを上位に置きます。続いて上で書いたような範囲検索で使うキー(よくあるのが日付)やinで取得するようなキーを指定します。必須であればあるほど上位のキーにする事が重要です。そして範囲検索やINでの検索はそれによってどれだけ絞り込みができるかが重要なのでアプリケーション仕様にまで踏み込まないとなかなか判断は難しいです。

アプリケーション仕様によって、キーが指定される場合とされない場合などがありますので、そういう場合は(key1,key2,key3)のインデックス以外に(key1,key3)のキーも作るなどアプリケーションが指定するキーと実行頻度を考えて最適なインデックス構成を考える必要があります。

最後に

Btreeの構造を理解すればわかるSQLパフォーマンスに関わる事をいくつかあげてみました。パフォーマンスチューニングにはジョインアルゴリズムの理解なども大きく響くのですが、まずはBtreeの理解をするのが一番だと思います。むしろ、ここを理解していないと確信を持ってのチューニングはできません。内部構造を理解して説明できる方が増えればSQL、DBのパフォーマンスもよくなりますので、是非ご理解いただけると良いかと思います。

BASEのSREチームではお客様に安心して買い物をしていただくために、サービスの安定性に責任を持ち、インフラ・アーキテクチャの改善に日々取り組み続けております。 ご興味を持たれた方いらっしゃいましたら是非ご連絡いただければ幸いです。 https://jobs.binc.jp/