世間的にはコロナが大流行していますね。

色々と話題がありますが、

東洋経済のDA(Data Analyst)さんがコロナの感染状況をきれいに可視化しているサービスがありました。

北海道が一番感染者数は多いのですが、地理的には近い東北はいまだに感染者数が0人。

こういう世間的なニーズをすぐにサービスに落とし込めるのはやっぱりすごいです。

toyokeizai.net

今回記事に書くこと

DBのindexについてです。

開発時にはRoRを利用しているので、indexに関わるマイグレーションも基本的にはOR経由で

DBに設定していきます。

今まで、なんとなく参照頻度が高くてデータ数が多いものについてはindexを貼っていましたが、

コードレビューの際に少し議論になったので復習をしました。

参考にした書籍はこちらです。

達人に学ぶDB設計徹底指南書

DBのindexって何?

Cなどをいじっている人には馴染み深いものですが、

プログラム的に例えると(x, α)形式の配列になります。(x=キー値, α=データへのポインタ)

indexというテーブルとは独立したオブジェクトがデータの並び順を担保することで、

探したいデータにたどり着くまでのパフォーマンスを向上させることができます。

f:id:wa_football_1120:20200229120130j:plain

indexを使うと何が嬉しいのか

データに見つけ出すパフォーマンス改善はもちろんですが、

下のようなメリットが挙げられます

メリット1 アプリケーション透過的

改善するための影響範囲がDBだけに留まるという意味になります。

indexを使う際には、DB側にindexを貼るだけなのでアプリケーション側で必要な操作というものがありません。

もう一つのパフォーマンス改善の手段である正規化はテーブル設計が変更となるので、

アプリケーション側の改修(SQLクエリやリレーションなど)が必要になってきます。

ちなみにアプリケーションから見た際に、indexの存在を気にしないで実装ができることを

アプリケーション透過的と言うそうです。

メリット2 データ透過的

indexはテーブルとは完全に独立したオブジェクトとして保存されます。

そのためindexを追加しても、テーブルやデータを変更する必要はないと言うことになります。

データから見ても、indexの存在は気にしないで設計・実装ができるのでデータ透過的となります。

B-treeインデックスについて

indexとは言っても複数種類があるようですが、

基本的にはB-treeが利用されているようです。

ケースバイケースとなるようですが、B-treeは下の5つの評価点のバランスがよく秀才型となります。

均一性
- 各キー値の間で検索速度のばらつきが少ない
持続性
- データ量の増加に対してパフォーマンス低下が少ない
処理汎用性
- CRUDのいずれの処理もそこそこに速い
非等値性
- =に限らず不等号を利用した処理もそこそこに速い

B-treeの構造

名前の通りですが、木構造でデータを保持します。

下の図で例えば5のデータ見るける場合は、

ルートノード→6→5の順序でデータを見つけにいきます。

f:id:wa_football_1120:20200229122149j:plain

B-treeの優れているところ

均一性

B-treeは平衡木になります。

平衡木とは、どのリーフもルートからの距離が均一になる木のことを挿します。

上の図だとどのリーフも深さが3ですよね。

同じ深さの場合、どのデータに対してもたどり着く計算量が同じと言うことになります。

そのため、均一性のパフォーマンスが優れていると訳です。

ただし、長期的に運用していくことでどうしてもB-treeのバランスが悪くなることがあるようなので、

定期的に、indexを再編成することが必要になります。

持続性

長期的に運用していくとB-treeでもバランスが悪くなりますが、

それでも性能劣化(計算量が増える)は非常に緩やかになります。

下の図の通りではありますが、計算量としてはO(log n)になります。(nはデータ量)

f:id:wa_football_1120:20200229161151j:plain

処理汎用性

B-treeはCRUDのどの操作においても、計算量はO(log n)になります。

非等値性

特定のノードよりも左みたいな形で探索範囲を絞ることができるので、

不等号(<, >, <=, >=)やBETWEENによる範囲検索の条件に対しても、パフォーマンスを発揮します。

