I noticed this behavior when searching for slow queries: Queries using an empty $nin modifier take a lot more time to finish than queries not including the empty notifier:

lennart ~$ mongo
MongoDB shell version: 1.6.3
connecting to: test
> use graylog2
switched to db graylog2
> db.messages.count();
185998
> db.messages.find({deleted:false, message:{$nin:[]}}).explain();
{
"cursor" : "BtreeCursor deleted_1",
"nscanned" : 185131,
"nscannedObjects" : 185131,
"n" : 185131,
"millis" : 560,
"indexBounds" :

{ "deleted" : [ [ false, false ] ] }

}

> db.messages.find(

{deleted:false}

).explain();
{
"cursor" : "BtreeCursor deleted_1",
"nscanned" : 185131,
"nscannedObjects" : 185131,
"n" : 185131,
"millis" : 158,
"indexBounds" :

{ "deleted" : [ [ false, false ] ] }

}

This is a 400ms difference for 185998 documents in the collection. I noticed this in a collection with ~4,000,000 documents (on a not that fast machine) and got a difference of 20 seconds. "message" always has a String as value.

Let me know if you need any more information.