You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@couchdb.apache.org by Glenn Rempe <gl...@rempe.us> on 2009/09/28 07:41:38 UTC
Help with complex key range query and map/reduce
Hello, I am hoping the group can provide some guidance on building a
map/reduce summary for a set of documents that I have retrieved with a
complex key range query.
In summary, I want to query a range of docs by a complex key
consisting of an [id, year, month, day, engine]. It is common for me
to need to query over a range of dates with something along the lines
of this (CouchRest Ruby code):
sd = SearchDocument.by_ad_domain_histogram(:startkey => [3, 2009,
9, 1, "g"], :endkey => [3, 2009, 9, 28, "g"], :include_docs =>
false, :reduce => true)
In this example, I want all SearchDocuments that are for category '3'
between 9/1/2009 and 9/28/2009, and for engine 'g'.
Now, this is working well and returning a range of docs. So the
tricky part (at least for me as a CouchDB n00b) is that each of these
docs also has an 'ad_domain' value. And what I want is to generate a
simple histogram which groups all of these range of docs by the
ad_domains found. So I want to get back at the end of the day is
something like:
{'foo.com' => 12, 'bar.com' => 32, 'baz.com' => 14}
This is what I am stuck on as I have not wrapped my head around map/
reduce in CouchDB quite yet. I think this would be easier if I
emitted the ad_domain at the end of the complex key if ALL of the
parts of the key that I was querying on were the same. But since I am
querying on a range of keys I end up with a reduce spitting out
multiple entries for 'foo.com' since that domain was found across
several days (unique complex keys) of results.
Is it possible to do what I want?
Here is a work in progress map/reduce, which doesn't do what I want
yet. Help in modifying it would be much appreciated (and tips for
doing what I am already doing, only better!):
view_by :ad_domain_histogram,
:map =>
'function(doc) {
if( (doc["couchrest-type"] == "SearchDocument") &&
doc.category_id && doc.searched_at && doc.engine) {
var domain;
if(doc.ad_domain == null){
domain="NONE";
}else{
domain=doc.ad_domain;
}
emit([doc.category_id,
new Date(Date.parse(doc.searched_at)).getFullYear(),
new Date(Date.parse(doc.searched_at)).getMonth() + 1,
new Date(Date.parse(doc.searched_at)).getDate(),
doc.engine],
domain);
}
}',
:reduce =>
"function(keys, values, rereduce) {
return sum(values);
}"
Thanks very much in advance,
Glenn
Re: Help with complex key range query and map/reduce
Posted by Glenn Rempe <gl...@rempe.us>.
So if I flipped it around as suggested to emit key/values of:
[cat, engine, year, month, day], {"val1":one, "val2":two}
# query a specific cat, a SPECIFIC engine, a RANGE of dates
startkey = [1, "g", 2009, 9, 1]
endkey = [1, "g", 2009, 9, 28]
# query a specific cat, a RANGE of engines, a RANGE of dates
startkey = [1, "a", 2009, 9, 1]
endkey = [1, "z", 2009, 9, 28]
# query a specific cat, a RANGE of engines, a RANGE of dates that cross a
year boundary
startkey = [1, "a", 2008, 12, 1]
endkey = [1, "z", 2009, 1, 30]
Will that do the trick? Thanks all for helping me catch (and grok) the
error of my ways. :-)
Cheers,
Glenn
On Mon, Sep 28, 2009 at 2:00 PM, Ning Tan <ni...@gmail.com> wrote:
> On Mon, Sep 28, 2009 at 4:51 PM, Glenn Rempe <gl...@rempe.us> wrote:
> >
> > startkey = [1, 2009, 9, 1, "g"]
> > endkey = [1, 2009, 9, 28, "g"]
> >
> > Would it not return category 1, across the entire date range, but limited
> to
> > those with the engine 'g' only?
>
> No. CouchDB keys are not filters. They occupy a linear space, and as
> long as a key is "larger" than (or equal to) the startkey and
> "smaller" than (or equal to) the endkey, the corresponding row is
> included in query results. In the above case, [1, 2009, 9, 1, "h"]
> will be included in your query result. There is a Wiki page on view
> collation that explains this.
>
--
Glenn Rempe
email : glenn@rempe.us
voice : (415) 894-5366 or (415)-89G-LENN
twitter : @grempe
contact info : http://www.rempe.us/contact.html
pgp : http://www.rempe.us/gnupg.txt
Re: Help with complex key range query and map/reduce
Posted by Ning Tan <ni...@gmail.com>.
On Mon, Sep 28, 2009 at 4:51 PM, Glenn Rempe <gl...@rempe.us> wrote:
>
> startkey = [1, 2009, 9, 1, "g"]
> endkey = [1, 2009, 9, 28, "g"]
>
> Would it not return category 1, across the entire date range, but limited to
> those with the engine 'g' only?
No. CouchDB keys are not filters. They occupy a linear space, and as
long as a key is "larger" than (or equal to) the startkey and
"smaller" than (or equal to) the endkey, the corresponding row is
included in query results. In the above case, [1, 2009, 9, 1, "h"]
will be included in your query result. There is a Wiki page on view
collation that explains this.
Re: Help with complex key range query and map/reduce
Posted by Glenn Rempe <gl...@rempe.us>.
Excellent! I am implementing as we speak.
I've put off the histogram reduction for the moment. Maybe I'll come back
to the group as I tackle that one.
Thanks.
On Tue, Sep 29, 2009 at 1:04 PM, Jesse Hallett <ha...@gmail.com> wrote:
> Yes, you got it.
>
>
Re: Help with complex key range query and map/reduce
Posted by Jesse Hallett <ha...@gmail.com>.
Yes, you got it.
On Sep 29, 2009 1:01 PM, "Glenn Rempe" <gl...@rempe.us> wrote:
Thanks Jesse for helping me walk through this. I think I am (slowly)
wrapping my head around it. :-) I think your example of having two
different views to cover this is helpful. Let me replay, and tell me if I
may finally have it.
(Just a note to clarify my use case, the date ranges can be an arbitrary
number of days e.g. Today - 60 days, and not strictly tied to one month at a
time on the natural monthly boundaries).
# Break up the views by *either* ALL engines, or a *SPECIFIC* engines.
A different view for each. The view executed is based on whether the engine
is all or specific.
# View 1 : When you want to query a single category (1), ALL engines,
and a date range of 8/1 - 9/30:
# [1,2009,8,1] to [1,2009,9,30]
# View 2 : When you want to query a single category (1), a SPECIFIC
Engine, and a date range of 8/1 - 9/30:
# [1,"g", 2009,9,1] to [1,"g",2009,9,30]
Correct?
Thanks again. Hopefully I've got it now.
Glenn
On Tue, Sep 29, 2009 at 9:17 AM, Jesse Hallett <ha...@gmail.com> wrote: >
Glenn, > > I am afrai...
Re: Help with complex key range query and map/reduce
Posted by Glenn Rempe <gl...@rempe.us>.
Thanks Jesse for helping me walk through this. I think I am (slowly)
wrapping my head around it. :-) I think your example of having two
different views to cover this is helpful. Let me replay, and tell me if I
may finally have it.
(Just a note to clarify my use case, the date ranges can be an arbitrary
number of days e.g. Today - 60 days, and not strictly tied to one month at a
time on the natural monthly boundaries).
# Break up the views by *either* ALL engines, or a *SPECIFIC* engines.
A different view for each. The view executed is based on whether the engine
is all or specific.
# View 1 : When you want to query a single category (1), ALL engines,
and a date range of 8/1 - 9/30:
# [1,2009,8,1] to [1,2009,9,30]
# View 2 : When you want to query a single category (1), a SPECIFIC
Engine, and a date range of 8/1 - 9/30:
# [1,"g", 2009,9,1] to [1,"g",2009,9,30]
Correct?
Thanks again. Hopefully I've got it now.
Glenn
On Tue, Sep 29, 2009 at 9:17 AM, Jesse Hallett <ha...@gmail.com> wrote:
> Glenn,
>
> I am afraid that to do what you want to do you will need at least two
> different views. As Ning explained, the most significant position of the
> key determines what will be filtered. For example:
>
> start: [1, 2009, 9, 1, "g"]
> end: [1, 2009, 9, 29, "g"]
>
> Will return all results for September with cat_id 1, regardless of engine,
> except that it will exclude items from 9/1 with engines "a"-"f" and items
> from 9/29 with engines "h"-"z". To demonstrate this, consider these
> ordering facts:
>
> [1, 2009, 9, 5, "r"] > [1, 2009, 9, 1, "g"] // 5 > 1
> [1, 2009, 9, 23, "m"] < [1, 2009, 9, 29, "g"] // 23 < 29
>
> That is why it is necessary to move the engine parameter in front of the
> date. If you want the options of filtering by a specific engine or
> including all engines in a given date range you will need two different
> views that have keys that are ordered differently. If you want a specific
> range of engines you will have to lock that query to a specific date
> parameter. But you can for example create a view that only emits year and
> month values for the date to query based on a specific range of engines
> over
> one month.
>
>
Re: Help with complex key range query and map/reduce
Posted by Jesse Hallett <ha...@gmail.com>.
Glenn,
I am afraid that to do what you want to do you will need at least two
different views. As Ning explained, the most significant position of the
key determines what will be filtered. For example:
start: [1, 2009, 9, 1, "g"]
end: [1, 2009, 9, 29, "g"]
Will return all results for September with cat_id 1, regardless of engine,
except that it will exclude items from 9/1 with engines "a"-"f" and items
from 9/29 with engines "h"-"z". To demonstrate this, consider these
ordering facts:
[1, 2009, 9, 5, "r"] > [1, 2009, 9, 1, "g"] // 5 > 1
[1, 2009, 9, 23, "m"] < [1, 2009, 9, 29, "g"] // 23 < 29
That is why it is necessary to move the engine parameter in front of the
date. If you want the options of filtering by a specific engine or
including all engines in a given date range you will need two different
views that have keys that are ordered differently. If you want a specific
range of engines you will have to lock that query to a specific date
parameter. But you can for example create a view that only emits year and
month values for the date to query based on a specific range of engines over
one month.
As for the increasing size of reduce function output; I think whether this
is a problem depends on the ratio of domains to documents that you are
querying across. The volume of data output by the reduce function must be
less than the log of the volume of data emitted by the map function for the
same key range. So if you have a small number of domains compared to
documents you are likely to be ok.
On Sep 28, 2009 3:08 PM, "Adam Wolff" <aw...@gmail.com> wrote:
On Mon, Sep 28, 2009 at 1:51 PM, Glenn Rempe <gl...@rempe.us> wrote: > Thank
you Jeremy, Jesse, Ada...
The problem is with the use-case, not the data representation (so "both.")
More about reduce limitations here:
http://wiki.apache.org/couchdb/Introduction_to_CouchDB_views#reduced_value_sizes
One workaround here is to limit the number of values that are emitted in a
given reduce step to, say, the top n. This causes data-loss problems, but is
adequate for some applications.
A
Re: Help with complex key range query and map/reduce
Posted by Adam Wolff <aw...@gmail.com>.
On Mon, Sep 28, 2009 at 1:51 PM, Glenn Rempe <gl...@rempe.us> wrote:
> Thank you Jeremy, Jesse, Adam, and Chris for the responses. It is really
> very much appreciated.
> Chris, is your concern specifically with what Adam was proposing? Would
> Jesse's solution be more performant over time and in-line with how CDB
> wants
> to operate? Or do both of these pose a problem.
>
>
The problem is with the use-case, not the data representation (so "both.")
More about reduce limitations here:
http://wiki.apache.org/couchdb/Introduction_to_CouchDB_views#reduced_value_sizes
One workaround here is to limit the number of values that are emitted in a
given reduce step to, say, the top n. This causes data-loss problems, but is
adequate for some applications.
A
Re: Help with complex key range query and map/reduce
Posted by Glenn Rempe <gl...@rempe.us>.
Thank you Jeremy, Jesse, Adam, and Chris for the responses. It is really
very much appreciated.
Chris, is your concern specifically with what Adam was proposing? Would
Jesse's solution be more performant over time and in-line with how CDB wants
to operate? Or do both of these pose a problem.
I currently have about 26 million records in a DB I am converting over to
CouchDB, and the reduce could potentially be performed on hundreds of
thousands of records for a query if the user wanted to generate a report
across say 90 days of data.
Jesse et. al, regarding your warning about how best to search across the
complex key. Could you take a peek at a code snippet and let me know if I
am going astray in my currently in dev code? Here is a link to a snippet
(Ruby code)
http://pastie.org/633956
So here is what I am trying to do:
The user wants to filter a search based on category_id, date range, and
engine.
- The category_id is always the same for the start and end key.
- The dates in the start and end key would almost always be a range
(specific start/end dates, or a backwards X # of days from today)
- They should be able to filter on engine (specifically g, y, or b, or
across all of them)
So are you saying that if I query like:
startkey = [1, 2009, 9, 1, "a"]
endkey = [1, 2009, 9, 28, "a\u9999"]
Would it not return all records between 9/1 and 9/28, across ALL engines?
Alternatively if I was specific with the engine, but still provided a date
range:
startkey = [1, 2009, 9, 1, "g"]
endkey = [1, 2009, 9, 28, "g"]
Would it not return category 1, across the entire date range, but limited to
those with the engine 'g' only?
Again, thanks very much for all your help with getting over the humps.
Glenn
On Mon, Sep 28, 2009 at 11:07 AM, Chris Anderson <jc...@apache.org> wrote:
> On Mon, Sep 28, 2009 at 10:31 AM, Adam Wolff <aw...@gmail.com> wrote:
> > If you change your map like this: var value ={};
> > value[domain] = 1;
> > emit([key...], value);
> >
> > Then you don't need conditional handling of rereduce. You can just write:
> > values.forEach(function(v) {
> > for (var k in v) {
> > hist[k] = (hist[k] || 0) + v[k];
> > }
> > }
> >
>
> Just a warning that keeping a growing dictionary in your reduce values
> can be considered an anti-pattern. You'll get reduce overflows on big
> data sets.
>
>
Re: Help with complex key range query and map/reduce
Posted by Chris Anderson <jc...@apache.org>.
On Mon, Sep 28, 2009 at 10:31 AM, Adam Wolff <aw...@gmail.com> wrote:
> If you change your map like this: var value ={};
> value[domain] = 1;
> emit([key...], value);
>
> Then you don't need conditional handling of rereduce. You can just write:
> values.forEach(function(v) {
> for (var k in v) {
> hist[k] = (hist[k] || 0) + v[k];
> }
> }
>
Just a warning that keeping a growing dictionary in your reduce values
can be considered an anti-pattern. You'll get reduce overflows on big
data sets.
> A
>
> On Mon, Sep 28, 2009 at 9:31 AM, Jesse Hallett <ha...@gmail.com> wrote:
>
>> It is entirely possible to do what you want. The reduce function required
>> is reasonably complicated.
>>
>> First I want to point out that in the example query you gave the results
>> will not be filtered by engine. If you want results matching only a
>> specific category_id and engine you will have to move `engine` to the
>> second
>> or first position of the key. If you want to get all engine values for a
>> given date range then the last position in the key is appropriate.
>> Otherwise the map function is looking good.
>>
>> Here is a reduce function that should work:
>>
>> function (keys, values, rereduce) {
>> var hist = {};
>> if (rereduce) {
>> values.forEach(function(v) {
>> // v is the intermediate output of a previous reduce call.
>> for (var k in v) {
>> hist[k] = (hist[k] || 0) + v[k];
>> }
>> }
>> } else {
>> // v is a domain.
>> values.forEach(function(v) {
>> hist[v] = (hist[v] || 0) + 1;
>> }
>> }
>> return hist;
>> }
>>
>> Make sure to run your queries with `group=true`. Futon uses `group=false`
>> in the interactive view editor - so results may not look correct there.
>>
>> The 'Introduction to Views' wiki page is very helpful to me for getting a
>> good idea of how reduce functions work:
>>
>> http://wiki.apache.org/couchdb/Introduction_to_CouchDB_views
>>
>> On Sep 28, 2009 7:21 AM, "Jeremy Wall" <jw...@google.com> wrote:
>>
>> Typing from my phone so I can't give a code example. But from what you are
>> describing I think you want a key that looks something like this.
>> [CategoryId, Date, domain]. You can then use reduce to return counts by
>> category, date, and domain. If you want counts that span categories and
>> dates though then you will have to merge them in your application code.
>>
>> Sent from my G1 google phone
>>
>> On Sep 28, 2009 12:42 AM, "Glenn Rempe" <gl...@rempe.us> wrote: Hello, I
>> am
>> hoping the group can ...
>>
>
--
Chris Anderson
http://jchrisa.net
http://couch.io
Re: Help with complex key range query and map/reduce
Posted by Adam Wolff <aw...@gmail.com>.
If you change your map like this: var value ={};
value[domain] = 1;
emit([key...], value);
Then you don't need conditional handling of rereduce. You can just write:
values.forEach(function(v) {
for (var k in v) {
hist[k] = (hist[k] || 0) + v[k];
}
}
A
On Mon, Sep 28, 2009 at 9:31 AM, Jesse Hallett <ha...@gmail.com> wrote:
> It is entirely possible to do what you want. The reduce function required
> is reasonably complicated.
>
> First I want to point out that in the example query you gave the results
> will not be filtered by engine. If you want results matching only a
> specific category_id and engine you will have to move `engine` to the
> second
> or first position of the key. If you want to get all engine values for a
> given date range then the last position in the key is appropriate.
> Otherwise the map function is looking good.
>
> Here is a reduce function that should work:
>
> function (keys, values, rereduce) {
> var hist = {};
> if (rereduce) {
> values.forEach(function(v) {
> // v is the intermediate output of a previous reduce call.
> for (var k in v) {
> hist[k] = (hist[k] || 0) + v[k];
> }
> }
> } else {
> // v is a domain.
> values.forEach(function(v) {
> hist[v] = (hist[v] || 0) + 1;
> }
> }
> return hist;
> }
>
> Make sure to run your queries with `group=true`. Futon uses `group=false`
> in the interactive view editor - so results may not look correct there.
>
> The 'Introduction to Views' wiki page is very helpful to me for getting a
> good idea of how reduce functions work:
>
> http://wiki.apache.org/couchdb/Introduction_to_CouchDB_views
>
> On Sep 28, 2009 7:21 AM, "Jeremy Wall" <jw...@google.com> wrote:
>
> Typing from my phone so I can't give a code example. But from what you are
> describing I think you want a key that looks something like this.
> [CategoryId, Date, domain]. You can then use reduce to return counts by
> category, date, and domain. If you want counts that span categories and
> dates though then you will have to merge them in your application code.
>
> Sent from my G1 google phone
>
> On Sep 28, 2009 12:42 AM, "Glenn Rempe" <gl...@rempe.us> wrote: Hello, I
> am
> hoping the group can ...
>
Re: Help with complex key range query and map/reduce
Posted by Jesse Hallett <ha...@gmail.com>.
It is entirely possible to do what you want. The reduce function required
is reasonably complicated.
First I want to point out that in the example query you gave the results
will not be filtered by engine. If you want results matching only a
specific category_id and engine you will have to move `engine` to the second
or first position of the key. If you want to get all engine values for a
given date range then the last position in the key is appropriate.
Otherwise the map function is looking good.
Here is a reduce function that should work:
function (keys, values, rereduce) {
var hist = {};
if (rereduce) {
values.forEach(function(v) {
// v is the intermediate output of a previous reduce call.
for (var k in v) {
hist[k] = (hist[k] || 0) + v[k];
}
}
} else {
// v is a domain.
values.forEach(function(v) {
hist[v] = (hist[v] || 0) + 1;
}
}
return hist;
}
Make sure to run your queries with `group=true`. Futon uses `group=false`
in the interactive view editor - so results may not look correct there.
The 'Introduction to Views' wiki page is very helpful to me for getting a
good idea of how reduce functions work:
http://wiki.apache.org/couchdb/Introduction_to_CouchDB_views
On Sep 28, 2009 7:21 AM, "Jeremy Wall" <jw...@google.com> wrote:
Typing from my phone so I can't give a code example. But from what you are
describing I think you want a key that looks something like this.
[CategoryId, Date, domain]. You can then use reduce to return counts by
category, date, and domain. If you want counts that span categories and
dates though then you will have to merge them in your application code.
Sent from my G1 google phone
On Sep 28, 2009 12:42 AM, "Glenn Rempe" <gl...@rempe.us> wrote: Hello, I am
hoping the group can ...
Re: Help with complex key range query and map/reduce
Posted by Jeremy Wall <jw...@google.com>.
Typing from my phone so I can't give a code example. But from what you are
describing I think you want a key that looks something like this.
[CategoryId, Date, domain]. You can then use reduce to return counts by
category, date, and domain. If you want counts that span categories and
dates though then you will have to merge them in your application code.
Sent from my G1 google phone
On Sep 28, 2009 12:42 AM, "Glenn Rempe" <gl...@rempe.us> wrote:
Hello, I am hoping the group can provide some guidance on building a
map/reduce summary for a set of documents that I have retrieved with a
complex key range query.
In summary, I want to query a range of docs by a complex key consisting of
an [id, year, month, day, engine]. It is common for me to need to query
over a range of dates with something along the lines of this (CouchRest Ruby
code):
sd = SearchDocument.by_ad_domain_histogram(:startkey => [3, 2009, 9, 1,
"g"], :endkey => [3, 2009, 9, 28, "g"], :include_docs => false, :reduce =>
true)
In this example, I want all SearchDocuments that are for category '3'
between 9/1/2009 and 9/28/2009, and for engine 'g'.
Now, this is working well and returning a range of docs. So the tricky part
(at least for me as a CouchDB n00b) is that each of these docs also has an
'ad_domain' value. And what I want is to generate a simple histogram which
groups all of these range of docs by the ad_domains found. So I want to get
back at the end of the day is something like:
{'foo.com' => 12, 'bar.com' => 32, 'baz.com' => 14}
This is what I am stuck on as I have not wrapped my head around map/reduce
in CouchDB quite yet. I think this would be easier if I emitted the
ad_domain at the end of the complex key if ALL of the parts of the key that
I was querying on were the same. But since I am querying on a range of keys
I end up with a reduce spitting out multiple entries for 'foo.com' since
that domain was found across several days (unique complex keys) of results.
Is it possible to do what I want?
Here is a work in progress map/reduce, which doesn't do what I want yet.
Help in modifying it would be much appreciated (and tips for doing what I
am already doing, only better!):
view_by :ad_domain_histogram,
:map =>
'function(doc) {
if( (doc["couchrest-type"] == "SearchDocument") && doc.category_id
&& doc.searched_at && doc.engine) {
var domain;
if(doc.ad_domain == null){
domain="NONE";
}else{
domain=doc.ad_domain;
}
emit([doc.category_id,
new Date(Date.parse(doc.searched_at)).getFullYear(),
new Date(Date.parse(doc.searched_at)).getMonth() + 1,
new Date(Date.parse(doc.searched_at)).getDate(),
doc.engine],
domain);
}
}',
:reduce =>
"function(keys, values, rereduce) {
return sum(values);
}"
Thanks very much in advance,
Glenn