Mongodb multikey index and $all in queries
First, not sure if you have altered the question or not since posted, but contrary to one of the answers, this is not doing a full collection scan, it is using an index, as evidenced by the "cursor" : "BtreeCursor in the explain output.

As for your question - you are asking about the $all operator, but I think your issue here is that you are using the $elemMatch operator incorrectly.  When you do:

$elemMatch: {
          title: 'OS',
          value: 'Android'
        }


Or similar, you are running $elemMatch against a document, not an array, which is how it is intended.  Hence the explain shows the bounds on the index as specific values of just OS and Android on properties.title and properties.value respectively rather than what you probably wanted, which I think is to only return if all the various properties are present in the array.

Try without $elemMatch:

{
  category_id: ObjectId("50bcc2f0b910a6c1936a4424"),
  properties: {
    $all: [
      {
          title: 'OS',
          value: 'Android'
      },
      {
          title: 'Display',
          value: '4.8"'
      }
    ]
  }
}