図解インデックス爆発 - 市中弾き語りの刑

Google App EngineのDatastoreにはインデックス爆発という現象があります。
こちらで公式に説明されているのですが、
http://code.google.com/intl/ja/appengine/docs/java/datastore/queriesandindexes.html#Big_Entities_and_Exploding_Indexes
自分にとってはすごく分かりにくく、理解するのにとても苦労しましたので、自分なりにメモを残しておきます。

まず2,3の前提を。

基本的な事ですが用語が統一されてなくて惑わされましたw
複合インデックス＝カスタムインデックス＝コンポジットインデックス
です。

またGoogle App Engine for Javaでは
WEB-INF/appengine-generated/datastore-indexes-auto.xml に自動的に作成されるのが、
必要とされる複合インデックスです。
一見、複雑に見えるクエリでも、ここに追記されない場合は複合インデックスが必要ないケースです。

複合インデックスが必要ない場合
Datastore API内部にて、
複数の（自動的に生成される）シングルプロパティインデックスを元に、
マージジョインという手法によりクエリ結果が求められます。

インデックス爆発とは

順を追って説明します。

シングルプロパティ(String)インデックス

これは自動的に作られるものですが、比較のために載せます。
これは説明不要ですね。

シングルプロパティ(List)インデックス

これも自動的に作られるものですが、
Listプロパティの場合、エンティティは１つ（RDBでいう１レコード）にも関わらず
List内のすべての値に対してインデックスのエントリーが用意されます。

複合インデックス

これが複合インデックスです。
一つ前の例と同じく、エンティティは１つなのに、Datastoreは
すべての組み合わせに対してインデックスのエントリーを用意する必要があります。
なぜなら、
x=aaa and y=ddd
x=bbb and y=fff
など、どんな組み合わせにのクエリにもヒットする必要があるからです。

インデックス爆発を起こすケース

上記のように１エンティティに対して複数のインデックスエントリーが生成される場合において、
そのエントリーが5000を超えた場合に「インデックス爆発」となり、
該当インデックスは使用不可となります。

具体的には例えば、Listプロパティが３つあった場合、
値のバリエーションがそれぞれ１８個あった場合、18×18×18でその複合インデックスは爆発します。
（もちろん複合インデックスを必要としなければデータの格納自体に問題はありません。）

間違いやすいケース１

（私だけかもしれませんが）勘違いしやすいケースとしてこんな場合があります。
この場合、複合インデックスであっても
１エンティティに対するインデックスのエントリーは１つなので、何の問題もありません。

間違いやすいケース２

複合インデックスが必要ない場合、Listプロパティがいくつあっても問題ありません。
この場合はマージジョインで処理されます。

ちなみに複合インデックスが必要なケースというのが意外に分かりづらいです。以下引用です。

次のような他の形式のクエリはインデックスが datastore-indexes.xml で指定されている必要があります。
・複数の並び替え順序を持つクエリ
・キーに降順の並び替え順序の指定されているクエリ
・1 つのプロパティに対して 1 つ以上の不等式フィルタを持ち、その他の~~クエリ~~プロパティに対して 1 つ以上の等式フィルタを持つクエリ
・不等式フィルタと祖先フィルタを持つクエリ

まとめ

結論としては、「複合インデックス」と「Listプロパティ」が合わさると意外に簡単に発生します。
が、上記を理解していれば、絶対に防げる現象でもあります。
後からモデルの設計を変更するのは非常に大変なため、事前によく吟味することをおすすめします。

間違っていたら突っ込みおねがいします！