basho/riak_kv — pull request #333 by beerriot (2012-05-25 20:52:12+00:00)
Title: Speed up accumulation of results for single-keep MR queries

A similar solution to what was suggested in PR #331 is applied here. In fact, the branch is based on #331's branch, so this PR is targeted there to make the diff more obvious.

Result lists are now built in reverse order to take advantage of the cheaper cons operation instead of the more expensive append. It is assumed that the number of phases producing results is small enough that a linear search through a list of phases will not be expensive.

Testing can be done in a similar manner:

```
# Load 50k items into bucket fmrg2
for i in {1..10000}; do curl -X PUT -H "content-type: text/plain" http://localhost:8091/riak/fmrg2/$i --data "hello"; done

# Two-reduce query
time curl -s -X POST -H "content-type: application/json" http://localhost:8091/mapred --data "{\"inputs\":\"fmrg2\",\"query\":[{\"reduce\":{\"language\":\"erlang\",\"module\":\"riak_kv_mapreduce\",\"function\":\"reduce_identity\",\"keep\":true}},{\"reduce\":{\"language\":\"erlang\",\"module\":\"riak_kv_mapreduce\",\"function\":\"reduce_identity\",\"keep\":true}}]}" > /dev/null

# Two-map query
time curl -s -X POST -H "content-type: application/json" http://localhost:8091/mapred --data "{\"inputs\":\"fmrg2\",\"query\":[{\"map\":{\"language\":\"javascript\",\"source\":\"function(v) { return [ [v.bucket, v.key] ]; }\",\"keep\":true}},{\"map\":{\"language\":\"javascript\",\"source\":\"function(v) { return [v.key]; }\",\"keep\":true}}]}" > /dev/null
```

These two queries test important different behaviors: two reduces in a row mean that the sink will likely read all of one phase's results and then all of the others, while two maps in a row is likely to yield a mixed order of each phases results. This could have an affect on the efficiency of the aggregation process.

On a Mac laptop with the eleveldb backend with this 50k set, I see the two-reduce query drop from ~72 seconds to ~28.5 seconds. On the same system, I see the two-map query drop from ~95 seconds to ~40 seconds. It may also be worth noting that the 10k input described in #331 drops from 3.5 seconds to ~2.5 seconds for two-reduce, and from 9.5 seconds to ~8.2 seconds for two-map, reinforcing that this improvement is about growth of result counts.