title: MongoDB scans entire index when using $all and $elemMatch
body: <p>I have a collection of user documents, where each user can have an arbitrary set of properties. Each user is associated to an app document. Here is an example user:</p>
  
  <pre><code>{
      "appId": "XXXXXXX",
      "properties": [
          { "name": "age", "value": 30 },
          { "name": "gender", "value": "female" },
          { "name": "alive", "value": true }
      ]
  }
  </code></pre>
  
  <p>I would like to be able to find/count users based on the values of their properties. For example, find me all users for app X that have property Y > 10 and Z equals true.</p>
  
  <p>I have a compound, multikey index on this collection <code>db.users.ensureIndex({ "appId": 1, "properties.name": 1, "properties.value": 1})</code>. This index is working well for single condition queries, ex:</p>
  
  <pre><code>db.users.find({
      appId: 'XXXXXX',
      properties: {
          $elemMatch: {
              name: 'age',
              value: {
                  $gt: 10
              }
          }
      }
  })
  </code></pre>
  
  <p>The above query completes in &lt; 300ms with a collection of 1M users. However, when I try and add a second condition, the performance degrades considerably (7-8s), and the <code>explain()</code> output indicates that the whole index is being scanned to fulfill the query (<code>"nscanned" : 2752228</code>). </p>
  
  <p>Query</p>
  
  <pre><code>db.users.find({
      appId: 'XXXXXX',
      properties: {
          $all: [
              {
                  $elemMatch: {
                      name: 'age',
                      value: {
                          $gt: 10
                      }
                  }
              },
              {
                  $elemMatch: {
                      name: 'alive',
                      value: true
                  }
              }
          ]
      }
  })
  </code></pre>
  
  <p>Explain</p>
  
  <pre><code>{
      "cursor" : "BtreeCursor appId_1_properties.name_1_properties.value_1",
      "isMultiKey" : true,
      "n" : 256,
      "nscannedObjects" : 1000000,
      "nscanned" : 2752228,
      "nscannedObjectsAllPlans" : 1018802,
      "nscannedAllPlans" : 2771030,
      "scanAndOrder" : false,
      "indexOnly" : false,
      "nYields" : 21648,
      "nChunkSkips" : 0,
      "millis" : 7425,
      "indexBounds" : {
          "appId" : [
              [
                  "XXXXX",
                  "XXXXX"
              ]
          ],
          "properties.name" : [
              [
                  {
                      "$minElement" : 1
                  },
                  {
                      "$maxElement" : 1
                  }
              ]
          ],
          "properties.value" : [
              [
                  {
                      "$minElement" : 1
                  },
                  {
                      "$maxElement" : 1
                  }
              ]
          ]
      },
      "filterSet" : false
  }
  </code></pre>
  
  <p>I assume this is because Mongo is unable to create suitable bounds since I am looking for both boolean and integer values.</p>
  
  <p>My question is this: Is there a better way to structure my data, or modify my query to improve performance and take better advantage of my index? Is it possible to instruct mongo to treat each condition separately, generate appropriate bounds, and then perform the intersection of the results, instead of scanning all documents? Or is mongo just not suited for this type of use case?</p>