Discussion:
unwind vs reduce
(too old to reply)
Shiv
2017-04-15 01:37:25 UTC
Permalink
We have new $reduce operator in 3.4 and I'm finding I can replace my
existing $unwind calls with $reduce.

Just wanted to understand the impact.

1. Is $reduce a better alternative to $unwind ? If yes please explain in
terms of space and time complexity.

2. Does $unwind includes sort in its processing ?

Some references and documentation will be helpful. Appreciate the response.
Please let me know if you need specific example.
--
You received this message because you are subscribed to the Google Groups "mongodb-user"
group.

For other MongoDB technical support options, see: https://docs.mongodb.com/manual/support/
---
You received this message because you are subscribed to the Google Groups "mongodb-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mongodb-user+***@googlegroups.com.
To post to this group, send email to mongodb-***@googlegroups.com.
Visit this group at https://groups.google.com/group/mongodb-user.
To view this discussion on the web visit https://groups.google.com/d/msgid/mongodb-user/aab54313-945e-4b83-a26f-6edf82353f03%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
'Rupa Narayanan' via mongodb-user
2017-04-21 16:32:27 UTC
Permalink
Shiv,

$unwind
<https://docs.mongodb.com/manual/reference/operator/aggregation/unwind/> is
an aggregation pipeline stage, which deconstructs the output by each
element in the array and $reduce
<https://docs.mongodb.com/manual/reference/operator/aggregation/reduce/> is
an aggregation pipeline operator to combine elements in an array. $reduce
needs to be used with an aggregation pipeline stage like $project. For both
instances you would need to be cognizant of the aggregation pipeline
limitations
<https://docs.mongodb.com/manual/core/aggregation-pipeline-limits/>.

Note that $unwind deconstruct an array input and turns into individual
documents. $reduce operator is to process each element in an array through
an expression, but is not able to "expand/create" new documents. They have
quite different purpose.
It would be good to understand the structure of your document on how the
array is embedded, so could you please share the details with a sample
document and how you are using $reduce for your use case, so that I can
help provide additional guidance. Additionally, please confirm which
MongoDB version you are using with db.version(), is it 3.4?

To address your second question, $unwind doesn't include $sort, please
refer to this documentation
<https://docs.mongodb.com/manual/reference/operator/aggregation/sort/#sort-operator-and-performance>
on how to utilize $unwind and $sort together.


Regards,
Rupa
Post by Shiv
We have new $reduce operator in 3.4 and I'm finding I can replace my
existing $unwind calls with $reduce.
Just wanted to understand the impact.
1. Is $reduce a better alternative to $unwind ? If yes please explain in
terms of space and time complexity.
2. Does $unwind includes sort in its processing ?
Some references and documentation will be helpful. Appreciate the
response. Please let me know if you need specific example.
--
You received this message because you are subscribed to the Google Groups "mongodb-user"
group.

For other MongoDB technical support options, see: https://docs.mongodb.com/manual/support/
---
You received this message because you are subscribed to the Google Groups "mongodb-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mongodb-user+***@googlegroups.com.
To post to this group, send email to mongodb-***@googlegroups.com.
Visit this group at https://groups.google.com/group/mongodb-user.
To view this discussion on the web visit https://groups.google.com/d/msgid/mongodb-user/bd067af2-9acd-4fbb-8645-0ebbf8be67f5%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Shiv
2017-04-21 21:41:58 UTC
Permalink
Thank you Rupa for clean explanation. Here is stackoverflow post which I
believe demonstrates the use of $reduce and $unwind to find the min item in
a collection type.

http://stackoverflow.com/questions/43364675/mongodb-project-to-array-item-with-minimum-value-of-field/

The post has both answers. Yes my db.version() is 3.4.0.

If you could take a look at both the accepted answer and the other answers
and provide your feedback that will be really helpful.

Also, I would be interested to know the Big-0 algorithm space and time
complexity for both solutions.

Please let me know if you need more details.

Thanks again.

