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 2020/01/15 14:16:54 UTC
[GitHub] [couchdb] garrensmith opened a new pull request #2456: FDB Builtin
reduce
garrensmith opened a new pull request #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456
## Overview
Adds builtin reduce indexes for CouchDB on FDB. The reduce indexes are created using a skiplist like data structure. See the [RFC](https://github.com/apache/couchdb-documentation/pull/441) for the full details.
This work is not 100% complete. Currently, the reduce index cannot update an index when a document is updated as it will not remove the original document from the index.
There are two ways to query the index. By default a query of the reduce index will read through the full skiplist to return the results. But if you add the parameter `use_skiplist=false` it will only read from the level = 0 of the skip list and compute the group_level results in memory. level = 0 of the skiplist is equivalent of `group=true` for reduce.
I'm currently at the point where I need feedback from the rest of the team on how best to finish the work. The Skiplist algorithm works but it does seem a bit slow and its pretty complex. I need help on the following things:
1. Review the skip list traversing algorithm to see if we can improve it and make it faster
1. Review the add keys to the skip list and see if there are any bugs or issues with this
1. Finally should we continue with the skip list implementation? Or should we rather go with a reduce index that just stores the equivalent of the level 0 keys for the skiplist, and then calculate the reduce group levels in memory when returning the results.
## Testing recommendations
New tests have been added. Current the PR fails the reduce_builtin.js when using the full skiplist but pass with only using level 0.
## Checklist
- [ ] Code is written and works correctly
- [ ] Changes are covered by tests
- [ ] Any new configurable parameters are documented in `rel/overlay/etc/default.ini`
- [ ] A PR for documentation changes has been made in https://github.com/apache/couchdb-documentation
----------------------------------------------------------------
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
[GitHub] [couchdb] davisp commented on issue #2456: FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
davisp commented on issue #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#issuecomment-579458016
I finally had some downtime to start looking into this more closely. So far I've only spent a couple hours reading through and thinking about things so hopefully this comes out semi-coherently.
So far I'm just focusing on the skiplist implementation. First off, as @chewbranca's confusion points out, we should probably scrub all references to skiplists because these are different enough that it'll just lead to confusion when people attempt to compare them. I'd at least mention RankedSets and include links to the Java implementation in fdb-record-layer [1]. RankedSets is a bit overly specific given we've got arbitrary reduce functions. But maybe `reduced_sets` would be good enough?
I started reading on the update side of things first and it looks like you've basically nailed it. I think we should change around a few definitions though. If we refer to the map index's key/value pairs as level 0 and then keep the rest as written we'll have covered custom javascript reduce functions and all of the builtin reduce functions. Which is way more awesome than when I was thinking we were going to have to invent some sort of un-reduce function which would have been super error prone. Brilliant work there!
The query/traversal side of things is going to need some work. I think there's a bit of confusion around how group levels work that got mixed into the traversal code. To simplify the implementation and development here you should write a function that will correctly answer a group=true query with a start and end key. Once you have an implementation of that function, turning it into a `foldl` style API will be straightforward. And then once you have that API you'll basically just be copying the group logic from couch_btree. The algorithm that @chewbranca sketched should be a good starting place here.
Once you've got all that done, adding the removal logic is as simple as cribbing off the Java `RankedSet.remove` method.
That's about it from me for now. Good work!
[1] https://github.com/FoundationDB/fdb-record-layer/blob/master/fdb-extensions/src/main/java/com/apple/foundationdb/async/RankedSet.java
----------------------------------------------------------------
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
[GitHub] [couchdb] chewbranca commented on a change in pull request #2456:
FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
chewbranca commented on a change in pull request #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#discussion_r367080496
##########
File path: src/couch_views/src/couch_views_reduce.erl
##########
@@ -0,0 +1,232 @@
+% Licensed under the Apache License, Version 2.0 (the "License"); you may not
+% use this file except in compliance with the License. You may obtain a copy of
+% the License at
+%
+% http://www.apache.org/licenses/LICENSE-2.0
+%
+% Unless required by applicable law or agreed to in writing, software
+% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+% License for the specific language governing permissions and limitations under
+% the License.
+
+-module(couch_views_reduce).
+
+
+-export([
+ run_reduce/2,
+ read_reduce/7
+]).
+
+
+-include("couch_views.hrl").
+-include_lib("couch/include/couch_db.hrl").
+-include_lib("couch_mrview/include/couch_mrview.hrl").
+-include_lib("fabric/include/fabric2.hrl").
+
+
+run_reduce(#mrst{views = Views}, MappedResults) ->
+ lists:map(fun (MappedResult) ->
+ #{
+ results := Results
+ } = MappedResult,
+
+ ReduceResults = lists:map(fun ({View, Result}) ->
+ #mrview{
+ reduce_funs = ViewReduceFuns
+ } = View,
+
+ lists:map(fun({_, ReduceFun}) ->
+ couch_views_reducer:reduce(ReduceFun, Result)
+ end, ViewReduceFuns)
+
+ end, lists:zip(Views, Results)),
+
+ MappedResult#{
+ reduce_results => ReduceResults
+ }
+ end, MappedResults).
+
+
+read_reduce(Db, Sig, ViewId, Reducer, UserCallback, UserAcc0, Args) ->
+ #{
+ db_prefix := DbPrefix
+ } = Db,
+
+ ReduceIdxPrefix = couch_views_reduce_fdb:idx_prefix(
+ DbPrefix, Sig, ViewId),
+
+ #mrargs{
+ limit = Limit,
+ group = Group,
+ group_level = GroupLevel,
+ use_skiplist = UseSkipList,
+ skip = Skip
+ } = Args,
+ GroupLevel1 = case Group of
+ true -> group_true;
+ _ -> GroupLevel
+ end,
+ Opts = case UseSkipList of
+ true -> args_to_skiplist_opts(Args);
+ false -> args_to_fdb_opts(Args)
+ end,
+
+ Acc0 = #{
+ sig => Sig,
+ view_id => ViewId,
+ user_acc => UserAcc0,
+ args => Args,
+ callback => UserCallback,
+ reduce_idx_prefix => ReduceIdxPrefix,
+ limit => Limit,
+ row_count => 0,
+ skip => Skip
+ },
+ read_reduce_int(Db, Sig, ViewId, Reducer, GroupLevel1, Acc0, Opts,
+ UseSkipList).
+
+
+read_reduce_int(Db, Sig, ViewId, Reducer, GroupLevel, Acc0, Opts,
+ UseSkiplist) ->
+ try
+ Fun = fun handle_row/3,
+ Acc1 = fabric2_fdb:transactional(Db, fun(TxDb) ->
+ case UseSkiplist of
+ true ->
+ couch_views_skiplist:fold(TxDb, Sig, ViewId,
+ Reducer, GroupLevel, Opts, Fun, Acc0);
+ false ->
+ couch_views_reduce_fdb:fold_level0(TxDb, Sig, ViewId,
+ Reducer, GroupLevel, Opts, Fun, Acc0)
+ end
+ end),
+ #{
+ callback := UserCallback,
+ user_acc := UserAcc1
+ } = Acc1,
+ {ok, maybe_stop(UserCallback(complete, UserAcc1))}
+ catch
+ throw:reduce_transaction_ended ->
+ {ContinueStartKey, Acc} = get(reduce_acc),
+ ReduceIdxPrefix = maps:get(reduce_idx_prefix, Acc),
+
+ StartKey0 = couch_views_reduce_fdb:create_key(ReduceIdxPrefix, 0,
+ ContinueStartKey),
+ StartKey = erlfdb_key:first_greater_or_equal(StartKey0),
+ FdbOpts1 = lists:keyreplace(startkey, 1, Opts,
+ {startkey, StartKey}),
+
+ read_reduce_int(Db, Sig, ViewId, Reducer, GroupLevel, Acc,
+ FdbOpts1, UseSkiplist);
+ throw:{done, Out} ->
+ {ok, Out}
+ end.
+
+
+args_to_skiplist_opts(#mrargs{} = Args) ->
+ #mrargs{
+ start_key = StartKey,
+ end_key = EndKey,
+ direction = Direction,
+ inclusive_end = InclusiveEnd
+ } = Args,
+
+ StartKey1 = case StartKey of
+ undefined ->
+ undefined;
+ StartKey ->
+ StartKey
+ end,
+
+ EndKey1 = case EndKey of
+ undefined ->
+ undefined;
+ EndKey ->
+ EndKey
+ end,
+
+ % CouchDB swaps the key meanings based on the direction
+ % of the fold. FoundationDB does not so we have to
+ % swap back here.
+ {StartKey2, EndKey2} = case Direction == rev of
+ true -> {EndKey1, StartKey1};
+ false -> {StartKey1, EndKey1}
+ end,
+
+ #{
+ startkey => StartKey2,
+ endkey => EndKey2,
+ reverse => Direction == rev,
Review comment:
Minor nit, but `Direction == rev` is duplicated, might be worth doing:
```erlang
Reversed = Direction == rev,
{StartKey2, EndKey2} = case Reversed of
true -> {EndKey1, StartKey1};
false -> {StartKey1, EndKey1}
end,
#{
startkey => StartKey2,
endkey => EndKey2,
reverse => Reversed,
...
}
```
----------------------------------------------------------------
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
[GitHub] [couchdb] chewbranca commented on issue #2456: FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
chewbranca commented on issue #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#issuecomment-575840299
That approach would also easily support the non skip list toggle with something like
```erlang
query_view(View, StartKey, EndKey, UseSkipList) ->
case UseSkipList of
true -> query(View, StartKey, EndKey);
false -> query(View, ?MIN_LEVEL, StartKey, EndKey)
end.
```
----------------------------------------------------------------
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
[GitHub] [couchdb] chewbranca commented on a change in pull request #2456:
FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
chewbranca commented on a change in pull request #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#discussion_r367063727
##########
File path: src/couch_views/src/couch_views_reducer.erl
##########
@@ -0,0 +1,325 @@
+% Licensed under the Apache License, Version 2.0 (the "License"); you may not
+% use this file except in compliance with the License. You may obtain a copy of
+% the License at
+%
+% http://www.apache.org/licenses/LICENSE-2.0
+%
+% Unless required by applicable law or agreed to in writing, software
+% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+% License for the specific language governing permissions and limitations under
+% the License.
+
+
+-module(couch_views_reducer).
+
+
+-export([
+ start_value/1,
+ decode/1,
+ encode/1,
+ reduce/2,
+ rereduce/3,
+ finalize/2
+]).
+
+
+-include_lib("couch/include/couch_db.hrl").
+
+
+-define(SUMERROR, <<"The _sum function requires that map values be numbers, "
+"arrays of numbers, or objects. Objects cannot be mixed with other "
+"data structures. Objects can be arbitrarily nested, provided that the values "
+"for all fields are themselves numbers, arrays of numbers, or objects.">>).
+
+-define(STATERROR, <<"The _stats function requires that map values be numbers "
+"or arrays of numbers, not '~p'">>).
+
+-define(BUILTIN_SUM, <<"_sum", _/binary>>).
+-define(BUILTIN_COUNT, <<"_count", _/binary>>).
+-define(BUILTIN_STATS, <<"_stats", _/binary>>).
+-define(BUILTIN_COUNT_DISTINCT, <<"_approx_count_distinct", _/binary>>).
+
+
+start_value(<<"_approx_count_distinct">>) ->
+ hyper:new(11);
+
+start_value(_) ->
+ 0.
+
+
+%% Decode if its the _stats object or for _approx_count_distinct
+decode(Value) when is_binary(Value) ->
+ jiffy:decode(Value, [return_maps]);
+
+decode(Value) when is_tuple(Value) ->
+ hyper:from_json(Value);
+
+decode(Value) ->
+ Value.
+
+
+%% Encode if its the _stats object or hyper record
+encode(Value) when is_map(Value) ->
+ jiffy:encode(Value);
+
+encode(Value) ->
+ IsHyperFilter = hyper:is_hyper(Value),
+ if IsHyperFilter == false -> Value; true ->
+ hyper:to_json(Value)
+ end.
+
+
+reduce(?BUILTIN_SUM, Results) ->
+ KVSize = ?term_size(Results),
+ ReduceResults = lists:foldl(fun ({Key, Val}, Acc) ->
+ case maps:is_key(Key, Acc) of
+ true ->
+ #{Key := Sum} = Acc,
+ Sum1 = builtin_sum_rows([Val], Sum),
+ Sum2 = check_sum_overflow(KVSize, ?term_size(Sum1), Sum1),
+ Acc#{Key := Sum2};
+ false ->
+ Acc#{Key => Val}
+ end
+ end, #{}, Results),
+ maps:to_list(ReduceResults);
+
+reduce(?BUILTIN_COUNT, Results) ->
+ ReduceResults = lists:foldl(fun ({Key, _}, Acc) ->
+ case maps:is_key(Key, Acc) of
+ true ->
+ #{Key := Count0} = Acc,
+ Count1 = builtin_sum_rows([1], Count0),
+ Acc#{Key := Count1};
+ false ->
+ Acc#{Key => 1}
+ end
+ end, #{}, Results),
+ maps:to_list(ReduceResults);
+
+reduce(?BUILTIN_COUNT_DISTINCT, Results) ->
+ ReduceResults = lists:foldl(fun ({Key, _Val}, Acc) ->
+ EK = couch_views_encoding:encode(Key),
+ Filter = case maps:is_key(Key, Acc) of
+ true ->
+ maps:get(Key, Acc);
+ false ->
+ hyper:new(11)
Review comment:
We should move `11` to a macro so we're not duplicating magic numbers.
----------------------------------------------------------------
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
[GitHub] [couchdb] chewbranca edited a comment on issue #2456: FDB Builtin
reduce
Posted by GitBox <gi...@apache.org>.
chewbranca edited a comment on issue #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#issuecomment-575836265
So I've been perusing the RFC, `couch_views_skiplist.erl` and the original whitepaper, and one major difference jumps out to me: the skip list implementation here is _not_ a linked list based approach, as per traditional skip lists, but rather embeds the levels into the keys themselves to allow for walking different levels of values. The other thing that jumps out to me is that the querying algorithm utilizes a bottom up approach starting at level zero rather than a top down approach starting at max level, which seems backwards and potentially less performant, especially since right now it seems to spend a lot of time fetching individual keys.
I think storing the levels in the key affords us an opportunity to heavily lean on range queries, and potentially ignore direct key lookups entirely. Essentially I was thinking you could start at max level, take the baseline supplied startkey and endkey, and then do a range query on `{...,...,$MAX_LEVEL,$start_key}..{...,...,$MAX_LEVEL,$end_key}`. Then you take the results and divide and conquer the lower and upper key spaces with similar queries at one level lower, eg lower query of `{...,...,$MAX_LEVEL - 1,$start_key}..{...,...,$MAX_LEVEL - 1,$results[0]}` and upper query of `{...,...,$MAX_LEVEL - 1,$results[-1]}..{...,...,$MAX_LEVEL - 1,$end_key}`. And then you recurse through the lower levels until you've bottomed out or `$start_key == $results[0] and $end_key == $results[-1]`. In theory this algorithm could fulfill the requests without ever needing to do individual key lookups, while maximizing the range of results queried at the upper levels.
Here's a proof of concept query algorithm:
```erlang
query(View, StartKey, EndKey) ->
query(View, ?MAX_LEVEL, StartKey, EndKey).
query(_, ?MIN_LEVEL, _, _) ->
[];
query(View, Level, StartKey, EndKey) ->
LevelDown = Level - 1,
Start = make_key(View, Level, StartKey),
End = make_key(View, Level, EndKey),
[First | _] = Results = fdb_range_query(Start, End),
Last = lists:last(Results),
case {StartKey < First, Last < EndKey} of
{true, true} ->
query(View, LevelDown, StartKey, First) ++ Results ++ query(View, LevelDown, Last, EndKey);
{true, false} when Last =:= EndKey ->
query(View, LevelDown, StartKey, First) ++ Results;
{false, true} when First =:= StartKey ->
Results ++ query(View, LevelDown, Last, EndKey);
{false, false} when First =:= StartKey andalso Last =:= EndKey ->
Results;
{_, _} ->
throw({error, shouldnt_be_here})
end.
make_key(View, Level, Key) ->
{View#view.db, ?DB_VIEWS, View#view.sig, ?VIEW_REDUCE_SK_RANGE, View#view.id, Level, Key}.
```
It's quite possible this approach isn't practical for any number of reasons, but it jumped out to me as a potentially viable algorithm that is simple and utilizes the range query support provided by FoundationDB.
----------------------------------------------------------------
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
[GitHub] [couchdb] chewbranca commented on a change in pull request #2456:
FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
chewbranca commented on a change in pull request #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#discussion_r367069719
##########
File path: src/fabric/src/fabric2_fdb.erl
##########
@@ -1301,14 +1302,17 @@ get_fold_opts(RangePrefix, Options) ->
undefined ->
<<RangePrefix/binary, 16#00>>;
SK2 ->
- erlfdb_tuple:pack({SK2}, RangePrefix)
+ SK3 = if AddTuple == false -> SK2; true -> {SK2} end,
+ Out = erlfdb_tuple:pack(SK3, RangePrefix),
+ Out
Review comment:
Extraneous `Out` variable here.
----------------------------------------------------------------
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
[GitHub] [couchdb] chewbranca commented on a change in pull request #2456:
FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
chewbranca commented on a change in pull request #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#discussion_r367158148
##########
File path: src/couch_views/src/couch_views_fdb.erl
##########
@@ -165,8 +180,20 @@ write_doc(TxDb, Sig, ViewIds, Doc) ->
update_kv_size(TxDb, Sig, ViewId, SizeChange),
[]
end,
- update_map_idx(TxDb, Sig, ViewId, DocId, ExistingKeys, NewRows)
- end, lists:zip(ViewIds, Results)).
+ update_map_idx(TxDb, Sig, ViewId, DocId, ExistingKeys, NewRows),
+ update_reduce_idx(TxDb, Sig, ViewId, ViewReduceFuns, DocId,
+ ExistingKeys, ViewReduceResult)
+ end, lists:zip3(Views, Results, ReduceResults)).
+
+
+update_reduce_idx(TxDb, Sig, ViewId, ViewReduceFuns, DocId, ExistingKeys,
+ ViewReduceResult) ->
Review comment:
Continued function heads should be double indented, eg:
```erlang
update_reduce_idx(TxDb, Sig, ViewId, ViewReduceFuns, DocId, ExistingKeys,
ViewReduceResult) ->
lists:foreach(fun({ViewReduceFun, ReduceResult}) ->
```
----------------------------------------------------------------
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
[GitHub] [couchdb] garrensmith commented on a change in pull request #2456:
FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
garrensmith commented on a change in pull request #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#discussion_r367279447
##########
File path: src/couch_views/src/couch_views_reduce.erl
##########
@@ -0,0 +1,232 @@
+% Licensed under the Apache License, Version 2.0 (the "License"); you may not
+% use this file except in compliance with the License. You may obtain a copy of
+% the License at
+%
+% http://www.apache.org/licenses/LICENSE-2.0
+%
+% Unless required by applicable law or agreed to in writing, software
+% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+% License for the specific language governing permissions and limitations under
+% the License.
+
+-module(couch_views_reduce).
+
+
+-export([
+ run_reduce/2,
+ read_reduce/7
+]).
+
+
+-include("couch_views.hrl").
+-include_lib("couch/include/couch_db.hrl").
+-include_lib("couch_mrview/include/couch_mrview.hrl").
+-include_lib("fabric/include/fabric2.hrl").
+
+
+run_reduce(#mrst{views = Views}, MappedResults) ->
+ lists:map(fun (MappedResult) ->
+ #{
+ results := Results
+ } = MappedResult,
+
+ ReduceResults = lists:map(fun ({View, Result}) ->
+ #mrview{
+ reduce_funs = ViewReduceFuns
+ } = View,
+
+ lists:map(fun({_, ReduceFun}) ->
+ couch_views_reducer:reduce(ReduceFun, Result)
+ end, ViewReduceFuns)
+
+ end, lists:zip(Views, Results)),
+
+ MappedResult#{
+ reduce_results => ReduceResults
+ }
+ end, MappedResults).
Review comment:
I would prefer to leave it more verbose. Its something we have tried to do more in the couch_views map work. I find it a little easier to read.
----------------------------------------------------------------
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
[GitHub] [couchdb] chewbranca commented on a change in pull request #2456:
FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
chewbranca commented on a change in pull request #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#discussion_r367054984
##########
File path: src/couch_views/src/couch_views_reduce.erl
##########
@@ -0,0 +1,232 @@
+% Licensed under the Apache License, Version 2.0 (the "License"); you may not
+% use this file except in compliance with the License. You may obtain a copy of
+% the License at
+%
+% http://www.apache.org/licenses/LICENSE-2.0
+%
+% Unless required by applicable law or agreed to in writing, software
+% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+% License for the specific language governing permissions and limitations under
+% the License.
+
+-module(couch_views_reduce).
+
+
+-export([
+ run_reduce/2,
+ read_reduce/7
+]).
+
+
+-include("couch_views.hrl").
+-include_lib("couch/include/couch_db.hrl").
+-include_lib("couch_mrview/include/couch_mrview.hrl").
+-include_lib("fabric/include/fabric2.hrl").
+
+
+run_reduce(#mrst{views = Views}, MappedResults) ->
+ lists:map(fun (MappedResult) ->
+ #{
+ results := Results
+ } = MappedResult,
+
+ ReduceResults = lists:map(fun ({View, Result}) ->
+ #mrview{
+ reduce_funs = ViewReduceFuns
+ } = View,
+
+ lists:map(fun({_, ReduceFun}) ->
+ couch_views_reducer:reduce(ReduceFun, Result)
+ end, ViewReduceFuns)
+
+ end, lists:zip(Views, Results)),
+
+ MappedResult#{
+ reduce_results => ReduceResults
+ }
+ end, MappedResults).
+
+
+read_reduce(Db, Sig, ViewId, Reducer, UserCallback, UserAcc0, Args) ->
+ #{
+ db_prefix := DbPrefix
+ } = Db,
+
+ ReduceIdxPrefix = couch_views_reduce_fdb:idx_prefix(
+ DbPrefix, Sig, ViewId),
+
+ #mrargs{
+ limit = Limit,
+ group = Group,
+ group_level = GroupLevel,
+ use_skiplist = UseSkipList,
+ skip = Skip
+ } = Args,
+ GroupLevel1 = case Group of
+ true -> group_true;
+ _ -> GroupLevel
+ end,
+ Opts = case UseSkipList of
+ true -> args_to_skiplist_opts(Args);
+ false -> args_to_fdb_opts(Args)
+ end,
+
+ Acc0 = #{
+ sig => Sig,
+ view_id => ViewId,
+ user_acc => UserAcc0,
+ args => Args,
+ callback => UserCallback,
+ reduce_idx_prefix => ReduceIdxPrefix,
+ limit => Limit,
+ row_count => 0,
+ skip => Skip
+ },
+ read_reduce_int(Db, Sig, ViewId, Reducer, GroupLevel1, Acc0, Opts,
+ UseSkipList).
+
+
+read_reduce_int(Db, Sig, ViewId, Reducer, GroupLevel, Acc0, Opts,
+ UseSkiplist) ->
+ try
+ Fun = fun handle_row/3,
+ Acc1 = fabric2_fdb:transactional(Db, fun(TxDb) ->
+ case UseSkiplist of
+ true ->
+ couch_views_skiplist:fold(TxDb, Sig, ViewId,
+ Reducer, GroupLevel, Opts, Fun, Acc0);
+ false ->
+ couch_views_reduce_fdb:fold_level0(TxDb, Sig, ViewId,
+ Reducer, GroupLevel, Opts, Fun, Acc0)
+ end
+ end),
+ #{
+ callback := UserCallback,
+ user_acc := UserAcc1
+ } = Acc1,
+ {ok, maybe_stop(UserCallback(complete, UserAcc1))}
+ catch
+ throw:reduce_transaction_ended ->
+ {ContinueStartKey, Acc} = get(reduce_acc),
+ ReduceIdxPrefix = maps:get(reduce_idx_prefix, Acc),
+
+ StartKey0 = couch_views_reduce_fdb:create_key(ReduceIdxPrefix, 0,
+ ContinueStartKey),
+ StartKey = erlfdb_key:first_greater_or_equal(StartKey0),
+ FdbOpts1 = lists:keyreplace(startkey, 1, Opts,
+ {startkey, StartKey}),
+
+ read_reduce_int(Db, Sig, ViewId, Reducer, GroupLevel, Acc,
+ FdbOpts1, UseSkiplist);
+ throw:{done, Out} ->
+ {ok, Out}
+ end.
+
+
+args_to_skiplist_opts(#mrargs{} = Args) ->
+ #mrargs{
+ start_key = StartKey,
+ end_key = EndKey,
+ direction = Direction,
+ inclusive_end = InclusiveEnd
+ } = Args,
+
+ StartKey1 = case StartKey of
+ undefined ->
+ undefined;
+ StartKey ->
+ StartKey
+ end,
+
+ EndKey1 = case EndKey of
+ undefined ->
+ undefined;
+ EndKey ->
+ EndKey
+ end,
Review comment:
Both of these blocks are no-ops. Were these meant to do something else originally?
----------------------------------------------------------------
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
[GitHub] [couchdb] chewbranca commented on issue #2456: FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
chewbranca commented on issue #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#issuecomment-575836265
So I've been perusing the RFC, `couch_views_skiplist.erl` and the original whitepaper, and one major difference jumps out to me: the skip List implementation here is _not_ a linked list based approach, as per traditional skip Lists, but rather embeds the levels into the keys themselves to allow for walking different levels of values. The other thing that jumps out to me is that the querying algorithm utilizes a bottom up approach starting at level zero rather than a top down approach starting at max level, which seems backwards and potentially less performant, especially since right now it seems to spend a lot of time fetching individual keys.
I think storing the levels in the key affords us an opportunity to heavily lean on range queries, and potentially ignore direct key lookups entirely. Essentially I was thinking you could start at max level, take the baseline supplied startkey and endkey, and then do a range query on `{...,...,$MAX_LEVEL,$start_key}..{...,...,$MAX_LEVEL,$end_key}`. Then you take the results and divide and conquer the lower and upper key spaces with similar queries at one level lower, eg lower query of `{...,...,$MAX_LEVEL - 1,$start_key}..{...,...,$MAX_LEVEL - 1,$results[0]}` and upper query of `{...,...,$MAX_LEVEL - 1,$results[-1]}..{...,...,$MAX_LEVEL - 1,$end_key}`. And then you recurse through the lower levels until you've bottomed out or `$start_key == $results[0] and $end_key == $results[-1]`. In theory this algorithm could fulfill the requests without ever needing to do individual key lookups, while maximizing the range of results queried at the upper levels.
Here's a proof of concept query algorithm:
```erlang
query(View, StartKey, EndKey) ->
query(View, ?MAX_LEVEL, StartKey, EndKey).
query(_, ?MIN_LEVEL, _, _) ->
[];
query(View, Level, StartKey, EndKey) ->
LevelDown = Level - 1,
Start = make_key(View, Level, StartKey),
End = make_key(View, Level, EndKey),
[First | _] = Results = fdb_range_query(Start, End),
Last = lists:last(Results),
case {StartKey < First, Last < EndKey} of
{true, true} ->
query(View, LevelDown, StartKey, First) ++ Results ++ query(View, LevelDown, Last, EndKey);
{true, false} when Last =:= EndKey ->
query(View, LevelDown, StartKey, First) ++ Results;
{false, true} when First =:= StartKey ->
Results ++ query(View, LevelDown, Last, EndKey);
{false, false} when First =:= StartKey andalso Last =:= EndKey ->
Results;
{_, _} ->
throw({error, shouldnt_be_here})
end.
make_key(View, Level, Key) ->
{View#view.db, ?DB_VIEWS, View#view.sig, ?VIEW_REDUCE_SK_RANGE, View#view.id, Level, Key}.
```
It's quite possible this approach isn't practical for any number of reasons, but it jumped out to me as a potentially viable algorithm that is simple and utilizes the range query support provided by FoundationDB>
----------------------------------------------------------------
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
[GitHub] [couchdb] garrensmith commented on issue #2456: FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
garrensmith commented on issue #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#issuecomment-575035893
@chewbranca thanks for the review. I've made the fixes you suggested. Where I would really value your feedback is the actual skip list algorithm. `couch_views_skiplist.erl`. I need another set of eyes to check if it looks correct and if you can see any improvements.
----------------------------------------------------------------
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
[GitHub] [couchdb] chewbranca commented on a change in pull request #2456:
FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
chewbranca commented on a change in pull request #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#discussion_r367079517
##########
File path: src/couch_views/src/couch_views_reduce.erl
##########
@@ -0,0 +1,232 @@
+% Licensed under the Apache License, Version 2.0 (the "License"); you may not
+% use this file except in compliance with the License. You may obtain a copy of
+% the License at
+%
+% http://www.apache.org/licenses/LICENSE-2.0
+%
+% Unless required by applicable law or agreed to in writing, software
+% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+% License for the specific language governing permissions and limitations under
+% the License.
+
+-module(couch_views_reduce).
+
+
+-export([
+ run_reduce/2,
+ read_reduce/7
+]).
+
+
+-include("couch_views.hrl").
+-include_lib("couch/include/couch_db.hrl").
+-include_lib("couch_mrview/include/couch_mrview.hrl").
+-include_lib("fabric/include/fabric2.hrl").
+
+
+run_reduce(#mrst{views = Views}, MappedResults) ->
+ lists:map(fun (MappedResult) ->
+ #{
+ results := Results
+ } = MappedResult,
+
+ ReduceResults = lists:map(fun ({View, Result}) ->
+ #mrview{
+ reduce_funs = ViewReduceFuns
+ } = View,
+
+ lists:map(fun({_, ReduceFun}) ->
+ couch_views_reducer:reduce(ReduceFun, Result)
+ end, ViewReduceFuns)
+
+ end, lists:zip(Views, Results)),
+
+ MappedResult#{
+ reduce_results => ReduceResults
+ }
+ end, MappedResults).
+
+
+read_reduce(Db, Sig, ViewId, Reducer, UserCallback, UserAcc0, Args) ->
+ #{
+ db_prefix := DbPrefix
+ } = Db,
+
+ ReduceIdxPrefix = couch_views_reduce_fdb:idx_prefix(
+ DbPrefix, Sig, ViewId),
+
+ #mrargs{
+ limit = Limit,
+ group = Group,
+ group_level = GroupLevel,
+ use_skiplist = UseSkipList,
+ skip = Skip
+ } = Args,
+ GroupLevel1 = case Group of
+ true -> group_true;
+ _ -> GroupLevel
+ end,
+ Opts = case UseSkipList of
+ true -> args_to_skiplist_opts(Args);
+ false -> args_to_fdb_opts(Args)
+ end,
+
+ Acc0 = #{
+ sig => Sig,
+ view_id => ViewId,
+ user_acc => UserAcc0,
+ args => Args,
+ callback => UserCallback,
+ reduce_idx_prefix => ReduceIdxPrefix,
+ limit => Limit,
+ row_count => 0,
+ skip => Skip
+ },
+ read_reduce_int(Db, Sig, ViewId, Reducer, GroupLevel1, Acc0, Opts,
+ UseSkipList).
+
+
+read_reduce_int(Db, Sig, ViewId, Reducer, GroupLevel, Acc0, Opts,
+ UseSkiplist) ->
+ try
+ Fun = fun handle_row/3,
+ Acc1 = fabric2_fdb:transactional(Db, fun(TxDb) ->
+ case UseSkiplist of
+ true ->
+ couch_views_skiplist:fold(TxDb, Sig, ViewId,
+ Reducer, GroupLevel, Opts, Fun, Acc0);
+ false ->
+ couch_views_reduce_fdb:fold_level0(TxDb, Sig, ViewId,
+ Reducer, GroupLevel, Opts, Fun, Acc0)
+ end
+ end),
+ #{
+ callback := UserCallback,
+ user_acc := UserAcc1
+ } = Acc1,
+ {ok, maybe_stop(UserCallback(complete, UserAcc1))}
Review comment:
Minor nit, but I would separate out the use of `maybe_stop` from the return value as it implies `maybe_stop` always returns something, which is a commonly used pattern in the code base.
Either something like:
```erlang
Acc = maybe_stop(UserCallback(complete, UserAcc1)),
{ok, Acc}
```
or even make it more obvious with just:
```erlang
...
maybe_stop(UserCallback(complete, UserAcc1))
```
and have `maybe_stop` be:
```erlang
maybe_stop({ok, _}=Acc) -> Acc;
maybe_stop({stop, Acc}) -> throw({done, Acc}).
```
----------------------------------------------------------------
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
[GitHub] [couchdb] chewbranca commented on a change in pull request #2456:
FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
chewbranca commented on a change in pull request #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#discussion_r367063674
##########
File path: src/couch_views/src/couch_views_reducer.erl
##########
@@ -0,0 +1,325 @@
+% Licensed under the Apache License, Version 2.0 (the "License"); you may not
+% use this file except in compliance with the License. You may obtain a copy of
+% the License at
+%
+% http://www.apache.org/licenses/LICENSE-2.0
+%
+% Unless required by applicable law or agreed to in writing, software
+% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+% License for the specific language governing permissions and limitations under
+% the License.
+
+
+-module(couch_views_reducer).
+
+
+-export([
+ start_value/1,
+ decode/1,
+ encode/1,
+ reduce/2,
+ rereduce/3,
+ finalize/2
+]).
+
+
+-include_lib("couch/include/couch_db.hrl").
+
+
+-define(SUMERROR, <<"The _sum function requires that map values be numbers, "
+"arrays of numbers, or objects. Objects cannot be mixed with other "
+"data structures. Objects can be arbitrarily nested, provided that the values "
+"for all fields are themselves numbers, arrays of numbers, or objects.">>).
+
+-define(STATERROR, <<"The _stats function requires that map values be numbers "
+"or arrays of numbers, not '~p'">>).
+
+-define(BUILTIN_SUM, <<"_sum", _/binary>>).
+-define(BUILTIN_COUNT, <<"_count", _/binary>>).
+-define(BUILTIN_STATS, <<"_stats", _/binary>>).
+-define(BUILTIN_COUNT_DISTINCT, <<"_approx_count_distinct", _/binary>>).
+
+
+start_value(<<"_approx_count_distinct">>) ->
+ hyper:new(11);
Review comment:
We should move `11` to a macro so we're not duplicating magic numbers.
----------------------------------------------------------------
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
[GitHub] [couchdb] davisp commented on issue #2456: FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
davisp commented on issue #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#issuecomment-579461875
Also I should have mentioned, that algorithmically the example that @chewbranca is a good starting place. @garrensmith was quite right that we'll have to worry about RAM usage and what not. Eventually, the `fdb_range_query` part will be limited in the number of rows returned and then we'll have to handle that complication. However, for the first pass I'd ignore those concerns and write it as simply as currently sketched.
----------------------------------------------------------------
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
[GitHub] [couchdb] garrensmith commented on issue #2456: FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
garrensmith commented on issue #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#issuecomment-576257566
@chewbranca I'm not sure this would work. I think the algorithm treats the skiplist a bit too much like a b-tree. I used your algorithm and did a bit of a mental run-through of the skiplist diagram from the [rfc](https://github.com/apache/couchdb-documentation/blob/8864c35dcb27c9e5996532255fa59e544dee885d/rfcs/012-fdb-reduce.md#create)
There were two things that were issues that I couldn't quite see a way around. The first one is that once we reach an endkey at a level above 0 it assumes it can stop. The issue here is that any node above level 0 contains aggregations of the keys a level below. So we can easily have aggregations of key/values that are not in the group level for that key or not in the range for the query. So far I've found we always have to go down to level 0 to check that an endkey value or group level key has the correct values. So basically a skip list allows us to skip many keys for a group level but we still have to check the final key in the group level to make sure the value does not contain aggregates of values outside the group level.
The second issue is that we would have to keep all the results in memory before doing a final rereduce right at the end. Maybe that isn't an issue, but I think on large reduce queries we will OOM on this. We could rereduce after each level read and that should reduce the number of results. But it will again require some logic to make sure all the values we have are correct.
The bottom-up design I have is definitely not the most optimal, so its great to have you thinking of different designs. But with the bottom-up design, we do find the end keys correctly and can stream group level keys to a user as we traverse the skiplist.
----------------------------------------------------------------
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
[GitHub] [couchdb] davisp edited a comment on issue #2456: FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
davisp edited a comment on issue #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#issuecomment-579461875
Also I should have mentioned, that algorithmically the example that @chewbranca wrote is a good starting place. @garrensmith is quite right that we'll have to worry about RAM usage and what not. Eventually, the `fdb_range_query` part will be limited in the number of rows returned and then we'll have to handle that complication. However, for the first pass I'd ignore those concerns and write it as simply as currently sketched.
----------------------------------------------------------------
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
[GitHub] [couchdb] chewbranca commented on a change in pull request #2456:
FDB Builtin reduce
Posted by GitBox <gi...@apache.org>.
chewbranca commented on a change in pull request #2456: FDB Builtin reduce
URL: https://github.com/apache/couchdb/pull/2456#discussion_r367077871
##########
File path: src/couch_views/src/couch_views_reduce.erl
##########
@@ -0,0 +1,232 @@
+% Licensed under the Apache License, Version 2.0 (the "License"); you may not
+% use this file except in compliance with the License. You may obtain a copy of
+% the License at
+%
+% http://www.apache.org/licenses/LICENSE-2.0
+%
+% Unless required by applicable law or agreed to in writing, software
+% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+% License for the specific language governing permissions and limitations under
+% the License.
+
+-module(couch_views_reduce).
+
+
+-export([
+ run_reduce/2,
+ read_reduce/7
+]).
+
+
+-include("couch_views.hrl").
+-include_lib("couch/include/couch_db.hrl").
+-include_lib("couch_mrview/include/couch_mrview.hrl").
+-include_lib("fabric/include/fabric2.hrl").
+
+
+run_reduce(#mrst{views = Views}, MappedResults) ->
+ lists:map(fun (MappedResult) ->
+ #{
+ results := Results
+ } = MappedResult,
+
+ ReduceResults = lists:map(fun ({View, Result}) ->
+ #mrview{
+ reduce_funs = ViewReduceFuns
+ } = View,
+
+ lists:map(fun({_, ReduceFun}) ->
+ couch_views_reducer:reduce(ReduceFun, Result)
+ end, ViewReduceFuns)
+
+ end, lists:zip(Views, Results)),
+
+ MappedResult#{
+ reduce_results => ReduceResults
+ }
+ end, MappedResults).
Review comment:
Bit of a style nit, but this function is fairly verbose and could be written more succinctly as:
```erlang
run_reduce(#mrst{views = Views}, MappedResults) ->
lists:map(fun (#{results := Results}=MappedResult) ->
ReduceResults = lists:map(fun({#mrview{reduce_funs=Funs}, Result}) ->
lists:map(fun({_, Fun}) ->
couch_views_reducer:reduce(Fun, Result)
end, Funs)
end, lists:zip(Views, Results)),
MappedResult#{reduce_results => ReduceResults}
end, MappedResults).
```
@garrensmith what level of feedback are you looking for in this PR? Would like you more feedback on places that seem overly verbose?
----------------------------------------------------------------
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