Proposal: Review DBs

[Wout Mertens <wo...@gmail.com>]

Intro
=====
How do you sort by reduce value? How do you join views? How do you get  
unique view results? How do you cache group key reduces?

I think that with the below proposed solution all the above and more  
are possible. The general idea is to store view results and run map/ 
reduce on them. There's been some discussions about this but they went  
nowhere. I've been thinking about this issue a bit and I think it can  
be done.

I'd like to call this feature a Review DB.

Use cases
=========
- Suppose you want to know what tags are most popular on your blog.  
Simply get:

   http://couchdb/db/_design/myblog/_review/tags_by_count/_view/sort_by_value

Where tags_by_count is a Review DB that gets input from the tagcount  
view and then runs the sort_by_value view on it, a map() function that  
simply emits (value,key).

Likewise, show pages in order of popularity, whereby user can vote up  
(+1) or down (-1):

   http://couchdb/db/_design/mywiki/_review/pagevotes/_view/ 
sort_by_value

- Given documents with attributes title, date and tags. You'd like to  
know the minimum value of date and a breakdown by count for tags, for  
every title. Normally you'd use 2 map+reduce views,  
minimum_date_by_title and tagcount_by_title, which you would then  
query separately. With a Review DB, you can let both views insert  
their results in the database and then run a view that combines the  
results in one view:

   http://couchdb/db/_design/mybookstore/_review/mybooks/_view/aggregate_book_data

- This is not a way to run an on-the-fly map/reduce on a subset of a  
view, like if you want to find the median popularity score of  
restaurants with "Tony" in their name that are close to you.

Implementation
==============
A Review DB is a hidden database maintained by CouchDB with these  
fields:
- _id of document is the string representation of the key
- "key" is the key of the incoming view row (unique)
- "value" is the value of the incoming view row

I hope that this is sufficiently like a normal view that it can be  
stored as a normal view. _id is just there to make it doc-compliant,  
it would be much better if "key" were the actual key.

A Review DB is defined in a design document like normal views. Each  
review is an entry in the "reviews" hash, and has a "incoming_views"  
array that lists all the views that should insert results in the  
review db plus the group level, as well as a normal "views" hash for  
further map/reduce of the review db (and perhaps another "reviews"  
hash for further result processing?).

Maintaining a database of results means that results have to be  
updated or even removed when documents change. I tried to make this  
work (in theory) for map-only views, but the resulting requirements  
are quite messy. You either need to cache the previous results of a  
view for each document, or you have to have an old version of the  
document available to regenerate those results.

Therefore, a Review DB only accepts results from one or more map 
+reduce views. You define beforehand what the group_level of the keys  
is that will be inserted.

Furthermore, a Review DB disallows (but doesn't enforce) having 2  
views that generate the same keys. Otherwise, refcounting would need  
to be used and while that's not difficult, I think there's limited  
value in allowing this.

The Review DB needs updating every time the reduction for a group key  
of one of the participating views gets updated. Even though a map 
+reduce view has unique keys, we need a refcount since we have  
multiple views. Whoever got to insert its value last wins.

There is a slight complication: group key values are calculated on-the- 
fly from the view result b-tree. So whenever a reduce call results in  
a new value for a b-tree node, AND that node is the upper node of a  
subtree that is completely part of a group key, that group key needs  
to be marked for recalculation.

Likewise, if deletion/addition of a b-tree node results in the removal/ 
creation of the sole upper node of a group key subtree, that group key  
needs to be marked for removal/addition.

This is the algorithm:
- When a reducing view gets updated, and it is part of a Review DB,  
use the 2 paragraphs above to keep a list of group keys that need  
handling
- After updating the reduce() results, for each of the marked group  
keys:
  - If a group key gets removed:
    - look up doc with key=group key in review db. If exists:
      - delete doc
  - If a group key gets added:
    - look up doc with key=group key in review db. If exists:
      - set doc.value to the row value
    - else
      - create doc with id=group key in string form, key=group key,  
value=value
  - If a group key gets updated:
    - look up doc with key=group key in review db. If exists:
      - set doc.value to the row value
    - else
      - create doc with id=group key in string form, key=group key,  
value=value
	
As you can see, this is something CouchDB should do since it knows  
when it's updating group key reduction values and it knows if this was  
an delete, update or addition.

View updates are done when the view is called; Review updates are done  
at this time as well. Views on Review DBs are done when they are called.

Summary
=======
Review DBs are a sort of view index that CouchDB can maintain with  
little overhead. It caches group key results and allows chained map 
+reduce calculations using mostly existing frameworks.

I think this would be a very useful feature for CouchDB to have. There  
are regularly requests for storing view results in a database for post- 
processing on the mailing lists.

I'm not saying this is a trivial change but it doesn't seem  
technically impossible to me either. (unless I missed something again;  
this is the 5th iteration of this proposal. Anyway I know *I* wouldn't  
be able to code this :-) )

What do you think, oh dear devs?

Wout.

Re: Proposal: Review DBs

[Zachary Zolton <za...@gmail.com>]

This also sounds related to the "View Intersections" proposal
discussed earlier...

http://mail-archives.apache.org/mod_mbox/couchdb-dev/200904.mbox/%3c011A0D62-06C2-490B-A4C4-7EEF0203B6C3@gmail.com%3e


On Wed, Apr 22, 2009 at 9:07 AM, Zachary Zolton
<za...@gmail.com> wrote:
> I would definitely +1 something like this.
>
> I'm essentially do something like this "manually", with an update
> notifier script, and I'd love to see it become a first-class feature
> —instead of my special-case version of it.
>
> On Wed, Apr 22, 2009 at 7:40 AM, Wout Mertens <wo...@gmail.com> wrote:
>> Intro
>> =====
>> How do you sort by reduce value? How do you join views? How do you get
>> unique view results? How do you cache group key reduces?
>>
>> I think that with the below proposed solution all the above and more are
>> possible. The general idea is to store view results and run map/reduce on
>> them. There's been some discussions about this but they went nowhere. I've
>> been thinking about this issue a bit and I think it can be done.
>>
>> I'd like to call this feature a Review DB.
>>
>> Use cases
>> =========
>> - Suppose you want to know what tags are most popular on your blog. Simply
>> get:
>>
>>  http://couchdb/db/_design/myblog/_review/tags_by_count/_view/sort_by_value
>>
>> Where tags_by_count is a Review DB that gets input from the tagcount view
>> and then runs the sort_by_value view on it, a map() function that simply
>> emits (value,key).
>>
>> Likewise, show pages in order of popularity, whereby user can vote up (+1)
>> or down (-1):
>>
>>  http://couchdb/db/_design/mywiki/_review/pagevotes/_view/sort_by_value
>>
>> - Given documents with attributes title, date and tags. You'd like to know
>> the minimum value of date and a breakdown by count for tags, for every
>> title. Normally you'd use 2 map+reduce views, minimum_date_by_title and
>> tagcount_by_title, which you would then query separately. With a Review DB,
>> you can let both views insert their results in the database and then run a
>> view that combines the results in one view:
>>
>>  http://couchdb/db/_design/mybookstore/_review/mybooks/_view/aggregate_book_data
>>
>> - This is not a way to run an on-the-fly map/reduce on a subset of a view,
>> like if you want to find the median popularity score of restaurants with
>> "Tony" in their name that are close to you.
>>
>> Implementation
>> ==============
>> A Review DB is a hidden database maintained by CouchDB with these fields:
>> - _id of document is the string representation of the key
>> - "key" is the key of the incoming view row (unique)
>> - "value" is the value of the incoming view row
>>
>> I hope that this is sufficiently like a normal view that it can be stored as
>> a normal view. _id is just there to make it doc-compliant, it would be much
>> better if "key" were the actual key.
>>
>> A Review DB is defined in a design document like normal views. Each review
>> is an entry in the "reviews" hash, and has a "incoming_views" array that
>> lists all the views that should insert results in the review db plus the
>> group level, as well as a normal "views" hash for further map/reduce of the
>> review db (and perhaps another "reviews" hash for further result
>> processing?).
>>
>> Maintaining a database of results means that results have to be updated or
>> even removed when documents change. I tried to make this work (in theory)
>> for map-only views, but the resulting requirements are quite messy. You
>> either need to cache the previous results of a view for each document, or
>> you have to have an old version of the document available to regenerate
>> those results.
>>
>> Therefore, a Review DB only accepts results from one or more map+reduce
>> views. You define beforehand what the group_level of the keys is that will
>> be inserted.
>>
>> Furthermore, a Review DB disallows (but doesn't enforce) having 2 views that
>> generate the same keys. Otherwise, refcounting would need to be used and
>> while that's not difficult, I think there's limited value in allowing this.
>>
>> The Review DB needs updating every time the reduction for a group key of one
>> of the participating views gets updated. Even though a map+reduce view has
>> unique keys, we need a refcount since we have multiple views. Whoever got to
>> insert its value last wins.
>>
>> There is a slight complication: group key values are calculated on-the-fly
>> from the view result b-tree. So whenever a reduce call results in a new
>> value for a b-tree node, AND that node is the upper node of a subtree that
>> is completely part of a group key, that group key needs to be marked for
>> recalculation.
>>
>> Likewise, if deletion/addition of a b-tree node results in the
>> removal/creation of the sole upper node of a group key subtree, that group
>> key needs to be marked for removal/addition.
>>
>> This is the algorithm:
>> - When a reducing view gets updated, and it is part of a Review DB, use the
>> 2 paragraphs above to keep a list of group keys that need handling
>> - After updating the reduce() results, for each of the marked group keys:
>>  - If a group key gets removed:
>>   - look up doc with key=group key in review db. If exists:
>>     - delete doc
>>  - If a group key gets added:
>>   - look up doc with key=group key in review db. If exists:
>>     - set doc.value to the row value
>>   - else
>>     - create doc with id=group key in string form, key=group key,
>> value=value
>>  - If a group key gets updated:
>>   - look up doc with key=group key in review db. If exists:
>>     - set doc.value to the row value
>>   - else
>>     - create doc with id=group key in string form, key=group key,
>> value=value
>>
>> As you can see, this is something CouchDB should do since it knows when it's
>> updating group key reduction values and it knows if this was an delete,
>> update or addition.
>>
>> View updates are done when the view is called; Review updates are done at
>> this time as well. Views on Review DBs are done when they are called.
>>
>> Summary
>> =======
>> Review DBs are a sort of view index that CouchDB can maintain with little
>> overhead. It caches group key results and allows chained map+reduce
>> calculations using mostly existing frameworks.
>>
>> I think this would be a very useful feature for CouchDB to have. There are
>> regularly requests for storing view results in a database for
>> post-processing on the mailing lists.
>>
>> I'm not saying this is a trivial change but it doesn't seem technically
>> impossible to me either. (unless I missed something again; this is the 5th
>> iteration of this proposal. Anyway I know *I* wouldn't be able to code this
>> :-) )
>>
>> What do you think, oh dear devs?
>>
>> Wout.
>>
>

Re: Proposal: Review DBs

[Zachary Zolton <za...@gmail.com>]

I would definitely +1 something like this.

I'm essentially do something like this "manually", with an update
notifier script, and I'd love to see it become a first-class feature
—instead of my special-case version of it.

On Wed, Apr 22, 2009 at 7:40 AM, Wout Mertens <wo...@gmail.com> wrote:
> Intro
> =====
> How do you sort by reduce value? How do you join views? How do you get
> unique view results? How do you cache group key reduces?
>
> I think that with the below proposed solution all the above and more are
> possible. The general idea is to store view results and run map/reduce on
> them. There's been some discussions about this but they went nowhere. I've
> been thinking about this issue a bit and I think it can be done.
>
> I'd like to call this feature a Review DB.
>
> Use cases
> =========
> - Suppose you want to know what tags are most popular on your blog. Simply
> get:
>
>  http://couchdb/db/_design/myblog/_review/tags_by_count/_view/sort_by_value
>
> Where tags_by_count is a Review DB that gets input from the tagcount view
> and then runs the sort_by_value view on it, a map() function that simply
> emits (value,key).
>
> Likewise, show pages in order of popularity, whereby user can vote up (+1)
> or down (-1):
>
>  http://couchdb/db/_design/mywiki/_review/pagevotes/_view/sort_by_value
>
> - Given documents with attributes title, date and tags. You'd like to know
> the minimum value of date and a breakdown by count for tags, for every
> title. Normally you'd use 2 map+reduce views, minimum_date_by_title and
> tagcount_by_title, which you would then query separately. With a Review DB,
> you can let both views insert their results in the database and then run a
> view that combines the results in one view:
>
>  http://couchdb/db/_design/mybookstore/_review/mybooks/_view/aggregate_book_data
>
> - This is not a way to run an on-the-fly map/reduce on a subset of a view,
> like if you want to find the median popularity score of restaurants with
> "Tony" in their name that are close to you.
>
> Implementation
> ==============
> A Review DB is a hidden database maintained by CouchDB with these fields:
> - _id of document is the string representation of the key
> - "key" is the key of the incoming view row (unique)
> - "value" is the value of the incoming view row
>
> I hope that this is sufficiently like a normal view that it can be stored as
> a normal view. _id is just there to make it doc-compliant, it would be much
> better if "key" were the actual key.
>
> A Review DB is defined in a design document like normal views. Each review
> is an entry in the "reviews" hash, and has a "incoming_views" array that
> lists all the views that should insert results in the review db plus the
> group level, as well as a normal "views" hash for further map/reduce of the
> review db (and perhaps another "reviews" hash for further result
> processing?).
>
> Maintaining a database of results means that results have to be updated or
> even removed when documents change. I tried to make this work (in theory)
> for map-only views, but the resulting requirements are quite messy. You
> either need to cache the previous results of a view for each document, or
> you have to have an old version of the document available to regenerate
> those results.
>
> Therefore, a Review DB only accepts results from one or more map+reduce
> views. You define beforehand what the group_level of the keys is that will
> be inserted.
>
> Furthermore, a Review DB disallows (but doesn't enforce) having 2 views that
> generate the same keys. Otherwise, refcounting would need to be used and
> while that's not difficult, I think there's limited value in allowing this.
>
> The Review DB needs updating every time the reduction for a group key of one
> of the participating views gets updated. Even though a map+reduce view has
> unique keys, we need a refcount since we have multiple views. Whoever got to
> insert its value last wins.
>
> There is a slight complication: group key values are calculated on-the-fly
> from the view result b-tree. So whenever a reduce call results in a new
> value for a b-tree node, AND that node is the upper node of a subtree that
> is completely part of a group key, that group key needs to be marked for
> recalculation.
>
> Likewise, if deletion/addition of a b-tree node results in the
> removal/creation of the sole upper node of a group key subtree, that group
> key needs to be marked for removal/addition.
>
> This is the algorithm:
> - When a reducing view gets updated, and it is part of a Review DB, use the
> 2 paragraphs above to keep a list of group keys that need handling
> - After updating the reduce() results, for each of the marked group keys:
>  - If a group key gets removed:
>   - look up doc with key=group key in review db. If exists:
>     - delete doc
>  - If a group key gets added:
>   - look up doc with key=group key in review db. If exists:
>     - set doc.value to the row value
>   - else
>     - create doc with id=group key in string form, key=group key,
> value=value
>  - If a group key gets updated:
>   - look up doc with key=group key in review db. If exists:
>     - set doc.value to the row value
>   - else
>     - create doc with id=group key in string form, key=group key,
> value=value
>
> As you can see, this is something CouchDB should do since it knows when it's
> updating group key reduction values and it knows if this was an delete,
> update or addition.
>
> View updates are done when the view is called; Review updates are done at
> this time as well. Views on Review DBs are done when they are called.
>
> Summary
> =======
> Review DBs are a sort of view index that CouchDB can maintain with little
> overhead. It caches group key results and allows chained map+reduce
> calculations using mostly existing frameworks.
>
> I think this would be a very useful feature for CouchDB to have. There are
> regularly requests for storing view results in a database for
> post-processing on the mailing lists.
>
> I'm not saying this is a trivial change but it doesn't seem technically
> impossible to me either. (unless I missed something again; this is the 5th
> iteration of this proposal. Anyway I know *I* wouldn't be able to code this
> :-) )
>
> What do you think, oh dear devs?
>
> Wout.
>

Re: Proposal: Review DBs

[Wout Mertens <wo...@gmail.com>]

On Apr 28, 2009, at 3:46 PM, Adam Kocoloski wrote:

> I'm not an expert on the btree code, but I think this statement
>
>> So whenever a reduce call results in a new value for a b-tree node,  
>> AND that node is the upper node of a subtree that is completely  
>> part of a group key, that group key needs to be marked for  
>> recalculation.
>
>
> misses some updates.  I thought things looked something like
>
>          root
>            |
>     ---------------
>    kp1           kp2
>     |             |
> ---------     ---------
> foo foo bar   bar bar bar
>
> where foo and bar are emitted keys from a map (values not show for  
> the sake of brevity).  kp1 and kp2 hold reduce(foo,foo,bar) and  
> reduce(bar,bar,bar) respectively, and root holds rereduce(kp1,kp2).

That is my understanding as well.

> When we request a view with group=true, Couch is smart enough to use  
> the reduction stored in kp2 directly, but it has to call  
> reduce(foo,foo) and reduce(bar) on the fly for the nodes underneath  
> kp1 (and then rereduce the bar reductions from kp1 and kp2 to get  
> the result for bar).  If I interpreted Wout's statement correctly,  
> it ignores the case where any of the nodes under kp1 change, since  
> kp1 is not "the upper node of a subtree that is completely part of a  
> group key".

