🗂️

CockroachDBにおけるインデックス選択

2023/04/11に公開

以前の投稿でCockroachDBがSQLテーブルデータとテーブルインデックスをキーバリューストレージにマッピングする方法について説明しました。この記事では特定のクエリーを実行するために使用する最適なインデックスを選択するために関係するいくつかの要因について説明します。

インデックス入門

テーブルの内部は特定の列（または列のグループ）に従って構成されています。このためテーブルが多数の行を含んでいても、その列または列グループの値に従って行を検索することは非常に効率的です。しかし、別の列の値で検索する必要がある場合はどうでしょうか。このような結果を得るためにはシステムはテーブルのすべての行を調べなければならず、大きなテーブルでは非常に時間がかかります。このような事態を避けるためには、システムにインデックスを保持させる必要があります。インデックスとは異なるカラム（またはカラムのグループ）に従ってデータを整理する追加の構造です。

簡単な例で説明します。例えば歌のデータベースを管理する場合を考えてみましょう。次のようなSongsテーブルがあるとします：

CREATE TABLE Songs (
    ID     INT PRIMARY KEY,
    Title  STRING,
    Artist STRING,
    Album  STRING,
    Year   INT
)

IDはある楽曲を一意に識別するために使用される番号です。このテーブルの行は内部的にはIDに従って順番に格納されるため、ある曲の詳細を非常に効率的に取り出すことがでます：

EXPLAIN SELECT * FROM Songs WHERE ID = 123

Level	Type	Description
0	scan	Songs@primary /123-/124

EXPLAIN文はSQLエンジンがどのようにクエリを実行するか（プランとして知られている）の詳細を見るために使用されます。この場合、/123-/124の範囲はIDが123以上、124未満の行をスキャンすることを示しています - つまり、IDが123の行だけをスキャンします。今はLevelを無視し、後で説明します。

残念ながら、あるアーティストの曲を見つけたい場合、CockroachDBはテーブル全体をスキャンして、各行をアーティスト名と比較する必要があります：

EXPLAIN SELECT ID FROM Songs WHERE Artist = 'Rick Astley'

Level	Type	Description
0	scan	Songs@primary -

範囲に縛りがない-はテーブル全体をスキャンする必要があることを意味します。これでは膨大な曲のデータベースがある場合に困ります。解決策はアーティストに対するインデックスを使用することです：

CREATE INDEX ByArtist ON Songs (Artist)

このインデックスによりアーティスト名で効率的に検索できるようになりますが、Songsテーブルを変更するたびにインデックスを更新し続けるというコストが発生します。

インデックスが内部でどのように保存されるかの詳細については別のブログ記事で説明します。この議論ではインデックスを元のテーブルの各曲に1つずつあるエントリのリストと考えることができます。各エントリにはアーティストと曲のID（「主キー」）が含まれています。エントリーはソートされた状態で利用できます。これによって上のクエリはより良く見えるようになります：

Level	Type	Description
0	scan	Songs@ByArtist /"Rick Astley"-/"Rick Astley\x00"

英語では「与えられたアーティスト名と完全に一致するエントリーを直接取得する」となります。

この例をもう少し詳しく見てみましょう。ByArtistインデックスの各エントリにはアーティストと曲のIDが含まれていることを述べましたが、このサンプルクエリでは、探している曲のIDだけを求めています！

しかし、もっと詳しい情報、例えば曲のタイトルを知りたい場合はどうすればいいのでしょうか？

カバーリングインデックスとノンカバーリングインデックス

クエリーがインデックスの一部でないカラムを要求した場合にどうなるかを見てみましょう：

EXPLAIN SELECT ID, Title FROM Songs WHERE Artist = 'Rick Astley'

Level	Type	Description
0	index-join
1	scan	Songs@ByArtist /"Rick Astley"-/"Rick Astley\x00"
1	scan	Songs@primary

今、何が起こったのでしょうか？インデックスには各アーティストの楽曲IDしか含まれていないため、インデックスから楽曲のタイトルを取得することはできません。インデックスから曲のIDを取得し、そのIDに対応するタイトルをメイン (primary) テーブルから取得する必要があるのです。このクエリの実装はツリーを形成する再利用可能な機能の断片に分割されています。ツリーのルート（レベル0）はindex-joinノードで、レベル1の2つのscanノード（リーフ）が実行する行の取得を調整します。

メインテーブルからのタイトルの取得はバッチで行われ、各バッチはByArtistインデックスからの曲IDのセットに対応します。一般にメインテーブルで探している行は任意の位置にあり（そして順次ではありません）、この検索は通常のスキャンよりも高価になります。

このクエリーではByArtistは検索する必要があるすべての列を「カバー」していないという意味で、いわゆるノンカバーリングインデックスと呼ばれるものです。前のクエリ（IDのみが必要）では同じインデックスがカバーリングされていました。カバーリングインデックスはノンカバーリングインデックスよりも効率性の面で優れています。

