Hello Kudu Jenkins, Todd Lipcon,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/12587
to look at the new patch set (#2).
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 the new "hot/cold" double
heap 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:
- NaiveMergeIterator, half-overlapping: 0.539506912231s Counter({'cmp': 500021,
'peak_blocks_in_mem': 100})
- SingleHeapMergeIterator, half-overlapping: 0.138118982315s Counter({'cmp':
203902, 'peak_blocks_in_mem': 3})
- DoubleHeapMergeIterator, half-overlapping: 0.0430920124054s Counter({'cmp':
29012, 'peak_blocks_in_mem': 3})
- NaiveMergeIterator, non-overlapping: 0.564009904861s Counter({'cmp': 495000,
'peak_blocks_in_mem': 100})
- SingleHeapMergeIterator, non-overlapping: 0.152870893478s Counter({'cmp':
202848, 'peak_blocks_in_mem': 1})
- DoubleHeapMergeIterator, non-overlapping: 0.0303959846497s Counter({'cmp':
4452, 'peak_blocks_in_mem': 1})
- NaiveMergeIterator, overlapping: 1.08536100388s Counter({'cmp': 980399,
'peak_blocks_in_mem': 100})
- SingleHeapMergeIterator, overlapping: 0.120500087738s Counter({'cmp': 176355,
'peak_blocks_in_mem': 100})
- DoubleHeapMergeIterator, overlapping: 0.115973949432s Counter({'cmp': 179273,
'peak_blocks_in_mem': 100})
The new algorithm shows some slight overhead compared 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, 351 insertions(+), 0 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/87/12587/2
--
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: newpatchset
Gerrit-Change-Id: I6ae1d2f9e4f41337f475146c648cbab122395f83
Gerrit-Change-Number: 12587
Gerrit-PatchSet: 2
Gerrit-Owner: Adar Dembo <a...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Todd Lipcon <t...@apache.org>
