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

Cloud Spannerのindex

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

そこで今回、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 (スポンサーはメルペイさん)を使用させてもらいました。
自前で借りたら月7万円もするSpannerを、いつでもどこでも自由に使える検証環境です。非常に有難いですね。Spannerを試してみたいと思ったら是非ご利用ください。

テーブル定義

1. 基本テーブル

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

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未使用になります）

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句で保存した列はこの制限に含まれないようです

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を張ります。

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個

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. 基本テーブル

2. シンプルなindex

11:56くらいからの山です

3. 複雑なindex

12:32くらいからの山です

4. 20個のシンプルなindex

13:12くらいからの山です。13:07くらいのはミス

5. 32個の複雑なindex

相当な負荷かけてしまい本当にあせりました。
長かったので開始時のグラフは切れてしまっています。

全体

検索性能について

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

1. 基本テーブル

1-1

SELECT * FROM fighter_play_count LIMIT 100

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

2-1

SELECT * FROM fighter_play_count_one_simple_index LIMIT 100

2-2

SELECT * FROM fighter_play_count_one_simple_index WHERE kirby > 900 LIMIT 100

2-3

SELECT player_id, kirby FROM fighter_play_count_one_simple_index WHERE kirby > 900 LIMIT 100

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

3-1

SELECT * FROM fighter_play_count_one_multi_column_index LIMIT 100

3-2

SELECT * FROM fighter_play_count_one_multi_column_index WHERE kirby > 900 LIMIT 100

3-3

SELECT player_id, kirby FROM fighter_play_count_one_multi_column_index WHERE kirby > 900 LIMIT 100

3-4

SELECT player_id, kirby FROM fighter_play_count_one_multi_column_index WHERE kirby > 900 ORDER BY mario LIMIT 100

3-5

SELECT * FROM fighter_play_count_one_multi_column_index WHERE kirby > 900 ORDER BY mario LIMIT 100

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

4-1

SELECT * FROM fighter_play_count_20_index LIMIT 100

4-2

SELECT * FROM fighter_play_count_20_index WHERE kirby > 900 LIMIT 100

4-3

SELECT player_id, kirby FROM fighter_play_count_20_index WHERE kirby > 900 LIMIT 100

4-4

SELECT player_id, kirby FROM fighter_play_count_20_index WHERE kirby > 900 ORDER BY mario LIMIT 100

4-5

SELECT * FROM fighter_play_count_20_index WHERE kirby > 900 ORDER BY mario LIMIT 100

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

5-1

SELECT * FROM fighter_play_count_32_multi_column_index LIMIT 100

5-2

SELECT * FROM fighter_play_count_32_multi_column_index WHERE kirby > 900 LIMIT 100

5-3

SELECT player_id, kirby FROM fighter_play_count_32_multi_column_index WHERE kirby > 900 LIMIT 100

5-4

SELECT player_id, kirby FROM fighter_play_count_32_multi_column_index WHERE kirby > 900 ORDER BY mario LIMIT 100

5-5

SELECT * FROM fighter_play_count_32_multi_column_index WHERE kirby > 900 ORDER BY mario LIMIT 100

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を使用した（つまり実用的な）パターンでも試験するべきでした。

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

Cloud Spannerのindex

index の limit

検証環境

テーブル定義

1. 基本テーブル

2. シンプルなindex

3. 複雑なindex

4. 20個のシンプルなindex

5. 32個の複雑なindex

性能試験

シナリオ

結果まとめ

性能試験時の負荷

1. 基本テーブル

2. シンプルなindex

3. 複雑なindex

4. 20個のシンプルなindex

5. 32個の複雑なindex

全体

検索性能について

1. 基本テーブル

2. シンプルなindex

3. 複雑なindex

4. 20個のシンプルなindex

5. 32個の複雑なindex

全体のまとめ