もし上のクエリが頻繁に行われるものでより効率的にしたい場合はどうすればいいでしょうか。インデックスを変更してタイトルも保存するようにすればいいのです：

CREATE INDEX ByArtist ON Songs (Artist) STORING (Title)

Level	Type	Description
0	scan	Songs@ByArtist /"Rick Astley"-/"Rick Astley\x00"

また、アーティストとタイトルの両方にインデックスを付けることもでき、同様の結果が得られます：

CREATE INDEX ByArtist ON Songs (Artist, Title)

違いはこのインデックスが曲名を利用可能にするだけでなく、任意のアーティストの曲をソート順に利用可能にすることです。もちろんどのような方法であれ、インデックスを変更して追加のカラムを格納することは無料ではありません：インデックスが使用するスペースはそれに応じて増加します。インデックスにカラムを追加する場合、特にそのカラムに格納されるデータ量が大きくなる可能性がある場合は注意が必要です。

ノンカバーリングインデックスの使用はより高価であるため、これはインデックス選択時に気にする要素ですが、最も重要な要素ではありません。

検索空間を制限する

様々なインデックスを検討する場合、主な目的はスキャンしなければならない行データの量を最小にすることです。

例えば、1987年または1989年に発売されたWで始まるすべてのアルバムを検索したい場合、曲を主にアルバム順に並べたインデックスがあるとします：

CREATE INDEX ByAlbum ON Songs (Album, Year, Title)
EXPLAIN SELECT Title FROM Songs
    WHERE Year IN (1987, 1989) AND Album >= 'W' AND Album < 'X'

Level	Type	Description
0	scan	Songs@ByAlbum /"W"-/"X"

Wの後、Xの前に辞書的に並べられたすべての文字列という、正しい開始文字を持つアルバムに検索空間を絞り込むことができます。

しかし、曲を主に年ごとに並べ、同じ年でもアルバムごとに並べたインデックスがあるとします：

CREATE INDEX Discographies ON Songs (Year, Album, Title)

Level	Type	Description
0	scan	Songs@Discographies /1987/"W"-/1987/"X" /1989/"W"-/1989/"X"

最初の範囲は1987年に発売されたアルバムで、WとXの間で辞書的に並べられたものに対応します。このインデックスは（このクエリーにとって）好ましく、この例で両方のインデックスが利用できる場合、システムによって選択されることになります。

インデックスの順序

インデックスを選択する際のもう一つの要素は、望ましい結果の順序です。

例えば、もう一つインデックスを追加するとします：

CREATE INDEX ByYear ON Songs (Year, Title)

例えば、タイトルに特定の部分文字列を含むすべての曲を検索し、その結果をアーティスト順に並べたいとします：

EXPLAIN SELECT ID, Title FROM Songs WHERE Title LIKE '%Give You Up%'
ORDER BY Artist

Level	Type	Description
0	nosort	+Artist
1	scan	Songs@ByArtist -

または年で：

EXPLAIN SELECT ID, Title FROM Songs WHERE Title LIKE '%Give You Up%'
ORDER BY Year

Level	Type	Description
0	nosort	+Year
1	scan	Songs@ByYear -

残念ながらすべての曲を調べてタイトルをチェックする以上のことはできません。しかし、少なくとも欲しい順番で結果が得られるインデックスを選択し、（nosortノードで示されるように）再検索を避けることはできます。

概念的には簡単なように思えますが、順序を合わせるには微妙なニュアンスがあります。例えば、ByArtistインデックスはすべての結果が同じアーティストであることが分かっている場合、titleによる順序を提供するために使用することができます：

EXPLAIN SELECT ID FROM Songs WHERE Artist = 'Rick Astley'
ORDER BY Title

Level	Type	Description
0	nosort	+Title
1	scan	Songs@ByArtist /"Rick Astley"-/"Rick Astley\x00"

これはByArtistが(Artist, Title)に対するインデックスであるため、アーティスト順にエントリーを保存するだけでなく、同じアーティスト内ではタイトル順に保存されるからです。もちろん、クエリーが複数のアーティストを含む可能性がある場合は、ソートを避けることはできません：

EXPLAIN SELECT ID FROM Songs WHERE Artist >= 'R' AND Artist < 'S'
ORDER BY Title

Level	Type	Description
0	nosort	+Title
1	scan	Songs@ByArtist /"R"-/"S"

また、集計関数MINとMAXを使用する場合にも特定の順序が必要な場合があります。もし最初のアーティスト名（辞書順）を取得したい場合、ByArtistインデックスを使用すると非常に便利です：

EXPLAIN SELECT MIN(Artist) FROM Songs

Level	Type	Description
0	group	MIN(Artist)
1	scan	Songs@ByArtist 1:-

1:-は境界のない範囲-の中で最初の項目だけが必要であることを意味します。上記のように、あるアーティストの最初の曲が欲しい場合にも同じインデックスが役に立ちます：

