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 (#6). Change subject: generic_iterators: implement three-heap merge algorithm ...................................................................... generic_iterators: 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, 418 insertions(+), 131 deletions(-) git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/47/12947/6 -- 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: 6 Gerrit-Owner: Adar Dembo <a...@cloudera.com> Gerrit-Reviewer: Grant Henke <granthe...@apache.org> Gerrit-Reviewer: Kudu Jenkins (120) Gerrit-Reviewer: Mike Percy <mpe...@apache.org> Gerrit-Reviewer: Tidy Bot (241) Gerrit-Reviewer: Todd Lipcon <t...@apache.org>