概要

MongoDBのインデックスをつける上で

複合インデックスの時はインデックスの順番に気をつける
{a: 1, b: 1}の反対{a: -1, b: -1}は使えるけど{a: 1, b: -1}は使えない

などいろいろ気をつける点が多く、一度しっかり学んでみましたのでそのメモ。
基本的にクエリをexplain()してどうなったか実験した結果をまとめてます。

環境

Ubuntu 14.04
MongoDB 2.6.8

インデックスでのポイント

explain()した時の結果を見る上でポイントとなる点を以下にまとめます。

explain()した時のサンプル

> db.restaurants.find({pref_id: 1}).explain()
{
    "cursor" : "BtreeCursor pref_id_1",
    "isMultiKey" : false,
    "n" : 9165,
    "nscannedObjects" : 9165,
    "nscanned" : 9165,
    "nscannedObjectsAllPlans" : 9165,
    "nscannedAllPlans" : 9165,
    "scanAndOrder" : false,
    "indexOnly" : false,
    "nYields" : 71,
    "nChunkSkips" : 0,
    "millis" : 10,
    "indexBounds" : {
        "pref_id" : [
            [
                1,
                1
            ]
        ]
    },
    "server" : "vagrant-ubuntu-trusty-64:27017",
    "filterSet" : false
}

以下ポイントです。

名称	説明	例
cursor	インデックスを使用しているかどうか。 `BasicCursor`はフルスキャンで遅い。 `BtreeCursor`はB-treeを使ってるので速い。	"cursor" : "BtreeCursor pref_id_1"
n	ヒットした件数	"n" : 9165
nscanned	検索するときに走査した件数。`n`より大きすぎると無駄が多い走査と言える。	"nscanned" : 9165
scanAndOrder	ソートするときにインデックスの並びを使っているか、それとも取得後並べなおしているか。注意として `false`なら使っていて高速。 `true`なら使っておらず並べなおしていて遅い。	"scanAndOrder" : false

explain()したときに主に上記を見ると適切なインデックスをつけられます。

複合インデックス（Compound Indexes）

以下の複合インデックスをつけたとします。

ensureIndex({a: 1, b: 1, c: 1})

以下のクエリを叩いた時の表です。

クエリ	インデックスを使用	備考
find({a: xxx})	o
find({a: xxx, b: yyy})	o
find({a: xxx, b: yyy, c: zzz})	o
find({b: yyy})	x
find({c: zzz})	x
find({b: yyy, c: zzz})	x
find({a: xxx, c: zzz})	o	※１

上記の法則を予想すると、複合インデックスをつけた場合、前方に一致したインデックスなら機能してくれることがわかります。
公式ドキュメントではPrefixesと呼びます。

B-treeと複合インデックス

Prefixesについて

さて、どうして上記のようなPrefixesが使えるかですが、インデックスにB-treeを使っていることを考えれば理解しやすいです。先ほどのインデックスだと以下のように構築されます（簡単のため子ノード等省略）。 f:id:quoll00:20150303032220j:plain

このようにa->b->cの順にインデックスが作成されます。したがって

find({a: xxx})やfind({a: xxx, b: yyy})などは上からたどっていけるのでインデックスを使えますが、
find({b: yyy})やfind({b: yyy, c: zzz})などは途中からになるのでインデックスを利用できないというわけです。

※１はどうしてインデックスを使える？

先ほどの説明だとfind({a: xxx, c: zzz})は途中のbが抜けているからできないのでは？と思うかもしれません。
公式ドキュメントでも基本的にはダメと書いていますが、実際に動かしてみると以下のようになってます。