In this case, both foos are the upper node of a subtree that is  
completely part of a group key. bar isn't.

Same graph with the group keys indicated:

          root
            |
     ------BAR------
    kp1           kp2
     |             |
--FOO----     ---------
foo foo bar   bar bar bar

So whenever the first bar changes, kp1 needs to be calculated and then  
BAR is marked as needing updating, since kp1 is a top node under BAR.

FOO is only marked for updating when either of the foos change.

> I think the problem of tracking which group keys to update can be  
> made simpler.  We really only need to see the key updates coming out  
> of the incremental map.  Couch knows the lists of keys to add and  
> keys to remove at that point; the set of all unique keys in those  
> two lists (the "changeset") is the set of group keys that would need  
> to be updated in the Review DB. Here I'm using "update" in the  
> general sense of add/remove/change; the way I see it, we could just  
> query the view for all the keys in the changeset.  If the MR view  
> has no results for a given key, that obviously means delete the  
> associated document from the Review DB.

That is a very good idea! It's not as efficient as marking group keys  
like I proposed (maps need not necessarily change reduce values), but  
it's a lot easier to code.

> group_levels are a straightforward extension -- we just check what  
> group_level we'll be using in the Review DB when we calculate the  
> changeset.

Exactly.

So the algorithm becomes:

- When updating a view, keep track of all mentioned keys in the  
previous and current map() output, keep only group_level key parts.

- After updating the reduce() results, for each of the marked group  
keys:
- If a group key gets removed:
- look up doc with key=group key in review db. If exists:
   - delete doc
- If a group key gets added:
- look up doc with key=group key in review db. If exists:
   - set doc.value to the row value
- else
   - create doc with id=group key in string form, key=group key,  
value=value
- If a group key gets updated:
- look up doc with key=group key in review db. If exists:
   - set doc.value to the row value
- else
   - create doc with id=group key in string form, key=group key,  
value=value

Good thinking!

Wout.

Re: Proposal: Review DBs

[Adam Kocoloski <ko...@apache.org>]

On Apr 28, 2009, at 8:13 AM, Wout Mertens wrote:

> On Apr 28, 2009, at 11:42 AM, Brian Candler wrote:
>
>> Furthermore, if I understand rightly, these grouped reduce values  
>> are *not*
>> persisted anywhere (*). That is: every time you do a  
>> reduce=true&group=true
>> query then the entire map index is scanned for distinct keys and  
>> then each
>> set of values with equal keys is passed afresh to the reduce  
>> function.
>>
>> This means that it won't be possible to do incremental changes to  
>> the review
>> DB, since these grouped keys and reduce values aren't associated  
>> with the
>> docids they came from. You'd have to calculate it all from scratch  
>> every
>> time, in which case you might as well just get the client to do it.  
>> AFAICS,
>> CouchDB could cache the result only when the database is not  
>> receiving any
>> updates.
>
> You're correct in that group reduce values are not persisted,  
> however the algorithm I proposed can do incremental updates  
> nonetheless:
> =========
> Group key values are calculated on-the-fly from the view result b- 
> tree. So whenever a reduce call results in a new value for a b-tree  
> node, AND that node is the upper node of a subtree that is  
> completely part of a group key, that group key needs to be marked  
> for recalculation.
>
> Likewise, if deletion/addition of a b-tree node results in the  
> removal/creation of the sole upper node of a group key subtree, that  
> group key needs to be marked for removal/addition.
>
> This is the algorithm:
> - When a reducing view gets updated, and it is part of a Review DB,  
> use the 2 paragraphs above to keep a list of group keys that need  
> handling
> - After updating the reduce() results, for each of the marked group  
> keys:
> - If a group key gets removed:
>  - look up doc with key=group key in review db. If exists:
>    - delete doc
> - If a group key gets added:
>  - look up doc with key=group key in review db. If exists:
>    - set doc.value to the row value
>  - else
>    - create doc with id=group key in string form, key=group key,  
> value=value
> - If a group key gets updated:
>  - look up doc with key=group key in review db. If exists:
>    - set doc.value to the row value
>  - else
>    - create doc with id=group key in string form, key=group key,  
> value=value
> ========
> Is that explanation clear?
>
> I'm imagining that at any point on the b-tree where a reduce value  
> is received, CouchDB can see if that node is one of the top nodes  
> for a group key and can mark that group key somehow. I think that  
> should be feasible (although I admit I've never tried to grok the  
> code).
>
> Cheers,
>
> Wout.

I'm not an expert on the btree code, but I think this statement

> So whenever a reduce call results in a new value for a b-tree node,  
> AND that node is the upper node of a subtree that is completely part  
> of a group key, that group key needs to be marked for recalculation.


misses some updates.  I thought things looked something like

           root
             |
      ---------------
     kp1           kp2
      |             |
  ---------     ---------
foo foo bar   bar bar bar

where foo and bar are emitted keys from a map (values not show for the  
sake of brevity).  kp1 and kp2 hold reduce(foo,foo,bar) and  
reduce(bar,bar,bar) respectively, and root holds rereduce(kp1,kp2).

When we request a view with group=true, Couch is smart enough to use  
the reduction stored in kp2 directly, but it has to call  
reduce(foo,foo) and reduce(bar) on the fly for the nodes underneath  
kp1 (and then rereduce the bar reductions from kp1 and kp2 to get the  
result for bar).  If I interpreted Wout's statement correctly, it  
ignores the case where any of the nodes under kp1 change, since kp1 is  
not "the upper node of a subtree that is completely part of a group  
key".

I think the problem of tracking which group keys to update can be made  
simpler.  We really only need to see the key updates coming out of the  
incremental map.  Couch knows the lists of keys to add and keys to  
remove at that point; the set of all unique keys in those two lists  
(the "changeset") is the set of group keys that would need to be  
updated in the Review DB.  Here I'm using "update" in the general  
sense of add/remove/change; the way I see it, we could just query the  
view for all the keys in the changeset.  If the MR view has no results  
for a given key, that obviously means delete the associated document  
from the Review DB.

group_levels are a straightforward extension -- we just check what  
group_level we'll be using in the Review DB when we calculate the  
changeset.

Regards, Adam

Re: Proposal: Review DBs

[Wout Mertens <wo...@gmail.com>]

On Apr 28, 2009, at 11:42 AM, Brian Candler wrote:

> On Sun, Apr 26, 2009 at 11:26:33PM +0200, Wout Mertens wrote:
>> In a nutshell, I'm hoping that:
>> * A review is a new sort of view that has an "inputs" array in its
>> definition.
>> * Only MR views are allowed as inputs, no KV duplication allowed.
>> * It builds a persistent index of the incoming views when those get
>> updated.
>> * That index is then used to build the view index for the review when
>> the review gets updated.
>> * I think I covered the most important algorithms needed to implement
>> this in my original proposal.
>>
>> Does this sound feasible? If so I'll update my proposal accordingly.
>
> Could you define a bit more where the "inputs" array comes from?

Oh right, I didn't explain that well, and I never said how to add the  
group_level. Here's an example for counting the number of unique names  
in a database:

{
   "_id": "_design/foo",
   "views": {
       "unique_names": {
           "map": "function(doc) {emit(doc.name, 1);}",
           "reduce": "function(keys, values, rereduce) {return  
sum(values);}"
      }
       "unique_names_count": {
           "inputs": {"unique_names":1},
           "map": "function(doc) {emit(doc.key, 1);}",
           "reduce": "function(keys, values, rereduce) {return  
sum(values);}"
      }
   }
}

In this case, unique_names_count is the review db. It gets input from  
the unique_names view with group_level set to 1. Note that it's a hash  
since each view only gets added once and each view has a unique name.

(BTW, I can't figure out what to set group_level to if I want the  
equivalent of group=true. group_level=exact doesn't work although  
group_level=1000 might be good enough. How about allowing  
group_level=-1?)

(Also, in this case just "unique_names_count": {"inputs":  
{"unique_names":1}} would suffice since getting that view with limit=0  
will give you the total_rows number which is what was needed)

> Furthermore, if I understand rightly, these grouped reduce values  
> are *not*
> persisted anywhere (*). That is: every time you do a  
> reduce=true&group=true
> query then the entire map index is scanned for distinct keys and  
> then each
> set of values with equal keys is passed afresh to the reduce function.
>
> This means that it won't be possible to do incremental changes to  
> the review
> DB, since these grouped keys and reduce values aren't associated  
> with the
> docids they came from. You'd have to calculate it all from scratch  
> every
> time, in which case you might as well just get the client to do it.  
> AFAICS,
> CouchDB could cache the result only when the database is not  
> receiving any
> updates.

You're correct in that group reduce values are not persisted, however  
the algorithm I proposed can do incremental updates nonetheless:
=========
Group key values are calculated on-the-fly from the view result b- 
tree. So whenever a reduce call results in a new value for a b-tree  
node, AND that node is the upper node of a subtree that is completely  
part of a group key, that group key needs to be marked for  
recalculation.

Likewise, if deletion/addition of a b-tree node results in the removal/ 
creation of the sole upper node of a group key subtree, that group key  
needs to be marked for removal/addition.

This is the algorithm:
- When a reducing view gets updated, and it is part of a Review DB,  
use the 2 paragraphs above to keep a list of group keys that need  
handling
- After updating the reduce() results, for each of the marked group  
keys:
- If a group key gets removed:
   - look up doc with key=group key in review db. If exists:
     - delete doc
- If a group key gets added:
   - look up doc with key=group key in review db. If exists:
     - set doc.value to the row value
   - else
     - create doc with id=group key in string form, key=group key,  
value=value
- If a group key gets updated:
   - look up doc with key=group key in review db. If exists:
     - set doc.value to the row value
   - else
     - create doc with id=group key in string form, key=group key,  
value=value
========
Is that explanation clear?

I'm imagining that at any point on the b-tree where a reduce value is  
received, CouchDB can see if that node is one of the top nodes for a  
group key and can mark that group key somehow. I think that should be  
feasible (although I admit I've never tried to grok the code).

Cheers,

Wout.

Re: Proposal: Review DBs

[Brian Candler <B....@pobox.com>]

On Sun, Apr 26, 2009 at 11:26:33PM +0200, Wout Mertens wrote:
> In a nutshell, I'm hoping that:
> * A review is a new sort of view that has an "inputs" array in its  
> definition.
> * Only MR views are allowed as inputs, no KV duplication allowed.
> * It builds a persistent index of the incoming views when those get  
> updated.
> * That index is then used to build the view index for the review when  
> the review gets updated.
> * I think I covered the most important algorithms needed to implement  
> this in my original proposal.
>
> Does this sound feasible? If so I'll update my proposal accordingly.

Could you define a bit more where the "inputs" array comes from?

It can't be the overall reduce value for the whole database - that would
just be one single value :-) So it has to be the reduce value in some
grouped form, but there are multiple ways to slice that: e.g. group=true,
group_level=1, group_level=2 etc. This is something which will have to be
chosen by the user.

Furthermore, if I understand rightly, these grouped reduce values are *not*
persisted anywhere (*). That is: every time you do a reduce=true&group=true
query then the entire map index is scanned for distinct keys and then each
set of values with equal keys is passed afresh to the reduce function.

This means that it won't be possible to do incremental changes to the review
DB, since these grouped keys and reduce values aren't associated with the
docids they came from. You'd have to calculate it all from scratch every
time, in which case you might as well just get the client to do it. AFAICS,
CouchDB could cache the result only when the database is not receiving any
updates.

OTOH, it's quite possible that I have misunderstood entirely :-)

Regards,

Brian.

(*) Each B-tree node containing N key/value pairs also contains a single
reduce value for those N documents. However the B-tree nodes are not aligned
in any way with the map keys. These precalculated values do allow quicker
calculation of reduce values where a large number of documents emit the same
key, spanning multiple B-tree nodes, since the already-reduced values can be
re-reduced together.

Re: Proposal: Review DBs

[Wout Mertens <wo...@gmail.com>]

On Apr 27, 2009, at 5:20 AM, Chris Anderson wrote:

> On Apr 26, 2009, at 2:26 PM, Wout Mertens <wo...@gmail.com>  
> wrote:
>>
>>> You'd still be left with the problem of generating unique docids  
>>> for the documents in the Review DB, but I think that's a problem  
>>> that needs to be solved.  The restriction to only MR views with no  
>>> duplicate keys across views seems too strong to me.
>>
>> Well, since the Review DB is a local(*) hidden database that's  
>> handled a bit specially, I think the easiest is to assign _id a  
>> sequence number and create a default view that indexes the  
>> documents by doc.key (for updating the value for that key). There  
>> will never be contention and we're only interested in the key index.
>
> We discussed this a little at CouchHack and I argued that the  
> simplest solution is actually good for a few reasons.
>
> The simple solution: provide a mechanism to copy the rows of a  
> grouped reduce function to a new database.

Ok, the problems I see with that though are:
- How to assign _ids to the rows
- Separate design doc needed for each DB
   - Spreads application logic
   - All data not available from one parent URL a la CouchApps
- Namespace pollution, all these utility DBs

Or do you mean this as a single-shot data dump? Couldn't that get  
quite expensive, storage wise?

> Good because it is most like Hadoop/Google style map reduce. In that  
> paradigm, the output of a map/reduce job is not incremental, and it  
> is persisted in a way that allows for multiple later reduce stages  
> to be run on it. It's common in Hadoop to chain many m/r stages, and  
> to try a few iterations of each stage while developing code.

Hmmm. If a hidden DB/view index is used, then the same function  
hashing techniques will work to decide which index to use for  
intermediate queries. I see no functional difference here.

> I like this also because it provides the needed functionality  
> without adding any new primitives to CouchDB.

But how would that mechanism be used if there's no new primitives? If  
CouchDB would allow an extra field "inputs" on the view definitions,  
that's it as far as user-visible changes go in the current thinking  
for review DBs.

> The only downside of this approach is that it is not incremental.  
> I'm not sure that incremental chainability has much promise, as the  
> index management could be a pain, especially if you have branching  
> chains.

Hmmm, I think that I showed that it needn't be. Any update to a view  
would trigger review index updates for all the views that have that  
view as input. Subsequent updates of those views then get propagated  
onwards in the same fashion. Nothing painful...

If you want the latest info, first update the input views and then the  
review view.

> Another upside is that by reducing to a db, you give the user power  
> to do things like use replication to merge multiple data sets before  
> applying more views.

That's true... And I suppose it would be very useful in that case. I  
think there's room for both approaches perhaps?

Wout.

Re: Proposal: Review DBs

[Zachary Zolton <za...@gmail.com>]

Perhaps the background job could maintain some versioning number, in
the base DB's design doc, which clients could use to know which
version of the derived database to hit.

See? ;^) This might be simpler, as a 1st-class CouchDB feature, than a
bolted-on script.

