title: Why is regex prefix query on indexed array slow in MongoDB?
body: <p>I am trying to perform regex query on an array of strings in MongoDB collection. I could only find this limitation in the <a href="http://docs.mongodb.org/manual/reference/operator/regex/" rel="nofollow">docs</a>:</p>
  
  <blockquote>
    <p>$regex can only use an index efficiently when the regular expression
    has an <strong>anchor for the beginning (i.e. ^) of a string</strong> and is a
    <strong>case-sensitive match</strong>.</p>
  </blockquote>
  
  <p>Let's make a test:</p>
  
  <pre><code>&gt; for (var i=0; i&lt;100000; i++) db.test.insert({f: ['a_0_'+i, 'a_1_2']})
  &gt; db.test.count()
  100000
  &gt; db.test.ensureIndex({f: 1})
  &gt; db.test.find({f: /^a_(0)?_12$/ })
  { "_id" : ObjectId("514ac59886f004fe03ef2a96"), "f" : [ "a_0_12", "a_1_2" ] }
  &gt; db.test.find({f: /^a_(0)?_12$/ }).explain()
  {
      "cursor" : "BtreeCursor f_1 multi",
      "isMultiKey" : true,
      "n" : 1,
      "nscannedObjects" : 200000,
      "nscanned" : 200000,
      "nscannedObjectsAllPlans" : 200000,
      "nscannedAllPlans" : 200000,
      "scanAndOrder" : false,
      "indexOnly" : false,
      "nYields" : 0,
      "nChunkSkips" : 0,
      "millis" : 482,
      "indexBounds" : {
          "f" : [
              [
                  "a_",
                  "a`"
              ],
              [
                  /^a_(0)?_12$/,
                  /^a_(0)?_12$/
              ]
          ]
      },
      "server" : "someserver:27017"
  }
  </code></pre>
  
  <p>The query is sloooow. On the other hand, this query is optimal: (but doesn't suit my use case)</p>
  
  <pre><code>&gt; db.test.find({f: 'a_0_12' }).explain()
  {
      "cursor" : "BtreeCursor f_1",
      "isMultiKey" : true,
      "n" : 1,
      "nscannedObjects" : 1,
      "nscanned" : 1,
      "nscannedObjectsAllPlans" : 1,
      "nscannedAllPlans" : 1,
      "scanAndOrder" : false,
      "indexOnly" : false,
      "nYields" : 0,
      "nChunkSkips" : 0,
      "millis" : 0,
      "indexBounds" : {
          "f" : [
              [
                  "a_0_12",
                  "a_0_12"
              ]
          ]
      },
      "server" : "someserver:27017"
  }
  </code></pre>
  
  <p>Why is regex query scanning all (sub)records when it has an index? What am I missing? </p>