$in MongoDB

MongoDB の $in の実装がどうなっているのかと思ってソースをちょっと覗いてみた。

---

まず、ライセンスは AGPL 3.0 らしい。

とりあえず Matcher::matches の中で処理をしているに違いない、と当たりをつけてみる。そこには normal non-regex cases があって matchesDotted が呼ばれている。多分 $in を処理するときは、この中の compareOp == BSONObj::opIN が真になって valuesMatch が呼ばれるんでしょう。そうすると op == BSONObj::opIN なんていうそれっぽい式があって、ここの if 文の中で $in を処理しているように見える。bm の型は ElementMatcher らしいので bm._myset の型である set は pch.h で include してる set っぽい。じゃあ count の時間計算量は要素数 n に対して O(log(n)) とかかなあ。知らんけど。ところで ElementMatcher には _myregex なるものが定義されていて、実際に使われているみたいだけど何かしらん。多分 $regex とかいうやつだなあ。多分 { $in: [ "foo", /bar/i ] } みたいに正規表現を混ぜられたときに使うんだろう。

上記はバージョン 2.4.1 の話ですが、このあたりのコードはどうも大幅に書き直しているらしく、master を見てみると src/mongo/db の下に matcher というディレクトリが出来ていて、$in は InMatchExpression という分かりやすい名前のクラスに収まっていた。ちなみに処理そのものは変わっていないみたい。

---

インデックスが張られていたときのことを考えていなかった。findOne を見ると NamespaceDetailsTransient::getCursor を呼んでいるようなので、そのあたりから読めば良いのかもしれない。