Optimize couch_key_tree:stem/2
authorPaul J. Davis <paul.joseph.davis@gmail.com>
Wed, 13 Jun 2018 18:15:11 +0000 (13:15 -0500)
committerPaul J. Davis <paul.joseph.davis@gmail.com>
Sat, 16 Jun 2018 21:56:53 +0000 (16:56 -0500)
commitaebdbc452573f70f4e50d88af5814d0fbe936333
tree3592cf5288ad409a6e2e6da18378102d622f4a73
parent000766c4f8b51562757818dfa36b3e6579d16309
Optimize couch_key_tree:stem/2

This is two related optimizations for stemming revisions. The first
optimization re-writes the stemming algorithm to drop it from an O(N^2)
to O(N) operation by using a depth first search through the tree and
tracking which revisions are within `revs_limit` revs from a leaf
dropping any revision that exceeds that limit.

The second optimization is just that we avoid calling stemming more
often than necessary by switching away from using `merge/3` to `merge/2`
and then calling `stem/2` only when necessary.

Co-Authored-By: Nick Vatamaniuc <vatamane@apache.org>
src/couch/src/couch_db.erl
src/couch/src/couch_db_updater.erl
src/couch/src/couch_key_tree.erl