On Mon, Apr 27, 2009 at 2:48 PM, Paul Davis <pa...@gmail.com> wrote:
> Zachary,
>
> Hmm. Naming your derived databases as base_db-stage-etag doesn't sound like
> a bad idea. Though I dunno how you'd communicate to clients to start hitting
> the new versions and also doesn't tell the admins when to drop old indices.
>
> The only thing that comes to mind is to stick some intermediary in between
> clients and the actual derived data to make it transparent and also to allow
> you to know when you can clean up old versions etc.
>
> I'll keep thinking on it.
>
> Paul
>
> Zachary Zolton wrote:
>>
>> okay, i'm starting to get ya. my question is, if i'm constantly
>> dropping/recreating/reindexing the derived database, how can i keep
>> serving requests from my website?
>>
>> one possible solution would be to time/etag/etc-stamp the derived db
>> name, but that would seem to add a number of moving parts to my
>> system.
>>
>> hmm... any ideas of how to pull a quick switcheroo on the backend of
>> my system, without too much hassle in the client code?
>>
>> On Mon, Apr 27, 2009 at 1:44 PM, Paul Davis <pa...@gmail.com>
>> wrote:
>>
>>>
>>> Zachary,
>>>
>>> No worries, the rough outline I'd do here is something like:
>>>
>>> 1. Figure out some member structure in the _design document that will
>>> represent your data flow. For them moment I would do something extremely
>>> simple as in:
>>>
>>> Assume:
>>> db_name = "base_db"
>>>
>>> {
>>>  "_id":  " _design/base",
>>>  "views": {
>>>      "stage-1": {
>>>          "map": "function(doc) ...",
>>>          "reduce": "function(keys, values, rereduce) ..."
>>>      }
>>>  },
>>>  "review": [
>>>      {"map": "function(doc) ...", "reduce": "function(keys, vals,
>>> rereduce)
>>> ..."},
>>>      {"map": "function(doc) ...", "reduce": "function(keys, vals,
>>> rereduce)
>>> ..."}
>>>  ]
>>> }
>>>
>>> So the review member becomes the stages in your data flow. I'm avoiding
>>> any
>>> forking or merging in this example in honor of the "make it work, make it
>>> not suck" development flow.
>>>
>>> Now the basic algorithm would be something like:
>>>
>>> For each array element in the "review" member, create a db something
>>> like:
>>>
>>> base_db-stage-1 with a design document that contains a view with the
>>> first
>>> element of the "reviews" member.
>>> base_db-stage-2 with the second member and so on.
>>>
>>> Then your script can check the view status in each database either with a
>>> cron (or an update_notifier) to do so, you can just:
>>>
>>> HEAD /base_db/_design/base/_view/stage-1
>>>
>>> And then check the returned ETag. For the moment this is exactly
>>> equivalent
>>> to checking the database's update_seq because of how the etag is
>>> calculated,
>>> but in the future when we track the last update_seq for each view change
>>> this will be a free upgrade. Plus there's a bit more logical-ness to
>>> checking "view state" instead of "db state".
>>>
>>> When the etag's don't match, you can just drop the next db in the flow,
>>> create it, and then copy the view output. The drop/create just makes the
>>> algorithm easily implementable for now. In the future there can be some
>>> extra logic to only change the new view as far as it requires by
>>> iterating
>>> over the two views and doing a merge sortish type of thing. I think...
>>> Sounds like there should be a way at least.
>>>
>>> Once that works we can look at bolting on different fancy things like
>>> having
>>> forking map/reduce mechanisms and my current pet idea of adding in the
>>> merge
>>> stuff that has been talked about.
>>>
>>> This is actually starting to sound like a fun little project....
>>>
>>> HTH,
>>> Paul Davis
>>>
>>> Zachary Zolton wrote:
>>>
>>>>
>>>> paul
>>>>
>>>> alright... you've gotta give me the remedial explanation of what you
>>>> meant here! (sorry, i'm still noob-ish)
>>>>
>>>> so, are you saying that i shouldn't even check for individual doc
>>>> updates, but instead just recreate the entire database? that sounds
>>>> like a job for cron, more so than the update notifier, right?
>>>>
>>>> i'd put up my current ruby script, but it deals update notifications
>>>> in a way that's very specific to my data —probably very naïvely, to
>>>> boot!
>>>>
>>>> zach
>>>>
>>>> On Mon, Apr 27, 2009 at 11:28 AM, Paul Davis
>>>> <pa...@gmail.com> wrote:
>>>>
>>>>
>>>>>
>>>>> Zachary,
>>>>>
>>>>> Awesome. The thing with non-incremental updates is that the basic
>>>>> algorithm
>>>>> would be to just look for updates to the view and on update, delete the
>>>>> review DB, create a new one, and then dump the new data into it. I
>>>>> wouldn't
>>>>> try too hard for the optimizing updates at this point in time.
>>>>>
>>>>> Getting a ruby script out to show the basics should probably be the
>>>>> first
>>>>> step. Beyond that we'll have to take it a step at a time.
>>>>>
>>>>> HTH,
>>>>> Paul Davis
>>>>>
>>>>>
>>>>> Zachary Zolton wrote:
>>>>>
>>>>>
>>>>>>
>>>>>> @jchris et al,
>>>>>>
>>>>>> if you had any pointer, on how to implement this, i have a strong
>>>>>> motivation to try my hand at it.
>>>>>>
>>>>>> i have a janky ruby script running as an update notifier that looks
>>>>>> for certain criteria, idiomatic to my data, that puts docs into a
>>>>>> derived database. but i'm not terribly happy with my current
>>>>>> implementation...
>>>>>>
>>>>>> is there a general-purpose algorithm for dealing with updates?
>>>>>>
>>>>>>
>>>>>> cheers,
>>>>>>
>>>>>> zach
>>>>>>
>>>>>>
>>>>>> On Sun, Apr 26, 2009 at 10:20 PM, Chris Anderson <jc...@gmail.com>
>>>>>> wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>>>
>>>>>>> Sent from my iPhone
>>>>>>>
>>>>>>> On Apr 26, 2009, at 2:26 PM, Wout Mertens <wo...@gmail.com>
>>>>>>> wrote:
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>>
>>>>>>>> Hi Adam,
>>>>>>>>
>>>>>>>> On Apr 22, 2009, at 4:48 PM, Adam Kocoloski wrote:
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>
>>>>>>>>> Hi Wout, thanks for writing this up.
>>>>>>>>>
>>>>>>>>> One comment about the map-only views:  I think you'll find that
>>>>>>>>> Couch
>>>>>>>>> has
>>>>>>>>> already done a good bit of the work needed to support them, too.
>>>>>>>>>  Couch
>>>>>>>>> maintains a btree for each design doc keyed on docid that stores
>>>>>>>>> all
>>>>>>>>> the
>>>>>>>>> view keys emitted by the maps over each document.  When a document
>>>>>>>>> is
>>>>>>>>> updated and then analyzed, Couch has to consult that btree, purge
>>>>>>>>> all
>>>>>>>>> the
>>>>>>>>> KVs associated with the old version of the doc from each view, and
>>>>>>>>> then
>>>>>>>>> insert the new KVs.  So the tracking information correlating docids
>>>>>>>>> and
>>>>>>>>> view
>>>>>>>>> keys is already available.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>> See I did not know that :-) Although I should have guessed.
>>>>>>>>
>>>>>>>> However, in the mail before this one I argued that it doesn't make
>>>>>>>> sense
>>>>>>>> to combine or chain map-only views since you can always write a map
>>>>>>>> function
>>>>>>>> that does it in one step. Do you agree?
>>>>>>>>
>>>>>>>> You might also know the answer to this: is it possible to make the
>>>>>>>> Review
>>>>>>>> DB be a sort of view index on the current database? All it needs are
>>>>>>>> JSON
>>>>>>>> keys and values, no other fields.
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>
>>>>>>>>> You'd still be left with the problem of generating unique docids
>>>>>>>>> for
>>>>>>>>> the
>>>>>>>>> documents in the Review DB, but I think that's a problem that needs
>>>>>>>>> to
>>>>>>>>> be
>>>>>>>>> solved.  The restriction to only MR views with no duplicate keys
>>>>>>>>> across
>>>>>>>>> views seems too strong to me.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>> Well, since the Review DB is a local(*) hidden database that's
>>>>>>>> handled
>>>>>>>> a
>>>>>>>> bit specially, I think the easiest is to assign _id a sequence
>>>>>>>> number
>>>>>>>> and
>>>>>>>> create a default view that indexes the documents by doc.key (for
>>>>>>>> updating
>>>>>>>> the value for that key). There will never be contention and we're
>>>>>>>> only
>>>>>>>> interested in the key index.
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>> We discussed this a little at CouchHack and I argued that the
>>>>>>> simplest
>>>>>>> solution is actually good for a few reasons.
>>>>>>>
>>>>>>> The simple solution: provide a mechanism to copy the rows of a
>>>>>>> grouped
>>>>>>> reduce function to a new database.
>>>>>>>
>>>>>>> Good because it is most like Hadoop/Google style map reduce. In that
>>>>>>> paradigm, the output of a map/reduce job is not incremental, and it
>>>>>>> is
>>>>>>> persisted in a way that allows for multiple later reduce stages to be
>>>>>>> run
>>>>>>> on
>>>>>>> it. It's common in Hadoop to chain many m/r stages, and to try a few
>>>>>>> iterations of each stage while developing code.
>>>>>>>
>>>>>>> I like this also because it provides the needed functionality without
>>>>>>> adding
>>>>>>> any new primitives to CouchDB.
>>>>>>>
>>>>>>> The only downside of this approach is that it is not incremental. I'm
>>>>>>> not
>>>>>>> sure that incremental chainability has much promise, as the index
>>>>>>> management
>>>>>>> could be a pain, especially if you have branching chains.
>>>>>>>
>>>>>>> Another upside is that by reducing to a db, you give the user power
>>>>>>> to
>>>>>>> do
>>>>>>> things like use replication to merge multiple data sets before
>>>>>>> applying
>>>>>>> more
>>>>>>> views.
>>>>>>>
>>>>>>> I don't want to discourage anyone from experimenting with code, just
>>>>>>> want
>>>>>>> to
>>>>>>> point out this simple solution which would be Very Easy to implement.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>>
>>>>>>>> (*)local: I'm assuming that views are not replicated and need to be
>>>>>>>> recalculated for each CouchDB node. If they are replicated somehow,
>>>>>>>> I
>>>>>>>> think
>>>>>>>> it would still work but we'd have to look at it a little more.
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>
>>>>>>>>> With that said, I'd prefer to spend my time extending the view
>>>>>>>>> engine
>>>>>>>>> to
>>>>>>>>> handle chainable MR workflows in a single shot.  Especially in the
>>>>>>>>> simple
>>>>>>>>> sort_by_value case it just seems like a cleaner way to go about
>>>>>>>>> things.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>> Yes, that seems to be the gist of all repliers and I agree :-)
>>>>>>>>
>>>>>>>> In a nutshell, I'm hoping that:
>>>>>>>> * A review is a new sort of view that has an "inputs" array in its
>>>>>>>> definition.
>>>>>>>> * Only MR views are allowed as inputs, no KV duplication allowed.
>>>>>>>> * It builds a persistent index of the incoming views when those get
>>>>>>>> updated.
>>>>>>>> * That index is then used to build the view index for the review
>>>>>>>> when
>>>>>>>> the
>>>>>>>> review gets updated.
>>>>>>>> * I think I covered the most important algorithms needed to
>>>>>>>> implement
>>>>>>>> this
>>>>>>>> in my original proposal.
>>>>>>>>
>>>>>>>> Does this sound feasible? If so I'll update my proposal accordingly.
>>>>>>>>
>>>>>>>> Wout.
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>
>>>>>
>>>
>>>
>
>

Re: Proposal: Review DBs

[Paul Davis <pa...@gmail.com>]

Zachary,

Hmm. Naming your derived databases as base_db-stage-etag doesn't sound 
like a bad idea. Though I dunno how you'd communicate to clients to 
start hitting the new versions and also doesn't tell the admins when to 
drop old indices.

The only thing that comes to mind is to stick some intermediary in 
between clients and the actual derived data to make it transparent and 
also to allow you to know when you can clean up old versions etc.

I'll keep thinking on it.

Paul

