💽

SQLのインデックスについてまとめてみる

2022/11/12に公開約10,000字

今度身内でSQLのインデックス(index)についての勉強会をすることになりそのことについて調べたのでここに載せます。

index

indexとは

index(直訳:索引)とは

百科事典・学術書などにおいて、特定の項目を素早く参照できるように見出し語を特定の配列に並べ、その所在をまとめたもの[1]

とのことだそうです。技術書などにおいても最後の方に特定の項目について何ページに書かれているか一覧になっているものがあると思います。

indexの例

項目     ページ
ああああ ‐ 1
いいいい - 2
うううう - 3

DBサーバーにおいても技術書などの書籍と同じようにindexを貼ることができSQLの高速化を図ることができます。

なぜindexを貼ると速くなるのか[2]

なぜindexを貼ると速くなるのかを示すために今回は以下のUserテーブルを用いて考えます

Userテーブル
id name age
1 John 10
2 Lloyd 15
3 Jack 16
4 Cedrix 18
5 Eliot 20
6 Chalmers 22
7 Otis 15
8 Jamey 16
9 Ernie 18
10 Harvey 16

今、Userテーブルからageが16のカラムを取得しようと思います。クエリで表すならこうです。

SELECT age FROM User WHERE age = 16

まずageについてのindexを貼っていない場合について考えます。indexを貼っていない場合はテーブルの最初のレコードから順に見ていき、ageが16の場合はコレクションします。それを最後の行まで繰り返し行い、最終的にageが16のレコード全てを返却します。このようにテーブルの全部の行をスキャンすることをフルテーブルスキャン[3]と言います。今回は10レコードとそこまでレコード数は多くないためフルテーブルスキャンを行ってもそこまで影響はないですが、1億、10億レコードといった膨大なレコード数においてフルテーブルスキャンした場合はパフォーマンスが悪化することが容易に想像できます。

次にageについてindexを貼っていた場合について考えます。ageについてindexを貼った場合以下のような形になります。

ageについてindexを貼った場合
age ポインタ(番地)
10 101
15 102
15 107
16 103
16 108
16 110
18 104
18 109
20 105
22 106

このようにageについてindexを貼った場合は

  • indexを作成した列のデータ
  • そのデータが含まれる行のポインタ(番地)

が格納されています。またindexはageの値でソートされていることもわかります。この性質によりageが16ではなくなった時点(今回は18)で探索を打ち切ることができ、フルテーブルスキャンするよりも高速に結果を返すことができるようになります。

indexの種類について

一言indexと言っても様々な種類のindexが存在しています。今回は以下の

  • B+ツリーインデックス
  • ビットマップインデックス
  • ハッシュインデックス
    について書いていこうと思います

B+ツリーインデックス

B+ツリーインデックスはツリーと書いてある通り木構造を用いたインデックスです。今回サンプルとする木構造は

とします。これはこちらのサイトのHighest Scoreとなっている図を参考にしています。まず各要素名について説明します。1段目の6と書かれているノードはルートノードと言います。次に2段目の515 18と書かれているノードはブランチノードと言います。最後の3段目はリーフノードと言います。リーフノードには列データと行ポインタ、次のリーフノードへのポインタが格納されています。実際の探索の仕方ですが2分探索木を用います。例として、10という値を探索してみます。まず、ルートノードでは10は6以上のため右側のノードへ移動します。次に15 18のブランチノードでは10は15より小さいため10のリーフノードへ移動します。その10のリーフノードから行ポインタを取得することによりO(log n)で探索を行うことができます。

このB+ツリーインデックスですが範囲検索に強いという利点があります[4]。理由としてはリーフノードには次のリーフノードのポインタが含まれているため、範囲検索をする際には一々ルートノードから探索する必要がないからです。しかし、このB+ツリーインデックスはカーディナリティ(カラムに含まれている値の種類)が少ないとあまり効果が見込めないという難点があります。そのため、B+ツリーインデックスは、身長や体重といった値の種類が多くなりそうなカラムに貼る必要があります。

ビットマップインデックス

ビットマップインデックスは検索に用いられるカラムに対して、その値とレコードとのビットマップを取ってレコードを検索するインデックスです[5]
今回は先に述べたUserテーブルに性別・ユーザー認証済みか否かを記録するカラムを追加したものをサンプルとして考えます。

Userテーブル
id name age sex authorized
1 John 10 male Yes
2 Lloyd 15 male No
3 Jack 16 male No
4 Cedrix 18 male Yes
5 Eliot 20 female Yes
6 Chalmers 22 female No
7 Otis 15 male Yes
8 Jamey 16 female No
9 Ernie 18 female Yes
10 Harvey 16 male No

まずsexカラムについてのビットマップインデックスを貼ります。すると以下のようなインデックスになります。

sexカラムについてのビットマップインデックス
id male female
1 1 0
2 1 0
3 1 0
4 1 0
5 0 1
6 0 1
7 1 0
8 0 1
9 0 1
10 1 0

