Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/12197 )
Change subject: generic_iterators: basic MergeIterator dominance ...................................................................... Patch Set 7: (1 comment) http://gerrit.cloudera.org:8080/#/c/12197/7/src/kudu/common/generic_iterators.cc File src/kudu/common/generic_iterators.cc: http://gerrit.cloudera.org:8080/#/c/12197/7/src/kudu/common/generic_iterators.cc@589 PS7, Line 589: // Move all sub-iterators dominated by 'smallest' back into the main list : // before destroying 'smallest'. I think we need to recheck these sub-iterators for dominance instead of moving them back into states_. The algorithm that establishes dominance relations when the MergeIterator is initialized is greedy, and thus which relations are established is a function of the order of iterators passed to the constructor. Thus, it's possible to start off with "sub-optimal" relations (i.e. relations that will be broken earlier in the merge). Consider this example: - Iter A with block [5, 10] - Iter B with block [16, 20] - Iter C with block [11, 15] If initialization yielded dominance relations A>B and A>C, when we fully exhaust A we should establish C>B. The current code would just throw both back into states_. Mike/Todd, what do you guys think? -- 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: 7 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: Thu, 24 Jan 2019 02:13:39 +0000 Gerrit-HasComments: Yes