> db.test.find({a: 1, c: 1}).explain()
{
    "cursor" : "BtreeCursor a_1_b_1_c_1",
    "isMultiKey" : false,
    "n" : 3,
    "nscannedObjects" : 3,
    "nscanned" : 25,
    "nscannedObjectsAllPlans" : 29,
    "nscannedAllPlans" : 51,
    "scanAndOrder" : false,
    "indexOnly" : false,
    "nYields" : 0,
    "nChunkSkips" : 0,
    "millis" : 1,
    "indexBounds" : {
        "a" : [
            [
                1,
                1
            ]
        ],
        "b" : [
            [
                {
                    "$minElement" : 1
                },
                {
                    "$maxElement" : 1
                }
            ]
        ],
        "c" : [
            [
                1,
                1
            ]
        ]
    },
    "server" : "vagrant-ubuntu-trusty-64:27017",
    "filterSet" : false
}

つまりこっそりbは最小〜最大の全部というクエリが挟まっています。
これにより仮想的に{a: xxx, b: yyy, c: zzz}という並びを実現してるみたいです。

インデックスとソート

次はソートと組み合わせた場合の検証です。以下のインデックスをつけたとします。

ensureIndex({a: 1, b: 1, c: 1, d: 1})

explainの結果です。

クエリ	インデックスを使用	scanAndOrder	備考
find({a: xxx}).sort({b: 1})	o	false
find({a: xxx}).sort({b: -1})	o	false	※０
find({a: xxx, b: yyy}).sort({c: 1})	o	false
find({a: xxx, b: yyy, c: zzz}).sort({d: 1})	o	false
find({a: xxx, b: { $gt: yyy}}).sort({b: 1})	o	false
find({a: xxx}).sort({b: 1, c: 1})	o	false
find({a: xxx}).sort({b: -1, c: -1})	o	false
find({a: xxx}).sort({b: 1, c: -1})	o	true	※１
find({a: xxx}).sort({b: -1, c: 1})	o	true	※１
find({a: xxx}).sort({c: 1, d: 1})	o	true	※１
find({a: xxx, b: { $gt: yyy}}).sort({c: 1})	o	true	※２
find({a: xxx}).sort({c: 1})	o	true	※２
find({a: xxx, c: zzz}).sort({b: 1})	o	false	※３

sortAndOrder: trueって？

ポイントはインデックスしたものを再度メモリ上で並び替える必要があるかどうかということです。
※１や※２の場合、

※１：インデックス構築時の並び順{b: 1, c: 1}と違うため、インデックスの順番が使えない
※２：該当する項目が複数あり（中間ノードが複数あるせい）、インデックスの順番が使えない（重複があったり、大小関係が保証されてない）

といったことが原因で

f:id:quoll00:20150303033748j:plain

上図のようにヒットしたドキュメントをメモリ上で並び替える必要があります。
※２で言うとc=2とかc=4とかかぶっちゃいますし、右のc=3は左のc=4より小さいので順番が保証されないですよね。
なのでsortAndOrder: trueになります。

※０はなんでOK？

aで検索して、bの降順に並べるからインデックスは{a: 1, b: -1}と考えるかもしれませんが、ツリーの並びを考えると

ヒットするaを探す
bで逆ソート。ただしインデックス時にソート済なので反対から読むだけ。

といった感じでreverseが使えるので{a: 1, b: 1}でも問題ないことがわかります。

sort({a: 1, b: -1})をしたいならインデックスも{a: 1, b; -1}とすべき
find({a: xxx}).sort({b: -1})をしたいならインデックスは{a: 1, b; 1}でも{a: 1, b; -1}でも変わらない

ということです。

※３はなんでOK？

一見ダメそうな※３も図と比べると理解できるのですが、

ヒットするaを探す
ソートするbはaをルートとしてすでにインデックス作成時にソート済み。なので並び替え不要
cを探す

という流れであるためsortAndOrder: falseになります。

まとめ

MySQLのインデックスでもそうですが、B-treeを使っていることを意識するとどうしてこのインデックスは使えて、こっちは使えないのかといったことがわかると思います。

Carpe Diem

備忘録

MongoDBのインデックス

概要

環境