Cloud Spannerのindexの簡単な性能試験

Advent Calendar 2018 25日目でしたが、盛大に遅刻しました。ごめんなさい。

# Cloud Spannerのindex

Cloud Spannerは昨今注目されるGCPのサービスですが、現在の疑問点としてindexってどうなの？というのがあります。
indexについてのTIPSは公式の[Cloud Spanner でのクエリ パフォーマンスの向上](https://cloud.google.com/spanner/docs/whitepapers/improving-query-performance)を読むと大まかに分かりますが、その性能についての詳細な記事は公式/非公式問わず見かけません。

そこで今回、Cloud Spanner（以下Spanner）のindexを張ったときの性能劣化やindex利用による検索速度の向上がどんなものかを調べました。
ストレージがSplitに分かれていてPaxosによる遅延がそこそこあるのでindexを付けることでSplitをまたぐ更新が行われるためindexによる性能劣化が他のRDBMSより大きいのでは？とか、結果について技術的な面からの考察はやりません。

## index の limit
基本的なところを確認しておきます

|項目|制限|
|:--|:--|
|データベースあたりのindex数|4,096|
|テーブルあたりのindex数|32|
|index名の文字数|1～128 文字|
|indexキーの列数|	16 |

実は当初このテーブル辺りのindex数の制限はもっと高いと勘違いしていて、100index/テーブルで試そうとしていました。

# 検証環境
今回試験に当たっては、[GCPUG Shared Spanner](https://spanner.gcpug.jp/) (スポンサーはメルペイさん)を使用させてもらいました。
自前で借りたら月7万円もするSpannerを、いつでもどこでも自由に使える検証環境です。非常に有難いですね。Spannerを試してみたいと思ったら是非ご利用ください。

# テーブル定義
## 1. 基本テーブル
一般的には推奨されない、いわゆる列持ちテーブルです。
この基本テーブルでは、セカンダリindexはつけていないため、主キーを用いない検索は全てテーブルスキャンになります。
比較に使うindex付きのテーブルも、異なるのはindex定義のみで基本となる部分はすべてこれと同じです

```SQL
CREATE TABLE fighter_play_count (
  player_id INT64,
  kirby INT64,
  mario INT64,
  donkey_kong INT64,
  link INT64,
  samus INT64,
  yoshi INT64,
  fox INT64,
  pikachu INT64,
  luigi INT64,
  ness INT64,
  captain_falcon INT64,
  peach INT64,
  koopa INT64,
  zelda INT64,
  marth INT64,
  sonic INT64,
  snake INT64,
  rockman INT64,
  murabito INT64,
  inkling INT64,
) PRIMARY KEY(player_id);

```

## 2. シンプルなindex
kirby列にのみindexを張ります。
このテーブルでは、kirbyによる検索や並び替えにはindexが利きますが、その場合は主キーのplayer_idとkirby以外の値を取得できません。（取得しようとする場合はindex未使用になります）

```SQL
CREATE TABLE fighter_play_count_one_simple_index (
-- 省略
) PRIMARY KEY (player_id);

CREATE INDEX simple_kirby 
ON fighter_play_count_one_simple_index (
	kirby
);
```

## 3. 複雑なindex
許可されてる最大数（つまり16）の列にindexを張ります
「15列しかないじゃないか？」ですって？
そうなんですよね。実は主キーもこの制限に含まれるんですよ。これはSpannerのindex使う上でのちょっとした注意点です。
ちなみに、[STORING句で保存した列](https://cloud.google.com/spanner/docs/secondary-indexes#storing_clause)はこの制限に含まれないようです

```SQL
CREATE TABLE fighter_play_count_one_multi_column_index(
-- 省略
) PRIMARY KEY (player_id);

CREATE INDEX simple_kirby 
ON fighter_play_count_one_multi_column_index (
	kirby,
	mario,
	donkey_kong,
	link,
	samus,
	yoshi,
	fox,
	pikachu,
	luigi,
	ness,
	captain_falcon,
	peach,
	koopa,
	zelda,
	marth
);
```

## 4. 20個のシンプルなindex
全ての列に対して個別にindexを張ります。


```SQL
CREATE TABLE fighter_play_count_20_index(
-- 省略
) PRIMARY KEY (player_id);

CREATE INDEX captain_falcon ON fighter_play_count_20_index(captain_falcon);
CREATE INDEX donkey_kong ON fighter_play_count_20_index(donkey_kong);
CREATE INDEX fox ON fighter_play_count_20_index(fox);
CREATE INDEX inkling ON fighter_play_count_20_index(inkling);
CREATE INDEX kirby ON fighter_play_count_20_index(kirby);
CREATE INDEX koopa ON fighter_play_count_20_index(koopa);
CREATE INDEX link ON fighter_play_count_20_index(link);
CREATE INDEX luigi ON fighter_play_count_20_index(luigi);
CREATE INDEX mario ON fighter_play_count_20_index(mario);
CREATE INDEX marth ON fighter_play_count_20_index(marth);
CREATE INDEX murabito ON fighter_play_count_20_index(murabito);
CREATE INDEX ness ON fighter_play_count_20_index(ness);
CREATE INDEX peach ON fighter_play_count_20_index(peach);
CREATE INDEX pikachu ON fighter_play_count_20_index(pikachu);
CREATE INDEX rockman ON fighter_play_count_20_index(rockman);
CREATE INDEX samus ON fighter_play_count_20_index(samus);
CREATE INDEX snake ON fighter_play_count_20_index(snake);
CREATE INDEX sonic ON fighter_play_count_20_index(sonic);
CREATE INDEX yoshi ON fighter_play_count_20_index(yoshi);
CREATE INDEX zelda ON fighter_play_count_20_index(zelda);
```

## 5. 32個の複雑なindex

セカンダリindexは32個つけられます（プライマリindexは制限に含まれない）

- 2列に対するindexが1つ
- 3列に対するindexが1つ
- ・・・
- 13列に対するindexが1つ
- 15列に対するinedxが20個

```SQL
CREATE TABLE fighter_play_count_32_multi_column_index(
-- 省略
) PRIMARY KEY (player_id);

CREATE INDEX kirby_to_mario ON fighter_play_count_32_multi_column_index(kirby, mario);
CREATE INDEX kirby_to_kong ON fighter_play_count_32_multi_column_index(kirby, mario, donkey_kong);
CREATE INDEX kirby_to_link ON fighter_play_count_32_multi_column_index(kirby, mario, donkey_kong, link);
CREATE INDEX kirby_to_samus ON fighter_play_count_32_multi_column_index(kirby, mario, donkey_kong, link, samus);
CREATE INDEX kirby_to_yoshi ON fighter_play_count_32_multi_column_index(kirby, mario, donkey_kong, link, samus, yoshi);
CREATE INDEX kirby_to_fox ON fighter_play_count_32_multi_column_index(kirby, mario, donkey_kong, link, samus, yoshi, fox);
CREATE INDEX kirby_to_pikachu ON fighter_play_count_32_multi_column_index(kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu);
CREATE INDEX kirby_to_luigi ON fighter_play_count_32_multi_column_index(kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu, luigi);
CREATE INDEX kirby_to_ness ON fighter_play_count_32_multi_column_index(kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu, luigi, ness);
CREATE INDEX kirby_to_falcon ON fighter_play_count_32_multi_column_index(kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu, luigi, ness, captain_falcon);
CREATE INDEX kirby_to_peach ON fighter_play_count_32_multi_column_index(kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu, luigi, ness, captain_falcon, peach);
CREATE INDEX kirby_to_koopa ON fighter_play_count_32_multi_column_index(kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu, luigi, ness, captain_falcon, peach, koopa);
CREATE INDEX kirby_to_marth ON fighter_play_count_32_multi_column_index(kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu, luigi, ness, captain_falcon, peach, koopa, zelda, marth);
CREATE INDEX donkey_to_inkling ON fighter_play_count_32_multi_column_index(donkey_kong, link, samus, yoshi, fox, pikachu, luigi, ness, captain_falcon, peach, koopa, zelda, marth, sonic, snake);
CREATE INDEX falcon_to_samus ON fighter_play_count_32_multi_column_index(captain_falcon, peach, koopa, zelda, marth, sonic, snake, rockman, murabito, inkling, kirby, mario, donkey_kong, link, samus);
CREATE INDEX fox_to_kirby ON fighter_play_count_32_multi_column_index(fox, pikachu, luigi, ness, captain_falcon, peach, koopa, zelda, marth, sonic, snake, rockman, murabito, inkling, kirby);
CREATE INDEX inkling_to_zelda ON fighter_play_count_32_multi_column_index(inkling, kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu, luigi, ness, captain_falcon, peach, koopa, zelda);
CREATE INDEX koopa_to_fox ON fighter_play_count_32_multi_column_index(koopa, zelda, marth, sonic, snake, rockman, murabito, inkling, kirby, mario, donkey_kong, link, samus, yoshi, fox);
CREATE INDEX link_to_rockman ON fighter_play_count_32_multi_column_index(link, samus, yoshi, fox, pikachu, luigi, ness, captain_falcon, peach, koopa, zelda, marth, sonic, snake, rockman);
CREATE INDEX luigi_to_donkey ON fighter_play_count_32_multi_column_index(luigi, ness, captain_falcon, peach, koopa, zelda, marth, sonic, snake, rockman, murabito, inkling, kirby, mario, donkey_kong);
CREATE INDEX mario_to_sonic ON fighter_play_count_32_multi_column_index(mario, donkey_kong, link, samus, yoshi, fox, pikachu, luigi, ness, captain_falcon, peach, koopa, zelda, marth, sonic);
CREATE INDEX marth_to_luigi ON fighter_play_count_32_multi_column_index(marth, sonic, snake, rockman, murabito, inkling, kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu, luigi);
CREATE INDEX murabito_to_koopa ON fighter_play_count_32_multi_column_index(murabito, inkling, kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu, luigi, ness, captain_falcon, peach, koopa);
CREATE INDEX ness_to_link ON fighter_play_count_32_multi_column_index(ness, captain_falcon, peach, koopa, zelda, marth, sonic, snake, rockman, murabito, inkling, kirby, mario, donkey_kong, link);
CREATE INDEX peach_to_yoshi ON fighter_play_count_32_multi_column_index(peach, koopa, zelda, marth, sonic, snake, rockman, murabito, inkling, kirby, mario, donkey_kong, link, samus, yoshi);
CREATE INDEX pikachu_to_mario ON fighter_play_count_32_multi_column_index(pikachu, luigi, ness, captain_falcon, peach, koopa, zelda, marth, sonic, snake, rockman, murabito, inkling, kirby, mario);
CREATE INDEX rockman_to_peach ON fighter_play_count_32_multi_column_index(rockman, murabito, inkling, kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu, luigi, ness, captain_falcon, peach);
CREATE INDEX samus_to_murabito ON fighter_play_count_32_multi_column_index(samus, yoshi, fox, pikachu, luigi, ness, captain_falcon, peach, koopa, zelda, marth, sonic, snake, rockman, murabito);
CREATE INDEX snake_to_falcon ON fighter_play_count_32_multi_column_index(snake, rockman, murabito, inkling, kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu, luigi, ness, captain_falcon);
CREATE INDEX sonic_to_ness ON fighter_play_count_32_multi_column_index(sonic, snake, rockman, murabito, inkling, kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu, luigi, ness);
CREATE INDEX yoshi_to_inkling ON fighter_play_count_32_multi_column_index(yoshi, fox, pikachu, luigi, ness, captain_falcon, peach, koopa, zelda, marth, sonic, snake, rockman, murabito, inkling);
CREATE INDEX zelda_to_pikachu ON fighter_play_count_32_multi_column_index(zelda, marth, sonic, snake, rockman, murabito, inkling, kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu);

```


# 性能試験
これら5つのテーブルに対して同じシナリオでinsertのみの試験を行いました
ただ、予想されたことですが4.と5.のテーブルは性能劣化が著しく、CPU負荷も半端なかったので試験を予定の半分で打ち切りました。

## シナリオ

かなり雑ですが以下のようにやりました。一応ですが、ローカルマシンのリソースは基本テーブルへの試験時も十分に余裕がありました。

- ローカルのマシンで8スレッドに並列化して複数トランザクションを同時に実行
- 1トランザクションで30レコードをinsert
- insert する内容
 - player_id：MIN(INT64)～MAX(INT64)の範囲で無作為な値
 - 主キー以外の各列：0～999の範囲で無作為な値
- レコード数が(~~目視で~~)10万を超えたら(~~手動で~~)停止して、掛かった時間を計測（4.と5.は半分の5万）

## 結果まとめ
index数を増やした4.と5.はレコード数増加により明確に性能劣化が見られました。


|項目|試験終了時の行数|所要時間|大体のCPU負荷|1秒当たりのオペレーション回数(概算)|
|:--|--:|--:|--:|--:|
|1. 基本テーブル|101,640 |13:11|50%|200|
|2. シンプルなindex|100,680|26:35|70%|105|
|3. 複雑なindex|100,140|27:41|75%|102|
|4. 20個のシンプルなindex|50,190|25:34|100%|60~45|
|5. 32個の複雑なindex|50,130|57:07|100%付近であらぶる|38~25|


- 1.と2.の比較
    - indexの有る無しでCPU負荷・秒間オペレーション回数ともにまず大きな差が見られます
- 2.と3.の比較
    - indexのキー列数が1→15(主キーも入れると2→16)では、微々たる差でした。
- 2.および3. と4.の比較
    - index自体の数が増えると、明確に性能が落ちます
- 4.と5.の比較
    - そもそもindexの数も20→32に増えてるので同様に性能は落ちますよね。
    - 5.をやる意味はあまりなかったかもしれない


## 性能試験時の負荷
各テーブルごとにSpannerへの負荷がどれくらいだったのかの記録

### 1. 基本テーブル
![ss_fighter_play_count.png](https://qiita-image-store.s3.amazonaws.com/0/210857/e68c5e35-effb-cfe3-3590-f28f9aa4f9d5.png)

### 2. シンプルなindex
11:56くらいからの山です
![ss_fighter_play_count_one_simple_index.png](https://qiita-image-store.s3.amazonaws.com/0/210857/395aeac7-fbd7-0b33-521c-3c676a95ffb3.png)

### 3. 複雑なindex
12:32くらいからの山です
![ss_fighter_play_count_one_multi_column_index.png](https://qiita-image-store.s3.amazonaws.com/0/210857/855237c4-5f19-5d15-bc05-88deed36eb91.png)

### 4. 20個のシンプルなindex
13:12くらいからの山です。13:07くらいのはミス

![ss_fighter_play_count_20_index.png](https://qiita-image-store.s3.amazonaws.com/0/210857/e63e7200-a642-cb40-263c-d0cf4dec194e.png)

### 5. 32個の複雑なindex
相当な負荷かけてしまい本当にあせりました。
長かったので開始時のグラフは切れてしまっています。
![ss_fighter_play_count_32_multi_column_index.png](https://qiita-image-store.s3.amazonaws.com/0/210857/45f4fcb5-09e7-bebe-fa1b-b55b2d3c6789.png)

### 全体
![ss_whole.png](https://qiita-image-store.s3.amazonaws.com/0/210857/fa1cab53-e29f-c66a-d016-7a873491dcea.png)


# 検索性能について
Spanner はGCPコンソール上から検索ができ、しかも詳細な実行計画も取得できます。
いくつか試してみました。もし読者の方で自分でも試してみたいという方が居れば、[GCPUG slack](https://gcpug.jp/) に参加して声をかけてください

## 1. 基本テーブル
```SQL:1-1
SELECT * FROM fighter_play_count LIMIT 100
```
```SQL:1-2
SELECT * FROM fighter_play_count WHERE kirby > 900 LIMIT 100
```

|SQL|合計経過時間|CPU時間|検索方法|
|:--|--:|--:|:--|
|1-1|20.62ms|15.48ms|Table Scan|
|1-2|21.09ms|16.98ms|Table Scan|

- フルスキャンなので当然変わらないです

## 2. シンプルなindex
```SQL:2-1
SELECT * FROM fighter_play_count_one_simple_index LIMIT 100
```
```SQL:2-2
SELECT * FROM fighter_play_count_one_simple_index WHERE kirby > 900 LIMIT 100
```
```SQL:2-3
SELECT player_id, kirby FROM fighter_play_count_one_simple_index WHERE kirby > 900 LIMIT 100
```
```SQL:2-4
SELECT player_id, kirby FROM fighter_play_count_one_simple_index WHERE kirby > 900 ORDER BY mario LIMIT 100
```

|SQL|合計経過時間|CPU時間|検索方法|
|:--|--:|--:|:--|
|2-1|20.85ms|15.97ms|Table Scan|
|2-2|23.97ms|17.09ms|Table Scan|
|2-3|8.9ms|5.19ms|Index Scan|
|2-4|337.54ms|392.3ms|Table Scan|

- 2-2、2-3から分かるように、カバリングindexとしてしかindexの恩恵を受けられません。
- 「合計経過時間＜CPU時間」の場合は、実行計画の一部を並列化しています


## 3. 複雑なindex
```SQL:3-1
SELECT * FROM fighter_play_count_one_multi_column_index LIMIT 100
```
```SQL:3-2
SELECT * FROM fighter_play_count_one_multi_column_index WHERE kirby > 900 LIMIT 100
```
```SQL:3-3
SELECT player_id, kirby FROM fighter_play_count_one_multi_column_index WHERE kirby > 900 LIMIT 100
```
```SQL:3-4
SELECT player_id, kirby FROM fighter_play_count_one_multi_column_index WHERE kirby > 900 ORDER BY mario LIMIT 100
```
```SQL:3-5
SELECT * FROM fighter_play_count_one_multi_column_index WHERE kirby > 900 ORDER BY mario LIMIT 100
```
```SQL:3-6
SELECT player_id, kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu FROM fighter_play_count_one_multi_column_index WHERE kirby > 900 ORDER BY mario LIMIT 100
```

|SQL|合計経過時間|CPU時間|検索方法|
|:--|--:|--:|:--|
|3-1|20.68ms|15.77ms|Table Scan|
|3-2|23.05ms|19.82ms|Table Scan|
|3-3|11.49ms|6.36ms|Index Scan|
|3-4|78.35ms|68.66ms|Index Scan|
|3-5|955.21ms|910.91ms|Table Scan|
|3-6|79.61ms|63.44ms|Index Scan|

- 3-6を見ると、indexに含まれてさえいれば取得列数による性能の変化は特に無いようですね。
- ただし、検索条件やソート条件に含めないのであればこの場合はSTORING句で指定するほうが良いでしょう。

## 4. 20個のシンプルなindex
```SQL:4-1
SELECT * FROM fighter_play_count_20_index LIMIT 100
```
```SQL:4-2
SELECT * FROM fighter_play_count_20_index WHERE kirby > 900 LIMIT 100
```
```SQL:4-3
SELECT player_id, kirby FROM fighter_play_count_20_index WHERE kirby > 900 LIMIT 100
```
```SQL:4-4
SELECT player_id, kirby FROM fighter_play_count_20_index WHERE kirby > 900 ORDER BY mario LIMIT 100
```
```SQL:4-5
SELECT * FROM fighter_play_count_20_index WHERE kirby > 900 ORDER BY mario LIMIT 100
```
```SQL:4-6
SELECT player_id, kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu FROM fighter_play_count_20_index WHERE kirby > 900 ORDER BY mario LIMIT 100
```

|SQL|合計経過時間|CPU時間|検索方法|
|:--|--:|--:|:--|
|4-1|21.13ms|16.37ms|Table Scan|
|4-2|25.44ms|14.62ms|Table Scan|
|4-3|9.61ms|3.84ms|Index Scan|
|4-4|168.20ms|148.36ms|Table Scan|
|4-5|522.22ms|505.88ms|Table Scan|
|4-6|234.72ms|224.52ms|Table Scan|

- 4-5と4-6 は何回か試してもこの傾向。Table Scanの場合かつソートする場合は、取ってくる列数によって変わるのかもしれません。
- というか4.のテーブルで試験をする意味があったかというと、あまりなかったかも。

## 5. 32個の複雑なindex

```SQL:5-1
SELECT * FROM fighter_play_count_32_multi_column_index LIMIT 100
```
```SQL:5-2
SELECT * FROM fighter_play_count_32_multi_column_index WHERE kirby > 900 LIMIT 100
```
```SQL:5-3
SELECT player_id, kirby FROM fighter_play_count_32_multi_column_index WHERE kirby > 900 LIMIT 100
```
```SQL:5-4
SELECT player_id, kirby FROM fighter_play_count_32_multi_column_index WHERE kirby > 900 ORDER BY mario LIMIT 100
```
```SQL:5-5
SELECT * FROM fighter_play_count_32_multi_column_index WHERE kirby > 900 ORDER BY mario LIMIT 100
```
```SQL:5-6
SELECT player_id, kirby, mario, donkey_kong, link, samus, yoshi, fox, pikachu FROM fighter_play_count_32_multi_column_index WHERE kirby > 900 ORDER BY mario LIMIT 100
```

|SQL|合計経過時間|CPU時間|検索方法|
|:--|--:|--:|:--|
|5-1|20.97ms|16.32ms|Table Scan|
|5-2|98.07ms|81.34ms|Table Scan|
|5-3|10.92ms|4.32ms|Index Scan|
|5-4|52.30ms|45.16ms|Index Scan|
|5-5|3.89s|3.4s|Table Scan|
|5-6|132.86ms|126.17ms|Index Scan|

- 5-2は何度やっても重かったです。indexがあまりに複雑だとTable Scanにも影響出るのでしょうか？

# 全体のまとめ

- 基本的には一般的に知られるindexとの付き合い方をするってことで良さそう。
- indexあるなしではそれなりに性能差が出る
- 更新系もちゃんと試験するべきでした。
- 相関クエリなど複雑なクエリで試したときに効果でるindexを使用した（つまり実用的な）パターンでも試験するべきでした。