中年engineerの独り言 - crumbjp

LinuxとApacheの憂鬱

Index intersection を試してみた。（失敗談）

mongodb

MongoDB 2.6 からIndex intersectionという機能が追加された。
１つのクエリーで２つのインデックスを使う（かもしれない）機能で、より効率的にクエリーを処理できる。
（どう効率的なのか？はこのへんが詳しい）

さて、じゃあ実際に見てみようというのが今回の趣旨。

元データ

国土地理院が公開している住所情報が手元にあったのでこれを使うことにした。
大体1000万件/4GB弱のデータ。

> db.block_master.stats().count
11700898
> db.block_master.stats().size
3713899792
> db.block_master.findOne()
{
        "_id" : ObjectId("52b8378dab3de2fd4abb193f"),
        "full" : "北海道 札幌市中央区 南七条西十一丁目 １２８１",
        "pref" : ObjectId("52b8378dab3de2fd4abb193c"),
        "pref_name" : "北海道",
        "city" : ObjectId("52b8378dab3de2fd4abb193d"),
        "city_name" : "札幌市中央区",
        "town" : ObjectId("52b8378dab3de2fd4abb193e"),
        "town_name" : "南七条西十一丁目",
        "name" : "１２８１",
        "loc" : {
                "type" : "Point",
                "coordinates" : [
                        141.342094,
                        43.050264
                ]
        }
}

Indexを張る

db.block_master.ensureIndex({pref_name:1});
db.block_master.ensureIndex({city_name:1});
db.block_master.ensureIndex({town_name:1});

今までは、複合インデックスを張っておかないと大変だったのだがさてどうなるか。。。

ちょっとデータを確認

Index intersection はそれぞれのインデックスで絞り込んだ結果の共通部分を抜き出すので、投げるクエリーを検討する。

  1. 幾つかの県にある同名の市区町村
  2. 幾つかの市区町村にある同名の町丁

が狙い目だ。

> db.block_master.aggregate([
  { $group: {_id: {city: "$city_name", pref: "$pref_name"}}},
  { $group: {_id: "$_id.city", num: {$sum: 1}, prefs: {$push: "$_id.pref"}}},
  { $match: {num: {$gt:1}}},
  { $sort:  {num: -1}}
 ])
{ "_id" : "伊達市", "num" : 2, "prefs" : [ "福島県", "北海道" ] }
{ "_id" : "府中市", "num" : 2, "prefs" : [ "東京都", "広島県" ] }

へー意外と少ない！

> db.block_master.aggregate([
  { $group: {_id: {town: "$town_name", city: "$city_name"}}},
  { $group: {_id: "$_id.town", num: {$sum: 1}}},
  { $match: {num: {$gt:1}}},
  { $sort:  {num: -1}}
 ])
{ "_id" : "本町", "num" : 144 }
{ "_id" : "本町二丁目", "num" : 141 }
{ "_id" : "本町一丁目", "num" : 140 }
{ "_id" : "栄町", "num" : 133 }
{ "_id" : "本町三丁目", "num" : 114 }
{ "_id" : "新町", "num" : 106 }
{ "_id" : "幸町", "num" : 97 }
{ "_id" : "中央二丁目", "num" : 93 }
{ "_id" : "中央一丁目", "num" : 92 }
{ "_id" : "本町四丁目", "num" : 84 }
{ "_id" : "東町", "num" : 84 }
{ "_id" : "末広町", "num" : 79 }
{ "_id" : "旭町", "num" : 77 }
{ "_id" : "栄町二丁目", "num" : 75 }
{ "_id" : "中央三丁目", "num" : 74 }
{ "_id" : "栄町一丁目", "num" : 73 }
{ "_id" : "緑町", "num" : 72 }
{ "_id" : "南町", "num" : 69 }
{ "_id" : "泉町", "num" : 65 }
{ "_id" : "中町", "num" : 63 }
Type "it" for more
>

おお！流石の『本町』！
意外な『栄町』！？
『新町』だと思ったのになぁ。。。
じゃなかった。。まあ兎に角この辺が狙い目。。

あと余談だけどaggregationがcursorで帰って来るようになったのも2.4から。
それまでは単に配列で帰ってくるわ、64MB超えるとコケるわ。。ダメダメだった。
このaggregationも13970程帰って来たから、市区町村名までArrayに含めたらコケたでしょうね。

さてintersectionに戻ろう。。

チャレンジ１

