Hello Todd Lipcon,
I'd like you to do a code review. Please visit
http://gerrit.cloudera.org:8080/12587
to review the following change.
Change subject: experiments: merge iterator optimization tests
......................................................................
experiments: merge iterator optimization tests
Here's a brief exploration into various MergeIterator algorithms, prototyped
in Python. Only after I was done did I see that there was an existing
experiment on this same subject in C++ (see merge-test.cc). It's not all
wasted work though; that experiment didn't include this algorithm, nor did
it account for all MergeIterator quirks, such as paged blocks and
lower/upper bounds.
Below are some timing results on my laptop, using the default parameters.
I've omitted the "naive" results because they're much much slower and thus
not worth discussing:
- SingleHeapMergeIterator with non-overlapped input: 2.81650519371s
- DoubleHeapMergeIterator with non-overlapped input: 2.00009703636s
- SingleHeapMergeIterator with overlapped input: 3.01065206528s
- DoubleHeapMergeIterator with overlapped input: 2.99612498283s
The new "hot/cold" algorithm is comparable to a heap-based merge when input
is overlapped, but really shines when it's non-overlapped (i.e. when the
tablet is fully compacted).
Change-Id: I6ae1d2f9e4f41337f475146c648cbab122395f83
---
A src/kudu/experiments/merge-test.py
1 file changed, 295 insertions(+), 0 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/87/12587/1
--
To view, visit http://gerrit.cloudera.org:8080/12587
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: I6ae1d2f9e4f41337f475146c648cbab122395f83
Gerrit-Change-Number: 12587
Gerrit-PatchSet: 1
Gerrit-Owner: Adar Dembo <[email protected]>
Gerrit-Reviewer: Todd Lipcon <[email protected]>