-Shiv
Post by Shiv
Shiv,
$unwind
<https://docs.mongodb.com/manual/reference/operator/aggregation/unwind/>
is an aggregation pipeline stage, which deconstructs the output by each
element in the array and $reduce
<https://docs.mongodb.com/manual/reference/operator/aggregation/reduce/>
is an aggregation pipeline operator to combine elements in an array.
$reduce needs to be used with an aggregation pipeline stage like $project.
For both instances you would need to be cognizant of the aggregation
pipeline limitations
<https://docs.mongodb.com/manual/core/aggregation-pipeline-limits/>.
Note that $unwind deconstruct an array input and turns into individual
documents. $reduce operator is to process each element in an array through
an expression, but is not able to "expand/create" new documents. They have
quite different purpose.
It would be good to understand the structure of your document on how the
array is embedded, so could you please share the details with a sample
document and how you are using $reduce for your use case, so that I can
help provide additional guidance. Additionally, please confirm which
MongoDB version you are using with db.version(), is it 3.4?
To address your second question, $unwind doesn't include $sort, please
refer to this documentation
<https://docs.mongodb.com/manual/reference/operator/aggregation/sort/#sort-operator-and-performance>
on how to utilize $unwind and $sort together.
Regards,
Rupa
Post by Shiv
We have new $reduce operator in 3.4 and I'm finding I can replace my
existing $unwind calls with $reduce.
Just wanted to understand the impact.
1. Is $reduce a better alternative to $unwind ? If yes please explain in
terms of space and time complexity.
2. Does $unwind includes sort in its processing ?
Some references and documentation will be helpful. Appreciate the
response. Please let me know if you need specific example.
--
You received this message because you are subscribed to the Google Groups "mongodb-user"
group.

For other MongoDB technical support options, see: https://docs.mongodb.com/manual/support/
---
You received this message because you are subscribed to the Google Groups "mongodb-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mongodb-user+***@googlegroups.com.
To post to this group, send email to mongodb-***@googlegroups.com.
Visit this group at https://groups.google.com/group/mongodb-user.
To view this discussion on the web visit https://groups.google.com/d/msgid/mongodb-user/2ec82d1a-1895-44b7-9419-1e85c2364cfb%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
'Rupa Narayanan' via mongodb-user
2017-04-25 23:41:30 UTC
Permalink
Shiv,

Thanks for sharing the example from Stackoverflow.

In the first instance using $reduce, it compares the current value in the
array with the minimum value identified (which is initially set to the
first one), as described in the comments the time complexity should O(n), n
being the size of the array and the result is stored in the variable
$$value, thereby requiring a fixed space O(1).

While using $unwind as described in the second instance, you need to
deconstruct the array elements, which would be O(n). Subsequently, need to
sort on item_field, once you unwind the array, you can't utilize any
available indexes
<https://docs.mongodb.com/manual/core/aggregation-pipeline/#pipeline-operators-and-indexes>
.
In this case, $reduce only executes per document array field items, while
$unwind would expand the number of documents to group, i.e. If you unwind
100 documents of 3 array items each, the subsequent stages (sort and group)
will end up with 300 documents to process. Thereby increasing the
complexity for $unwind to O(n+logn), O(logn) for the sort.

Additionally, sort has a couple of limitations - memory
<https://docs.mongodb.com/manual/reference/operator/aggregation/sort/#sort-and-memory-restrictions>
and performance
<https://docs.mongodb.com/manual/reference/operator/aggregation/sort/#sort-operator-and-performance>
that you need to consider, for a bigger array.

Regards,
Rupa
Post by Shiv
We have new $reduce operator in 3.4 and I'm finding I can replace my
existing $unwind calls with $reduce.
Just wanted to understand the impact.
1. Is $reduce a better alternative to $unwind ? If yes please explain in
terms of space and time complexity.
2. Does $unwind includes sort in its processing ?
Some references and documentation will be helpful. Appreciate the
response. Please let me know if you need specific example.
--
You received this message because you are subscribed to the Google Groups "mongodb-user"
group.

For other MongoDB technical support options, see: https://docs.mongodb.com/manual/support/
---
You received this message because you are subscribed to the Google Groups "mongodb-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mongodb-user+***@googlegroups.com.
To post to this group, send email to mongodb-***@googlegroups.com.
Visit this group at https://groups.google.com/group/mongodb-user.
To view this discussion on the web visit https://groups.google.com/d/msgid/mongodb-user/7bb60244-39b7-40bf-ba64-8c44b12f8e74%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Shiv
2017-04-26 14:19:45 UTC
Permalink
Thanks again Rupa for to the point explanation.

