Adar Dembo has submitted this change and it was merged. ( http://gerrit.cloudera.org:8080/13536 )
Change subject: KUDU-2809 (4/6): skip unobservable rows when iterating a DRS ...................................................................... KUDU-2809 (4/6): skip unobservable rows when iterating a DRS The counterpart to the MRS patch, this one makes an equivalent change to the DRS diff scanning logic. It's far more complicated than the MRS version, for several reasons: 1. A row's history is fragmented across multiple delta stores. 2. UNDOs' view of time is inverted, complicating attempts at tracing a row's liveness across stores. To implement this, we need to reconsider how the DeltaApplier initializes its selection vector. The overall structure remains the same: 1. The DeltaApplier sets up data structure to capture selectivity info. 2. It invokes a method on each store to add that store's selectivity info to the structure. 3. Finally, converts the structure into the selection vector. Before this patch, it was sufficient for the data structure to be the selection vector itself. But now the selection vector is insufficient. Instead we use a new data structure which tracks, for each row, the row's oldest and newest selected deltas. Armed with this information, we can omit unobservable rows at conversion time: if a row was dead before the oldest delta and after the newest delta, its lifetime exists entirely within the diff scan and it should be omitted from the results. Much of the complexity here lies with the need to totally order all deltas, regardless of whether they're UNDOs or REDOs, even if they share the same timestamps (fuzz-itest is a super effective way of testing this). The ordering starts with timestamps, but then orders deltas in some potentially non-obvious ways based on Kudu invariants: 1. Timestamps (obviously) 2. UNDOs, then REDOs. Within a rowset all UNDOs come before REDOs. 3. The order in which the deltas were observed in the store. This is equivalent to the order in which they are applied. Change-Id: I2b616c4e8b99dbc7063b940bcb35352f87ab0226 Reviewed-on: http://gerrit.cloudera.org:8080/13536 Reviewed-by: Mike Percy <[email protected]> Tested-by: Kudu Jenkins --- M src/kudu/common/row_changelist.cc M src/kudu/common/row_changelist.h M src/kudu/common/rowblock.h M src/kudu/tablet/compaction.cc M src/kudu/tablet/delta_applier.cc M src/kudu/tablet/delta_iterator_merger.cc M src/kudu/tablet/delta_iterator_merger.h M src/kudu/tablet/delta_store.cc M src/kudu/tablet/delta_store.h M src/kudu/tablet/deltafile.cc M src/kudu/tablet/deltafile.h M src/kudu/tablet/deltamemstore.cc M src/kudu/tablet/deltamemstore.h M src/kudu/tablet/tablet-test-util.h M src/kudu/tablet/tablet-test.cc 15 files changed, 387 insertions(+), 60 deletions(-) Approvals: Mike Percy: Looks good to me, approved Kudu Jenkins: Verified -- To view, visit http://gerrit.cloudera.org:8080/13536 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: merged Gerrit-Change-Id: I2b616c4e8b99dbc7063b940bcb35352f87ab0226 Gerrit-Change-Number: 13536 Gerrit-PatchSet: 8 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: Will Berkeley <[email protected]>