ここでUserテーブルからsexカラムがmaleのレコードを取得します。クエリで表すなら以下のような感じです。

SELECT sex FROM User WHERE sex = 'male'

そうするとsexカラムにはインデックスが貼ってあるためビット列でsexカラムがmaleかどうか判定することができます。例えば今回の場合だとビット列は1111001001のためidが1,2,3,4,7,10のレコードを返せばよいということになります。以上よりビット列を用いてレコードを取得することで高速化が期待できます。

このビットマップインデックスですがOR検索においても使えるというのがメリットでもあります。例として先のテーブルにauthorizedカラムでもビットマップインデックスを貼ってみます。

authorizedカラムについてのビットマップインデックス
id Yes No
1 1 0
2 0 1
3 0 1
4 1 0
5 1 0
6 0 1
7 1 0
8 0 1
9 1 0
10 0 1

ここでUserテーブルからsexカラムがfemaleあるいはauthorizedカラムがNoのレコードを取得します。クエリで表すと以下のような感じです。

SELECT sex, authorized FROM User WHERE sex = 'female' OR authorized = 'No'

そうするとsex='female'のビット列は0000110110authorized='No'のビット列は0110010101となります。ここでこの2つビット列の論理和を取ることで今回のクエリを解釈することができます。00001101100110010101の論理和は0110110111となるためidが2,3,5,6,8,9,10のレコードを返せばよいということになります。

ただしこのビットマップインデックスはカーディナリティが高いカラムに対してはあまり有効的ではないという点があります[5:1]。理由としてはこのビットマップインデックスはそのカラムが取り得る値の種類の数だけビット列が生成されるため身長や体重といったカーディナリティが高いカラムではビット列の数が膨大になってしまうためです。そのためカーディナリティが高いカラムに対してはB+ツリーインデックス、低いカラムに対してはビットマップインデックスを用いるのが効果的と言われています。

ハッシュインデックス

ハッシュインデックスは、ハッシュ関数(任意の長さのデータを一定の長さのデータに変換する関数[6]。例:任意の整数を100で割ったあまりを返却する関数)を用いて検索に使用するキーとレコードを直接関係付けるインデックスです[7]。今回は以下のUserテーブルを例にして考えます。

Userテーブル
id name age
1 John 10
2 Lloyd 15
3 Jack 16
4 Cedrix 18
5 Eliot 20
6 Chalmers 22
7 Otis 15
8 Jamey 16
9 Ernie 18
10 Harvey 16

ageカラムにハッシュインデックスを貼ります。今回使用するハッシュ関数はage % 10とします。そうするとハッシュインデックスは以下のような形になります。

ageカラムのハッシュインデックス
ハッシュキー ポインタ
0 1,5
1
2 6
3
4
5 2,7
6 3,8,10
7
8 4,9
9

ここでageが10のレコードを取得します。クエリで表すなら以下のようになります。

SELECT age FROM User WHERE age = 10

まずage=10のハッシュ値を考えます。10 % 10なので0になります。そのためハッシュキーが0のところを探索します。そうするとポインタが1,5のレコードが存在します。ハッシュインデックスではインデックスを用いた検索の後に、再度検索結果の正当性を確認する処理(リチェック処理)を行います[8]。リチェック処理した結果idが1のレコードが返却されます。以上の処理により高速にレコードを取得することができます。

ハッシュインデックスのメリットとしてはハッシュ関数によってうまくデータが分散されている場合はほぼ定数時間O(1)で検索することができる点です[8:1]。また、ハッシュ値の衝突がないと仮定すればデータ量が増えても処理時間がO(1)が保証されている点もメリットの1つです[9]

ただしこのハッシュインデックスですが一致検索にしか使えないというデメリットもあります。理由としては範囲検索などにおいては複数のハッシュキーを検索する必要が出てくるためあまり効率的ではないからです。また、うまくレコードが分散するハッシュ関数を用いないと衝突が発生し、効率が下がるという点もデメリットの1つです。

複合インデックスについて

上記では単一のカラムについてのインデックスについて考えました。しかし、インデックスはB(+)ツリーインデックスを利用することで複数カラムを用いて貼ることもできます。これを複合インデックスと言います。技術書などの書籍の索引で考えるとまず日本語・英語で分けた後、それぞれの頭文字でページ数を調べていく感じです。

索引(複合インデックス)

項目     ページ
日本語

  • ああああ ‐ 1
  • いいいい - 2
  • うううう - 3

英語

  • aaaaaaaa - 4
  • bbbbbbbb - 5
  • cccccccc - 6

このように最初に日本語・英語で分けることにより、より素早く目的の単語を探すことができます。

実際に例を用いて考えてみます。今回は以下のUserテーブルを用いて考えます。

