MongoDBの複合インデックスにおけるESRの法則について

はじめに

自社のサーバーでMongoDBを使用しています。
クエリの高速化にindexを用いるのは常套手段ですが、何も考えずに貼ったIndexが適用されない事がありました。
今回はその原因となったESRの法則について調べたことを簡単にまとめました。

ESR(Equality,Sort,Range)の法則

ESRの法則はMongoDBの公式ドキュメントで紹介されています。
１言でまとめると

indexは、Equal(一致)、Sort(並び替え)、Range(絞り込み) の順番に貼ったほうがいいよ

と言っています。
例えば、以下のqueryがあったとします。

query_cars

 db.cars.find({ manufacturer: 'Ford', cost: { $gt: 10000 } }).sort({ model: 1 })

何も考えないとmanufacturer, cost, modelの順にindexを貼ってしまいますが、ESRの法則に従うと

index_cars

 db.cars.createIndex({ manufacturer: 1, model: 1, cost: 1 })

の順番でIndexを貼ることでqueryが適切に高速化するとのことです。
(公式ドキュメント)https://www.mongodb.com/docs/v4.2/tutorial/equality-sort-range-rule/

考察

なぜこの順番でIndexを貼ると高速なのか考察してみました。
(以下は個人的な考察なので間違っている可能性があります)
MongoDBの複合Index(Compound Index)はツリー構造をとっています。
最初に等式条件に一致しない不適当な枝を除くことで高速化されるのは直観的に明らかです。
問題はその次に、絞り込みと並び替えのどちらを先に行うかです。
まず等式条件に一致するDocument数を$k$とします。
並び替えを行うパラメータの配列サイズを$s_s$(上の例ではmodelの種類の数)、絞り込みを行うパラメータの配列サイズを$s_r$(上の例ではcostの種類の数)とします。
最終的にqueryに一致するDocument数を $d$とします。
$k,s,d$は $k\geqq s,d$を満たす範囲で任意の正の数をとります。
($k$はindexを考える程度には大きい数とします)

①Sort(並び替え)、Range(絞り込み)の順の場合
indexを貼っているということはRAM内にキャッシュとしてリストをsortされた状態で持っているので、
並び替えの計算時間は $O(1)$です。
その後、絞り込みは $s_s$回、sortされた平均サイズ $k/s_s$のリストで行います。
ここのMongoDB内部の処理ロジックがよくわかっていないのですが、
絞り込みの計算時間は $s_s\approx 1$のときは$O(\log k)$, $s_s \approx k$のときは$O(k)$と推定されます。

②Range(絞り込み)、Sort(並び替え)の順の場合
絞り込みはすでにsortされたサイズ $s_r$のリストから行うので計算時間は$O(\log s_r)$です。
その後、並び替えでsortされていないリストをsortする計算時間は$O(d\log d)$です。

つまり,計算時間$T(k,s,d)$は
①Sort(並び替え)、Range(絞り込み)の順の場合

