Check if every element in array matches condition

Question

I have a collection of documents:

date: Date
users: [
  { user: 1, group: 1 }
  { user: 5, group: 2 }
]

date: Date
users: [
  { user: 1, group: 1 }
  { user: 3, group: 2 }
]

I would like to query against this collection to find all documents where every user id in my array of users is in another array, [1, 5, 7]. In this example, only the first document matches.

The best solution I've been able to find is to do:

$where: function() { 
  var ids = [1, 5, 7];
  return this.users.every(function(u) { 
    return ids.indexOf(u.user) !== -1;
  });
}

Unfortunately, this seems to hurt performance is stated in the $where docs:

$where evaluates JavaScript and cannot take advantage of indexes.

How can I improve this query?

Answer 1

The query you want is this:

db.collection.find({"users":{"$not":{"$elemMatch":{"user":{$nin:[1,5,7]}}}}})

This says find me all documents that don't have elements that are outside of the list 1,5,7.

Answer 2

I don't know about better, but there are a few different ways to approach this, and depending on the version of MongoDB you have available.

Not too sure if this is your intention or not, but the query as shown will match the first document example because as your logic is implemented you are matching the elements within that document's array that must be contained within the sample array.

So if you actually wanted the document to contain all of those elements, then the $all operator would be the obvious choice:

db.collection.find({ "users.user": { "$all": [ 1, 5, 7 ] } })

But working with the presumption that your logic is actually intended, at least as per suggestion you can "filter" those results by combining with the $in operator so that there are less documents subject to your $where** condition in evaluated JavaScript:

db.collection.find({
    "users.user": { "$in": [ 1, 5, 7 ] },
    "$where": function() { 
        var ids = [1, 5, 7];
        return this.users.every(function(u) { 
            return ids.indexOf(u.user) !== -1;
        });
    }
})

And you get an index though the actual scanned will be multiplied by the number of elements in the arrays from the matched documents, but still better than without the additional filter.

Or even possibly you consider the logical abstraction of the $and operator used in combination with $or and possibly the $size operator depending on your actual array conditions:

db.collection.find({
    "$or": [
        { "users.user": { "$all": [ 1, 5, 7 ] } },
        { "users.user": { "$all": [ 1, 5 ] } },
        { "users.user": { "$all": [ 1, 7 ] } },
        { "users": { "$size": 1 }, "users.user": 1 },
        { "users": { "$size": 1 }, "users.user": 5 },
        { "users": { "$size": 1 }, "users.user": 7 }
    ]
})

So this is a generations of all of the possible permutations of your matching condition, but again performance will likely vary depending on your available installed version.

NOTE: Actually a complete fail in this case as this does something entirely different and in fact results in a logical $in

---

Alternates are with the aggregation framework, your mileage may vary on which is most efficient due to the number of documents in your collection, one approach with MongoDB 2.6 and upwards:

db.problem.aggregate([
    // Match documents that "could" meet the conditions
    { "$match": { 
        "users.user": { "$in": [ 1, 5, 7 ] } 
    }},

    // Keep your original document and a copy of the array
    { "$project": {
        "_id": {
            "_id": "$_id",
            "date": "$date",
            "users": "$users"
        },
        "users": 1,
    }},

    // Unwind the array copy
    { "$unwind": "$users" },

    // Just keeping the "user" element value
    { "$group": {
        "_id": "$_id",
        "users": { "$push": "$users.user" }
    }},

    // Compare to see if all elements are a member of the desired match
    { "$project": {
        "match": { "$setEquals": [
            { "$setIntersection": [ "$users", [ 1, 5, 7 ] ] },
            "$users"
        ]}
    }},

    // Filter out any documents that did not match
    { "$match": { "match": true } },

    // Return the original document form
    { "$project": {
        "_id": "$_id._id",
        "date": "$_id.date",
        "users": "$_id.users"
    }}
])

So that approach uses some newly introduced set operators in order to compare the contents, though of course you need to restructure the array in order to make the comparison.

As pointed out, there is a direct operator to do this in $setIsSubset which does the equivalent of the combined operators above in a single operator:

db.collection.aggregate([
    { "$match": { 
        "users.user": { "$in": [ 1,5,7 ] } 
    }},
    { "$project": {
        "_id": {
            "_id": "$_id",
            "date": "$date",
            "users": "$users"
        },
        "users": 1,
    }},
    { "$unwind": "$users" },
    { "$group": {
        "_id": "$_id",
        "users": { "$push": "$users.user" }
    }},
    { "$project": {
        "match": { "$setIsSubset": [ "$users", [ 1, 5, 7 ] ] }
    }},
    { "$match": { "match": true } },
    { "$project": {
        "_id": "$_id._id",
        "date": "$_id.date",
        "users": "$_id.users"
    }}
])

Or with a different approach while still taking advantage of the $size operator from MongoDB 2.6:

db.collection.aggregate([
    // Match documents that "could" meet the conditions
    { "$match": { 
        "users.user": { "$in": [ 1, 5, 7 ] } 
    }},

    // Keep your original document and a copy of the array
    // and a note of it's current size
    { "$project": {
        "_id": {
            "_id": "$_id",
            "date": "$date",
            "users": "$users"
        },
        "users": 1,
        "size": { "$size": "$users" }
    }},

    // Unwind the array copy
    { "$unwind": "$users" },

    // Filter array contents that do not match
    { "$match": { 
        "users.user": { "$in": [ 1, 5, 7 ] } 
    }},

    // Count the array elements that did match
    { "$group": {
        "_id": "$_id",
        "size": { "$first": "$size" },
        "count": { "$sum": 1 }
    }},

    // Compare the original size to the matched count
    { "$project": { 
        "match": { "$eq": [ "$size", "$count" ] } 
    }},

    // Filter out documents that were not the same
    { "$match": { "match": true } },

    // Return the original document form
    { "$project": {
        "_id": "$_id._id",
        "date": "$_id.date",
        "users": "$_id.users"
    }}
])

Which of course can still be done, though a little more long winded in versions prior to 2.6:

db.collection.aggregate([
    // Match documents that "could" meet the conditions
    { "$match": { 
        "users.user": { "$in": [ 1, 5, 7 ] } 
    }},

    // Keep your original document and a copy of the array
    { "$project": {
        "_id": {
            "_id": "$_id",
            "date": "$date",
            "users": "$users"
        },
        "users": 1,
    }},

    // Unwind the array copy
    { "$unwind": "$users" },

    // Group it back to get it's original size
    { "$group": { 
        "_id": "$_id",
        "users": { "$push": "$users" },
        "size": { "$sum": 1 }
    }},

    // Unwind the array copy again
    { "$unwind": "$users" },

    // Filter array contents that do not match
    { "$match": { 
        "users.user": { "$in": [ 1, 5, 7 ] } 
    }},

    // Count the array elements that did match
    { "$group": {
        "_id": "$_id",
        "size": { "$first": "$size" },
        "count": { "$sum": 1 }
    }},

    // Compare the original size to the matched count
    { "$project": { 
        "match": { "$eq": [ "$size", "$count" ] } 
    }},

    // Filter out documents that were not the same
    { "$match": { "match": true } },

    // Return the original document form
    { "$project": {
        "_id": "$_id._id",
        "date": "$_id.date",
        "users": "$_id.users"
    }}
])

That generally rounds out the different ways, try them out and see what works best for you. In all likelihood the simple combination of $in with your existing form is probably going to be the best one. But in all cases, make sure you have an index that can be selected:

db.collection.ensureIndex({ "users.user": 1 })

Which is going to give you the best performance as long as you are accessing that in some way, as all the examples here do.

---

Verdict

I was intrigued by this so ultimately contrived a test case in order to see what had the best performance. So first some test data generation:

var batch = [];
for ( var n = 1; n <= 10000; n++ ) {
    var elements = Math.floor(Math.random(10)*10)+1;

    var obj = { date: new Date(), users: [] };
    for ( var x = 0; x < elements; x++ ) {
        var user = Math.floor(Math.random(10)*10)+1,
            group = Math.floor(Math.random(10)*10)+1;

        obj.users.push({ user: user, group: group });
    }

    batch.push( obj );

    if ( n % 500 == 0 ) {
        db.problem.insert( batch );
        batch = [];
    }

} 

With 10000 documents in a collection with random arrays from 1..10 in length holding random values of 1..0, I came to a match count of 430 documents (reduced from 7749 from the $in match ) with the following results (avg):

• JavaScript with $in clause: 420ms
• Aggregate with $size : 395ms
• Aggregate with group array count : 650ms
• Aggregate with two set operators : 275ms
• Aggregate with $setIsSubset : 250ms

Noting that over the samples done all but the last two had a peak variance of approximately 100ms faster, and the last two both exhibited 220ms response. The largest variations were in the JavaScript query which also exhibited results 100ms slower.

But the point here is relative to hardware, which on my laptop under a VM is not particularly great, but gives an idea.

So the aggregate, and specifically the MongoDB 2.6.1 version with set operators clearly wins on performance with the additional slight gain coming from $setIsSubset as a single operator.

This is particularly interesting given (as indicated by the 2.4 compatible method) the largest cost in this process will be the $unwind statement ( over 100ms avg ), so with the $in selection having a mean around 32ms the rest of the pipeline stages execute in less than 100ms on average. So that gives a relative idea of aggregation versus JavaScript performance.

Answer 3

I just spent a substantial portion of my day trying to implement Asya's solution above with object-comparisons rather than strict equality. So I figured I'd share it here.

Let's say you expanded your question from userIds to full users. You want to find all documents where every item in its users array is present in another users array: [{user: 1, group: 3}, {user: 2, group: 5},...]

This won't work: db.collection.find({"users":{"$not":{"$elemMatch":{"$nin":[{user: 1, group: 3},{user: 2, group: 5},...]}}}}}) because $nin only works for strict equality. So we need to find a different way of expressing "Not in array" for arrays of objects. And using $where would slow down the query too much.

Solution:

db.collection.find({
 "users": {
   "$not": {
     "$elemMatch": {
       // if all of the OR-blocks are true, element is not in array
       "$and": [{
         // each OR-block == true if element != that user
         "$or": [
           "user": { "ne": 1 },
           "group": { "ne": 3 }
         ]
       }, {
         "$or": [
           "user": { "ne": 2 },
           "group": { "ne": 5 }
         ]
       }, {
         // more users...
       }]
     }
   }
 }
})

To round out the logic: $elemMatch matches all documents that have a user not in the array. So $not will match all documents that have all of the users in the array.