ただし、否定条件についてはB-treeによる範囲の絞り込みができなくなるので、

パフォーマンスは発揮されません。

B-treeインデックスをどのように設計していくか

B-treeはアプリケーションのパフォーマンスを向上させる便利な機能です。

とはいえ、全部に付けておけばいいと言うものではありません。

前述の通り、テーブルとは異なるオブジェクトとして保存されるためHDのデータ量も喰うことになります。

本には、3つほどの指針が掲示されていました。

大規模なテーブルに対して作成する
カーディナリティの高い列に作成する
SQLでWHEREの選択条件もしくは結合条件に利用される列に作成する

上２つの指針については、少し詳しく説明します。

最後の奴は頻繁に参照とかで使われる物を選びましょうと言う感じです。

指針1 大規模なテーブルに対して作成する

先ほどの計算量のグラフと同じではありますが、

あるデータ量までは、フルスキャンの方が計算量が少ない領域があります。

データ量が少ない領域なのでそこまで大差は出ないのですが、無駄なindexを張らないためにもこの考え方は重要です。

大体1万件以下の場合は、indexの性能がそこまで発揮されるものでは無いようです。

f:id:wa_football_1120:20200229162155j:plain

指針2 カーディナリティの高い列に作成する

カーディナリティは特定の列の値がどれぐらいの種類の多さをもつかと言うことを表す概念です。

下の図のように、カーディナリティが高い列(=種類が多い)列を選ぶことが基本とされています。

特定のキー値を指定した時に、全体のレコード数の5%程度に絞り込めるだけのカーディナリティがあること目安とされています。

f:id:wa_football_1120:20200229162657j:plain

また、複合インデックスを貼る場合には、先頭に近いキーのカーディナリティが高いほど

パフォーマンスを発揮しやすいとされています。

B-treeのindexによる効果が期待できないSQL

CRUD全てにおいてある程度のパフォーマンスが期待できると書きましたが、

SQLの種類によってはパフォーマンスが期待できないことがあります。

index列で演算を行う

indexで作成された列はSQLにおいてはそのままで用いるのが原則です。そもそも、演算された値はindexに保管されている訳では無いのでパフォーマンスは発揮されません。

-- こう言うのはパフォーマンスを発揮しない

SELECT  * 
FROM shohin
WHERE col_1 * 1.1 > 100;

--SQL組み込み関数も同様
SELECT *
FROM shoshin
WHERE SUBSTR(col_1, 1, 1) = 'a';

IS NULL述語

NULL許容の列から値がnullの行のみを取得したい場合があるかと思います。

その時に下記のようなSQLを発行すると思いますが、これはindexのパフォーマンスは発揮されないSQLになります。

B-treeはnullについてはデータの値みなさず、indexに保持しないようにしているからです。

-- NOT NULLも同様
SELECT *
from shohin
WHERE col_1 IS NULL;

否定形

前述ではありますが、<>を用いた否定形も

検索範囲が広すぎるためindexのパフォーマンスは発揮されません。

OR

これとても驚いたのですが、ORを使った場合にindexは利用されないようです。

これの回避策として、INを利用することでindexを利用できる形式になるようです。

-- これはindexが使われない
SELECT *
FROM shohin
WHERE col_1 = 10 OR col_1 = 11;

-- INを使った場合はindexが使われる
SELECT *
FROM shohin
WHERE col_1 IN (10, 11)

後方一致と中間一致のLIKE

LIKEを利用した場合、後方一致と中間一致については、

indexが利用されません。

ただし前方一致についてはindexが利用されます。(確かに範囲検索が前方一致の場合はできそう)

最後に

概要レベルではありますが、DBのindexについて理解が深まった気がします。

RoRなんかを使っていると、形式的にindexを貼ったりしがちなので

indexについてもリファクタ対象として改修していきたいと思います。

頑張るときはいつも今

自称エンジニアのゴリラです。日々精進。

【忘備録】なんとなく使っているDBのindexについて復習した