Userテーブル
id name age sex authorized
1 John 10 male Yes
2 Lloyd 15 male No
3 Jack 16 male No
4 Cedrix 18 male Yes
5 Eliot 20 female Yes
6 Chalmers 22 female No
7 Otis 15 male Yes
8 Jamey 16 female No
9 Ernie 18 female Yes
10 Harvey 16 male No

まず(age, name)の順で複合インデックスを貼った時について考えます。貼った結果については以下のようになります。

(age, name)の順で複合インデックスを貼った結果
id name age sex authorized
1 John 10 male Yes
2 Lloyd 15 male No
7 Otis 15 male Yes
10 Harvey 16 male No
3 Jack 16 male No
8 Jamey 16 female No
4 Cedrix 18 male Yes
9 Ernie 18 female Yes
5 Eliot 20 female Yes
6 Chalmers 22 female No

これよりまずageを昇順ソートした後にnameで同様に昇順ソートしていることがわかります。ここでageカラムが16、nameカラムがJで始まるレコードを取得したいと考えます。クエリで表現すると以下になります。

SELECT name FROM User WHERE age = 16 AND name LIKE 'J%'

まずageが16のところを探します。今回だと4行目から6行目が該当します。その次にnameがJから始まるレコードを探索します。今回だと5,6行目が該当します。こうすることで高速にレコードを探索することができます。

次に複合インデックスが効かない例を考えてみます。nameがCから始まるレコードを取得したいと考えます。クエリで表現すると以下になります。

SELECT name FROM User WHERE name LIKE 'C%'

上記のクエリだと(age, name)で複合インデックスを貼った場合、インデックスが効きません。理由としては、複合インデックスはまず最初に指定したカラムでソートをかけるためです。今回の場合だとまずageカラムでソートをかけるためnameカラムはageカラムが同値の中でソートされることになります。よってnameカラム単体でみるとソートはされておらず結果として、インデックスは効かないという形になります。そのため今回のクエリの場合はnameカラム単体でインデックスを貼るか、(name, age)の順といったようにnameカラムが最初にくるような複合インデックスを貼る必要があります。

以上より複合インデックスを貼る場合は順番に注意すればよいことが分かりました。

インデックスが使える・使えない検索条件例[2:1]

使える

  • 定数値との比較(ageにインデックスが貼ってあります)
SELECT age FROM User WHERE age >= 16

B+ツリーインデックスではソートされているためインデックスが使えます。

  • IS (NOT) NULL 条件での検索(ageにインデックスが貼ってあります)
SELECT age FROM User WHERE age IS NULL

NULL値は非NULL値の前後に入るためインデックスが使えます[10]

  • 前方一致(nameにインデックスが貼ってあります)
SELECT name FROM User WHERE name = 'J%'

文字列は最初の文字から順にソートされていくためインデックスが使えます。

  • MAX(), MIN()関数(ageにインデックスが貼ってあります)
SELECT MAX(age) FROM User

B+ツリーインデックスはソートされるためインデックスが使えます[11]

  • マルチカラムインデックスの先頭列からANDで使っている場合((age,name)の順でインデックスが貼ってあります)
SELECT id FROM User WHERE age = 16 AND name LIKE 'J%'

(age, name)の順でソートしてあるためインデックスが使えます。

使えない

  • 前方一致でないLIKE検索
SELECT id FROM User WHERE LIKE '%j%'

文字列は最初の文字からソートされるためインデックスは使えません。ただし後方一致(LIKE '%j')は工夫することでインデックスが使えます[12]

  • ORDER BYのソート順に、ASC,DESCを同時に指定している場合
SELECT id FROM User ORDER BY name ASC, age DESC
脚注
  1. https://ja.wikipedia.org/wiki/索引 ↩︎

  2. https://gihyo.jp/magazine/SD/archive/2022/202209 ↩︎ ↩︎

  3. https://atmarkit.itmedia.co.jp/ait/articles/0901/29/news152.html ↩︎

  4. https://christina04.hatenablog.com/entry/2017/05/17/190000 ↩︎

  5. https://qiita.com/gohandesuyo/items/b3a684157b2eefc69a79#ビットマップインデックスとは ↩︎ ↩︎

  6. https://www.jipdec.or.jp/project/research/why-e-signature/hash-function.html#:~:text=ハッシュ関数(Hash Function)と,関数(アルゴリズム)"です。 ↩︎

  7. https://xtech.nikkei.com/it/article/COLUMN/20060113/227241/ ↩︎

  8. https://www.intellilink.co.jp/column/oss/2018/051400.aspx ↩︎ ↩︎

  9. https://gihyo.jp/dev/serial/01/sql_academy2/000702 ↩︎

  10. https://techblog.istyle.co.jp/archives/1514 ↩︎

  11. http://mickindex.sakura.ne.jp/database/db_optimize.html ↩︎

  12. https://lets.postgresql.jp/documents/technical/text-processing/3#endswith ↩︎

Discussion

ログインするとコメントできます