You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@couchdb.apache.org by Brian Candler <B....@pobox.com> on 2009/04/25 23:39:12 UTC
Reduce limitations
Has anyone found a clear definition of the limitations of reduce functions,
in terms of how large the reduced data may be?
I am considering using a reduce function for a low-ordinality value, to be
able to determine quickly what the unique values are, and how many of each.
That is, the final reduced value would be a small object of the form
{"foo"=>50000, "bar"=>20000, "baz"=>30000}
(in this example there are 100,000 documents but only three unique values).
As I understand it, the final reduced object sits in the root node, so what
would be the practical limit on the size of this object? That in turn limits
the number of distinct values I can have.
I imagine this would be more efficient than a grouped reduce query (which
would have to re-reduce each key range separately), although I'm not sure by
how much.
Regards,
Brian.
// implementation idea (completely untested)
function(keys, values, rereduce) {
if (rereduce) {
result = values.shift();
for(var i in values) {
for(var j in values[i]) {
result[j] = (result[j] || 0) + values[i][j];
}
}
}
else {
result = {};
for(var i in keys) {
var key = keys[i];
result[key] = (result[key] || 0) + 1;
}
}
}
Re: Reduce limitations
Posted by Zachary Zolton <za...@gmail.com>.
I think it's worth putting in writing (perhaps on the wiki?) that
reduces functions are useful for *computations* over your data—not
trying to emulate SQL-style joins!
This was a hard lesson for me. I found I had to change my code
considerably to do more of that work on the client side, due to the
performance implications I found in a production environment.
Doing group=true queries of reduce views causes considerable work, as
all the work in the reduce steps must be repeated each time. Keep your
view code simple, especially if you're on EC2 small instances!
Cheers,
Zach
On Tue, Jun 2, 2009 at 4:04 AM, Brian Candler <B....@pobox.com> wrote:
> On Thu, May 28, 2009 at 12:54:16PM -0700, Chris Anderson wrote:
>> The deal is that if your reduce function's output is the same size as
>> its input, the final reduce value will end up being as large as all
>> the map rows put together.
>>
>> If your reduce function's output is 1/2 the size of it's input, you'll
>> also end up with quite a large amount of data in the final reduce. In
>> these cases each reduction stage actually accumulates more data, as it
>> is based on ever increasing numbers of map rows.
>>
>> If the function reduces data fast enough, the intermediate reduction
>> values will stay relatively constant, even as each reduce stage
>> reflects logarithmically more map rows. This is the kind of reduce
>> function you want.
>
> So actually, the requirement is that the final (root) result of the reduce
> process should be of a moderate size, and so should all the intermediate
> reduce values which comprise it. That makes sense.
>
> Depending on the type of reduce function you use, the "growth" may or may
> not be related to the number of documents which have been reduced together
> to form the reduce value.
>
> For example: an object which returns a map of {tag: count}, where the number
> of unique tags is bounded, may return a fairly large object when reduced
> across a small number of docs, but the final root reduce is no larger. So
> all you need to do is keep the number of tags into a 'reasonable' range
> (e.g. tens rather than thousands)
>
> Regards,
>
> Brian.
>
Re: Reduce limitations
Posted by Brian Candler <B....@pobox.com>.
On Thu, May 28, 2009 at 12:54:16PM -0700, Chris Anderson wrote:
> The deal is that if your reduce function's output is the same size as
> its input, the final reduce value will end up being as large as all
> the map rows put together.
>
> If your reduce function's output is 1/2 the size of it's input, you'll
> also end up with quite a large amount of data in the final reduce. In
> these cases each reduction stage actually accumulates more data, as it
> is based on ever increasing numbers of map rows.
>
> If the function reduces data fast enough, the intermediate reduction
> values will stay relatively constant, even as each reduce stage
> reflects logarithmically more map rows. This is the kind of reduce
> function you want.
So actually, the requirement is that the final (root) result of the reduce
process should be of a moderate size, and so should all the intermediate
reduce values which comprise it. That makes sense.
Depending on the type of reduce function you use, the "growth" may or may
not be related to the number of documents which have been reduced together
to form the reduce value.
For example: an object which returns a map of {tag: count}, where the number
of unique tags is bounded, may return a fairly large object when reduced
across a small number of docs, but the final root reduce is no larger. So
all you need to do is keep the number of tags into a 'reasonable' range
(e.g. tens rather than thousands)
Regards,
Brian.
Re: Reduce limitations
Posted by Chris Anderson <jc...@apache.org>.
On Thu, May 28, 2009 at 12:37 PM, Brian Candler <B....@pobox.com> wrote:
> On Tue, May 26, 2009 at 12:21:10PM +0100, Michael Stillwell wrote:
>> On Sat, Apr 25, 2009 at 10:39 PM, Brian Candler <B....@pobox.com> wrote:
>> > Has anyone found a clear definition of the limitations of reduce functions,
>> > in terms of how large the reduced data may be?
>>
>> In http://mail-archives.apache.org/mod_mbox/couchdb-user/200808.mbox/%3cEC4EAF59-78BA-4238-9827-B3561E3DC183@apache.org%3e,
>> Damian says:
>>
>> "the size of the reduce value can be logarithmic with respect to the rows"
>
> Which doesn't give any guidance as to the absolute maximum size of the
> reduce value, only how big it can get in relation to the number of rows,
> e.g.
>
> max_reduce_object_size = k . ln(number of rows reduced)
>
> for some unknown k. Or is it ln(total size of rows reduced)?
>
The deal is that if your reduce function's output is the same size as
its input, the final reduce value will end up being as large as all
the map rows put together.
If your reduce function's output is 1/2 the size of it's input, you'll
also end up with quite a large amount of data in the final reduce. In
these cases each reduction stage actually accumulates more data, as it
is based on ever increasing numbers of map rows.
If the function reduces data fast enough, the intermediate reduction
values will stay relatively constant, even as each reduce stage
reflects logarithmically more map rows. This is the kind of reduce
function you want.
Theoretically, there are no hard limits, and theoretically, even the
first kind of function (identity on values, which leads to logarithmic
growth of intermediate values) could eventually complete even on a
large data set.
Practically, the first limit you'll hit is that all the input values
for the function will not fit in the JavaScript interpreter's memory
space. Even if that were not an issue, the function computation time
will likely go up logarithmically; similarly there will be slowdowns
in index processing as the reduction values are stored in the btree
inner-nodes. Shuffling around multi-gigabyte inner nodes is not
optimal and should be avoided.
I hope that's clear, let me know if I can make it clearer.
Chris
--
Chris Anderson
http://jchrisa.net
http://couch.io
Re: Reduce limitations
Posted by Brian Candler <B....@pobox.com>.
On Tue, May 26, 2009 at 12:21:10PM +0100, Michael Stillwell wrote:
> On Sat, Apr 25, 2009 at 10:39 PM, Brian Candler <B....@pobox.com> wrote:
> > Has anyone found a clear definition of the limitations of reduce functions,
> > in terms of how large the reduced data may be?
>
> In http://mail-archives.apache.org/mod_mbox/couchdb-user/200808.mbox/%3cEC4EAF59-78BA-4238-9827-B3561E3DC183@apache.org%3e,
> Damian says:
>
> "the size of the reduce value can be logarithmic with respect to the rows"
Which doesn't give any guidance as to the absolute maximum size of the
reduce value, only how big it can get in relation to the number of rows,
e.g.
max_reduce_object_size = k . ln(number of rows reduced)
for some unknown k. Or is it ln(total size of rows reduced)?
Re: Reduce limitations
Posted by Jan Lehnardt <ja...@apache.org>.
On 26 May 2009, at 13:21, Michael Stillwell wrote:
> On Sat, Apr 25, 2009 at 10:39 PM, Brian Candler
> <B....@pobox.com> wrote:
>> Has anyone found a clear definition of the limitations of reduce
>> functions,
>> in terms of how large the reduced data may be?
>
> In http://mail-archives.apache.org/mod_mbox/couchdb-user/200808.mbox/%3cEC4EAF59-78BA-4238-9827-B3561E3DC183@apache.org%3e
> ,
> Damian says:
>
> "the size of the reduce value can be logarithmic with respect to the
> rows"
The wiki says the same.
Cheers
Jan
--
Re: Reduce limitations
Posted by Michael Stillwell <mj...@beebo.org>.
On Sat, Apr 25, 2009 at 10:39 PM, Brian Candler <B....@pobox.com> wrote:
> Has anyone found a clear definition of the limitations of reduce functions,
> in terms of how large the reduced data may be?
In http://mail-archives.apache.org/mod_mbox/couchdb-user/200808.mbox/%3cEC4EAF59-78BA-4238-9827-B3561E3DC183@apache.org%3e,
Damian says:
"the size of the reduce value can be logarithmic with respect to the rows"
--M.
--
http://beebo.org
Re: Reduce limitations
Posted by Paul Davis <pa...@gmail.com>.
On Sat, Apr 25, 2009 at 5:39 PM, Brian Candler <B....@pobox.com> wrote:
> Has anyone found a clear definition of the limitations of reduce functions,
> in terms of how large the reduced data may be?
>
There is no real hard limit. There's nothing at the moment that
prevents you from returning a huge amount of data, its just that
performance will suffer fairly dramatically. Chris Anderson was
working on a patch at #couchhack to throw errors if the value grows
too large, but that would allow for people to turn it off so that it
only acts as a heads up for the unsuspecting.
> I am considering using a reduce function for a low-ordinality value, to be
> able to determine quickly what the unique values are, and how many of each.
> That is, the final reduced value would be a small object of the form
> {"foo"=>50000, "bar"=>20000, "baz"=>30000}
>
> (in this example there are 100,000 documents but only three unique values).
>
This particular example would be more than fine. The issue is that you
need to bound the number of unique values. As in, if you ended up
having 10K unique values you'd notice the performance degradation.
> As I understand it, the final reduced object sits in the root node, so what
> would be the practical limit on the size of this object? That in turn limits
> the number of distinct values I can have.
>
It do and there is none and it do. :D 3 keys is fine, 10 of this
nature would be fine. 1 million is probably not fine.
> I imagine this would be more efficient than a grouped reduce query (which
> would have to re-reduce each key range separately), although I'm not sure by
> how much.
>
With only a few keys, I'm not entirely certain. I would put money on
"noticeably" but I'm wouldn't upgrade that to "drastically" without
testing.
> Regards,
>
> Brian.
>
> // implementation idea (completely untested)
>
> function(keys, values, rereduce) {
> if (rereduce) {
> result = values.shift();
> for(var i in values) {
> for(var j in values[i]) {
> result[j] = (result[j] || 0) + values[i][j];
> }
> }
> }
> else {
> result = {};
> for(var i in keys) {
> var key = keys[i];
> result[key] = (result[key] || 0) + 1;
> }
> }
> }
>
>
Notice that this is quite similar to the "top N tags" example on the
wiki. There's actually a bit of a bug in that example that came up
when me and Damien had a white boarding exercise at #couchhack that I
need to fix, but the theory is fairly sound. The basic idea is that I
was only keeping the last key in the reduce stage when you really need
to keep both the first and last keys. It should be fairly
straightforward to add but I just haven't gotten around to it yet.
HTH,
Paul Davis
Re: Reduce limitations
Posted by Brian Candler <B....@pobox.com>.
On Sat, Apr 25, 2009 at 10:39:12PM +0100, Brian Candler wrote:
> I am considering using a reduce function for a low-ordinality value
Of course I meant low cardinality.
FWIW, here's a working implementation:
function(ks, vs, co) {
if (co) {
var result = vs.shift();
for (var i in vs) {
for (var j in vs[i]) {
result[j] = (result[j] || 0) + vs[i][j];
}
}
return result;
} else {
var result = {};
for (var i in ks) {
var key = ks[i];
result[key[0]] = (result[key[0]] || 0) + 1;
}
return result;
}
}
Regards,
Brian.