Hello Mike Percy, Kudu Jenkins, Grant Henke, Todd Lipcon,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/12197
to look at the new patch set (#2).
Change subject: generic_iterators: basic MergeIterator dominance
......................................................................
generic_iterators: basic MergeIterator dominance
This patch adds a dominance algorithm to the MergeIterator. The idea is:
rather than considering every sub-iterator for merging, we can omit a
sub-iterator if its current block's last primary key is lexicographically
greater than another sub-iterator's current block's first primary key. In
this state the omitted sub-iterator is said to be "fully dominated" and the
two sub-iterators are said to have a "dominance relation".
We're already using a similar algorithm in merge compaction (see
MergeCompactionInput in compaction.cc). I toyed with the idea of reusing the
code but found it to be too unwieldy to be workable.
Additionally, because dominance relations come and go as blocks are pulled,
this patch also makes all MergeIterState lists intrusive.
To test, I ran TestMerge and TestMergeOverlap twice with --num-lists=50:
once with dominance and once without. The table below captures the
MergeIterator histogram for all four runs.
Basic-overlap | basic-nonoverlap | dom-overlap | dom-nonoverlap
--------------+------------------+-------------+---------------
total count: 43699 | 43664 | 43840 | 43631
total sum: 2155405 | 1113852 | 2059279 | 417242
min: 1 | 1 | 1 | 1
mean: 49.3239 | 25.5096 | 46.9726 | 9.56297
p75: 50 | 38 | 48 | 15
p95: 50 | 48 | 50 | 20
p99: 50 | 50 | 50 | 21
p99.9: 50 | 50 | 50 | 21
p99.99: 50 | 50 | 50 | 21
max: 50 | 50 | 50 | 21
The results show a mild improvement when the input is fully overlapping and
a more significant one (almost 3x) when non-overlapping. Real tablets are
likely to fall in between the two ends of the spectrum, edging closer to
non-overlapping the more they are compacted.
More optimizations are on the way:
- Better memory consumption by establishing dominance using rowset bounds.
- Faster merge by copying block-by-block when there's only one non-dominated
sub-iterator.
Change-Id: If59d831240af15bfa7ef5709ec3d105d13b28322
---
M src/kudu/common/generic_iterators-test.cc
M src/kudu/common/generic_iterators.cc
M src/kudu/common/generic_iterators.h
3 files changed, 256 insertions(+), 68 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/97/12197/2
--
To view, visit http://gerrit.cloudera.org:8080/12197
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: If59d831240af15bfa7ef5709ec3d105d13b28322
Gerrit-Change-Number: 12197
Gerrit-PatchSet: 2
Gerrit-Owner: Adar Dembo <[email protected]>
Gerrit-Reviewer: Grant Henke <[email protected]>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Mike Percy <[email protected]>
Gerrit-Reviewer: Todd Lipcon <[email protected]>
