Datastoreによるクエリの実装

クエリ＝インデックス＋スキャン

• すべてのクエリは「インデックス＋スキャン」に変換される
  • Bigtableはクエリをサポートしていない。GAEのアプリが実行するすべてのクエリは、インデックスとスキャンの組み合わせに変換される
• Datastoreのインデックスとは
  • エンティティテーブルとは別に作成されるBigtableのテーブル
  • クエリを記述すると自動的に作成される。明示的な作成も可能
  • 3種類のインデックス
    • カインドインデックス
    • シングルプロパティインデックス
    • コンポジットインデックス

カインドインデックス

• 「エンティティのカインド（Kind＝クラスのこと）の名前」をキーとするインデックス
  • あるクラスのすべてのエンティティの一覧を提供
  • 例：Grandparentでカインドインデックスをスキャン

SELECT * FROM Grandparent

＜カインドインデックス：引用元＞

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

• 「エンティティの特定のプロパティ値」をキーとするインデックス
• ひとつのプロパティを検索条件またはソート条件とするクエリに使用
  • 例：name = 'John'
  • 例：ORDER BY name
• 昇順用と降順用の2つが作成される（後者は必要に応じて作成？）
• 例：nameプロパティの範囲指定＋nameプロパティでソート
  • nameプロパティのインデックスでrangeスキャン

WHERE name >= 'B' AND name < 'C' ORDER BY name

＜シングルプロパティインデックス：引用元＞

コンポジットインデックス

• 「エンティティの複数のプロパティ値の組み合わせ」をキーとするインデックス
• index.yamlで明示的に指定して作成

- kind: Parent
  properties: 
  - name: lastname 
  - name: firstname

• 例：lastnameプロパティのeq指定＋firstnameプロパティの範囲指定
  • インデックスで「Parent/Smith/B」から「Parent/Smith/C」までrangeスキャン

＜コンポジットインデックス：引用元＞

• コンポジットインデックスは使うべきか？
  • すべてのプロパティ値の順列組み合わせでインデックス内容が作成されるので、インデックスサイズが膨大になりやすい

マージジョイン

• マージジョイン（merge join）とは
  • Datastoreでは、コンポジットインデックスに頼らずに複数プロパティの条件検索を実現するために、マージジョインを実装している
  • シングルプロパティインデックスの検索結果をマージする
  • "zig-zag"アルゴリズムにより、個々のインデックスを並行してスキャンする

＜zig-zagアルゴリズムによるマージジョイン：引用元＞