採用面接他で「SQLできますか？」と聞かれて無力だった話2

## はじめに

indexのチューニングをできますかと聞かれて、そもそもindexのチューニングってなに？っていうレベルだったので調べたところ、とてもわかりやすいチュートリアル記事があったのでそちらを解読しています。
まだ途中ですが、その基本的な部分だけ少しまとめてみました。

[参考: USE THE INDEX,LUKE!](https://use-the-index-luke.com/ja/sql/preface)

## Q. SQLのindexって？

A. 索引、つまり対応するテーブルの行への参照を示しているもの。
基本的な単位としてリーフノードというもので構成され、キーとテーブルへの参照を示すROUND(またはRID)と呼ばれるもので構成される。

indexはソートされているが、対応するテーブルのデータたちはそうではない。
これはつまり、目的のデータを検索するのにテーブルの全行をチェックしていたら時間がかかってしようのないということのようだ。
なので、テーブルにあるデータを分類し、索引としてリーフノードにまとめておくことでデータ検索の際に網羅的に探してしまうところに道しるべを作ってあげることで最適化(高速化)するというのがindexの目的であり、チューニングはそのindexをDBの更新等に応じて最適化する行為のことを指すのだと感じた。

リーフノードは双方向連結リストとして存在している。
これはつまり、参考ページで例えられている電話帳で考えてみると

田中さんの電話番号を探すには「田中」というindexを頼りに探すことになるが、田村さんの電話番号を探すには「田村」というindexを探すことになる。
もっとわかりやすく言うと佐藤さんと田中さんが同じindexに含まれることは通常ありえない。
なぜなら索引はデータへのアクセスの最適化のために作られるものであり、それを考えると電話帳のindexは50音順ということを考えても佐藤という名字と田中という名字を同じ索引に入れることは基本的には不合理だからである。

## indexはツリー状に階層を構成する

さらにリーフノードは同ディレクトリ内だけではなく、ツリー状に形成することができる。
indexがデータへの索引であるのに対して、その集合であるリーフノードへの索引というべきindexも存在するということなのだろうか。

先程の例から続けると「田中」というindexは「タ段」というindexから探すことになる。
さらにその「タ段」というindexは「タ行」というindexから探すことになり……と書くとわかりやすい。
つまり電話帳のindexは五十音のあ～わ行をルートインデックスとして、そこからツリー状に階層を作りながら形成されていることになる。
つまり、データの検索の実態はこの場合は上位のindexから下位のリーフノードを走査し、該当のindexを見つけ、それを当該データへの参照indexに辿り着くまで行われるということになる。

## indexを作ったのに検索が遅くなってしまう？

問題はindexを使った検索の際はリーフノードに同じエントリがある可能性があるということになる。
つまり、キーが一意ではなく同じキーを持ったindexが同じリーフノードや別のリーフノードにあるという可能性があるので、ツリーの階層を追うだけではなく、別のリーフノードを読み込んで該当のキーを探し発見した場合はさらに下層のindexへ……となってしまう。
なので、リーフノードが増えるたびに該当indexを探すためのアクセスが増え、さらに当然階層が深くなればなるほどそれはネズミ算式に増えてしまうのでindexを使っていでも結果的に検索が遅くなってしまうという矛盾を引き起こしてしまう問題がある。

それではindexを使っている意味がないので、WHERE句で一意(UNIQUE)であるprimary keyを使い、ツリーの走査だけで終わらすことや、indexを適切に作るなどすることで検索が遅くなってしまうことへの対処を行っていく。

## アプローチ１ PKの性質から

DBはprimary key(以下PK)に対して、自動的にindexを作成してくれる。
そして、PKはそもそもの制約として一意であることが保証されているのでWHERE句で使った場合複数の行にヒットすることはない。
なので、indexは一意となるのでデータベースはリーフノードは辿らず、indexツリーを辿るだけになるので検索の実行は速くなるという寸法になる。

## アプローチ2 複合indexの場合

では、複合indexではどうなるか？
例として企業合併による従業員テーブルの統合が挙げられているが、この例がindexのチューニングがどういうことかという1番簡単な例であると感じた。
DBはPKが複数の列からなる場合、その列全てにindexを作成する。
例えば従業員テーブルAと従業員テーブルBとでEMPLOYEE_ID列が存在していた場合、それは当然統合した場合一意とはならない。

なので、この場合はどちらかのテーブルのEMPLOYEE_ID列を統合先のテーブルに合わせて変更する(つまり、新しく登録し直す)か、どちらかのテーブルに子会社ID列を作り、それとEMPLOYEE_ID列とを持ってPKとするかのどちらかを選択しないといけない。
前者の方がテーブルの可読性はあるし、PKも1つの列だけで済むが従業員数が膨大な場合その作業は現実的なものとはならないはずなので、基本的には後者の方法を取るのだろうと思う。

すると統合したテーブルでの新しいPKは以下の通りに作られる。

```sql

CREATE UNIQUE INDEX employees_pk
    ON employees (employee_id, subsidiary_id）

```

それに応じてWHERE句でのQuery文も以下のように新しい列をANDで指定する必要が出てくる。
このときどちらか片方の列だけでWHERE句を使うとTABLE ACCESS FULL、つまりテーブルを全件検索してしまうようです。

```sql

SELECT first_name, last_name
  FROM employees
 WHERE employee_id   = 123
   AND subsidiary_id = 30

```

複合indexを使う際に気をつけなくてはならないのは列の優先順位は定義された列の順序に依るというところです。
つまり、先程のこちらの定義の場合

```sql

CREATE UNIQUE INDEX employees_pk
    ON employees (employee_id, subsidiary_id）

```

employee_id > subsidiary_idという優先順位となる。
つまりまず従業員IDでソートし、次に子会社IDでソートを行った上で検索が行われるということになる。
さらに一番最初に定義された列は必ず検索で用いられるという特徴がある。
統合会社の従業員を探す場合、恐らく元はどちらの会社の従業員であったかというを探した場合のほうが話は早い(employee_idは一意ではないから)ので、上記のindexの場合

```sql

CREATE UNIQUE INDEX employees_pk
    ON employees (subsidiary_id, employee_id）

```

とすることでまずどちらの会社の従業員であったかというソートを行ってしまえば、片方のツリーだけ探していくだけで済むのでより早くなるという理屈なのだろう。
今回の例の場合はあまり関係のない話だが、複数のindexを作った場合1列目のindexだけで事足りる場合はそれだけで検索ができる(当然、例えば3列の複合indexを作った場合は1列目と2列目だけで事足りるという可能性もある)ので複合indexの列の順番は非常に重要な意味合いを持つと感じた。
しかし、当然複合indexを作るということはチューニングやメンテナンスの煩雑化を招くことが容易に想像できる。
なので、参考記事ではテーブルに対するindexが少ないほどパフォーマンスが向上するという記述がある。