You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@couchdb.apache.org by GitBox <gi...@apache.org> on 2019/09/24 15:52:01 UTC
[GitHub] [couchdb-documentation] kocolosk commented on a change in pull
request #441: initial reduce rfc
kocolosk commented on a change in pull request #441: initial reduce rfc
URL: https://github.com/apache/couchdb-documentation/pull/441#discussion_r327665082
##########
File path: rfcs/012-fdb-reduce.md
##########
@@ -0,0 +1,190 @@
+---
+name: Formal RFC
+about: Submit a formal Request For Comments for consideration by the team.
+title: 'Reduce indexes on FoundationDB'
+labels: rfc, discussion
+assignees: ''
+
+---
+
+## Introduction
+
+This document describes 3 possible ways to support CouchDB's reduce functionality on top of FoundationDB.
+The main focus will be on a Skip List algorithm as it has the most potential to support all the required functionality.
+
+## Abstract
+
+Reduce indexes allow users of CouchDB to perform aggregations on a map index. These aggregations need to be stored in FoundationDB in a way that is efficient for updating the index on document updates and when retrieving results for different reduce group level's.
+Three options are initially listed, with a skip list approach selected as the most viable option. A process flow for building, retrieving and updating a skip list based reduce index is described. Finally, the data model for using this with FoundationDB is shown.
+
+## Requirements Language
+
+The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
+"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
+document are to be interpreted as described in
+[RFC 2119](https://www.rfc-editor.org/rfc/rfc2119.txt).
+
+## Terminology
+
+No new terminology at this point.
+
+---
+
+## Detailed Description
+
+Reduce indexes allow users of CouchDB to perform aggregations based on the key/values emitted from the map function.
+A lot of the power of the reduce functionality that CouchDB currently supports is because internally each map/reduce index is stored in a b+tree with non-leaf nodes containing aggregated results of the leaf nodes below them. Allowing for efficient retrieval of those values. It is difficult to replicate that behavior exactly using FoundationDB. Therefore to implement reduce indexes in FoundationDB three possible ways are considered.
+
+### Option 1 - On the fly reduce calculation
+
+The simplest implementation is to perform the reduce function on the fly when a reduce query is requested.
+The map index will be read and the reduce aggregation performed on the keys as they are fetched from FoundationDB.
+This is by far the easiest to implement, but query performance will degrade as the database and index grows and could reach a point where the reduce query just stops working.
+
+### Option 2 - Precompute of all group-levels
+
+Another option is to precompute all group level's for a reduce function and store them as key/values in FoundationDB.
+This makes querying fast as the results are already calculated. The first difficulty comes when updating the index.
+For the built-in `_sum` and `_count` reduce functions, a single reduce calculation can be run and then applied to all group levels.
+For any custom reduce functions along with `_stats` and `_approx_count_distinct`, the updating of each group level would be more complex as it requires reading all keys and running them through the reduce functions for all group levels before storing it back in FoundationDB.
+
+Another issue is any queries using startkey/endkey can be an expensive operations as we would have to perform aggregations on the startkey and the endkey key ranges. Then `group_level = 0` queries with a startkey or endkey would require a full aggregation of the keys in that range which again could be an expensive operation.
+
+### Option 3 - Skip list implementation
+
+The final option is using a skip list. A skip list can be thought of as a layered linked list. The bottom layer contains all the elements in an index. Each layer up from that is has a reduced (pun intended) number of elements in that list. See figure 1 for a simple skip list layout.
+
+
+*Figure 1:* Example of a skip list
+
+A skip list would make it easier to query an index using startkey/endkey and more efficient than option 2 to update an index for all types of reduce functions.
+
+### Skip list implementation
+
+This section does a deep dive into how a skip list can be used to create, query and update a reduce index.
+To explore these situations, we will have the following design document defined.
+
+```js
+ {
+ "_id": "_design/reduce-example"
+ "views: {
+ "example": {
+ "map": function (doc) {
+ emit([doc.year, doc.month, doc.day], 1);
+ },
+
+ "reduce": "_count"
+ }
+ }
+ }
+
+```
+
+And it emits the following key/value results for the reduce function:
+
+```js
+ [2017, 03, 1] = 1
+ [2017, 04, 1] = 1
+ [2017, 04, 15] = 1
+ [2017, 05, 1] = 1
+
+ [2018, 03, 1] = 1
+ [2018, 04, 1] = 1
+ [2018, 05, 1] = 1
+
+ [2019, 03, 1] = 1
+ [2018, 04, 1] = 1
+ [2018, 05, 1] = 1
+```
+
+#### Create
+
+To build the skip list, all keys will be added to level 0. Then each level up, a reduced number of keys will be added. For each level above 0, if a key/value is not added to that level, then that key's value is aggregated with the previous node in that row. Therefore each key/value node in a level is an aggregation of its key/value in level 0 and any key/values from the previous level that are greater than the node and smaller than the next node on that level.
Review comment:
Is level 0 the output of the map phase or is it the group=true reduce? It's not clear to me. Maybe an example that had a count > 1 for some key would help.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services