クエリー
> db.block_master.find({city_name:'府中市', pref_name:'東京都'}).count()
5219
explain(true)
> var explain = db.block_master.find({city_name:'府中市', pref_name:'東京都'}).explain(true)
> explain.indexBounds
{ "city_name" : [ [ "府中市", "府中市" ] ] }
> explain.allPlans
[
        {
                "cursor" : "BtreeCursor city_name_1",
                "isMultiKey" : false,
                "n" : 5219,
                "nscannedObjects" : 13272,
                "nscanned" : 13272,
                "scanAndOrder" : false,
                "indexOnly" : false,
                "nChunkSkips" : 0,
                "indexBounds" : {
                        "city_name" : [
                                [
                                        "府中市",
                                        "府中市"
                                ]
                        ]
                }
        },
        {
                "cursor" : "BtreeCursor pref_name_1",
                "isMultiKey" : false,
                "n" : 0,
                "nscannedObjects" : 101,
                "nscanned" : 102,
                "scanAndOrder" : false,
                "indexOnly" : false,
                "nChunkSkips" : 0,
                "indexBounds" : {
                        "pref_name" : [
                                [
                                        "東京都",
                                        "東京都"
                                ]
                        ]
                }
        },
        {
                "cursor" : "Complex Plan",
                "n" : 0,
                "nscannedObjects" : 0,
                "nscanned" : 103,
                "nChunkSkips" : 0
        }
]
> explain.stats
{
        "type" : "KEEP_MUTATIONS",
        "works" : 13273,
        "yields" : 104,
        "unyields" : 104,
        "invalidates" : 0,
        "advanced" : 5219,
        "needTime" : 8053,
        "needFetch" : 0,
        "isEOF" : 1,
        "children" : [
                {
                        "type" : "FETCH",
                        "works" : 13273,
                        "yields" : 104,
                        "unyields" : 104,
                        "invalidates" : 0,
                        "advanced" : 5219,
                        "needTime" : 8053,
                        "needFetch" : 0,
                        "isEOF" : 1,
                        "alreadyHasObj" : 0,
                        "forcedFetches" : 0,
                        "matchTested" : 5219,
                        "children" : [
                                {
                                        "type" : "IXSCAN",
                                        "works" : 13272,
                                        "yields" : 104,
                                        "unyields" : 104,
                                        "invalidates" : 0,
                                        "advanced" : 13272,
                                        "needTime" : 0,
                                        "needFetch" : 0,
                                        "isEOF" : 1,
                                        "keyPattern" : "{ city_name: 1.0 }",
                                        "boundsVerbose" : "field #0['city_name']: [\"府中市\", \"府中市\"]",
                                        "isMultiKey" : 0,
                                        "yieldMovedCursor" : 0,
                                        "dupsTested" : 0,
                                        "dupsDropped" : 0,
                                        "seenInvalidated" : 0,
                                        "matchTested" : 0,
                                        "keysExamined" : 13272,
                                        "children" : [ ]
                                }
                        ]
                }
        ]
}
あれ！？

効かない。。
13272件舐めて5219件抽出した。
IXSCANで13272件舐めてFETCHで13273件って事は普通にcity_nameだけ使ったな。
city_name: '東京都'が22万件ほどあって全然絞れないから、
普通に処理することを選択したっぽい。

チャレンジ２

クエリー

期待の『本町』だ。

クエリー
> db.block_master.find({city_name: '松戸市', town_name: '本町'}).count()
25
データ数
> db.block_master.find({city_name: '松戸市'}).count()
30661
> db.block_master.find({town_name: '本町'}).count()
6563

良い感じのバランスである。

explain(true)
> db.block_master.find({city_name: '松戸市', town_name: '本町'}).explain(true).indexBounds
{ "town_name" : [ [ "本町", "本町" ] ] }
> db.block_master.find({city_name: '松戸市', town_name: '本町'}).explain(true).allPlans
[
        {
                "cursor" : "BtreeCursor town_name_1",
                "isMultiKey" : false,
                "n" : 25,
                "nscannedObjects" : 6563,
                "nscanned" : 6563,
                "scanAndOrder" : false,
                "indexOnly" : false,
                "nChunkSkips" : 0,
                "indexBounds" : {
                        "town_name" : [
                                [
                                        "本町",
                                        "本町"
                                ]
                        ]
                }
        },
        {
                "cursor" : "BtreeCursor city_name_1",
                "isMultiKey" : false,
                "n" : 15,
                "nscannedObjects" : 6564,
                "nscanned" : 6565,
                "scanAndOrder" : false,
                "indexOnly" : false,
                "nChunkSkips" : 0,
                "indexBounds" : {
                        "city_name" : [
                                [
                                        "松戸市",
                                        "松戸市"
                                ]
                        ]
                }
        },
        {
                "cursor" : "Complex Plan",
                "n" : 15,
                "nscannedObjects" : 0,
                "nscanned" : 6566,
                "nChunkSkips" : 0
        }
]
> db.block_master.find({city_name: '松戸市', town_name: '本町'}).explain(true).stats
{
        "type" : "KEEP_MUTATIONS",
        "works" : 6565,
        "yields" : 153,
        "unyields" : 153,
        "invalidates" : 0,
        "advanced" : 25,
        "needTime" : 6538,
        "needFetch" : 0,
        "isEOF" : 1,
        "children" : [
                {
                        "type" : "FETCH",
                        "works" : 6564,
                        "yields" : 153,
                        "unyields" : 153,
                        "invalidates" : 0,
                        "advanced" : 25,
                        "needTime" : 6538,
                        "needFetch" : 0,
                        "isEOF" : 1,
                        "alreadyHasObj" : 0,
                        "forcedFetches" : 0,
                        "matchTested" : 25,
                        "children" : [
                                {
                                        "type" : "IXSCAN",
                                        "works" : 6563,
                                        "yields" : 153,
                                        "unyields" : 153,
                                        "invalidates" : 0,
                                        "advanced" : 6563,
                                        "needTime" : 0,
                                        "needFetch" : 0,
                                        "isEOF" : 1,
                                        "keyPattern" : "{ town_name: 1.0 }",
                                        "boundsVerbose" : "field #0['town_name']: [\"本町\", \"本町\"]",
                                        "isMultiKey" : 0,
                                        "yieldMovedCursor" : 0,
                                        "dupsTested" : 0,
                                        "dupsDropped" : 0,
                                        "seenInvalidated" : 0,
                                        "matchTested" : 0,
                                        "keysExamined" : 6563,
                                        "children" : [ ]
                                }
                        ]
                }
        ]
}
またしても効かぬ。。。

これは理由が解らないな。。
『本町』は144もの市区町村に存在しており25/6563まで絞れるのにComplex Planが選択されなかった。

因みにallPlans の'松戸市'のnscanned が30661ではなく6564なのはこのバグである。

まとめ

Index intersectionの気持ちは解りませんでした。。

、、かといって今は精進（source code reading）してる暇は無いんだよなぁ。。。