couchdb-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Paul Davis <>
Subject Re: reduce order vs descending
Date Wed, 23 Feb 2011 21:03:35 GMT
> Right, but it seems to work without sorting in reduce if descending is
> true. Although haven't tested on larger data set.
> I would like to know if I can omit sorting entirely in this case with
> same result, that is:
> For: reduce (null, [key_range_A1_A2, key_range_B1_B2, key_range_C1_C2], true)
> Does the relation A1 < A2 < B1 < B2 < C1 < C2 hold? Does it depend on
> descending?
> For: reduce ([k1,k2,k3], [v1,v2,v3], false)
> Can I depend on k1 < k2 < k3 if descending=true?

These are specifically the assertions I'm saying you can't rely on. In
your case you will absolutely need to sort the input data.

The only assumption I think its possible to make is that re-reductions
will always process reductions from contiguous parts of the b+tree.
I'm only at the *think* stage of certainty. I haven't gone through the
implementation to check if that's an absolute truth, and I can't yet
guarantee that it won't ever change if it is true.

Just in case that doesn't make sense, imagine you have a set of
reductions that are from ordered regions of the view b+tree labeled as
such: A, B, C, D. That is to say, data in the reduction A is based
entirely of keys <= reduction keys in B <= reduction keys in C <=
reduction keys in D. Given that, the only assumption I think is
possible is that you are guaranteed that if A and C are passed
simultaneously to a re-reduce, then B is guaranteed to be passed as
well. In other words, you wont get a reduction graph that looks like
((A | C) | (B | D)) which would break this sort of approach.

View raw message