Level	Type	Description
0	group	MIN(Title)
1	scan	Songs@ByArtist 1:/"Rick Astley"/#-/"Rick Astley\x00"

制限

このように考慮すべき要素が多いため、インデックスを選ぶ際に自明でない選択を迫られることが多いのは当然です。私たちが求めている順序を提供するインデックスがあるかもしれませんが、検索空間という点では制限が少ないかもしれませんし、カバーできないかもしれません。SELECT文のLIMIT句によって結果が変わることもあります。

最初に見たインデックスに戻ります：

CREATE INDEX ByArtist ON Songs (Artist)

このように曲のIDとアーティスト以上の情報を返す必要がある場合、このインデックスはカバーできないので、各結果を元のテーブルの行と相互参照しなければなりません。そのため、曲名が欲しい場合、このインデックスと一致する順番で欲しい場合でも、システムはそれを使用しないことを選択することになります：

EXPLAIN SELECT Title FROM Songs ORDER BY Artist

Level	Type	Description
0	sort	+Artist
1	scan	Songs@primary -

いずれにせよ、すべての曲を調べなければならないので、カバーしないインデックスを使用するよりも、自分で結果をソートした方が安上がりです。

しかし、LIMITはこの理屈を覆すことができます：もし最初の数曲だけが欲しいのであれば、テーブル全体をスキャンして行をソートし、一番上の結果以外を捨ててしまうのは非常にもったいないことです。この場合、インデックスを使用することが望ましいのですが、ノンカバーリングインデックスに関連するオーバーヘッドがあるにもかかわらず、ほんの一握りの行を調べるだけでよいからです：

EXPLAIN SELECT Title FROM Songs ORDER BY Artist LIMIT 10

Level	Type	Description
0	limit	count: 10, offset: 0
1	nosort	+Artist
2	index-join
3	scan	Songs@ByArtist -
4	scan	Songs@primary

結果をソートする必要がなくnosortノードを通過するだけなので（limitノードの指示により）求めている10個の結果を得ると、すぐに行のスキャンを停止することができます。

インデックスのヒント

インデックスアルゴリズムが最適なインデックスを正しく特定できないケースにぶつかったらどうしますか？それが稀であることを祈りますが、CockroachDBはテーブル名に@index_name、または同等の@{FORCE_INDEX=index_name}を付加して特定のインデックスを強制的に使用する方法を提供します。

以下のインデックスを例にとりクエリーを実行します：

CREATE INDEX ByArtist ON Songs (Artist)
CREATE INDEX ByTitle ON Songs (Title)
EXPLAIN SELECT Title FROM Songs
    WHERE Artist >= 'A' AND Artist < 'Z' AND Title >= 'A' AND Title < 'F'

Level	Type	Description
0	index-join
1	scan	Songs@ByArtist /"A"-/"Z"
2	scan	Songs@primary

これは両方のインデックスがうまく機能するようなクエリーです。ByTitleインデックスの方が効率的であれば、これらのステートメントのどちらかを使って強制的にそれを行うことができます：

EXPLAIN SELECT Title FROM Songs@ByTitle
    WHERE Artist >= 'A' AND Artist < 'Z' AND Title >= 'A' AND Title < 'F'
EXPLAIN SELECT Title FROM Songs@{FORCE_INDEX=ByTitle};
    WHERE Artist >= 'A' AND Artist < 'Z' AND Title >= 'A' AND Title < 'F'

Level	Type	Description
0	index-join
1	scan	Songs@ByTitle /"A"-/"F"
2	scan	Songs@primary

ノンカバーリングインデックスの使用を禁止したい場合は、@{NO_INDEX_JOIN}を使用することができます。また、@primaryを指定することで任意のインデックスを使用しないようにすることもできます：

EXPLAIN SELECT Title FROM Songs@{NO_INDEX_JOIN}
    WHERE Artist >= 'A' AND Artist < 'Z' AND Title >= 'A' AND Title < 'F'
EXPLAIN SELECT Title FROM Songs@primary
    WHERE Artist >= 'A' AND Artist < 'Z' AND Title >= 'A' AND Title < 'F'

Level	Type	Description
1	scan	Songs@primary

今後の方向性

CockroachDBは私たちが議論したすべての要素を考慮した堅実なインデックス選択の実装から始めています。しかし、私たちが行う選択はデータそのものに依存しないという意味で「静的」であり、その構造だけに依存しています。将来的にはテーブルのサイズや値の分布などさまざまな指標を追跡して、よりインテリジェントな意思決定を行う予定です。また、頻度の高いクエリについては別のプランを試してその効率を分析し、後続の同様のクエリーではそのプランに切り替える可能性があるようなフィードバック機構も検討する予定です。

分散型SQLやインデックス作成に興味がおありですか？そんなあなたに朗報です！私たちは採用活動を行っています！募集中の職種はこちらでご確認ください。