T(k,s,d) =\left\{
\begin{array}{ll}
O(\log k) & (s_s\approx 1) \\
O(k) & (s_s\approx k)
\end{array}
\right.

②Range(絞り込み)、Sort(並び替え)の順の場合

T(k,s,d)=\left\{
\begin{array}{ll}
O(d\log d) &(s_r \approx d)\\
O(\log s_r) &(\log s_r \gg d\log d)
\end{array}
\right.

queryにもよりますが、$d$、$s$は$k$までの値を取りえます。
$d \approx k$のときの $O(d\log d)$が一番計算量が大きくなることがわかります。
これがESRの法則です。ただし、ESRの法則が当て嵌まらないケースもありそうです。
例えば、dがkに依存せず、小さな値しか取らないケースです。
UserDBでユーザーのリストを取得するqueryで特定の1ヶ月に登録しているユーザーへの絞り込みを行う場合が具体例の一つとして挙げられます。
これはソートを行うパラメータの配列サイズ$s_s$が大きいときにより起こりやすくなることも上の結果から予想されます。

検証

ESRの法則は簡単に確かめることができるので、今回はESRの法則の例外の検証をします。
MongoDB AtlasのsampleDataを用います。"sample_training"の"grades"DBを用いました。
(MongoDB Atlas sampleData)https://www.mongodb.com/docs/atlas/sample-data/sample-training/#std-label-sample-training
documentは以下の構造を持っています。

document

{
  "_id":{"$oid":"56d5f7eb604eb380b0d8d8ce"},
  "student_id":{"$numberDouble":"0.0"},
  "scores":[
     {"type":"exam","score":{"$numberDouble":"78.40446309504266"}},
     {"type":"quiz","score":{"$numberDouble":"73.36224783231339"}},
     {"type":"homework","score":{"$numberDouble":"46.980982486720535"}},
     {"type":"homework","score":{"$numberDouble":"76.67556138656222"}}
  ],
  "class_id":{"$numberDouble":"339.0"}
}

scoresの配列に入っているtypeは常にこの順番で全ドキュメントに含まれています。
scoreは0から100までのランダムな実数、class_idは0から500までのランダムな整数を取ります。
Equal(一致)条件に{"scores.0.type":"exam"}を用います。
(全ドキュメントがヒットするので、本来は必要がないですが、Indexのprefixを効かせないために検証では不可欠です。)
Sort(並び替え)条件に{"scores.1.score":1}、絞り込み条件に{"scores.2.score":{＄lt:0.001}}を用いましょう。
(2件ヒットします)

①Sort(並び替え)、Range(絞り込み)の順でIndexを貼った場合

index and query

db.getCollection("grades").createIndex({ scores.0.type: 1, scores.1.score: 1, scores.2.score: 1})
db.getCollection("grades").find({"scores.0.type":"exam","scores.2.score":{$lt:0.001}}).sort({"scores.1.score":1}).explain("executionStats")

結果

{ 
    //省略
    "executionStats" : {
        "executionSuccess" : true, 
        "nReturned" : 2.0, 
        "executionTimeMillis" : 210.0, 
        "totalKeysExamined" : 100000.0, 
        "totalDocsExamined" : 2.0, 
    //省略
}

indexを貼っているとは思えないほど遅いですね。

②Range(絞り込み)、Sort(並び替え)の順でIndexを貼った場合

index and query

db.getCollection("grades").createIndex({ scores.0.type: 1, scores.2.score: 1, scores.1.score: 1})
db.getCollection("grades").find({"scores.0.type":"exam","scores.2.score":{$lt:0.001}}).sort({"scores.1.score":1}).explain("executionStats")

結果

{ 
   //省略
   "executionStats" : {
        "executionSuccess" : true, 
        "nReturned" : 2.0, 
        "executionTimeMillis" : 1.0, 
        "totalKeysExamined" : 2.0, 
        "totalDocsExamined" : 2.0, 
   //省略
}

ちゃんとindexが効いています。ESRの法則に例外があることが確かめられました。
省略しますが、Range(絞り込み)条件をゆるくしていくとこのqueryは劇的に遅くなります。
つまり、ESRの法則が成り立つようになります。(①のqueryの速度は変わらないため、遅いのに変わりはないですが。)
最後にsortパラメータの配列サイズ$s_s$の依存性も確かめます。
Sort(並び替え)条件を{"scores.1.score":1}から{"class_id":1}に変更しましょう。(indexも貼り直します)

①' Sort(並び替え)、Range(絞り込み)の順でIndexを貼った場合(sortパラメータの配列サイズを縮小)

index and query

db.getCollection("grades").createIndex({ scores.0.type: 1, class_id: 1, scores.2.score: 1})
db.getCollection("grades").find({"scores.0.type":"exam","scores.2.score":{$lt:0.001}}).sort({"class_id":1}).explain("executionStats")

結果

{ 
    //省略
    "executionStats" : {
        "executionSuccess" : true, 
        "nReturned" : 2.0, 
        "executionTimeMillis" : 2.0, 
        "totalKeysExamined" : 503.0, 
        "totalDocsExamined" : 2.0, 
    //省略
}

totalKeysExaminedが劇的に減った結果、速度も速くなっています。
sortパラメータの配列サイズ$s_s$の依存性もあることが確かめられました。

結論

ESRの法則は基本的には成り立つが、queryの構造によっては遅くなることもある。
依存するパラメータとして返却するDocument数とsortパラメータの配列サイズ$s_s$が挙げられる。