MongoDB : how to index the keys of a Map

What about structuring your document like this:

{
"_id" : ObjectId("4fb538eb5e9e7b17b211d5d3"),
    "someProps" : {
        "PROCESSED":["4fda4993eb14ea4a4a149c04","4f56a5c4b6f621f092b00525"],
        "TODO" : ["4f56a5c4b6f621f092b00526"],
        "CANCELLED" : [ ]
    }
}

The three advantages of this are:

1. You can see if some object is processed by flipping your query from "someProps.4fda4993eb14ea4a4a149c04","PROCESSED" to "someProps.PROCESSED", "4fda4993eb14ea4a4a149c04"

2. you can create an index on "someProps.TODO" and another one on "someProps.PROCESSED" (you can't create a compound index on several parallel arrays but it sounds like you'd be querying by a single status, right?

3. you can atomically move a document from one state to another, like this:

.

db.collection.update({"someProps.PROCESSED": "4fda4993eb14ea4a4a149c04"},
                     {$pull:{"someProps.PROCESSED":"4fda4993eb14ea4a4a149c04"},
                      $push:{"someProps.CANCELLED":"4fda4993eb14ea4a4a149c04"}});

If you want to keep your properties embedded, you could also use the dynamic attributes pattern as proposed by Kyle Banke in "MongoDB in Action". So instead of putting the props in their own collection, you modify your mydocs collection to look like this:

{
  "_id" : ObjectId("4fb538eb5e9e7b17b211d5d3"),
  "someProps" : [
      { k: "4fda4993eb14ea4a4a149c04", v: "PROCESSED" },
      { k: "4f56a5c4b6f621f092b00525", v: "PROCESSED" },
      { k: "4fd95a2a0baaefd1837fe504", v : "TODO" }
  ]
}

And then index on the embedded document keys:

db.mydoc.ensureIndex({'someProps.k' :1}, {'someProps.v' :1})

This is very close to what Sergio suggested, but your data will still be one document in a single collection.