Zachary Zolton wrote:
> okay, i'm starting to get ya. my question is, if i'm constantly
> dropping/recreating/reindexing the derived database, how can i keep
> serving requests from my website?
>
> one possible solution would be to time/etag/etc-stamp the derived db
> name, but that would seem to add a number of moving parts to my
> system.
>
> hmm... any ideas of how to pull a quick switcheroo on the backend of
> my system, without too much hassle in the client code?
>
> On Mon, Apr 27, 2009 at 1:44 PM, Paul Davis <pa...@gmail.com> wrote:
>   
>> Zachary,
>>
>> No worries, the rough outline I'd do here is something like:
>>
>> 1. Figure out some member structure in the _design document that will
>> represent your data flow. For them moment I would do something extremely
>> simple as in:
>>
>> Assume:
>> db_name = "base_db"
>>
>> {
>>   "_id":  " _design/base",
>>   "views": {
>>       "stage-1": {
>>           "map": "function(doc) ...",
>>           "reduce": "function(keys, values, rereduce) ..."
>>       }
>>   },
>>   "review": [
>>       {"map": "function(doc) ...", "reduce": "function(keys, vals, rereduce)
>> ..."},
>>       {"map": "function(doc) ...", "reduce": "function(keys, vals, rereduce)
>> ..."}
>>   ]
>> }
>>
>> So the review member becomes the stages in your data flow. I'm avoiding any
>> forking or merging in this example in honor of the "make it work, make it
>> not suck" development flow.
>>
>> Now the basic algorithm would be something like:
>>
>> For each array element in the "review" member, create a db something like:
>>
>> base_db-stage-1 with a design document that contains a view with the first
>> element of the "reviews" member.
>> base_db-stage-2 with the second member and so on.
>>
>> Then your script can check the view status in each database either with a
>> cron (or an update_notifier) to do so, you can just:
>>
>> HEAD /base_db/_design/base/_view/stage-1
>>
>> And then check the returned ETag. For the moment this is exactly equivalent
>> to checking the database's update_seq because of how the etag is calculated,
>> but in the future when we track the last update_seq for each view change
>> this will be a free upgrade. Plus there's a bit more logical-ness to
>> checking "view state" instead of "db state".
>>
>> When the etag's don't match, you can just drop the next db in the flow,
>> create it, and then copy the view output. The drop/create just makes the
>> algorithm easily implementable for now. In the future there can be some
>> extra logic to only change the new view as far as it requires by iterating
>> over the two views and doing a merge sortish type of thing. I think...
>> Sounds like there should be a way at least.
>>
>> Once that works we can look at bolting on different fancy things like having
>> forking map/reduce mechanisms and my current pet idea of adding in the merge
>> stuff that has been talked about.
>>
>> This is actually starting to sound like a fun little project....
>>
>> HTH,
>> Paul Davis
>>
>> Zachary Zolton wrote:
>>     
>>> paul
>>>
>>> alright... you've gotta give me the remedial explanation of what you
>>> meant here! (sorry, i'm still noob-ish)
>>>
>>> so, are you saying that i shouldn't even check for individual doc
>>> updates, but instead just recreate the entire database? that sounds
>>> like a job for cron, more so than the update notifier, right?
>>>
>>> i'd put up my current ruby script, but it deals update notifications
>>> in a way that's very specific to my data —probably very naïvely, to
>>> boot!
>>>
>>> zach
>>>
>>> On Mon, Apr 27, 2009 at 11:28 AM, Paul Davis
>>> <pa...@gmail.com> wrote:
>>>
>>>       
>>>> Zachary,
>>>>
>>>> Awesome. The thing with non-incremental updates is that the basic
>>>> algorithm
>>>> would be to just look for updates to the view and on update, delete the
>>>> review DB, create a new one, and then dump the new data into it. I
>>>> wouldn't
>>>> try too hard for the optimizing updates at this point in time.
>>>>
>>>> Getting a ruby script out to show the basics should probably be the first
>>>> step. Beyond that we'll have to take it a step at a time.
>>>>
>>>> HTH,
>>>> Paul Davis
>>>>
>>>>
>>>> Zachary Zolton wrote:
>>>>
>>>>         
>>>>> @jchris et al,
>>>>>
>>>>> if you had any pointer, on how to implement this, i have a strong
>>>>> motivation to try my hand at it.
>>>>>
>>>>> i have a janky ruby script running as an update notifier that looks
>>>>> for certain criteria, idiomatic to my data, that puts docs into a
>>>>> derived database. but i'm not terribly happy with my current
>>>>> implementation...
>>>>>
>>>>> is there a general-purpose algorithm for dealing with updates?
>>>>>
>>>>>
>>>>> cheers,
>>>>>
>>>>> zach
>>>>>
>>>>>
>>>>> On Sun, Apr 26, 2009 at 10:20 PM, Chris Anderson <jc...@gmail.com>
>>>>> wrote:
>>>>>
>>>>>
>>>>>           
>>>>>> Sent from my iPhone
>>>>>>
>>>>>> On Apr 26, 2009, at 2:26 PM, Wout Mertens <wo...@gmail.com>
>>>>>> wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>>             
>>>>>>> Hi Adam,
>>>>>>>
>>>>>>> On Apr 22, 2009, at 4:48 PM, Adam Kocoloski wrote:
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>               
>>>>>>>> Hi Wout, thanks for writing this up.
>>>>>>>>
>>>>>>>> One comment about the map-only views:  I think you'll find that Couch
>>>>>>>> has
>>>>>>>> already done a good bit of the work needed to support them, too.
>>>>>>>>  Couch
>>>>>>>> maintains a btree for each design doc keyed on docid that stores all
>>>>>>>> the
>>>>>>>> view keys emitted by the maps over each document.  When a document is
>>>>>>>> updated and then analyzed, Couch has to consult that btree, purge all
>>>>>>>> the
>>>>>>>> KVs associated with the old version of the doc from each view, and
>>>>>>>> then
>>>>>>>> insert the new KVs.  So the tracking information correlating docids
>>>>>>>> and
>>>>>>>> view
>>>>>>>> keys is already available.
>>>>>>>>
>>>>>>>>
>>>>>>>>                 
>>>>>>> See I did not know that :-) Although I should have guessed.
>>>>>>>
>>>>>>> However, in the mail before this one I argued that it doesn't make
>>>>>>> sense
>>>>>>> to combine or chain map-only views since you can always write a map
>>>>>>> function
>>>>>>> that does it in one step. Do you agree?
>>>>>>>
>>>>>>> You might also know the answer to this: is it possible to make the
>>>>>>> Review
>>>>>>> DB be a sort of view index on the current database? All it needs are
>>>>>>> JSON
>>>>>>> keys and values, no other fields.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>               
>>>>>>>> You'd still be left with the problem of generating unique docids for
>>>>>>>> the
>>>>>>>> documents in the Review DB, but I think that's a problem that needs
>>>>>>>> to
>>>>>>>> be
>>>>>>>> solved.  The restriction to only MR views with no duplicate keys
>>>>>>>> across
>>>>>>>> views seems too strong to me.
>>>>>>>>
>>>>>>>>
>>>>>>>>                 
>>>>>>> Well, since the Review DB is a local(*) hidden database that's handled
>>>>>>> a
>>>>>>> bit specially, I think the easiest is to assign _id a sequence number
>>>>>>> and
>>>>>>> create a default view that indexes the documents by doc.key (for
>>>>>>> updating
>>>>>>> the value for that key). There will never be contention and we're only
>>>>>>> interested in the key index.
>>>>>>>
>>>>>>>
>>>>>>>               
>>>>>> We discussed this a little at CouchHack and I argued that the simplest
>>>>>> solution is actually good for a few reasons.
>>>>>>
>>>>>> The simple solution: provide a mechanism to copy the rows of a grouped
>>>>>> reduce function to a new database.
>>>>>>
>>>>>> Good because it is most like Hadoop/Google style map reduce. In that
>>>>>> paradigm, the output of a map/reduce job is not incremental, and it is
>>>>>> persisted in a way that allows for multiple later reduce stages to be
>>>>>> run
>>>>>> on
>>>>>> it. It's common in Hadoop to chain many m/r stages, and to try a few
>>>>>> iterations of each stage while developing code.
>>>>>>
>>>>>> I like this also because it provides the needed functionality without
>>>>>> adding
>>>>>> any new primitives to CouchDB.
>>>>>>
>>>>>> The only downside of this approach is that it is not incremental. I'm
>>>>>> not
>>>>>> sure that incremental chainability has much promise, as the index
>>>>>> management
>>>>>> could be a pain, especially if you have branching chains.
>>>>>>
>>>>>> Another upside is that by reducing to a db, you give the user power to
>>>>>> do
>>>>>> things like use replication to merge multiple data sets before applying
>>>>>> more
>>>>>> views.
>>>>>>
>>>>>> I don't want to discourage anyone from experimenting with code, just
>>>>>> want
>>>>>> to
>>>>>> point out this simple solution which would be Very Easy to implement.
>>>>>>
>>>>>>
>>>>>>
>>>>>>             
>>>>>>> (*)local: I'm assuming that views are not replicated and need to be
>>>>>>> recalculated for each CouchDB node. If they are replicated somehow, I
>>>>>>> think
>>>>>>> it would still work but we'd have to look at it a little more.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>               
>>>>>>>> With that said, I'd prefer to spend my time extending the view engine
>>>>>>>> to
>>>>>>>> handle chainable MR workflows in a single shot.  Especially in the
>>>>>>>> simple
>>>>>>>> sort_by_value case it just seems like a cleaner way to go about
>>>>>>>> things.
>>>>>>>>
>>>>>>>>
>>>>>>>>                 
>>>>>>> Yes, that seems to be the gist of all repliers and I agree :-)
>>>>>>>
>>>>>>> In a nutshell, I'm hoping that:
>>>>>>> * A review is a new sort of view that has an "inputs" array in its
>>>>>>> definition.
>>>>>>> * Only MR views are allowed as inputs, no KV duplication allowed.
>>>>>>> * It builds a persistent index of the incoming views when those get
>>>>>>> updated.
>>>>>>> * That index is then used to build the view index for the review when
>>>>>>> the
>>>>>>> review gets updated.
>>>>>>> * I think I covered the most important algorithms needed to implement
>>>>>>> this
>>>>>>> in my original proposal.
>>>>>>>
>>>>>>> Does this sound feasible? If so I'll update my proposal accordingly.
>>>>>>>
>>>>>>> Wout.
>>>>>>>
>>>>>>>
>>>>>>>               
>>>>         
>>     

Re: Proposal: Review DBs

[Zachary Zolton <za...@gmail.com>]

okay, i'm starting to get ya. my question is, if i'm constantly
dropping/recreating/reindexing the derived database, how can i keep
serving requests from my website?

one possible solution would be to time/etag/etc-stamp the derived db
name, but that would seem to add a number of moving parts to my
system.

hmm... any ideas of how to pull a quick switcheroo on the backend of
my system, without too much hassle in the client code?

On Mon, Apr 27, 2009 at 1:44 PM, Paul Davis <pa...@gmail.com> wrote:
> Zachary,
>
> No worries, the rough outline I'd do here is something like:
>
> 1. Figure out some member structure in the _design document that will
> represent your data flow. For them moment I would do something extremely
> simple as in:
>
> Assume:
> db_name = "base_db"
>
> {
>   "_id":  " _design/base",
>   "views": {
>       "stage-1": {
>           "map": "function(doc) ...",
>           "reduce": "function(keys, values, rereduce) ..."
>       }
>   },
>   "review": [
>       {"map": "function(doc) ...", "reduce": "function(keys, vals, rereduce)
> ..."},
>       {"map": "function(doc) ...", "reduce": "function(keys, vals, rereduce)
> ..."}
>   ]
> }
>
> So the review member becomes the stages in your data flow. I'm avoiding any
> forking or merging in this example in honor of the "make it work, make it
> not suck" development flow.
>
> Now the basic algorithm would be something like:
>
> For each array element in the "review" member, create a db something like:
>
> base_db-stage-1 with a design document that contains a view with the first
> element of the "reviews" member.
> base_db-stage-2 with the second member and so on.
>
> Then your script can check the view status in each database either with a
> cron (or an update_notifier) to do so, you can just:
>
> HEAD /base_db/_design/base/_view/stage-1
>
> And then check the returned ETag. For the moment this is exactly equivalent
> to checking the database's update_seq because of how the etag is calculated,
> but in the future when we track the last update_seq for each view change
> this will be a free upgrade. Plus there's a bit more logical-ness to
> checking "view state" instead of "db state".
>
> When the etag's don't match, you can just drop the next db in the flow,
> create it, and then copy the view output. The drop/create just makes the
> algorithm easily implementable for now. In the future there can be some
> extra logic to only change the new view as far as it requires by iterating
> over the two views and doing a merge sortish type of thing. I think...
> Sounds like there should be a way at least.
>
> Once that works we can look at bolting on different fancy things like having
> forking map/reduce mechanisms and my current pet idea of adding in the merge
> stuff that has been talked about.
>
> This is actually starting to sound like a fun little project....
>
> HTH,
> Paul Davis
>
> Zachary Zolton wrote:
>>
>> paul
>>
>> alright... you've gotta give me the remedial explanation of what you
>> meant here! (sorry, i'm still noob-ish)
>>
>> so, are you saying that i shouldn't even check for individual doc
>> updates, but instead just recreate the entire database? that sounds
>> like a job for cron, more so than the update notifier, right?
>>
>> i'd put up my current ruby script, but it deals update notifications
>> in a way that's very specific to my data —probably very naïvely, to
>> boot!
>>
>> zach
>>
>> On Mon, Apr 27, 2009 at 11:28 AM, Paul Davis
>> <pa...@gmail.com> wrote:
>>
>>>
>>> Zachary,
>>>
>>> Awesome. The thing with non-incremental updates is that the basic
>>> algorithm
>>> would be to just look for updates to the view and on update, delete the
>>> review DB, create a new one, and then dump the new data into it. I
>>> wouldn't
>>> try too hard for the optimizing updates at this point in time.
>>>
>>> Getting a ruby script out to show the basics should probably be the first
>>> step. Beyond that we'll have to take it a step at a time.
>>>
>>> HTH,
>>> Paul Davis
>>>
>>>
>>> Zachary Zolton wrote:
>>>
>>>>
>>>> @jchris et al,
>>>>
>>>> if you had any pointer, on how to implement this, i have a strong
>>>> motivation to try my hand at it.
>>>>
>>>> i have a janky ruby script running as an update notifier that looks
>>>> for certain criteria, idiomatic to my data, that puts docs into a
>>>> derived database. but i'm not terribly happy with my current
>>>> implementation...
>>>>
>>>> is there a general-purpose algorithm for dealing with updates?
>>>>
>>>>
>>>> cheers,
>>>>
>>>> zach
>>>>
>>>>
>>>> On Sun, Apr 26, 2009 at 10:20 PM, Chris Anderson <jc...@gmail.com>
>>>> wrote:
>>>>
>>>>
>>>>>
>>>>> Sent from my iPhone
>>>>>
>>>>> On Apr 26, 2009, at 2:26 PM, Wout Mertens <wo...@gmail.com>
>>>>> wrote:
>>>>>
>>>>>
>>>>>
>>>>>>
>>>>>> Hi Adam,
>>>>>>
>>>>>> On Apr 22, 2009, at 4:48 PM, Adam Kocoloski wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>>>
>>>>>>> Hi Wout, thanks for writing this up.
>>>>>>>
>>>>>>> One comment about the map-only views:  I think you'll find that Couch
>>>>>>> has
>>>>>>> already done a good bit of the work needed to support them, too.
>>>>>>>  Couch
>>>>>>> maintains a btree for each design doc keyed on docid that stores all
>>>>>>> the
>>>>>>> view keys emitted by the maps over each document.  When a document is
>>>>>>> updated and then analyzed, Couch has to consult that btree, purge all
>>>>>>> the
>>>>>>> KVs associated with the old version of the doc from each view, and
>>>>>>> then
>>>>>>> insert the new KVs.  So the tracking information correlating docids
>>>>>>> and
>>>>>>> view
>>>>>>> keys is already available.
>>>>>>>
>>>>>>>
>>>>>>
>>>>>> See I did not know that :-) Although I should have guessed.
>>>>>>
>>>>>> However, in the mail before this one I argued that it doesn't make
>>>>>> sense
>>>>>> to combine or chain map-only views since you can always write a map
>>>>>> function
>>>>>> that does it in one step. Do you agree?
>>>>>>
>>>>>> You might also know the answer to this: is it possible to make the
>>>>>> Review
>>>>>> DB be a sort of view index on the current database? All it needs are
>>>>>> JSON
>>>>>> keys and values, no other fields.
>>>>>>
>>>>>>
>>>>>>
>>>>>>>
>>>>>>> You'd still be left with the problem of generating unique docids for
>>>>>>> the
>>>>>>> documents in the Review DB, but I think that's a problem that needs
>>>>>>> to
>>>>>>> be
>>>>>>> solved.  The restriction to only MR views with no duplicate keys
>>>>>>> across
>>>>>>> views seems too strong to me.
>>>>>>>
>>>>>>>
>>>>>>
>>>>>> Well, since the Review DB is a local(*) hidden database that's handled
>>>>>> a
>>>>>> bit specially, I think the easiest is to assign _id a sequence number
>>>>>> and
>>>>>> create a default view that indexes the documents by doc.key (for
>>>>>> updating
>>>>>> the value for that key). There will never be contention and we're only
>>>>>> interested in the key index.
>>>>>>
>>>>>>
>>>>>
>>>>> We discussed this a little at CouchHack and I argued that the simplest
>>>>> solution is actually good for a few reasons.
>>>>>
>>>>> The simple solution: provide a mechanism to copy the rows of a grouped
>>>>> reduce function to a new database.
>>>>>
>>>>> Good because it is most like Hadoop/Google style map reduce. In that
>>>>> paradigm, the output of a map/reduce job is not incremental, and it is
>>>>> persisted in a way that allows for multiple later reduce stages to be
>>>>> run
>>>>> on
>>>>> it. It's common in Hadoop to chain many m/r stages, and to try a few
>>>>> iterations of each stage while developing code.
>>>>>
>>>>> I like this also because it provides the needed functionality without
>>>>> adding
>>>>> any new primitives to CouchDB.
>>>>>
>>>>> The only downside of this approach is that it is not incremental. I'm
>>>>> not
>>>>> sure that incremental chainability has much promise, as the index
>>>>> management
>>>>> could be a pain, especially if you have branching chains.
>>>>>
>>>>> Another upside is that by reducing to a db, you give the user power to
>>>>> do
>>>>> things like use replication to merge multiple data sets before applying
>>>>> more
>>>>> views.
>>>>>
>>>>> I don't want to discourage anyone from experimenting with code, just
>>>>> want
>>>>> to
>>>>> point out this simple solution which would be Very Easy to implement.
>>>>>
>>>>>
>>>>>
>>>>>>
>>>>>> (*)local: I'm assuming that views are not replicated and need to be
>>>>>> recalculated for each CouchDB node. If they are replicated somehow, I
>>>>>> think
>>>>>> it would still work but we'd have to look at it a little more.
>>>>>>
>>>>>>
>>>>>>
>>>>>>>
>>>>>>> With that said, I'd prefer to spend my time extending the view engine
>>>>>>> to
>>>>>>> handle chainable MR workflows in a single shot.  Especially in the
>>>>>>> simple
>>>>>>> sort_by_value case it just seems like a cleaner way to go about
>>>>>>> things.
>>>>>>>
>>>>>>>
>>>>>>
>>>>>> Yes, that seems to be the gist of all repliers and I agree :-)
>>>>>>
>>>>>> In a nutshell, I'm hoping that:
>>>>>> * A review is a new sort of view that has an "inputs" array in its
>>>>>> definition.
>>>>>> * Only MR views are allowed as inputs, no KV duplication allowed.
>>>>>> * It builds a persistent index of the incoming views when those get
>>>>>> updated.
>>>>>> * That index is then used to build the view index for the review when
>>>>>> the
>>>>>> review gets updated.
>>>>>> * I think I covered the most important algorithms needed to implement
>>>>>> this
>>>>>> in my original proposal.
>>>>>>
>>>>>> Does this sound feasible? If so I'll update my proposal accordingly.
>>>>>>
>>>>>> Wout.
>>>>>>
>>>>>>
>>>
>>>
>
>

Re: Proposal: Review DBs

[Paul Davis <pa...@gmail.com>]

Zachary,

No worries, the rough outline I'd do here is something like:

1. Figure out some member structure in the _design document that will 
represent your data flow. For them moment I would do something extremely 
simple as in:

Assume:
db_name = "base_db"

{
    "_id":  " _design/base",
    "views": {
        "stage-1": {
            "map": "function(doc) ...",
            "reduce": "function(keys, values, rereduce) ..."
        }
    },
    "review": [
        {"map": "function(doc) ...", "reduce": "function(keys, vals, 
rereduce) ..."},
        {"map": "function(doc) ...", "reduce": "function(keys, vals, 
rereduce) ..."}
    ]
}

So the review member becomes the stages in your data flow. I'm avoiding 
any forking or merging in this example in honor of the "make it work, 
make it not suck" development flow.

Now the basic algorithm would be something like:

For each array element in the "review" member, create a db something like:

base_db-stage-1 with a design document that contains a view with the 
first element of the "reviews" member.
base_db-stage-2 with the second member and so on.

Then your script can check the view status in each database either with 
a cron (or an update_notifier) to do so, you can just:

HEAD /base_db/_design/base/_view/stage-1

And then check the returned ETag. For the moment this is exactly 
equivalent to checking the database's update_seq because of how the etag 
is calculated, but in the future when we track the last update_seq for 
each view change this will be a free upgrade. Plus there's a bit more 
logical-ness to checking "view state" instead of "db state".

When the etag's don't match, you can just drop the next db in the flow, 
create it, and then copy the view output. The drop/create just makes the 
algorithm easily implementable for now. In the future there can be some 
extra logic to only change the new view as far as it requires by 
iterating over the two views and doing a merge sortish type of thing. I 
think... Sounds like there should be a way at least.

Once that works we can look at bolting on different fancy things like 
having forking map/reduce mechanisms and my current pet idea of adding 
in the merge stuff that has been talked about.

This is actually starting to sound like a fun little project....

HTH,
Paul Davis

Zachary Zolton wrote:
> paul
>
> alright... you've gotta give me the remedial explanation of what you
> meant here! (sorry, i'm still noob-ish)
>
> so, are you saying that i shouldn't even check for individual doc
> updates, but instead just recreate the entire database? that sounds
> like a job for cron, more so than the update notifier, right?
>
> i'd put up my current ruby script, but it deals update notifications
> in a way that's very specific to my data —probably very naïvely, to
> boot!
>
> zach
>
> On Mon, Apr 27, 2009 at 11:28 AM, Paul Davis
> <pa...@gmail.com> wrote:
>   
>> Zachary,
>>
>> Awesome. The thing with non-incremental updates is that the basic algorithm
>> would be to just look for updates to the view and on update, delete the
>> review DB, create a new one, and then dump the new data into it. I wouldn't
>> try too hard for the optimizing updates at this point in time.
>>
>> Getting a ruby script out to show the basics should probably be the first
>> step. Beyond that we'll have to take it a step at a time.
>>
>> HTH,
>> Paul Davis
>>
>>
>> Zachary Zolton wrote:
>>     
>>> @jchris et al,
>>>
>>> if you had any pointer, on how to implement this, i have a strong
>>> motivation to try my hand at it.
>>>
>>> i have a janky ruby script running as an update notifier that looks
>>> for certain criteria, idiomatic to my data, that puts docs into a
>>> derived database. but i'm not terribly happy with my current
>>> implementation...
>>>
>>> is there a general-purpose algorithm for dealing with updates?
>>>
>>>
>>> cheers,
>>>
>>> zach
>>>
>>>
>>> On Sun, Apr 26, 2009 at 10:20 PM, Chris Anderson <jc...@gmail.com> wrote:
>>>
>>>       
>>>> Sent from my iPhone
>>>>
>>>> On Apr 26, 2009, at 2:26 PM, Wout Mertens <wo...@gmail.com> wrote:
>>>>
>>>>
>>>>         
>>>>> Hi Adam,
>>>>>
>>>>> On Apr 22, 2009, at 4:48 PM, Adam Kocoloski wrote:
>>>>>
>>>>>
>>>>>           
>>>>>> Hi Wout, thanks for writing this up.
>>>>>>
>>>>>> One comment about the map-only views:  I think you'll find that Couch
>>>>>> has
>>>>>> already done a good bit of the work needed to support them, too.  Couch
>>>>>> maintains a btree for each design doc keyed on docid that stores all
>>>>>> the
>>>>>> view keys emitted by the maps over each document.  When a document is
>>>>>> updated and then analyzed, Couch has to consult that btree, purge all
>>>>>> the
>>>>>> KVs associated with the old version of the doc from each view, and then
>>>>>> insert the new KVs.  So the tracking information correlating docids and
>>>>>> view
>>>>>> keys is already available.
>>>>>>
>>>>>>             
>>>>> See I did not know that :-) Although I should have guessed.
>>>>>
>>>>> However, in the mail before this one I argued that it doesn't make sense
>>>>> to combine or chain map-only views since you can always write a map
>>>>> function
>>>>> that does it in one step. Do you agree?
>>>>>
>>>>> You might also know the answer to this: is it possible to make the
>>>>> Review
>>>>> DB be a sort of view index on the current database? All it needs are
>>>>> JSON
>>>>> keys and values, no other fields.
>>>>>
>>>>>
>>>>>           
>>>>>> You'd still be left with the problem of generating unique docids for
>>>>>> the
>>>>>> documents in the Review DB, but I think that's a problem that needs to
>>>>>> be
>>>>>> solved.  The restriction to only MR views with no duplicate keys across
>>>>>> views seems too strong to me.
>>>>>>
>>>>>>             
>>>>> Well, since the Review DB is a local(*) hidden database that's handled a
>>>>> bit specially, I think the easiest is to assign _id a sequence number
>>>>> and
>>>>> create a default view that indexes the documents by doc.key (for
>>>>> updating
>>>>> the value for that key). There will never be contention and we're only
>>>>> interested in the key index.
>>>>>
>>>>>           
>>>> We discussed this a little at CouchHack and I argued that the simplest
>>>> solution is actually good for a few reasons.
>>>>
>>>> The simple solution: provide a mechanism to copy the rows of a grouped
>>>> reduce function to a new database.
>>>>
>>>> Good because it is most like Hadoop/Google style map reduce. In that
>>>> paradigm, the output of a map/reduce job is not incremental, and it is
>>>> persisted in a way that allows for multiple later reduce stages to be run
>>>> on
>>>> it. It's common in Hadoop to chain many m/r stages, and to try a few
>>>> iterations of each stage while developing code.
>>>>
>>>> I like this also because it provides the needed functionality without
>>>> adding
>>>> any new primitives to CouchDB.
>>>>
>>>> The only downside of this approach is that it is not incremental. I'm not
>>>> sure that incremental chainability has much promise, as the index
>>>> management
>>>> could be a pain, especially if you have branching chains.
>>>>
>>>> Another upside is that by reducing to a db, you give the user power to do
>>>> things like use replication to merge multiple data sets before applying
>>>> more
>>>> views.
>>>>
>>>> I don't want to discourage anyone from experimenting with code, just want
>>>> to
>>>> point out this simple solution which would be Very Easy to implement.
>>>>
>>>>
>>>>         
>>>>> (*)local: I'm assuming that views are not replicated and need to be
>>>>> recalculated for each CouchDB node. If they are replicated somehow, I
>>>>> think
>>>>> it would still work but we'd have to look at it a little more.
>>>>>
>>>>>
>>>>>           
>>>>>> With that said, I'd prefer to spend my time extending the view engine
>>>>>> to
>>>>>> handle chainable MR workflows in a single shot.  Especially in the
>>>>>> simple
>>>>>> sort_by_value case it just seems like a cleaner way to go about things.
>>>>>>
>>>>>>             
>>>>> Yes, that seems to be the gist of all repliers and I agree :-)
>>>>>
>>>>> In a nutshell, I'm hoping that:
>>>>> * A review is a new sort of view that has an "inputs" array in its
>>>>> definition.
>>>>> * Only MR views are allowed as inputs, no KV duplication allowed.
>>>>> * It builds a persistent index of the incoming views when those get
>>>>> updated.
>>>>> * That index is then used to build the view index for the review when
>>>>> the
>>>>> review gets updated.
>>>>> * I think I covered the most important algorithms needed to implement
>>>>> this
>>>>> in my original proposal.
>>>>>
>>>>> Does this sound feasible? If so I'll update my proposal accordingly.
>>>>>
>>>>> Wout.
>>>>>
>>>>>           
>>     

Re: Proposal: Review DBs

[Zachary Zolton <za...@gmail.com>]

paul

alright... you've gotta give me the remedial explanation of what you
meant here! (sorry, i'm still noob-ish)

so, are you saying that i shouldn't even check for individual doc
updates, but instead just recreate the entire database? that sounds
like a job for cron, more so than the update notifier, right?

i'd put up my current ruby script, but it deals update notifications
in a way that's very specific to my data —probably very naïvely, to
boot!

zach

On Mon, Apr 27, 2009 at 11:28 AM, Paul Davis
<pa...@gmail.com> wrote:
> Zachary,
>
> Awesome. The thing with non-incremental updates is that the basic algorithm
> would be to just look for updates to the view and on update, delete the
> review DB, create a new one, and then dump the new data into it. I wouldn't
> try too hard for the optimizing updates at this point in time.
>
> Getting a ruby script out to show the basics should probably be the first
> step. Beyond that we'll have to take it a step at a time.
>
> HTH,
> Paul Davis
>
>
> Zachary Zolton wrote:
>>
>> @jchris et al,
>>
>> if you had any pointer, on how to implement this, i have a strong
>> motivation to try my hand at it.
>>
>> i have a janky ruby script running as an update notifier that looks
>> for certain criteria, idiomatic to my data, that puts docs into a
>> derived database. but i'm not terribly happy with my current
>> implementation...
>>
>> is there a general-purpose algorithm for dealing with updates?
>>
>>
>> cheers,
>>
>> zach
>>
>>
>> On Sun, Apr 26, 2009 at 10:20 PM, Chris Anderson <jc...@gmail.com> wrote:
>>
>>>
>>> Sent from my iPhone
>>>
>>> On Apr 26, 2009, at 2:26 PM, Wout Mertens <wo...@gmail.com> wrote:
>>>
>>>
>>>>
>>>> Hi Adam,
>>>>
>>>> On Apr 22, 2009, at 4:48 PM, Adam Kocoloski wrote:
>>>>
>>>>
>>>>>
>>>>> Hi Wout, thanks for writing this up.
>>>>>
>>>>> One comment about the map-only views:  I think you'll find that Couch
>>>>> has
>>>>> already done a good bit of the work needed to support them, too.  Couch
>>>>> maintains a btree for each design doc keyed on docid that stores all
>>>>> the
>>>>> view keys emitted by the maps over each document.  When a document is
>>>>> updated and then analyzed, Couch has to consult that btree, purge all
>>>>> the
>>>>> KVs associated with the old version of the doc from each view, and then
>>>>> insert the new KVs.  So the tracking information correlating docids and
>>>>> view
>>>>> keys is already available.
>>>>>
>>>>
>>>> See I did not know that :-) Although I should have guessed.
>>>>
>>>> However, in the mail before this one I argued that it doesn't make sense
>>>> to combine or chain map-only views since you can always write a map
>>>> function
>>>> that does it in one step. Do you agree?
>>>>
>>>> You might also know the answer to this: is it possible to make the
>>>> Review
>>>> DB be a sort of view index on the current database? All it needs are
>>>> JSON
>>>> keys and values, no other fields.
>>>>
>>>>
>>>>>
>>>>> You'd still be left with the problem of generating unique docids for
>>>>> the
>>>>> documents in the Review DB, but I think that's a problem that needs to
>>>>> be
>>>>> solved.  The restriction to only MR views with no duplicate keys across
>>>>> views seems too strong to me.
>>>>>
>>>>
>>>> Well, since the Review DB is a local(*) hidden database that's handled a
>>>> bit specially, I think the easiest is to assign _id a sequence number
>>>> and
>>>> create a default view that indexes the documents by doc.key (for
>>>> updating
>>>> the value for that key). There will never be contention and we're only
>>>> interested in the key index.
>>>>
>>>
>>> We discussed this a little at CouchHack and I argued that the simplest
>>> solution is actually good for a few reasons.
>>>
>>> The simple solution: provide a mechanism to copy the rows of a grouped
>>> reduce function to a new database.
>>>
>>> Good because it is most like Hadoop/Google style map reduce. In that
>>> paradigm, the output of a map/reduce job is not incremental, and it is
>>> persisted in a way that allows for multiple later reduce stages to be run
>>> on
>>> it. It's common in Hadoop to chain many m/r stages, and to try a few
>>> iterations of each stage while developing code.
>>>
>>> I like this also because it provides the needed functionality without
>>> adding
>>> any new primitives to CouchDB.
>>>
>>> The only downside of this approach is that it is not incremental. I'm not
>>> sure that incremental chainability has much promise, as the index
>>> management
>>> could be a pain, especially if you have branching chains.
>>>
>>> Another upside is that by reducing to a db, you give the user power to do
>>> things like use replication to merge multiple data sets before applying
>>> more
>>> views.
>>>
>>> I don't want to discourage anyone from experimenting with code, just want
>>> to
>>> point out this simple solution which would be Very Easy to implement.
>>>
>>>
>>>>
>>>> (*)local: I'm assuming that views are not replicated and need to be
>>>> recalculated for each CouchDB node. If they are replicated somehow, I
>>>> think
>>>> it would still work but we'd have to look at it a little more.
>>>>
>>>>
>>>>>
>>>>> With that said, I'd prefer to spend my time extending the view engine
>>>>> to
>>>>> handle chainable MR workflows in a single shot.  Especially in the
>>>>> simple
>>>>> sort_by_value case it just seems like a cleaner way to go about things.
>>>>>
>>>>
>>>> Yes, that seems to be the gist of all repliers and I agree :-)
>>>>
>>>> In a nutshell, I'm hoping that:
>>>> * A review is a new sort of view that has an "inputs" array in its
>>>> definition.
>>>> * Only MR views are allowed as inputs, no KV duplication allowed.
>>>> * It builds a persistent index of the incoming views when those get
>>>> updated.
>>>> * That index is then used to build the view index for the review when
>>>> the
>>>> review gets updated.
>>>> * I think I covered the most important algorithms needed to implement
>>>> this
>>>> in my original proposal.
>>>>
>>>> Does this sound feasible? If so I'll update my proposal accordingly.
>>>>
>>>> Wout.
>>>>
>
>

