You are viewing a plain text version of this content. The canonical link for it is here.

Posted to reviews@kudu.apache.org by "Adar Dembo (Code Review)" <ge...@cloudera.org> on 2019/01/09 09:42:56 UTC

[kudu-CR] generic iterators: basic MergeIterator dominance

Hello Mike Percy, Grant Henke, Todd Lipcon,

I'd like you to do a code review. Please visit

    http://gerrit.cloudera.org:8080/12197

to review the following change.


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.cc
M src/kudu/common/generic_iterators.h
2 files changed, 214 insertions(+), 67 deletions(-)



  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/97/12197/1
-- 
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: newchange
Gerrit-Change-Id: If59d831240af15bfa7ef5709ec3d105d13b28322
Gerrit-Change-Number: 12197
Gerrit-PatchSet: 1
Gerrit-Owner: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Grant Henke <gr...@apache.org>
Gerrit-Reviewer: Mike Percy <mp...@apache.org>
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>

[kudu-CR] generic iterators: basic MergeIterator dominance

Posted by "Todd Lipcon (Code Review)" <ge...@cloudera.org>.

Todd Lipcon has posted comments on this change. ( http://gerrit.cloudera.org:8080/12197 )

Change subject: generic_iterators: basic MergeIterator dominance
......................................................................


Patch Set 5:

(4 comments)

http://gerrit.cloudera.org:8080/#/c/12197/5//COMMIT_MSG
Commit Message:

http://gerrit.cloudera.org:8080/#/c/12197/5//COMMIT_MSG@11
PS5, Line 11: sub-iterator if its current block's last primary key is lexicographically
            : greater than another sub-iterator's current block's first primary key
is this phrased backwards? ie:

If we have sub-iterators A and B, where the last key of A is less than the first key of B, then we can say that A dominates B.


http://gerrit.cloudera.org:8080/#/c/12197/5/src/kudu/common/generic_iterators.cc
File src/kudu/common/generic_iterators.cc:

http://gerrit.cloudera.org:8080/#/c/12197/5/src/kudu/common/generic_iterators.cc@536
PS5, Line 536:     for (const auto& dominated_s : s.dominated()) {
is it worth adding:

  if (available >= dst->row_capacity()) break;

here, given we're going to 'min()' it anyway? that avoids iterating over all sub-iters for every batch. I think the common case is that we could early-out very quickly.


http://gerrit.cloudera.org:8080/#/c/12197/5/src/kudu/common/generic_iterators.cc@593
PS5, Line 593:       // main list.
if the dominated iterators were stored as a min-heap by their min_key, this could be an O(1) check instead of O(n), right?


http://gerrit.cloudera.org:8080/#/c/12197/5/src/kudu/common/generic_iterators.cc@606
PS5, Line 606:       for (auto& s : states_) {
similarly here if we have a heap of states_ we could O(1) find the state_ with the smallest max_key and check if that now dominates the newly exposed min_key?



-- 
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: comment
Gerrit-Change-Id: If59d831240af15bfa7ef5709ec3d105d13b28322
Gerrit-Change-Number: 12197
Gerrit-PatchSet: 5
Gerrit-Owner: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Grant Henke <gr...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Mike Percy <mp...@apache.org>
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Sat, 12 Jan 2019 00:21:16 +0000
Gerrit-HasComments: Yes