[kudu-CR] KUDU-2466: implement three-heap merge algorithm

["Adar Dembo (Code Review)" <ge...@cloudera.org>]

Hello Tidy Bot, Mike Percy, Kudu Jenkins, Grant Henke, Todd Lipcon, 

I'd like you to reexamine a change. Please visit

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

to look at the new patch set (#9).

Change subject: KUDU-2466: implement three-heap merge algorithm
......................................................................

KUDU-2466: implement three-heap merge algorithm

This patch implements a new algorithm for efficient merging in
MergeIterator. The algorithm is documented extensively in the code so
there's no point in recapping it here. There's also a high-level overview
with pseudocode available[1].

I microbenchmarked the old implementation against the new one, using both
overlapping and non-overlapping inputs with a varying number of lists and
10000 rows per list (see generic_iterators-test). Here are the scan times,
averaged across five runs:

Parameters                  | old      | new      | diff
----------------------------+----------+----------+------------------
overlapping, 10 lists       | 0.015s   | 0.0522s  | +0.0372   (0.29x)
overlapping, 100 lists      | 1.0798s  | 1.1024s  | +0.0226   (0.98x)
overlapping, 1000 lists     | 184.245s | 22.8156s | -161.4294 (8.07x)
non-overlapping, 10 lists   | 0.0126s  | 0.0196s  | +0.007    (0.64x)
non-overlapping, 100 lists  | 0.5038s  | 0.129s   | -0.3748   (3.91x)
non-overlapping, 1000 lists | 89.8626s | 0.9874s  | -88.8752  (91x)
----------------------------+----------+----------+------------------

The goal was to optimize ORDERED scans for large and mostly compacted
tablets, and the new algorithm does just that. With smaller input, the
overhead of using heaps becomes more pronounced. Overlapping input still
benefits from heap-based merging, but the overlapping defeats the hot vs.
cold optimization provided by the algorithm.

To see how it performed against real data, I tested the algorithm against a
mostly compacted "representative" 40G tablet with 1294 rowsets, all stored
on one disk. I used a new CLI tool that does a full tablet scan without
sending any data over the wire. I ran the tool three times: first with
UNORDERED scans, then with ORDERED scans using the old algorithm, and
finally with ORDERED scans using the new algorithm. Each run did six scans;
to account for any caching effects, I dropped the first scan. Results:

Parameters   | Average run time (s) | Peak RSS (kb)
-------------+----------------------+--------------
UNORDERED:   | 232                  | 710320
ORDERED, old | 33787                | 4465532
ORDERED, new | 979                  | 749440
-------------+----------------------+--------------

Lastly, the new algorithm opens the door to another optimization: while
there's just one "hot" sub-iterator, we can copy data block-by-block instead
of row-by-row. I'll implement this in a follow-up.

1. https://docs.google.com/document/d/1uP0ubjM6ulnKVCRrXtwT_dqrTWjF9tlFSRk0JN2e_O0/edit#

Change-Id: I6deab76a103f45c1b5042b104731e46a771a0f5d
---
M src/kudu/common/encoded_key.cc
M src/kudu/common/generic_iterators-test.cc
M src/kudu/common/generic_iterators.cc
M src/kudu/common/generic_iterators.h
M src/kudu/common/schema.cc
M src/kudu/common/schema.h
6 files changed, 424 insertions(+), 131 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/47/12947/9
-- 
To view, visit http://gerrit.cloudera.org:8080/12947
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I6deab76a103f45c1b5042b104731e46a771a0f5d
Gerrit-Change-Number: 12947
Gerrit-PatchSet: 9
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: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>