Re: Proposal: Review DBs

[Paul Davis <pa...@gmail.com>]

Zachary,

Awesome. The thing with non-incremental updates is that the basic 
algorithm would be to just look for updates to the view and on update, 
delete the review DB, create a new one, and then dump the new data into 
it. I wouldn't try too hard for the optimizing updates at this point in 
time.

Getting a ruby script out to show the basics should probably be the 
first step. Beyond that we'll have to take it a step at a time.

HTH,
Paul Davis


Zachary Zolton wrote:
> @jchris et al,
>
> if you had any pointer, on how to implement this, i have a strong
> motivation to try my hand at it.
>
> i have a janky ruby script running as an update notifier that looks
> for certain criteria, idiomatic to my data, that puts docs into a
> derived database. but i'm not terribly happy with my current
> implementation...
>
> is there a general-purpose algorithm for dealing with updates?
>
>
> cheers,
>
> zach
>
>
> On Sun, Apr 26, 2009 at 10:20 PM, Chris Anderson <jc...@gmail.com> wrote:
>   
>> Sent from my iPhone
>>
>> On Apr 26, 2009, at 2:26 PM, Wout Mertens <wo...@gmail.com> wrote:
>>
>>     
>>> Hi Adam,
>>>
>>> On Apr 22, 2009, at 4:48 PM, Adam Kocoloski wrote:
>>>
>>>       
>>>> Hi Wout, thanks for writing this up.
>>>>
>>>> One comment about the map-only views:  I think you'll find that Couch has
>>>> already done a good bit of the work needed to support them, too.  Couch
>>>> maintains a btree for each design doc keyed on docid that stores all the
>>>> view keys emitted by the maps over each document.  When a document is
>>>> updated and then analyzed, Couch has to consult that btree, purge all the
>>>> KVs associated with the old version of the doc from each view, and then
>>>> insert the new KVs.  So the tracking information correlating docids and view
>>>> keys is already available.
>>>>         
>>> See I did not know that :-) Although I should have guessed.
>>>
>>> However, in the mail before this one I argued that it doesn't make sense
>>> to combine or chain map-only views since you can always write a map function
>>> that does it in one step. Do you agree?
>>>
>>> You might also know the answer to this: is it possible to make the Review
>>> DB be a sort of view index on the current database? All it needs are JSON
>>> keys and values, no other fields.
>>>
>>>       
>>>> You'd still be left with the problem of generating unique docids for the
>>>> documents in the Review DB, but I think that's a problem that needs to be
>>>> solved.  The restriction to only MR views with no duplicate keys across
>>>> views seems too strong to me.
>>>>         
>>> Well, since the Review DB is a local(*) hidden database that's handled a
>>> bit specially, I think the easiest is to assign _id a sequence number and
>>> create a default view that indexes the documents by doc.key (for updating
>>> the value for that key). There will never be contention and we're only
>>> interested in the key index.
>>>       
>> We discussed this a little at CouchHack and I argued that the simplest
>> solution is actually good for a few reasons.
>>
>> The simple solution: provide a mechanism to copy the rows of a grouped
>> reduce function to a new database.
>>
>> Good because it is most like Hadoop/Google style map reduce. In that
>> paradigm, the output of a map/reduce job is not incremental, and it is
>> persisted in a way that allows for multiple later reduce stages to be run on
>> it. It's common in Hadoop to chain many m/r stages, and to try a few
>> iterations of each stage while developing code.
>>
>> I like this also because it provides the needed functionality without adding
>> any new primitives to CouchDB.
>>
>> The only downside of this approach is that it is not incremental. I'm not
>> sure that incremental chainability has much promise, as the index management
>> could be a pain, especially if you have branching chains.
>>
>> Another upside is that by reducing to a db, you give the user power to do
>> things like use replication to merge multiple data sets before applying more
>> views.
>>
>> I don't want to discourage anyone from experimenting with code, just want to
>> point out this simple solution which would be Very Easy to implement.
>>
>>     
>>> (*)local: I'm assuming that views are not replicated and need to be
>>> recalculated for each CouchDB node. If they are replicated somehow, I think
>>> it would still work but we'd have to look at it a little more.
>>>
>>>       
>>>> With that said, I'd prefer to spend my time extending the view engine to
>>>> handle chainable MR workflows in a single shot.  Especially in the simple
>>>> sort_by_value case it just seems like a cleaner way to go about things.
>>>>         
>>> Yes, that seems to be the gist of all repliers and I agree :-)
>>>
>>> In a nutshell, I'm hoping that:
>>> * A review is a new sort of view that has an "inputs" array in its
>>> definition.
>>> * Only MR views are allowed as inputs, no KV duplication allowed.
>>> * It builds a persistent index of the incoming views when those get
>>> updated.
>>> * That index is then used to build the view index for the review when the
>>> review gets updated.
>>> * I think I covered the most important algorithms needed to implement this
>>> in my original proposal.
>>>
>>> Does this sound feasible? If so I'll update my proposal accordingly.
>>>
>>> Wout.
>>>       

Re: Proposal: Review DBs

[Zachary Zolton <za...@gmail.com>]

@jchris et al,

if you had any pointer, on how to implement this, i have a strong
motivation to try my hand at it.

i have a janky ruby script running as an update notifier that looks
for certain criteria, idiomatic to my data, that puts docs into a
derived database. but i'm not terribly happy with my current
implementation...

is there a general-purpose algorithm for dealing with updates?


cheers,

zach


