Quick Note I have a gist markdown version of this that might be easier to
read https://gist.github.com/garrensmith/1ad1176e007af9c389301b1b6b00f180
Hi Everyone,
The team at Cloudant have been relooking at Reduce indexes for CouchDB on
FDB and we want to simply what we had initially planned and change some of
the reduce behaviour compared to CouchDB 3.x
Our initial design was to use a skip list. However this hasn’t proven to be
particularly useful approach. It would take very long to update and I can’t
find a good algorithm to query the skip list effectively.
So instead I would like to propose a much simpler reduce implementation. I
would like to use this as the base for reduce and we can look at adding
more functionality later if we need to.
For the new reduce design, instead of creating a skip list, we will instead
create group_level indexes for a key. For example say we have the following
keys we want to add to a reduce index:
```
([2019, 6, 1] , 1)
([2019, 6, 20] , 1)
([2019, 7, 3] , 1)
```
We would then create the following group_level indexes:
```
Level 0:
(null, 3)
Level=1:
([2019], 3)
Level 2:
([2019,6], 2)
([2019, 7] , 1)
Level3:
([2019, 6, 1,] , 1)
([2019, 6, 20,] , 1)
([2019, 7, 3,] , 1)
```
All of these group_level indexes would form part of the reduce index and
would be updated at the same time. We don’t need to know the actual
`group_levels` ahead of time as we would take any key we need to index look
at its length and add it to the group_levels it would belong to.
Another nice optimization we can do with this is when a user creates a view
they can specify the number of group levels to index e.g:
```
{
_id: _design/my-ddoc
views: {
one: {
map: function (doc) {emit(doc.val, 1)},
reduce: "_sum"
},
two: {
map: function (doc) {emit(doc.age, 1)},
reduce: "_count"
}
},
options: {group_levels: [1,3,5]}
}
```
This gives the user the ability to trade off index build speed, storage
overhead and performance.
One caveat of that, for now, is if a user changes the number of
`group_levels` to be indexed, the index is invalidated and we would have to
build it from scratch again. Later we could look at doing some work around
that so that isn’t the case.
This design will result in a behaviour change. Previously with reduce if
you set `group_level=2`. It will return all results with `group_level=2`
and below. E.g reduce key/values of the following:
```
# group = true
("key":1,"value":2},
{"key":2,"value":2},
{"key":3,"value":2},
{"key":[1,1],"value":1},
{"key":[1,2,6],"value":1},
{"key":[2,1],"value":1},
{"key":[2,3,6],"value":1},
{"key":[3,1],"value":1},
{"key":[3,1,5],"value":1},
{"key":[3,4,5],"value":1}
```
Then doing a query group_level=2 returns:
```
# group_level = 2
{"rows":[
{"key":1,"value":2},
{"key":2,"value":2},
{"key":3,"value":2},
{"key":[1,1],"value":1},
{"key":[1,2],"value":1},
{"key":[2,1],"value":1},
{"key":[2,3],"value":1},
{"key":[3,1],"value":2},
{"key":[3,4],"value":1}
]}
```
I want to **CHANGE** this behaviour, so if a query specifies
`group_level=2` then **only** `group_level=2` returns would be returned.
E.g from the example above the results would be:
```
# group_level = 2
{"rows":[
{"key":[1,1],"value":1},
{"key":[1,2],"value":1},
{"key":[2,1],"value":1},
{"key":[2,3],"value":1},
{"key":[3,1],"value":2},
{"key":[3,4],"value":1}
]}
```
## Group_level=0
`Group_level=0` queries would work as follows:
1. `group_level=0` without startkey/endkey and then the group_level=0 index
is used
2. For a `group_level=0` with a startkey/endkey or where `group_level=0` is
not indexed, the query will look for the smallest `group_level` and use
that to calculate the `group_level=0` result
3. `group_level=0` indexes with a startkey/endkey could timeout and be slow
in some cases because we having to do quite a lot of aggregation when
reading keys. But I don’t think that is much different from how it is done
now.
## Group=true
We will always build the `group=true` index.
## Querying non-indexed group_level
If a query has a `group_level` that is not indexed. We can do two things
here, CouchDB could use the nearest `group_level` to service the query or
it could return an error that this `group_level` is not available to query.
I would like to make this configurable so that an admin can choose how
reduce indexes behave.
## Supported Builtin Reduces
Initially, we would support reduces that can be updated by calculating a
delta change and applying it to all the group_levels. That means we can
support `_sum` and `_count` quite easily. Initially, we won’t implement
`max` and `min`. However, I would like to add them as soon after.
I would also later like to add support for `_stats` reducer. The best
option I can think of is breaking up each field in `_stats` into its own
k/v row in FDB.
I’m not sure how to handle the `_approx_count_distinct`. At the moment I
don’t understand the algorithm well enough to know if we could support it.
## Custom Reduces
Custom reduces will not be supported. This is because it will be tricky to
implement with this design and would not be very performant. Later if there
is a demand for this I guess we could look at doing it but with the caveat
that performance will be pretty bad. My view on custom reduces are that in
99% of cases they are a bad choice so I would prefer we don’t support them.
## Replication
Some basic replication rules:
1. If a design document is replicated across from an old database and does
not have the group_level option set. All `group_levels` will be supported.
2. If a design document is replicated across with a custom reduce or a
reduce we don’t support we will return an error when that reduce index is
queried. I’m thinking we would still build the map part of the index.
## limits
Reduce keys will have the same limits as map keys which are 8KB.
Hopefully that all makes sense, let me know if I need to explain a point
further and I would love to hear your thoughts on this.
