2

While I was trying to investigate performance issue with queries, I found that the source was this query. I am using Rails 4 with Mongoid gem.

Order.where("customer.email" => /\[email protected]\z/i) where [email protected] is just an example.

Customer is an embedded document in Order document and customer's email is indexed.

When I benchmarked performance using Benchmark.bmbm where Order.where("customer.email" => /\[email protected]\z/i).count was repeated 100 times, I got the following result.

       user     system      total        real
   0.090000   0.010000   0.100000 ( 27.656723)

I thought perhaps \A and \z was causing the slowness, so I tried the following where it looks for emails that start with given argument: Order.where("customer.email" => /^test/i).count

And result wasn't much different.

       user     system      total        real
   0.090000   0.010000   0.100000 ( 28.712883)

As the last resort, I tried just matching the entire string without regexp. This time, it made a huge difference: Order.where("customer.email" => "[email protected]").count

       user     system      total        real
   0.080000   0.000000   0.080000 (  0.122888)

When I looked at output of explain, it shows that using regexp scans all documents.

{
                     "cursor" => "BtreeCursor customer.email_1",
                 "isMultiKey" => false,
                          "n" => 781,
            "nscannedObjects" => 781,
                   "nscanned" => 500000,
    "nscannedObjectsAllPlans" => 781,
           "nscannedAllPlans" => 500000,
               "scanAndOrder" => false,
                  "indexOnly" => false,
                    "nYields" => 1397,
                "nChunkSkips" => 0,
                     "millis" => 406,
            "indexBounds" => {
    "customer.email" => [
        [0] [
            [0] "",
            [1] {}
        ],
        [1] [
            [0] /test/i,
            [1] /test/i
        ]
    ]
  }
}

While using entire string only scanned subset, which was what I expected.

{
                     "cursor" => "BtreeCursor customer.email_1",
                 "isMultiKey" => false,
                          "n" => 230,
            "nscannedObjects" => 230,
                   "nscanned" => 230,
    "nscannedObjectsAllPlans" => 230,
           "nscannedAllPlans" => 230,
               "scanAndOrder" => false,
                  "indexOnly" => false,
                    "nYields" => 1,
                "nChunkSkips" => 0,
                     "millis" => 0,
            "indexBounds" => {
    "customer.email" => [
        [0] [
            [0] "[email protected]",
            [1] "[email protected]"
        ]
    ]
  }
}

Can someone please explain to me why using regexp in mongodb query causes it to scan all documents instead of index?

EDIT: Added indexBounds in the explain output, which was omitted in the original post.

0

1 Answer 1

5

The quick version:

You have a case-insensitive regex here (the /i flag); that means that Mongo can't do prefix matching on the index, and thus has to scan the entire index (since it doesn't know if you want [email protected] or [email protected] or [email protected] or whatnot).

If you want case-insensitive lookups in Mongo, the correct solution is to downcase them prior to storage. If you need to not affect the user-entered input, then store it in a secondary field on the document (ie, email and email_normalized).

The longer version

Mongo's indexes are B-Trees, and when you perform a regex query, it will see a) if it can use an index (by field) and b) how much of that tree it has to scan to be assured of a result. In the case where you have a specific prefix, Mongo knows that it can limit its search to only a portion of the tree. You left out the most important part of your explains - the index bounds. Given a collection with an index and some emails:

kerrigan:PRIMARY> db.test.ensureIndex({email: 1})
kerrigan:PRIMARY> db.test.insert({email: "[email protected]"})
kerrigan:PRIMARY> db.test.insert({email: "[email protected]"})
kerrigan:PRIMARY> db.test.insert({email: "[email protected]"})
kerrigan:PRIMARY> db.test.insert({email: "[email protected]"})

If we explain the find on a non-case-insensitive match:

kerrigan:PRIMARY> db.test.find({email: /\[email protected]\z/}).explain()
{
        "cursor" : "IndexCursor email_1 multi",
        "isMultiKey" : false,
        "n" : 1,
        "nscannedObjects" : 1,
        "nscanned" : 1,
        "nscannedObjectsAllPlans" : 1,
        "nscannedAllPlans" : 1,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nChunkSkips" : 0,
        "millis" : 0,
        "indexBounds" : {
                "email" : [
                        [
                                "test@example",
                                "test@examplf"
                        ],
                        [
                                /\[email protected]\z/,
                                /\[email protected]\z/
                        ]
                ]
        },
        "server" : "luna:27019"
}

You'll see that it only has to scan one document, and that the scan upper and lower bounds are well-defined ("test@example".."test@examplf"). This is because Mongo looks at the prefix and says "That explicit prefix is guaranteed to be in every matching result", and thus knows that it can limit the portion of the index that it has to scan.

If we add the /i flag though:

kerrigan:PRIMARY> db.test.find({email: /\[email protected]\z/i}).explain()
{
        "cursor" : "IndexCursor email_1 multi",
        "isMultiKey" : false,
        "n" : 3,
        "nscannedObjects" : 3,
        "nscanned" : 4,
        "nscannedObjectsAllPlans" : 3,
        "nscannedAllPlans" : 4,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nChunkSkips" : 0,
        "millis" : 0,
        "indexBounds" : {
                "email" : [
                        [
                                "",
                                {

                                }
                        ],
                        [
                                /\[email protected]\z/i,
                                /\[email protected]\z/i
                        ]
                ]
        },
        "server" : "luna:27019"
}

Suddenly those index bounds are "".."", or a full index scan; because there's no guaranteed static prefix for the field, Mongo has to scan and check each value in the index to see if it matches your provided regex.

2
  • Thank you, Chris, for the quick answer. You are indeed right. Removing /i/ flag scanned a lot less documents. Another mystery resolved!
    – yangtheman
    Mar 25, 2015 at 19:00
  • I made original comment before the long explanation. I edited original post to include indexBounds, which match Chris' explanation.
    – yangtheman
    Mar 25, 2015 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.