On Sun, Apr 26, 2009 at 10:20 PM, Chris Anderson <jc...@gmail.com> wrote:
>
>
> Sent from my iPhone
>
> On Apr 26, 2009, at 2:26 PM, Wout Mertens <wo...@gmail.com> wrote:
>
>> Hi Adam,
>>
>> On Apr 22, 2009, at 4:48 PM, Adam Kocoloski wrote:
>>
>>> Hi Wout, thanks for writing this up.
>>>
>>> One comment about the map-only views:  I think you'll find that Couch has
>>> already done a good bit of the work needed to support them, too.  Couch
>>> maintains a btree for each design doc keyed on docid that stores all the
>>> view keys emitted by the maps over each document.  When a document is
>>> updated and then analyzed, Couch has to consult that btree, purge all the
>>> KVs associated with the old version of the doc from each view, and then
>>> insert the new KVs.  So the tracking information correlating docids and view
>>> keys is already available.
>>
>> See I did not know that :-) Although I should have guessed.
>>
>> However, in the mail before this one I argued that it doesn't make sense
>> to combine or chain map-only views since you can always write a map function
>> that does it in one step. Do you agree?
>>
>> You might also know the answer to this: is it possible to make the Review
>> DB be a sort of view index on the current database? All it needs are JSON
>> keys and values, no other fields.
>>
>>> You'd still be left with the problem of generating unique docids for the
>>> documents in the Review DB, but I think that's a problem that needs to be
>>> solved.  The restriction to only MR views with no duplicate keys across
>>> views seems too strong to me.
>>
>> Well, since the Review DB is a local(*) hidden database that's handled a
>> bit specially, I think the easiest is to assign _id a sequence number and
>> create a default view that indexes the documents by doc.key (for updating
>> the value for that key). There will never be contention and we're only
>> interested in the key index.
>
> We discussed this a little at CouchHack and I argued that the simplest
> solution is actually good for a few reasons.
>
> The simple solution: provide a mechanism to copy the rows of a grouped
> reduce function to a new database.
>
> Good because it is most like Hadoop/Google style map reduce. In that
> paradigm, the output of a map/reduce job is not incremental, and it is
> persisted in a way that allows for multiple later reduce stages to be run on
> it. It's common in Hadoop to chain many m/r stages, and to try a few
> iterations of each stage while developing code.
>
> I like this also because it provides the needed functionality without adding
> any new primitives to CouchDB.
>
> The only downside of this approach is that it is not incremental. I'm not
> sure that incremental chainability has much promise, as the index management
> could be a pain, especially if you have branching chains.
>
> Another upside is that by reducing to a db, you give the user power to do
> things like use replication to merge multiple data sets before applying more
> views.
>
> I don't want to discourage anyone from experimenting with code, just want to
> point out this simple solution which would be Very Easy to implement.
>
>>
>>
>> (*)local: I'm assuming that views are not replicated and need to be
>> recalculated for each CouchDB node. If they are replicated somehow, I think
>> it would still work but we'd have to look at it a little more.
>>
>>> With that said, I'd prefer to spend my time extending the view engine to
>>> handle chainable MR workflows in a single shot.  Especially in the simple
>>> sort_by_value case it just seems like a cleaner way to go about things.
>>
>> Yes, that seems to be the gist of all repliers and I agree :-)
>>
>> In a nutshell, I'm hoping that:
>> * A review is a new sort of view that has an "inputs" array in its
>> definition.
>> * Only MR views are allowed as inputs, no KV duplication allowed.
>> * It builds a persistent index of the incoming views when those get
>> updated.
>> * That index is then used to build the view index for the review when the
>> review gets updated.
>> * I think I covered the most important algorithms needed to implement this
>> in my original proposal.
>>
>> Does this sound feasible? If so I'll update my proposal accordingly.
>>
>> Wout.
>

Re: Proposal: Review DBs

[Chris Anderson <jc...@gmail.com>]

Sent from my iPhone

On Apr 26, 2009, at 2:26 PM, Wout Mertens <wo...@gmail.com>  
wrote:

> Hi Adam,
>
> On Apr 22, 2009, at 4:48 PM, Adam Kocoloski wrote:
>
>> Hi Wout, thanks for writing this up.
>>
>> One comment about the map-only views:  I think you'll find that  
>> Couch has already done a good bit of the work needed to support  
>> them, too.  Couch maintains a btree for each design doc keyed on  
>> docid that stores all the view keys emitted by the maps over each  
>> document.  When a document is updated and then analyzed, Couch has  
>> to consult that btree, purge all the KVs associated with the old  
>> version of the doc from each view, and then insert the new KVs.  So  
>> the tracking information correlating docids and view keys is  
>> already available.
>
> See I did not know that :-) Although I should have guessed.
>
> However, in the mail before this one I argued that it doesn't make  
> sense to combine or chain map-only views since you can always write  
> a map function that does it in one step. Do you agree?
>
> You might also know the answer to this: is it possible to make the  
> Review DB be a sort of view index on the current database? All it  
> needs are JSON keys and values, no other fields.
>
>> You'd still be left with the problem of generating unique docids  
>> for the documents in the Review DB, but I think that's a problem  
>> that needs to be solved.  The restriction to only MR views with no  
>> duplicate keys across views seems too strong to me.
>
> Well, since the Review DB is a local(*) hidden database that's  
> handled a bit specially, I think the easiest is to assign _id a  
> sequence number and create a default view that indexes the documents  
> by doc.key (for updating the value for that key). There will never  
> be contention and we're only interested in the key index.

We discussed this a little at CouchHack and I argued that the simplest  
solution is actually good for a few reasons.

The simple solution: provide a mechanism to copy the rows of a grouped  
reduce function to a new database.

Good because it is most like Hadoop/Google style map reduce. In that  
paradigm, the output of a map/reduce job is not incremental, and it is  
persisted in a way that allows for multiple later reduce stages to be  
run on it. It's common in Hadoop to chain many m/r stages, and to try  
a few iterations of each stage while developing code.

I like this also because it provides the needed functionality without  
adding any new primitives to CouchDB.

The only downside of this approach is that it is not incremental. I'm  
not sure that incremental chainability has much promise, as the index  
management could be a pain, especially if you have branching chains.

Another upside is that by reducing to a db, you give the user power to  
do things like use replication to merge multiple data sets before  
applying more views.

I don't want to discourage anyone from experimenting with code, just  
want to point out this simple solution which would be Very Easy to  
implement.

>
>
> (*)local: I'm assuming that views are not replicated and need to be  
> recalculated for each CouchDB node. If they are replicated somehow,  
> I think it would still work but we'd have to look at it a little more.
>
>> With that said, I'd prefer to spend my time extending the view  
>> engine to handle chainable MR workflows in a single shot.   
>> Especially in the simple sort_by_value case it just seems like a  
>> cleaner way to go about things.
>
> Yes, that seems to be the gist of all repliers and I agree :-)
>
> In a nutshell, I'm hoping that:
> * A review is a new sort of view that has an "inputs" array in its  
> definition.
> * Only MR views are allowed as inputs, no KV duplication allowed.
> * It builds a persistent index of the incoming views when those get  
> updated.
> * That index is then used to build the view index for the review  
> when the review gets updated.
> * I think I covered the most important algorithms needed to  
> implement this in my original proposal.
>
> Does this sound feasible? If so I'll update my proposal accordingly.
>
> Wout.

Re: Proposal: Review DBs

[Wout Mertens <wo...@gmail.com>]

Hi Adam,

On Apr 22, 2009, at 4:48 PM, Adam Kocoloski wrote:

> Hi Wout, thanks for writing this up.
>
> One comment about the map-only views:  I think you'll find that  
> Couch has already done a good bit of the work needed to support  
> them, too.  Couch maintains a btree for each design doc keyed on  
> docid that stores all the view keys emitted by the maps over each  
> document.  When a document is updated and then analyzed, Couch has  
> to consult that btree, purge all the KVs associated with the old  
> version of the doc from each view, and then insert the new KVs.  So  
> the tracking information correlating docids and view keys is already  
> available.

See I did not know that :-) Although I should have guessed.

However, in the mail before this one I argued that it doesn't make  
sense to combine or chain map-only views since you can always write a  
map function that does it in one step. Do you agree?

You might also know the answer to this: is it possible to make the  
Review DB be a sort of view index on the current database? All it  
needs are JSON keys and values, no other fields.

> You'd still be left with the problem of generating unique docids for  
> the documents in the Review DB, but I think that's a problem that  
> needs to be solved.  The restriction to only MR views with no  
> duplicate keys across views seems too strong to me.

Well, since the Review DB is a local(*) hidden database that's handled  
a bit specially, I think the easiest is to assign _id a sequence  
number and create a default view that indexes the documents by doc.key  
(for updating the value for that key). There will never be contention  
and we're only interested in the key index.

(*)local: I'm assuming that views are not replicated and need to be  
recalculated for each CouchDB node. If they are replicated somehow, I  
think it would still work but we'd have to look at it a little more.

> With that said, I'd prefer to spend my time extending the view  
> engine to handle chainable MR workflows in a single shot.   
> Especially in the simple sort_by_value case it just seems like a  
> cleaner way to go about things.

Yes, that seems to be the gist of all repliers and I agree :-)

In a nutshell, I'm hoping that:
* A review is a new sort of view that has an "inputs" array in its  
definition.
* Only MR views are allowed as inputs, no KV duplication allowed.
* It builds a persistent index of the incoming views when those get  
updated.
* That index is then used to build the view index for the review when  
the review gets updated.
* I think I covered the most important algorithms needed to implement  
this in my original proposal.

Does this sound feasible? If so I'll update my proposal accordingly.

Wout.

Re: Proposal: Review DBs

[Wout Mertens <wo...@gmail.com>]

On Apr 22, 2009, at 8:31 PM, Adam Kocoloski wrote:

> Hi Zachary, something like that.  The more I think about the problem  
> the more I converge on a solution like what Wout has proposed.  Some  
> quick thoughts:
>
> * Remapping the output of a map isn't terribly useful.  All the  
> power is in remapping the output of a reduction.

That's the conclusion I came to as well. I actually had that worked  
out as first but I saw that by eliminating it, the implementation  
became simpler. Of course, I didn't know that CouchDB kept the list of  
keys that a document emits, so I'm reworking my proposal.

> * Incremental generation of some complex multi-MR view still  
> requires persisting the output of each step individually, even if  
> you're only interested in the final result.  At least, I don't yet  
> see a clever way around it.

Me neither :-) Actually, I wonder how CouchDB handles _temp_views;  
those must be persistent as well, in order for paging to work, no?

> * Dumping the output of the first MR(s) into a Review DB is an easy  
> way to take advantage of code that's already written, but it's a bit  
> wasteful.  We could just take the results directly from the view  
> btree(s) and send them to the next step in the workflow.

Well with my proposal I was hoping that someone would step forward and  
say "you can store these key/value pairs as a view index, no  
problem!" :)

> * I'm not yet sold on the HTTP API in Wout's proposal.  I think I'd  
> prefer to keep the existing API, and in the _design doc specify the  
> full workflow required to generate a given view.

Hmmm... That could also work... It certainly makes for shorter URLs. I  
was thinking that chunking the URL up like that in _review/_view/ 
_review it provides a lot of flexibility in view generation. However,  
I see your point, there's no need for such flexibility. If multiple  
_review/_view combinations are needed, they can just as well be listed  
out specifically and CouchDB would take care not to duplicate indexes  
where appropriate (like views).

So the first example would be

    http://couchdb/db/_design/myblog/_view/tags_by_count

with the tags_by_count view defined as (for example)

   "inputs":["tagcount"]
   "map":"function(doc) { emit(doc.value,doc.key); }"

and tagcount of course being

   "map":"function(doc) { for (var i in doc.tags) { emit(i, 1); }"
   "reduce":"function(k,v,r) { return sum(v); }"

You're right, that is better.

Wout.

> Cheers, Adam
>
> On Apr 22, 2009, at 10:53 AM, Zachary Zolton wrote:
>
>> Such as having view definition, in the design doc, contain an array  
>> of
>> objects, each with the map/reduce function pair attributes?
>>
>> On Wed, Apr 22, 2009 at 9:48 AM, Adam Kocoloski  
>> <ko...@apache.org> wrote:
>>> Hi Wout, thanks for writing this up.
>>>
>>> One comment about the map-only views:  I think you'll find that  
>>> Couch has
>>> already done a good bit of the work needed to support them, too.   
>>> Couch
>>> maintains a btree for each design doc keyed on docid that stores  
>>> all the
>>> view keys emitted by the maps over each document.  When a document  
>>> is
>>> updated and then analyzed, Couch has to consult that btree, purge  
>>> all the
>>> KVs associated with the old version of the doc from each view, and  
>>> then
>>> insert the new KVs.  So the tracking information correlating  
>>> docids and view
>>> keys is already available.
>>>
>>> You'd still be left with the problem of generating unique docids  
>>> for the
>>> documents in the Review DB, but I think that's a problem that  
>>> needs to be
>>> solved.  The restriction to only MR views with no duplicate keys  
>>> across
>>> views seems too strong to me.
>>>
>>> With that said, I'd prefer to spend my time extending the view  
>>> engine to
>>> handle chainable MR workflows in a single shot.  Especially in the  
>>> simple
>>> sort_by_value case it just seems like a cleaner way to go about  
>>> things.
>>> Cheers,
>>>
>>> Adam
>>>
>>> On Apr 22, 2009, at 8:40 AM, Wout Mertens wrote:
>>>
>>>> Intro
>>>> =====
>>>> How do you sort by reduce value? How do you join views? How do  
>>>> you get
>>>> unique view results? How do you cache group key reduces?
>>>>
>>>> I think that with the below proposed solution all the above and  
>>>> more are
>>>> possible. The general idea is to store view results and run map/ 
>>>> reduce on
>>>> them. There's been some discussions about this but they went  
>>>> nowhere. I've
>>>> been thinking about this issue a bit and I think it can be done.
>>>>
>>>> I'd like to call this feature a Review DB.
>>>>
>>>> Use cases
>>>> =========
>>>> - Suppose you want to know what tags are most popular on your  
>>>> blog. Simply
>>>> get:
>>>>
>>>>
>>>> http://couchdb/db/_design/myblog/_review/tags_by_count/_view/sort_by_value
>>>>
>>>> Where tags_by_count is a Review DB that gets input from the  
>>>> tagcount view
>>>> and then runs the sort_by_value view on it, a map() function that  
>>>> simply
>>>> emits (value,key).
>>>>
>>>> Likewise, show pages in order of popularity, whereby user can  
>>>> vote up (+1)
>>>> or down (-1):
>>>>
>>>> http://couchdb/db/_design/mywiki/_review/pagevotes/_view/sort_by_value
>>>>
>>>> - Given documents with attributes title, date and tags. You'd  
>>>> like to know
>>>> the minimum value of date and a breakdown by count for tags, for  
>>>> every
>>>> title. Normally you'd use 2 map+reduce views,  
>>>> minimum_date_by_title and
>>>> tagcount_by_title, which you would then query separately. With a  
>>>> Review DB,
>>>> you can let both views insert their results in the database and  
>>>> then run a
>>>> view that combines the results in one view:
>>>>
>>>>
>>>> http://couchdb/db/_design/mybookstore/_review/mybooks/_view/aggregate_book_data
>>>>
>>>> - This is not a way to run an on-the-fly map/reduce on a subset  
>>>> of a view,
>>>> like if you want to find the median popularity score of  
>>>> restaurants with
>>>> "Tony" in their name that are close to you.
>>>>
>>>> Implementation
>>>> ==============
>>>> A Review DB is a hidden database maintained by CouchDB with these  
>>>> fields:
>>>> - _id of document is the string representation of the key
>>>> - "key" is the key of the incoming view row (unique)
>>>> - "value" is the value of the incoming view row
>>>>
>>>> I hope that this is sufficiently like a normal view that it can  
>>>> be stored
>>>> as a normal view. _id is just there to make it doc-compliant, it  
>>>> would be
>>>> much better if "key" were the actual key.
>>>>
>>>> A Review DB is defined in a design document like normal views.  
>>>> Each review
>>>> is an entry in the "reviews" hash, and has a "incoming_views"  
>>>> array that
>>>> lists all the views that should insert results in the review db  
>>>> plus the
>>>> group level, as well as a normal "views" hash for further map/ 
>>>> reduce of the
>>>> review db (and perhaps another "reviews" hash for further result
>>>> processing?).
>>>>
>>>> Maintaining a database of results means that results have to be  
>>>> updated or
>>>> even removed when documents change. I tried to make this work (in  
>>>> theory)
>>>> for map-only views, but the resulting requirements are quite  
>>>> messy. You
>>>> either need to cache the previous results of a view for each  
>>>> document, or
>>>> you have to have an old version of the document available to  
>>>> regenerate
>>>> those results.
>>>>
>>>> Therefore, a Review DB only accepts results from one or more map 
>>>> +reduce
>>>> views. You define beforehand what the group_level of the keys is  
>>>> that will
>>>> be inserted.
>>>>
>>>> Furthermore, a Review DB disallows (but doesn't enforce) having 2  
>>>> views
>>>> that generate the same keys. Otherwise, refcounting would need to  
>>>> be used
>>>> and while that's not difficult, I think there's limited value in  
>>>> allowing
>>>> this.
>>>>
>>>> The Review DB needs updating every time the reduction for a group  
>>>> key of
>>>> one of the participating views gets updated. Even though a map 
>>>> +reduce view
>>>> has unique keys, we need a refcount since we have multiple views.  
>>>> Whoever
>>>> got to insert its value last wins.
>>>>
>>>> There is a slight complication: group key values are calculated  
>>>> on-the-fly
>>>> from the view result b-tree. So whenever a reduce call results in  
>>>> a new
>>>> value for a b-tree node, AND that node is the upper node of a  
>>>> subtree that
>>>> is completely part of a group key, that group key needs to be  
>>>> marked for
>>>> recalculation.
>>>>
>>>> Likewise, if deletion/addition of a b-tree node results in the
>>>> removal/creation of the sole upper node of a group key subtree,  
>>>> that group
>>>> key needs to be marked for removal/addition.
>>>>
>>>> This is the algorithm:
>>>> - When a reducing view gets updated, and it is part of a Review  
>>>> DB, use
>>>> the 2 paragraphs above to keep a list of group keys that need  
>>>> handling
>>>> - After updating the reduce() results, for each of the marked  
>>>> group keys:
>>>> - If a group key gets removed:
>>>> - look up doc with key=group key in review db. If exists:
>>>>   - delete doc
>>>> - If a group key gets added:
>>>> - look up doc with key=group key in review db. If exists:
>>>>   - set doc.value to the row value
>>>> - else
>>>>   - create doc with id=group key in string form, key=group key,
>>>> value=value
>>>> - If a group key gets updated:
>>>> - look up doc with key=group key in review db. If exists:
>>>>   - set doc.value to the row value
>>>> - else
>>>>   - create doc with id=group key in string form, key=group key,
>>>> value=value
>>>>
>>>> As you can see, this is something CouchDB should do since it  
>>>> knows when
>>>> it's updating group key reduction values and it knows if this was  
>>>> an delete,
>>>> update or addition.
>>>>
>>>> View updates are done when the view is called; Review updates are  
>>>> done at
>>>> this time as well. Views on Review DBs are done when they are  
>>>> called.
>>>>
>>>> Summary
>>>> =======
>>>> Review DBs are a sort of view index that CouchDB can maintain  
>>>> with little
>>>> overhead. It caches group key results and allows chained map+reduce
>>>> calculations using mostly existing frameworks.
>>>>
>>>> I think this would be a very useful feature for CouchDB to have.  
>>>> There are
>>>> regularly requests for storing view results in a database for
>>>> post-processing on the mailing lists.
>>>>
>>>> I'm not saying this is a trivial change but it doesn't seem  
>>>> technically
>>>> impossible to me either. (unless I missed something again; this  
>>>> is the 5th
>>>> iteration of this proposal. Anyway I know *I* wouldn't be able to  
>>>> code this
>>>> :-) )
>>>>
>>>> What do you think, oh dear devs?
>>>>
>>>> Wout.
>>>
>>>
>

