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 <[email protected]> Gerrit-Reviewer: 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]> Gerrit-Comment-Date: Sat, 12 Jan 2019 00:21:16 +0000 Gerrit-HasComments: Yes
