22

I want to group all the documents according to a field but to restrict the number of documents grouped for each value.

Each message has a conversation_ID. I need to get 10 or lesser number of messages for each conversation_ID.

I am able to group according to the following command but can't figure out how to restrict the number of grouped documents apart from slicing the results Message.aggregate({'$group':{_id:'$conversation_ID',msgs:{'$push':{msgid:'$_id'}}}})

How to limit the length of msgs array for each conversation_ID to 10?

Community
  • 1
  • 1
ma08
  • 3,654
  • 3
  • 23
  • 36
  • 3
    Much curlier question than you might think. The big thing is [SERVER-6074](https://jira.mongodb.org/browse/SERVER-6074) and similar issues. The aggregation framework does not support `$slice` or have operations to "limit" the items pushed. But it is possible, just horrible. – Neil Lunn Jun 28 '14 at 08:18
  • @NeilLunn Just stubmled onto [SERVER-6074](https://jira.mongodb.org/browse/SERVER-6074) after a bit of googling. So for now manual slicing is the only option? – ma08 Jun 28 '14 at 08:37
  • Not the **only** option. As I said, big issue so it takes a bit to explain the process. It would be nice to have other operators to do this though. Vote for JIRA issues – Neil Lunn Jun 28 '14 at 10:17

5 Answers5

17

Modern

From MongoDB 3.6 there is a "novel" approach to this by using $lookup to perform a "self join" in much the same way as the original cursor processing demonstrated below.

Since in this release you can specify a "pipeline" argument to $lookup as a source for the "join", this essentially means you can use $match and $limit to gather and "limit" the entries for the array:

db.messages.aggregate([
  { "$group": { "_id": "$conversation_ID" } },
  { "$lookup": {
    "from": "messages",
    "let": { "conversation": "$_id" },
    "pipeline": [
      { "$match": { "$expr": { "$eq": [ "$conversation_ID", "$$conversation" ] } }},
      { "$limit": 10 },
      { "$project": { "_id": 1 } }
    ],
    "as": "msgs"
  }}
])

You can optionally add additional projection after the $lookup in order to make the array items simply the values rather than documents with an _id key, but the basic result is there by simply doing the above.

There is still the outstanding SERVER-9277 which actually requests a "limit to push" directly, but using $lookup in this way is a viable alternative in the interim.

NOTE: There also is $slice which was introduced after writing the original answer and mentioned by "outstanding JIRA issue" in the original content. Whilst you can get the same result with small result sets, it does involve still "pushing everything" into the array and then later limiting the final array output to the desired length.

So that's the main distinction and why it's generally not practical to $slice for large results. But of course can be alternately used in cases where it is.

There are a few more details on mongodb group values by multiple fields about either alternate usage.


Original

As stated earlier, this is not impossible but certainly a horrible problem.

Actually if your main concern is that your resulting arrays are going to be exceptionally large, then you best approach is to submit for each distinct "conversation_ID" as an individual query and then combine your results. In very MongoDB 2.6 syntax which might need some tweaking depending on what your language implementation actually is:

var results = [];
db.messages.aggregate([
    { "$group": {
        "_id": "$conversation_ID"
    }}
]).forEach(function(doc) {
    db.messages.aggregate([
        { "$match": { "conversation_ID": doc._id } },
        { "$limit": 10 },
        { "$group": {
            "_id": "$conversation_ID",
            "msgs": { "$push": "$_id" }
        }}
    ]).forEach(function(res) {
        results.push( res );
    });
});

But it all depends on whether that is what you are trying to avoid. So on to the real answer:


The first issue here is that there is no function to "limit" the number of items that are "pushed" into an array. It is certainly something we would like, but the functionality does not presently exist.

The second issue is that even when pushing all items into an array, you cannot use $slice, or any similar operator in the aggregation pipeline. So there is no present way to get just the "top 10" results from a produced array with a simple operation.

But you can actually produce a set of operations to effectively "slice" on your grouping boundaries. It is fairly involved, and for example here I will reduce the array elements "sliced" to "six" only. The main reason here is to demonstrate the process and show how to do this without being destructive with arrays that do not contain the total you want to "slice" to.

Given a sample of documents:

{ "_id" : 1, "conversation_ID" : 123 }
{ "_id" : 2, "conversation_ID" : 123 }
{ "_id" : 3, "conversation_ID" : 123 }
{ "_id" : 4, "conversation_ID" : 123 }
{ "_id" : 5, "conversation_ID" : 123 }
{ "_id" : 6, "conversation_ID" : 123 }
{ "_id" : 7, "conversation_ID" : 123 }
{ "_id" : 8, "conversation_ID" : 123 }
{ "_id" : 9, "conversation_ID" : 123 }
{ "_id" : 10, "conversation_ID" : 123 }
{ "_id" : 11, "conversation_ID" : 123 }
{ "_id" : 12, "conversation_ID" : 456 }
{ "_id" : 13, "conversation_ID" : 456 }
{ "_id" : 14, "conversation_ID" : 456 }
{ "_id" : 15, "conversation_ID" : 456 }
{ "_id" : 16, "conversation_ID" : 456 }

You can see there that when grouping by your conditions you will get one array with ten elements and another with "five". What you want to do here reduce both to the top "six" without "destroying" the array that only will match to "five" elements.

And the following query:

db.messages.aggregate([
    { "$group": {
        "_id": "$conversation_ID",
        "first": { "$first": "$_id" },
        "msgs": { "$push": "$_id" },
    }},
    { "$unwind": "$msgs" },
    { "$project": {
        "msgs": 1,
        "first": 1,
        "seen": { "$eq": [ "$first", "$msgs" ] }
    }},
    { "$sort": { "seen": 1 }},
    { "$group": {
        "_id": "$_id",
        "msgs": { 
            "$push": {
               "$cond": [ { "$not": "$seen" }, "$msgs", false ]
            }
        },
        "first": { "$first": "$first" },
        "second": { "$first": "$msgs" }
    }},
    { "$unwind": "$msgs" },
    { "$project": {
        "msgs": 1,
        "first": 1,
        "second": 1,
        "seen": { "$eq": [ "$second", "$msgs" ] }
    }},
    { "$sort": { "seen": 1 }},
    { "$group": {
        "_id": "$_id",
        "msgs": { 
            "$push": {
               "$cond": [ { "$not": "$seen" }, "$msgs", false ]
            }
        },
        "first": { "$first": "$first" },
        "second": { "$first": "$second" },
        "third": { "$first": "$msgs" }
    }},
    { "$unwind": "$msgs" },
    { "$project": {
        "msgs": 1,
        "first": 1,
        "second": 1,
        "third": 1,
        "seen": { "$eq": [ "$third", "$msgs" ] },
    }},
    { "$sort": { "seen": 1 }},
    { "$group": {
        "_id": "$_id",
        "msgs": { 
            "$push": {
               "$cond": [ { "$not": "$seen" }, "$msgs", false ]
            }
        },
        "first": { "$first": "$first" },
        "second": { "$first": "$second" },
        "third": { "$first": "$third" },
        "forth": { "$first": "$msgs" }
    }},
    { "$unwind": "$msgs" },
    { "$project": {
        "msgs": 1,
        "first": 1,
        "second": 1,
        "third": 1,
        "forth": 1,
        "seen": { "$eq": [ "$forth", "$msgs" ] }
    }},
    { "$sort": { "seen": 1 }},
    { "$group": {
        "_id": "$_id",
        "msgs": { 
            "$push": {
               "$cond": [ { "$not": "$seen" }, "$msgs", false ]
            }
        },
        "first": { "$first": "$first" },
        "second": { "$first": "$second" },
        "third": { "$first": "$third" },
        "forth": { "$first": "$forth" },
        "fifth": { "$first": "$msgs" }
    }},
    { "$unwind": "$msgs" },
    { "$project": {
        "msgs": 1,
        "first": 1,
        "second": 1,
        "third": 1,
        "forth": 1,
        "fifth": 1,
        "seen": { "$eq": [ "$fifth", "$msgs" ] }
    }},
    { "$sort": { "seen": 1 }},
    { "$group": {
        "_id": "$_id",
        "msgs": { 
            "$push": {
               "$cond": [ { "$not": "$seen" }, "$msgs", false ]
            }
        },
        "first": { "$first": "$first" },
        "second": { "$first": "$second" },
        "third": { "$first": "$third" },
        "forth": { "$first": "$forth" },
        "fifth": { "$first": "$fifth" },
        "sixth": { "$first": "$msgs" },
    }},
    { "$project": {
         "first": 1,
         "second": 1,
         "third": 1,
         "forth": 1,
         "fifth": 1,
         "sixth": 1,
         "pos": { "$const": [ 1,2,3,4,5,6 ] }
    }},
    { "$unwind": "$pos" },
    { "$group": {
        "_id": "$_id",
        "msgs": {
            "$push": {
                "$cond": [
                    { "$eq": [ "$pos", 1 ] },
                    "$first",
                    { "$cond": [
                        { "$eq": [ "$pos", 2 ] },
                        "$second",
                        { "$cond": [
                            { "$eq": [ "$pos", 3 ] },
                            "$third",
                            { "$cond": [
                                { "$eq": [ "$pos", 4 ] },
                                "$forth",
                                { "$cond": [
                                    { "$eq": [ "$pos", 5 ] },
                                    "$fifth",
                                    { "$cond": [
                                        { "$eq": [ "$pos", 6 ] },
                                        "$sixth",
                                        false
                                    ]}
                                ]}
                            ]}
                        ]}
                    ]}
                ]
            }
        }
    }},
    { "$unwind": "$msgs" },
    { "$match": { "msgs": { "$ne": false } }},
    { "$group": {
        "_id": "$_id",
        "msgs": { "$push": "$msgs" }
    }}
])

You get the top results in the array, up to six entries:

{ "_id" : 123, "msgs" : [ 1, 2, 3, 4, 5, 6 ] }
{ "_id" : 456, "msgs" : [ 12, 13, 14, 15 ] }

As you can see here, loads of fun.

After you have initially grouped you basically want to "pop" the $first value off of the stack for the array results. To make this process simplified a little, we actually do this in the initial operation. So the process becomes:

  • $unwind the array
  • Compare to the values already seen with an $eq equality match
  • $sort the results to "float" false unseen values to the top ( this still retains order )
  • $group back again and "pop" the $first unseen value as the next member on the stack. Also this uses the $cond operator to replace "seen" values in the array stack with false to help in the evaluation.

The final action with $cond is there to make sure that future iterations are not just adding the last value of the array over and over where the "slice" count is greater than the array members.

That whole process needs to be repeated for as many items as you wish to "slice". Since we already found the "first" item in the initial grouping, that means n-1 iterations for the desired slice result.

The final steps are really just an optional illustration of converting everything back into arrays for the result as finally shown. So really just conditionally pushing items or false back by their matching position and finally "filtering" out all the false values so the end arrays have "six" and "five" members respectively.

So there is not a standard operator to accommodate this, and you cannot just "limit" the push to 5 or 10 or whatever items in the array. But if you really have to do it, then this is your best approach.


You could possibly approach this with mapReduce and forsake the aggregation framework all together. The approach I would take ( within reasonable limits ) would be to effectively have an in-memory hash-map on the server and accumulate arrays to that, while using JavaScript slice to "limit" the results:

db.messages.mapReduce(
    function () {

        if ( !stash.hasOwnProperty(this.conversation_ID) ) {
            stash[this.conversation_ID] = [];
        }

        if ( stash[this.conversation_ID.length < maxLen ) {
            stash[this.conversation_ID].push( this._id );
            emit( this.conversation_ID, 1 );
        }

    },
    function(key,values) {
        return 1;   // really just want to keep the keys
    },
    { 
        "scope": { "stash": {}, "maxLen": 10 },
        "finalize": function(key,value) {
            return { "msgs": stash[key] };                
        },
        "out": { "inline": 1 }
    }
)

So that just basically builds up the "in-memory" object matching the emitted "keys" with an array never exceeding the maximum size you want to fetch from your results. Additionally this does not even bother to "emit" the item when the maximum stack is met.

The reduce part actually does nothing other than essentially just reduce to "key" and a single value. So just in case our reducer did not get called, as would be true if only 1 value existed for a key, the finalize function takes care of mapping the "stash" keys to the final output.

The effectiveness of this varies on the size of the output, and JavaScript evaluation is certainly not fast, but possibly faster than processing large arrays in a pipeline.


Vote up the JIRA issues to actually have a "slice" operator or even a "limit" on "$push" and "$addToSet", which would both be handy. Personally hoping that at least some modification can be made to the $map operator to expose the "current index" value when processing. That would effectively allow "slicing" and other operations.

Really you would want to code this up to "generate" all of the required iterations. If the answer here gets enough love and/or other time pending that I have in tuits, then I might add some code to demonstrate how to do this. It is already a reasonably long response.


Code to generate pipeline:

var key = "$conversation_ID";
var val = "$_id";
var maxLen = 10;

var stack = [];
var pipe = [];
var fproj = { "$project": { "pos": { "$const": []  } } };

for ( var x = 1; x <= maxLen; x++ ) {

    fproj["$project"][""+x] = 1;
    fproj["$project"]["pos"]["$const"].push( x );

    var rec = {
        "$cond": [ { "$eq": [ "$pos", x ] }, "$"+x ]
    };
    if ( stack.length == 0 ) {
        rec["$cond"].push( false );
    } else {
        lval = stack.pop();
        rec["$cond"].push( lval );
    }

    stack.push( rec );

    if ( x == 1) {
        pipe.push({ "$group": {
           "_id": key,
           "1": { "$first": val },
           "msgs": { "$push": val }
        }});
    } else {
        pipe.push({ "$unwind": "$msgs" });
        var proj = {
            "$project": {
                "msgs": 1
            }
        };
        
        proj["$project"]["seen"] = { "$eq": [ "$"+(x-1), "$msgs" ] };
       
        var grp = {
            "$group": {
                "_id": "$_id",
                "msgs": {
                    "$push": {
                        "$cond": [ { "$not": "$seen" }, "$msgs", false ]
                    }
                }
            }
        };

        for ( n=x; n >= 1; n-- ) {
            if ( n != x ) 
                proj["$project"][""+n] = 1;
            grp["$group"][""+n] = ( n == x ) ? { "$first": "$msgs" } : { "$first": "$"+n };
        }

        pipe.push( proj );
        pipe.push({ "$sort": { "seen": 1 } });
        pipe.push(grp);
    }
}

pipe.push(fproj);
pipe.push({ "$unwind": "$pos" });
pipe.push({
    "$group": {
        "_id": "$_id",
        "msgs": { "$push": stack[0] }
    }
});
pipe.push({ "$unwind": "$msgs" });
pipe.push({ "$match": { "msgs": { "$ne": false } }});
pipe.push({
    "$group": {
        "_id": "$_id",
        "msgs": { "$push": "$msgs" }
    }
}); 

That builds the basic iterative approach up to maxLen with the steps from $unwind to $group. Also embedded in there are details of the final projections required and the "nested" conditional statement. The last is basically the approach taken on this question:

Does MongoDB's $in clause guarantee order?

Community
  • 1
  • 1
Neil Lunn
  • 148,042
  • 36
  • 346
  • 317
  • Loads of fun indeed. Yes, my main concern was about unnecessarily obtaining large chunks of data which is a serious concern when dealing with large amounts of data. I really appreciate how you tried to explain every detail regarding this problem. I will have to go through the documentation to make sense of everything, though I understood the basic approach to solving the problem. It feels more like a hack :) to make it work while addressing the exact problem statement. I hope you add more information when you find time as I feel this is a prevalent usecase and it could help lots of mongo devs. – ma08 Jun 28 '14 at 19:09
  • I work with mongoose on nodejs. I get the feeling for bigger numbers like 10-20, a function can be written to generate the querying JSON, but it's likely to get too complex for anything bigger. – ma08 Jun 28 '14 at 19:20
  • @ma08 Absolutely true, which is the shame about running these results where you either do it individually or live with dumping out to a collection and using $slice with find. The latter not being very optimal if the arrays are getting large and possibly even breaking the BSON limit per document depending on the data. So the overall solution is workable, but with limits. What I think most would agree we really need is a "limit" option added to push. That puts a cap on how big the array results can get. I'll see if I can add some generation code here in a few hours. – Neil Lunn Jun 28 '14 at 21:14
  • @ma08 Added the code. Also put in a mapReduce approach to this a bit earlier. – Neil Lunn Jun 29 '14 at 03:49
  • Thanks for the input!!. But I feel mapReduce will almost never be used when it(the code to group the messages) will be used for sending response to client requests. Any suggestions on that?. For some reason tagging doesn't seem to work for me – ma08 Jun 29 '14 at 03:55
  • @ma08 are you talking about using `.populate()` on the results? Much the same applies to aggregate results. You just call it differently as [shown here](http://stackoverflow.com/a/24298860/2313887). It that is not clear enough by itself you can always ask another question. – Neil Lunn Jun 29 '14 at 05:01
  • I thought that mapReduce was a performance intensive operation and it is generally not used when processing client requests. Isn't it? – ma08 Jun 29 '14 at 05:23
  • @ma08 So is aggregate. The terms usually used here talk about "massive" aggregations. mapReduce runs slower than the aggregation framework due to the JavaScript interpreter invoked. But not that much slower. You really need to do your own testing rather than just believe everything you read. Testing is what proves results. – Neil Lunn Jun 29 '14 at 05:35
  • @NeilLunn this is definitely better than other alternatives, _(barring ditching mongodb entirely)_, I wrote a small module that puts together an aggregate query and allows you to set a few parameters. I think it's fine for most simpleish use cases. https://github.com/bevacqua/limited – bevacqua Jan 09 '15 at 20:39
4

Starting Mongo 4.4, the $group stage has a new aggregation operator $accumulator allowing custom accumulations of documents as they get grouped, via javascript user defined functions.

Thus, in order to only select n messages (for instance 2) for each conversation:

// { "conversationId" : 3, "messageId" : 14 }
// { "conversationId" : 5, "messageId" : 34 }
// { "conversationId" : 3, "messageId" : 39 }
// { "conversationId" : 3, "messageId" : 47 }
db.collection.aggregate([
  { $group: {
    _id: "$conversationId",
    messages: {
      $accumulator: {
        accumulateArgs: ["$messageId"],
        init: function() { return [] },
        accumulate:
          function(messages, message) { return messages.concat(message).slice(0, 2); },
        merge:
          function(messages1, messages2) { return messages1.concat(messages2).slice(0, 2); },
        lang: "js"
      }
    }
  }}
])
// { "_id" : 5, "messages" : [ 34 ] }
// { "_id" : 3, "messages" : [ 14, 39 ] }

The accumulator:

  • accumulates on the field messageId (accumulateArgs)
  • is initialised to an empty array (init)
  • accumulates messageId items in an array and only keeps a maximum of 2 (accumulate and merge)
Xavier Guihot
  • 54,987
  • 21
  • 291
  • 190
4

Starting in Mongo 5.2, it's a perfect use case for the new $topN aggregation accumulator:

// { "conversationId" : 3, "messageId" : 14 }
// { "conversationId" : 5, "messageId" : 34 }
// { "conversationId" : 3, "messageId" : 39 }
// { "conversationId" : 3, "messageId" : 47 }
db.collection.aggregate([
  { $group: {
    _id: "$conversationId",
    messages: { $topN: { n: 2, output: "$messageId", sortBy: { _id: 1 } } }
  }}
])
// { "_id" : 5, "messages" : [ 34 ] }
// { "_id" : 3, "messages" : [ 14, 39 ] }

This applies a $topN group accumulation that:

  • takes for each group the top 2 (n: 2) elements
  • and for each grouped record extracts the field value (output: "$messageId")
  • the choice of the "top 2" is defined by sortBy: { _id: 1 } (that I chose to be _id since you didn't specify an order).
Xavier Guihot
  • 54,987
  • 21
  • 291
  • 190
0

The $slice operator is not an aggregation operator so you can't do this (like I suggested in this answer, before the edit):

db.messages.aggregate([
   { $group : {_id:'$conversation_ID',msgs: { $push: { msgid:'$_id' }}}},
   { $project : { _id : 1, msgs : { $slice : 10 }}}]);

Neil's answer is very detailed, but you can use a slightly different approach (if it fits your use case). You can aggregate your results and output them to a new collection:

db.messages.aggregate([
   { $group : {_id:'$conversation_ID',msgs: { $push: { msgid:'$_id' }}}},
   { $out : "msgs_agg" }
]);

The $out operator will write the results of the aggregation to a new collection. You can then use a regular find query project your results with the $slice operator:

db.msgs_agg.find({}, { msgs : { $slice : 10 }});

For this test documents:

> db.messages.find().pretty();
{ "_id" : 1, "conversation_ID" : 123 }
{ "_id" : 2, "conversation_ID" : 123 }
{ "_id" : 3, "conversation_ID" : 123 }
{ "_id" : 4, "conversation_ID" : 123 }
{ "_id" : 5, "conversation_ID" : 123 }
{ "_id" : 7, "conversation_ID" : 1234 }
{ "_id" : 8, "conversation_ID" : 1234 }
{ "_id" : 9, "conversation_ID" : 1234 }

The result will be:

> db.msgs_agg.find({}, { msgs : { $slice : 10 }});
{ "_id" : 1234, "msgs" : [ { "msgid" : 7 }, { "msgid" : 8 }, { "msgid" : 9 } ] }
{ "_id" : 123, "msgs" : [ { "msgid" : 1 }, { "msgid" : 2 }, { "msgid" : 3 }, 
                          { "msgid" : 4 }, { "msgid" : 5 } ] }

Edit

I assume this would mean duplicating the whole messages collection. Isn't that overkill?

Well, obviously this approach won't scale with huge collections. But, since you're considering using large aggregation pipelines or large map-reduce jobs you probably won't use this for "real-time" requests.

There are many cons of this approach: 16 MB BSON limit if you're creating huge documents with aggregation, wasting disk space / memory with duplication, increased disk IO...

The pros of this approach: its simple to implement and thus easy to change. If your collection is rarely updated you can use this "out" collection like a cache. This way you wouldn't have to perform the aggregation operation multiple times and you could then even support "real-time" client requests on the "out" collection. To refresh your data, you can periodically do aggregation (e.g. in a background job that runs nightly).

Like it was said in the comments this isn't an easy problem and there isn't a perfect solution for this (yet!). I showed you another approach you can use, it's up to you to benchmark and decide what's most appropriate for your use case.

Christian P
  • 12,032
  • 6
  • 60
  • 71
  • { [MongoError: exception: invalid operator '$slice'] name: 'MongoError', errmsg: 'exception: invalid operator \'$slice\'', code: 15999, ok: 0 } I am using mongoose for nodejs. $slice doesn't seem to work with aggregation. And I want to limit mongoDB to stop grouping after a particular limit has reached, instead of slicing the results. Is there a way to do that? thanks – ma08 Jun 28 '14 at 08:29
  • I assume this would mean duplicating the whole messages collection. Isn't that overkill? – ma08 Jun 29 '14 at 03:50
  • @ma08 depends what your requirements are. See my edit. – Christian P Jun 29 '14 at 06:48
-1

I hope this will work as you wanted:

db.messages.aggregate([
   { $group : {_id:'$conversation_ID',msgs: { $push: { msgid:'$_id' }}}},
   { $project : { _id : 1, msgs : { $slice : ["$msgid",0,10] }}}
]);
Eric Aya
  • 69,473
  • 35
  • 181
  • 253