Re: Proposal: Review DBs

[Wout Mertens <wo...@gmail.com>]

On Apr 23, 2009, at 2:52 AM, Paul Davis wrote:

> I'm still kicking around ideas on how I might approach such an
> implementation. There are some obvious downfalls that Wout has come up
> on. Specifically, some obvious implementations would place some
> arduous constraints on emitted keys (namely: uniqueness, type must be
> string, string must not start with an underscore).

I really would prefer the review DB to be, in fact, a view index, but  
since I don't know the code, I was trying to provide the ability to go  
either way.

As for the uniqueness, I don't know if that is such a heavy  
constraint. After all, it is M views that can emit multiple non-unique  
KV pairs. There is no value in running a second M(R) after M, since  
you can write any map_b(map_a()) as a new map_c(). Likewise the  
results of map_a()+map_b() can be obtained by a map_c() function.

Therefore, review DBs should only contain the results of MR views,  
that by definition deliver unique KV pairs. When combining 2 MR views  
you can have KV collisions, but in all cases the MRs could be  
rewritten to avoid collisions (simply postfix the keys that the M  
emits).

As for the _id of a result row: If the review db would simply be a  
view index, no _id is needed. If it has to be a db, the _id can simply  
be the string version of the JSON representation of the key (it will  
never start with a _ but it's quite wasteful) or some sequence number  
for the review db.

> So there are some things to contemplate, but I think the general idea
> is pretty solid. Also as we start putting some serious effort into
> clustering CouchDB there's the eyebrow raising aspect that if we
> persist to DB's we might be able to leverage a lot of that for some
> added awesomeness.

I feel the same way.

I've also been contemplating using this persistence for _temp_views. I  
think it can be done, given garbage collection on the temporary review  
dbs. Then you could use the CouchDB view server farm to calculate  
multi-dimensional views (all documents with tag A AND tag B AND  
younger than 2 days).

Wout.

Re: Proposal: Review DBs

[Paul Davis <pa...@gmail.com>]

Durring #couchhack we kicked around some ideas on how to get chainable
map reduce. I came in angling on a full work flow specified in a
single design doc that would basically be the current view API but on
sterroids.

The other idea that was presented fairly convincingly was this idea of
persisting the output of views into a second DB and then running more
map/reduce operations on the derived database. The main characteristic
of this method would be that it could be implemented in an external
library (though for efficiency would probably be Erlang). The main
idea was that there would be little if any alteration to the current
view mechanism.

Wout's proposal definitely shares alot of characteristics with the
second proposal. I would argue as Adam does that changing the HTTP API
or even adding to it just creates more confusion. With the recent
release of Hovercraft we have a great point to start adding the
necessary view bits to actually do all of this persistence.

I'm still kicking around ideas on how I might approach such an
implementation. There are some obvious downfalls that Wout has come up
on. Specifically, some obvious implementations would place some
arduous constraints on emitted keys (namely: uniqueness, type must be
string, string must not start with an underscore).

So there are some things to contemplate, but I think the general idea
is pretty solid. Also as we start putting some serious effort into
clustering CouchDB there's the eyebrow raising aspect that if we
persist to DB's we might be able to leverage a lot of that for some
added awesomeness.

Anyway, those are just some raw thoughts.

Paul Davis

On Wed, Apr 22, 2009 at 2:31 PM, Adam Kocoloski <ko...@apache.org> wrote:
> Hi Zachary, something like that.  The more I think about the problem the
> more I converge on a solution like what Wout has proposed.  Some quick
> thoughts:
>
> * Remapping the output of a map isn't terribly useful.  All the power is in
> remapping the output of a reduction.
>
> * Incremental generation of some complex multi-MR view still requires
> persisting the output of each step individually, even if you're only
> interested in the final result.  At least, I don't yet see a clever way
> around it.
>
> * Dumping the output of the first MR(s) into a Review DB is an easy way to
> take advantage of code that's already written, but it's a bit wasteful.  We
> could just take the results directly from the view btree(s) and send them to
> the next step in the workflow.
>
> * I'm not yet sold on the HTTP API in Wout's proposal.  I think I'd prefer
> to keep the existing API, and in the _design doc specify the full workflow
> required to generate a given view.
>
> Cheers, Adam
>
> On Apr 22, 2009, at 10:53 AM, Zachary Zolton wrote:
>
>> Such as having view definition, in the design doc, contain an array of
>> objects, each with the map/reduce function pair attributes?
>>
>> On Wed, Apr 22, 2009 at 9:48 AM, Adam Kocoloski <ko...@apache.org>
>> wrote:
>>>
>>> Hi Wout, thanks for writing this up.
>>>
>>> One comment about the map-only views:  I think you'll find that Couch has
>>> already done a good bit of the work needed to support them, too.  Couch
>>> maintains a btree for each design doc keyed on docid that stores all the
>>> view keys emitted by the maps over each document.  When a document is
>>> updated and then analyzed, Couch has to consult that btree, purge all the
>>> KVs associated with the old version of the doc from each view, and then
>>> insert the new KVs.  So the tracking information correlating docids and
>>> view
>>> keys is already available.
>>>
>>> You'd still be left with the problem of generating unique docids for the
>>> documents in the Review DB, but I think that's a problem that needs to be
>>> solved.  The restriction to only MR views with no duplicate keys across
>>> views seems too strong to me.
>>>
>>> With that said, I'd prefer to spend my time extending the view engine to
>>> handle chainable MR workflows in a single shot.  Especially in the simple
>>> sort_by_value case it just seems like a cleaner way to go about things.
>>>  Cheers,
>>>
>>> Adam
>>>
>>> On Apr 22, 2009, at 8:40 AM, Wout Mertens wrote:
>>>
>>>> Intro
>>>> =====
>>>> How do you sort by reduce value? How do you join views? How do you get
>>>> unique view results? How do you cache group key reduces?
>>>>
>>>> I think that with the below proposed solution all the above and more are
>>>> possible. The general idea is to store view results and run map/reduce
>>>> on
>>>> them. There's been some discussions about this but they went nowhere.
>>>> I've
>>>> been thinking about this issue a bit and I think it can be done.
>>>>
>>>> I'd like to call this feature a Review DB.
>>>>
>>>> Use cases
>>>> =========
>>>> - Suppose you want to know what tags are most popular on your blog.
>>>> Simply
>>>> get:
>>>>
>>>>
>>>>
>>>>  http://couchdb/db/_design/myblog/_review/tags_by_count/_view/sort_by_value
>>>>
>>>> Where tags_by_count is a Review DB that gets input from the tagcount
>>>> view
>>>> and then runs the sort_by_value view on it, a map() function that simply
>>>> emits (value,key).
>>>>
>>>> Likewise, show pages in order of popularity, whereby user can vote up
>>>> (+1)
>>>> or down (-1):
>>>>
>>>>  http://couchdb/db/_design/mywiki/_review/pagevotes/_view/sort_by_value
>>>>
>>>> - Given documents with attributes title, date and tags. You'd like to
>>>> know
>>>> the minimum value of date and a breakdown by count for tags, for every
>>>> title. Normally you'd use 2 map+reduce views, minimum_date_by_title and
>>>> tagcount_by_title, which you would then query separately. With a Review
>>>> DB,
>>>> you can let both views insert their results in the database and then run
>>>> a
>>>> view that combines the results in one view:
>>>>
>>>>
>>>>
>>>>  http://couchdb/db/_design/mybookstore/_review/mybooks/_view/aggregate_book_data
>>>>
>>>> - This is not a way to run an on-the-fly map/reduce on a subset of a
>>>> view,
>>>> like if you want to find the median popularity score of restaurants with
>>>> "Tony" in their name that are close to you.
>>>>
>>>> Implementation
>>>> ==============
>>>> A Review DB is a hidden database maintained by CouchDB with these
>>>> fields:
>>>> - _id of document is the string representation of the key
>>>> - "key" is the key of the incoming view row (unique)
>>>> - "value" is the value of the incoming view row
>>>>
>>>> I hope that this is sufficiently like a normal view that it can be
>>>> stored
>>>> as a normal view. _id is just there to make it doc-compliant, it would
>>>> be
>>>> much better if "key" were the actual key.
>>>>
>>>> A Review DB is defined in a design document like normal views. Each
>>>> review
>>>> is an entry in the "reviews" hash, and has a "incoming_views" array that
>>>> lists all the views that should insert results in the review db plus the
>>>> group level, as well as a normal "views" hash for further map/reduce of
>>>> the
>>>> review db (and perhaps another "reviews" hash for further result
>>>> processing?).
>>>>
>>>> Maintaining a database of results means that results have to be updated
>>>> or
>>>> even removed when documents change. I tried to make this work (in
>>>> theory)
>>>> for map-only views, but the resulting requirements are quite messy. You
>>>> either need to cache the previous results of a view for each document,
>>>> or
>>>> you have to have an old version of the document available to regenerate
>>>> those results.
>>>>
>>>> Therefore, a Review DB only accepts results from one or more map+reduce
>>>> views. You define beforehand what the group_level of the keys is that
>>>> will
>>>> be inserted.
>>>>
>>>> Furthermore, a Review DB disallows (but doesn't enforce) having 2 views
>>>> that generate the same keys. Otherwise, refcounting would need to be
>>>> used
>>>> and while that's not difficult, I think there's limited value in
>>>> allowing
>>>> this.
>>>>
>>>> The Review DB needs updating every time the reduction for a group key of
>>>> one of the participating views gets updated. Even though a map+reduce
>>>> view
>>>> has unique keys, we need a refcount since we have multiple views.
>>>> Whoever
>>>> got to insert its value last wins.
>>>>
>>>> There is a slight complication: group key values are calculated
>>>> on-the-fly
>>>> from the view result b-tree. So whenever a reduce call results in a new
>>>> value for a b-tree node, AND that node is the upper node of a subtree
>>>> that
>>>> is completely part of a group key, that group key needs to be marked for
>>>> recalculation.
>>>>
>>>> Likewise, if deletion/addition of a b-tree node results in the
>>>> removal/creation of the sole upper node of a group key subtree, that
>>>> group
>>>> key needs to be marked for removal/addition.
>>>>
>>>> This is the algorithm:
>>>> - When a reducing view gets updated, and it is part of a Review DB, use
>>>> the 2 paragraphs above to keep a list of group keys that need handling
>>>> - After updating the reduce() results, for each of the marked group
>>>> keys:
>>>> - If a group key gets removed:
>>>>  - look up doc with key=group key in review db. If exists:
>>>>   - delete doc
>>>> - If a group key gets added:
>>>>  - look up doc with key=group key in review db. If exists:
>>>>   - set doc.value to the row value
>>>>  - else
>>>>   - create doc with id=group key in string form, key=group key,
>>>> value=value
>>>> - If a group key gets updated:
>>>>  - look up doc with key=group key in review db. If exists:
>>>>   - set doc.value to the row value
>>>>  - else
>>>>   - create doc with id=group key in string form, key=group key,
>>>> value=value
>>>>
>>>> As you can see, this is something CouchDB should do since it knows when
>>>> it's updating group key reduction values and it knows if this was an
>>>> delete,
>>>> update or addition.
>>>>
>>>> View updates are done when the view is called; Review updates are done
>>>> at
>>>> this time as well. Views on Review DBs are done when they are called.
>>>>
>>>> Summary
>>>> =======
>>>> Review DBs are a sort of view index that CouchDB can maintain with
>>>> little
>>>> overhead. It caches group key results and allows chained map+reduce
>>>> calculations using mostly existing frameworks.
>>>>
>>>> I think this would be a very useful feature for CouchDB to have. There
>>>> are
>>>> regularly requests for storing view results in a database for
>>>> post-processing on the mailing lists.
>>>>
>>>> I'm not saying this is a trivial change but it doesn't seem technically
>>>> impossible to me either. (unless I missed something again; this is the
>>>> 5th
>>>> iteration of this proposal. Anyway I know *I* wouldn't be able to code
>>>> this
>>>> :-) )
>>>>
>>>> What do you think, oh dear devs?
>>>>
>>>> Wout.
>>>
>>>
>
>

Re: Proposal: Review DBs

[Adam Kocoloski <ko...@apache.org>]

Hi Zachary, something like that.  The more I think about the problem  
the more I converge on a solution like what Wout has proposed.  Some  
quick thoughts:

* Remapping the output of a map isn't terribly useful.  All the power  
is in remapping the output of a reduction.

* Incremental generation of some complex multi-MR view still requires  
persisting the output of each step individually, even if you're only  
interested in the final result.  At least, I don't yet see a clever  
way around it.

* Dumping the output of the first MR(s) into a Review DB is an easy  
way to take advantage of code that's already written, but it's a bit  
wasteful.  We could just take the results directly from the view  
btree(s) and send them to the next step in the workflow.

* I'm not yet sold on the HTTP API in Wout's proposal.  I think I'd  
prefer to keep the existing API, and in the _design doc specify the  
full workflow required to generate a given view.

Cheers, Adam

On Apr 22, 2009, at 10:53 AM, Zachary Zolton wrote:

> Such as having view definition, in the design doc, contain an array of
> objects, each with the map/reduce function pair attributes?
>
> On Wed, Apr 22, 2009 at 9:48 AM, Adam Kocoloski  
> <ko...@apache.org> wrote:
>> Hi Wout, thanks for writing this up.
>>
>> One comment about the map-only views:  I think you'll find that  
>> Couch has
>> already done a good bit of the work needed to support them, too.   
>> Couch
>> maintains a btree for each design doc keyed on docid that stores  
>> all the
>> view keys emitted by the maps over each document.  When a document is
>> updated and then analyzed, Couch has to consult that btree, purge  
>> all the
>> KVs associated with the old version of the doc from each view, and  
>> then
>> insert the new KVs.  So the tracking information correlating docids  
>> and view
>> keys is already available.
>>
>> You'd still be left with the problem of generating unique docids  
>> for the
>> documents in the Review DB, but I think that's a problem that needs  
>> to be
>> solved.  The restriction to only MR views with no duplicate keys  
>> across
>> views seems too strong to me.
>>
>> With that said, I'd prefer to spend my time extending the view  
>> engine to
>> handle chainable MR workflows in a single shot.  Especially in the  
>> simple
>> sort_by_value case it just seems like a cleaner way to go about  
>> things.
>>  Cheers,
>>
>> Adam
>>
>> On Apr 22, 2009, at 8:40 AM, Wout Mertens wrote:
>>
>>> Intro
>>> =====
>>> How do you sort by reduce value? How do you join views? How do you  
>>> get
>>> unique view results? How do you cache group key reduces?
>>>
>>> I think that with the below proposed solution all the above and  
>>> more are
>>> possible. The general idea is to store view results and run map/ 
>>> reduce on
>>> them. There's been some discussions about this but they went  
>>> nowhere. I've
>>> been thinking about this issue a bit and I think it can be done.
>>>
>>> I'd like to call this feature a Review DB.
>>>
>>> Use cases
>>> =========
>>> - Suppose you want to know what tags are most popular on your  
>>> blog. Simply
>>> get:
>>>
>>>
>>>  http://couchdb/db/_design/myblog/_review/tags_by_count/_view/sort_by_value
>>>
>>> Where tags_by_count is a Review DB that gets input from the  
>>> tagcount view
>>> and then runs the sort_by_value view on it, a map() function that  
>>> simply
>>> emits (value,key).
>>>
>>> Likewise, show pages in order of popularity, whereby user can vote  
>>> up (+1)
>>> or down (-1):
>>>
>>>  http://couchdb/db/_design/mywiki/_review/pagevotes/_view/sort_by_value
>>>
>>> - Given documents with attributes title, date and tags. You'd like  
>>> to know
>>> the minimum value of date and a breakdown by count for tags, for  
>>> every
>>> title. Normally you'd use 2 map+reduce views,  
>>> minimum_date_by_title and
>>> tagcount_by_title, which you would then query separately. With a  
>>> Review DB,
>>> you can let both views insert their results in the database and  
>>> then run a
>>> view that combines the results in one view:
>>>
>>>
>>>  http://couchdb/db/_design/mybookstore/_review/mybooks/_view/aggregate_book_data
>>>
>>> - This is not a way to run an on-the-fly map/reduce on a subset of  
>>> a view,
>>> like if you want to find the median popularity score of  
>>> restaurants with
>>> "Tony" in their name that are close to you.
>>>
>>> Implementation
>>> ==============
>>> A Review DB is a hidden database maintained by CouchDB with these  
>>> fields:
>>> - _id of document is the string representation of the key
>>> - "key" is the key of the incoming view row (unique)
>>> - "value" is the value of the incoming view row
>>>
>>> I hope that this is sufficiently like a normal view that it can be  
>>> stored
>>> as a normal view. _id is just there to make it doc-compliant, it  
>>> would be
>>> much better if "key" were the actual key.
>>>
>>> A Review DB is defined in a design document like normal views.  
>>> Each review
>>> is an entry in the "reviews" hash, and has a "incoming_views"  
>>> array that
>>> lists all the views that should insert results in the review db  
>>> plus the
>>> group level, as well as a normal "views" hash for further map/ 
>>> reduce of the
>>> review db (and perhaps another "reviews" hash for further result
>>> processing?).
>>>
>>> Maintaining a database of results means that results have to be  
>>> updated or
>>> even removed when documents change. I tried to make this work (in  
>>> theory)
>>> for map-only views, but the resulting requirements are quite  
>>> messy. You
>>> either need to cache the previous results of a view for each  
>>> document, or
>>> you have to have an old version of the document available to  
>>> regenerate
>>> those results.
>>>
>>> Therefore, a Review DB only accepts results from one or more map 
>>> +reduce
>>> views. You define beforehand what the group_level of the keys is  
>>> that will
>>> be inserted.
>>>
>>> Furthermore, a Review DB disallows (but doesn't enforce) having 2  
>>> views
>>> that generate the same keys. Otherwise, refcounting would need to  
>>> be used
>>> and while that's not difficult, I think there's limited value in  
>>> allowing
>>> this.
>>>
>>> The Review DB needs updating every time the reduction for a group  
>>> key of
>>> one of the participating views gets updated. Even though a map 
>>> +reduce view
>>> has unique keys, we need a refcount since we have multiple views.  
>>> Whoever
>>> got to insert its value last wins.
>>>
>>> There is a slight complication: group key values are calculated on- 
>>> the-fly
>>> from the view result b-tree. So whenever a reduce call results in  
>>> a new
>>> value for a b-tree node, AND that node is the upper node of a  
>>> subtree that
>>> is completely part of a group key, that group key needs to be  
>>> marked for
>>> recalculation.
>>>
>>> Likewise, if deletion/addition of a b-tree node results in the
>>> removal/creation of the sole upper node of a group key subtree,  
>>> that group
>>> key needs to be marked for removal/addition.
>>>
>>> This is the algorithm:
>>> - When a reducing view gets updated, and it is part of a Review  
>>> DB, use
>>> the 2 paragraphs above to keep a list of group keys that need  
>>> handling
>>> - After updating the reduce() results, for each of the marked  
>>> group keys:
>>> - If a group key gets removed:
>>>  - look up doc with key=group key in review db. If exists:
>>>    - delete doc
>>> - If a group key gets added:
>>>  - look up doc with key=group key in review db. If exists:
>>>    - set doc.value to the row value
>>>  - else
>>>    - create doc with id=group key in string form, key=group key,
>>> value=value
>>> - If a group key gets updated:
>>>  - look up doc with key=group key in review db. If exists:
>>>    - set doc.value to the row value
>>>  - else
>>>    - create doc with id=group key in string form, key=group key,
>>> value=value
>>>
>>> As you can see, this is something CouchDB should do since it knows  
>>> when
>>> it's updating group key reduction values and it knows if this was  
>>> an delete,
>>> update or addition.
>>>
>>> View updates are done when the view is called; Review updates are  
>>> done at
>>> this time as well. Views on Review DBs are done when they are  
>>> called.
>>>
>>> Summary
>>> =======
>>> Review DBs are a sort of view index that CouchDB can maintain with  
>>> little
>>> overhead. It caches group key results and allows chained map+reduce
>>> calculations using mostly existing frameworks.
>>>
>>> I think this would be a very useful feature for CouchDB to have.  
>>> There are
>>> regularly requests for storing view results in a database for
>>> post-processing on the mailing lists.
>>>
>>> I'm not saying this is a trivial change but it doesn't seem  
>>> technically
>>> impossible to me either. (unless I missed something again; this is  
>>> the 5th
>>> iteration of this proposal. Anyway I know *I* wouldn't be able to  
>>> code this
>>> :-) )
>>>
>>> What do you think, oh dear devs?
>>>
>>> Wout.
>>
>>

Re: Proposal: Review DBs

[Zachary Zolton <za...@gmail.com>]

Such as having view definition, in the design doc, contain an array of
objects, each with the map/reduce function pair attributes?

On Wed, Apr 22, 2009 at 9:48 AM, Adam Kocoloski <ko...@apache.org> wrote:
> Hi Wout, thanks for writing this up.
>
> One comment about the map-only views:  I think you'll find that Couch has
> already done a good bit of the work needed to support them, too.  Couch
> maintains a btree for each design doc keyed on docid that stores all the
> view keys emitted by the maps over each document.  When a document is
> updated and then analyzed, Couch has to consult that btree, purge all the
> KVs associated with the old version of the doc from each view, and then
> insert the new KVs.  So the tracking information correlating docids and view
> keys is already available.
>
> You'd still be left with the problem of generating unique docids for the
> documents in the Review DB, but I think that's a problem that needs to be
> solved.  The restriction to only MR views with no duplicate keys across
> views seems too strong to me.
>
> With that said, I'd prefer to spend my time extending the view engine to
> handle chainable MR workflows in a single shot.  Especially in the simple
> sort_by_value case it just seems like a cleaner way to go about things.
>  Cheers,
>
> Adam
>
> On Apr 22, 2009, at 8:40 AM, Wout Mertens wrote:
>
>> Intro
>> =====
>> How do you sort by reduce value? How do you join views? How do you get
>> unique view results? How do you cache group key reduces?
>>
>> I think that with the below proposed solution all the above and more are
>> possible. The general idea is to store view results and run map/reduce on
>> them. There's been some discussions about this but they went nowhere. I've
>> been thinking about this issue a bit and I think it can be done.
>>
>> I'd like to call this feature a Review DB.
>>
>> Use cases
>> =========
>> - Suppose you want to know what tags are most popular on your blog. Simply
>> get:
>>
>>
>>  http://couchdb/db/_design/myblog/_review/tags_by_count/_view/sort_by_value
>>
>> Where tags_by_count is a Review DB that gets input from the tagcount view
>> and then runs the sort_by_value view on it, a map() function that simply
>> emits (value,key).
>>
>> Likewise, show pages in order of popularity, whereby user can vote up (+1)
>> or down (-1):
>>
>>  http://couchdb/db/_design/mywiki/_review/pagevotes/_view/sort_by_value
>>
>> - Given documents with attributes title, date and tags. You'd like to know
>> the minimum value of date and a breakdown by count for tags, for every
>> title. Normally you'd use 2 map+reduce views, minimum_date_by_title and
>> tagcount_by_title, which you would then query separately. With a Review DB,
>> you can let both views insert their results in the database and then run a
>> view that combines the results in one view:
>>
>>
>>  http://couchdb/db/_design/mybookstore/_review/mybooks/_view/aggregate_book_data
>>
>> - This is not a way to run an on-the-fly map/reduce on a subset of a view,
>> like if you want to find the median popularity score of restaurants with
>> "Tony" in their name that are close to you.
>>
>> Implementation
>> ==============
>> A Review DB is a hidden database maintained by CouchDB with these fields:
>> - _id of document is the string representation of the key
>> - "key" is the key of the incoming view row (unique)
>> - "value" is the value of the incoming view row
>>
>> I hope that this is sufficiently like a normal view that it can be stored
>> as a normal view. _id is just there to make it doc-compliant, it would be
>> much better if "key" were the actual key.
>>
>> A Review DB is defined in a design document like normal views. Each review
>> is an entry in the "reviews" hash, and has a "incoming_views" array that
>> lists all the views that should insert results in the review db plus the
>> group level, as well as a normal "views" hash for further map/reduce of the
>> review db (and perhaps another "reviews" hash for further result
>> processing?).
>>
>> Maintaining a database of results means that results have to be updated or
>> even removed when documents change. I tried to make this work (in theory)
>> for map-only views, but the resulting requirements are quite messy. You
>> either need to cache the previous results of a view for each document, or
>> you have to have an old version of the document available to regenerate
>> those results.
>>
>> Therefore, a Review DB only accepts results from one or more map+reduce
>> views. You define beforehand what the group_level of the keys is that will
>> be inserted.
>>
>> Furthermore, a Review DB disallows (but doesn't enforce) having 2 views
>> that generate the same keys. Otherwise, refcounting would need to be used
>> and while that's not difficult, I think there's limited value in allowing
>> this.
>>
>> The Review DB needs updating every time the reduction for a group key of
>> one of the participating views gets updated. Even though a map+reduce view
>> has unique keys, we need a refcount since we have multiple views. Whoever
>> got to insert its value last wins.
>>
>> There is a slight complication: group key values are calculated on-the-fly
>> from the view result b-tree. So whenever a reduce call results in a new
>> value for a b-tree node, AND that node is the upper node of a subtree that
>> is completely part of a group key, that group key needs to be marked for
>> recalculation.
>>
>> Likewise, if deletion/addition of a b-tree node results in the
>> removal/creation of the sole upper node of a group key subtree, that group
>> key needs to be marked for removal/addition.
>>
>> This is the algorithm:
>> - When a reducing view gets updated, and it is part of a Review DB, use
>> the 2 paragraphs above to keep a list of group keys that need handling
>> - After updating the reduce() results, for each of the marked group keys:
>> - If a group key gets removed:
>>  - look up doc with key=group key in review db. If exists:
>>    - delete doc
>> - If a group key gets added:
>>  - look up doc with key=group key in review db. If exists:
>>    - set doc.value to the row value
>>  - else
>>    - create doc with id=group key in string form, key=group key,
>> value=value
>> - If a group key gets updated:
>>  - look up doc with key=group key in review db. If exists:
>>    - set doc.value to the row value
>>  - else
>>    - create doc with id=group key in string form, key=group key,
>> value=value
>>
>> As you can see, this is something CouchDB should do since it knows when
>> it's updating group key reduction values and it knows if this was an delete,
>> update or addition.
>>
>> View updates are done when the view is called; Review updates are done at
>> this time as well. Views on Review DBs are done when they are called.
>>
>> Summary
>> =======
>> Review DBs are a sort of view index that CouchDB can maintain with little
>> overhead. It caches group key results and allows chained map+reduce
>> calculations using mostly existing frameworks.
>>
>> I think this would be a very useful feature for CouchDB to have. There are
>> regularly requests for storing view results in a database for
>> post-processing on the mailing lists.
>>
>> I'm not saying this is a trivial change but it doesn't seem technically
>> impossible to me either. (unless I missed something again; this is the 5th
>> iteration of this proposal. Anyway I know *I* wouldn't be able to code this
>> :-) )
>>
>> What do you think, oh dear devs?
>>
>> Wout.
>
>

Re: Proposal: Review DBs

[Adam Kocoloski <ko...@apache.org>]

Hi Wout, thanks for writing this up.

One comment about the map-only views:  I think you'll find that Couch  
has already done a good bit of the work needed to support them, too.   
Couch maintains a btree for each design doc keyed on docid that stores  
all the view keys emitted by the maps over each document.  When a  
document is updated and then analyzed, Couch has to consult that  
btree, purge all the KVs associated with the old version of the doc  
from each view, and then insert the new KVs.  So the tracking  
information correlating docids and view keys is already available.

You'd still be left with the problem of generating unique docids for  
the documents in the Review DB, but I think that's a problem that  
needs to be solved.  The restriction to only MR views with no  
duplicate keys across views seems too strong to me.

With that said, I'd prefer to spend my time extending the view engine  
to handle chainable MR workflows in a single shot.  Especially in the  
simple sort_by_value case it just seems like a cleaner way to go about  
things.  Cheers,

Adam

On Apr 22, 2009, at 8:40 AM, Wout Mertens wrote:

> Intro
> =====
> How do you sort by reduce value? How do you join views? How do you  
> get unique view results? How do you cache group key reduces?
>
> I think that with the below proposed solution all the above and more  
> are possible. The general idea is to store view results and run map/ 
> reduce on them. There's been some discussions about this but they  
> went nowhere. I've been thinking about this issue a bit and I think  
> it can be done.
>
> I'd like to call this feature a Review DB.
>
> Use cases
> =========
> - Suppose you want to know what tags are most popular on your blog.  
> Simply get:
>
>  http://couchdb/db/_design/myblog/_review/tags_by_count/_view/sort_by_value
>
> Where tags_by_count is a Review DB that gets input from the tagcount  
> view and then runs the sort_by_value view on it, a map() function  
> that simply emits (value,key).
>
> Likewise, show pages in order of popularity, whereby user can vote  
> up (+1) or down (-1):
>
>  http://couchdb/db/_design/mywiki/_review/pagevotes/_view/ 
> sort_by_value
>
> - Given documents with attributes title, date and tags. You'd like  
> to know the minimum value of date and a breakdown by count for tags,  
> for every title. Normally you'd use 2 map+reduce views,  
> minimum_date_by_title and tagcount_by_title, which you would then  
> query separately. With a Review DB, you can let both views insert  
> their results in the database and then run a view that combines the  
> results in one view:
>
>  http://couchdb/db/_design/mybookstore/_review/mybooks/_view/aggregate_book_data
>
> - This is not a way to run an on-the-fly map/reduce on a subset of a  
> view, like if you want to find the median popularity score of  
> restaurants with "Tony" in their name that are close to you.
>
> Implementation
> ==============
> A Review DB is a hidden database maintained by CouchDB with these  
> fields:
> - _id of document is the string representation of the key
> - "key" is the key of the incoming view row (unique)
> - "value" is the value of the incoming view row
>
> I hope that this is sufficiently like a normal view that it can be  
> stored as a normal view. _id is just there to make it doc-compliant,  
> it would be much better if "key" were the actual key.
>
> A Review DB is defined in a design document like normal views. Each  
> review is an entry in the "reviews" hash, and has a "incoming_views"  
> array that lists all the views that should insert results in the  
> review db plus the group level, as well as a normal "views" hash for  
> further map/reduce of the review db (and perhaps another "reviews"  
> hash for further result processing?).
>
> Maintaining a database of results means that results have to be  
> updated or even removed when documents change. I tried to make this  
> work (in theory) for map-only views, but the resulting requirements  
> are quite messy. You either need to cache the previous results of a  
> view for each document, or you have to have an old version of the  
> document available to regenerate those results.
>
> Therefore, a Review DB only accepts results from one or more map 
> +reduce views. You define beforehand what the group_level of the  
> keys is that will be inserted.
>
> Furthermore, a Review DB disallows (but doesn't enforce) having 2  
> views that generate the same keys. Otherwise, refcounting would need  
> to be used and while that's not difficult, I think there's limited  
> value in allowing this.
>
> The Review DB needs updating every time the reduction for a group  
> key of one of the participating views gets updated. Even though a map 
> +reduce view has unique keys, we need a refcount since we have  
> multiple views. Whoever got to insert its value last wins.
>
> There is a slight complication: group key values are calculated on- 
> the-fly from the view result b-tree. So whenever a reduce call  
> results in a new value for a b-tree node, AND that node is the upper  
> node of a subtree that is completely part of a group key, that group  
> key needs to be marked for recalculation.
>
> Likewise, if deletion/addition of a b-tree node results in the  
> removal/creation of the sole upper node of a group key subtree, that  
> group key needs to be marked for removal/addition.
>
> This is the algorithm:
> - When a reducing view gets updated, and it is part of a Review DB,  
> use the 2 paragraphs above to keep a list of group keys that need  
> handling
> - After updating the reduce() results, for each of the marked group  
> keys:
> - If a group key gets removed:
>   - look up doc with key=group key in review db. If exists:
>     - delete doc
> - If a group key gets added:
>   - look up doc with key=group key in review db. If exists:
>     - set doc.value to the row value
>   - else
>     - create doc with id=group key in string form, key=group key,  
> value=value
> - If a group key gets updated:
>   - look up doc with key=group key in review db. If exists:
>     - set doc.value to the row value
>   - else
>     - create doc with id=group key in string form, key=group key,  
> value=value
> 	
> As you can see, this is something CouchDB should do since it knows  
> when it's updating group key reduction values and it knows if this  
> was an delete, update or addition.
>
> View updates are done when the view is called; Review updates are  
> done at this time as well. Views on Review DBs are done when they  
> are called.
>
> Summary
> =======
> Review DBs are a sort of view index that CouchDB can maintain with  
> little overhead. It caches group key results and allows chained map 
> +reduce calculations using mostly existing frameworks.
>
> I think this would be a very useful feature for CouchDB to have.  
> There are regularly requests for storing view results in a database  
> for post-processing on the mailing lists.
>
> I'm not saying this is a trivial change but it doesn't seem  
> technically impossible to me either. (unless I missed something  
> again; this is the 5th iteration of this proposal. Anyway I know *I*  
> wouldn't be able to code this :-) )
>
> What do you think, oh dear devs?
>
> Wout.