Just one last thing. Would it have matter if we were to use $unwind & $min
in the $group instead of $sort and $first ? I believe the Big-0 complexity
(O(n+logn) for $unwind, O(n) for $min usage) of this approach would be
somewhere between the first instance and second instance. I was just
wondering if there is some kind of optimization behind the schema that will
reduce it to O(n+logn) for the $unwind part and log n for the min part ?
Post by 'Rupa Narayanan' via mongodb-user
Shiv,
Thanks for sharing the example from Stackoverflow.
In the first instance using $reduce, it compares the current value in the
array with the minimum value identified (which is initially set to the
first one), as described in the comments the time complexity should O(n), n
being the size of the array and the result is stored in the variable
$$value, thereby requiring a fixed space O(1).
While using $unwind as described in the second instance, you need to
deconstruct the array elements, which would be O(n). Subsequently, need to
sort on item_field, once you unwind the array, you can't utilize any
available indexes
<https://docs.mongodb.com/manual/core/aggregation-pipeline/#pipeline-operators-and-indexes>
.
In this case, $reduce only executes per document array field items, while
$unwind would expand the number of documents to group, i.e. If you unwind
100 documents of 3 array items each, the subsequent stages (sort and group)
will end up with 300 documents to process. Thereby increasing the
complexity for $unwind to O(n+logn), O(logn) for the sort.
Additionally, sort has a couple of limitations - memory
<https://docs.mongodb.com/manual/reference/operator/aggregation/sort/#sort-and-memory-restrictions>
and performance
<https://docs.mongodb.com/manual/reference/operator/aggregation/sort/#sort-operator-and-performance>
that you need to consider, for a bigger array.
Regards,
Rupa
Post by Shiv
We have new $reduce operator in 3.4 and I'm finding I can replace my
existing $unwind calls with $reduce.
Just wanted to understand the impact.
1. Is $reduce a better alternative to $unwind ? If yes please explain in
terms of space and time complexity.
2. Does $unwind includes sort in its processing ?
Some references and documentation will be helpful. Appreciate the
response. Please let me know if you need specific example.
--
You received this message because you are subscribed to the Google Groups "mongodb-user"
group.

For other MongoDB technical support options, see: https://docs.mongodb.com/manual/support/
---
You received this message because you are subscribed to the Google Groups "mongodb-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mongodb-user+***@googlegroups.com.
To post to this group, send email to mongodb-***@googlegroups.com.
Visit this group at https://groups.google.com/group/mongodb-user.
To view this discussion on the web visit https://groups.google.com/d/msgid/mongodb-user/1619d6e2-d533-4629-b458-2dd5255fcb7d%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Shiv
2017-04-26 14:40:19 UTC
Permalink
Thanks again Rupa for to the point explanation.

Just one last thing. Would it have matter if we were to use $unwind & $min
in the $group instead of $sort and $first ? I believe the Big-0 complexity
(O(n+logn) for $unwind, O(n) for $min usage) of this approach. I was just
wondering if there is some kind of optimization behind the schema that will
reduce it to O(n+logn) for the $unwind part and log n for the min part,
same as second instance ?
Post by Shiv
We have new $reduce operator in 3.4 and I'm finding I can replace my
existing $unwind calls with $reduce.
Just wanted to understand the impact.
1. Is $reduce a better alternative to $unwind ? If yes please explain in
terms of space and time complexity.
2. Does $unwind includes sort in its processing ?
Some references and documentation will be helpful. Appreciate the
response. Please let me know if you need specific example.
--
You received this message because you are subscribed to the Google Groups "mongodb-user"
group.

For other MongoDB technical support options, see: https://docs.mongodb.com/manual/support/
---
You received this message because you are subscribed to the Google Groups "mongodb-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mongodb-user+***@googlegroups.com.
To post to this group, send email to mongodb-***@googlegroups.com.
Visit this group at https://groups.google.com/group/mongodb-user.
To view this discussion on the web visit https://groups.google.com/d/msgid/mongodb-user/bc0d22c2-80b6-43f5-9a62-e1bfac48f5ca%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
'Rupa Narayanan' via mongodb-user
2017-04-27 16:29:51 UTC
Permalink
Shiv,

$min is an option as well and $group has O(n) complexity, so you could
achieve the same result. Although the major performance impact for the
second instance with $unwind, you will be deconstructing the array, thereby
multiplying the number of documents based on the length of 'items' array.
I highly recommend that you run explain
<https://docs.mongodb.com/manual/reference/method/db.collection.aggregate/#return-information-on-aggregation-pipeline-operation> on
each of these options to understand how the aggregation pipeline processes,
each stage and that way you can pick the most efficient query based on your
use case.

Regards,
Rupa
Post by Shiv
We have new $reduce operator in 3.4 and I'm finding I can replace my
existing $unwind calls with $reduce.
Just wanted to understand the impact.
1. Is $reduce a better alternative to $unwind ? If yes please explain in
terms of space and time complexity.
2. Does $unwind includes sort in its processing ?
Some references and documentation will be helpful. Appreciate the
response. Please let me know if you need specific example.
--
You received this message because you are subscribed to the Google Groups "mongodb-user"
group.

For other MongoDB technical support options, see: https://docs.mongodb.com/manual/support/
---
You received this message because you are subscribed to the Google Groups "mongodb-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mongodb-user+***@googlegroups.com.
To post to this group, send email to mongodb-***@googlegroups.com.
Visit this group at https://groups.google.com/group/mongodb-user.
To view this discussion on the web visit https://groups.google.com/d/msgid/mongodb-user/dee3b9a0-ae28-4a1c-9c9d-c0773e788e71%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Loading...