[
https://issues.apache.org/jira/browse/HBASE-28043?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Bryan Beaudreault updated HBASE-28043:
--------------------------------------
Fix Version/s: 2.6.0
3.0.0-beta-1
Release Note: Optimizes StoreFileScanner.seekToPreviousRow to use keep
track of a hint which allows us to eliminate one seek per call, resulting in
40% or more throughput increase for reverse scans. External users (Phoenix) of
this LimitedPrivate method should be aware of the change in semantics. It is
expected that seekToPreviousRow is used for scanning backwards in the
StoreFile. Calling with an originalKey greater than the previously passed key
(i.e. forward in the StoreFile), the originalKey will not be honored. Instead
use seek for this case.
Resolution: Fixed
Status: Resolved (was: Patch Available)
Thanks for all the work here [~bewing]! Big optimization
> Reduce seeks from beginning of block in StoreFileScanner.seekToPreviousRow
> --------------------------------------------------------------------------
>
> Key: HBASE-28043
> URL: https://issues.apache.org/jira/browse/HBASE-28043
> Project: HBase
> Issue Type: Improvement
> Reporter: Becker Ewing
> Assignee: Becker Ewing
> Priority: Major
> Fix For: 2.6.0, 3.0.0-beta-1
>
> Attachments: Current_SeekToPreviousRowBehavior.png,
> Proposed_SeekToPreviousRowBehavior.png
>
>
> Currently, for non-RIV1 DBE encodings, each call to
> [StoreFileScanner.seekToPreviousRow|https://github.com/apache/hbase/blob/89ca7f4ade84c84a246281c71898543b6161c099/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreFileScanner.java#L493-L506]
> (a common operation in reverse scans) results in two seeks:
> # Seek from the beginning of the block to before the given row to find the
> prior row
> # Seek from the beginning of the block to the first cell of the prior row
> So if there are "N" rows in a block, a reverse scan through each row results
> in seeking past summation from i=1 to N (2(i-1)) rows.
>
> This is a particularly expensive operation for tall tables that have many
> rows in a block.
>
> By introducing a state variable "previousRow" to StoreFileScanner, I believe
> that we could modify the seeking algorithm to be:
> # Seek from the beginning of the block to before the given row to find the
> prior row
> # Seek from the beginning of the block to before the row that is before the
> row that was just seeked to (i.e. 2 rows back). _Save_ this as a hint for
> where the prior row is in "previousRow"
> # Reseek from "previousRow" (2 rows back from start) to 1 row back from
> start (to the actual previousRow)
> Then the rest of the calls where a "previousRow" is present, you just need to
> seek to the beginning of the block once instead of twice, i.e.
> # seek from the beginning of the block to right before the beginning of your
> "previousRow" marker. Save this as the new "previousRow" marker
> # Reseek to the next row (i.e. your previous "previousRow" marker)
>
> If there are "N" rows in a block, a reverse scan from row N to row 0 results
> in seeking past approximately summation from i=1 to N (i-1) rows i.e. 50%
> less than the current behavior.
>
> See the attached diagrams for the current and proposed behavior.
>
>
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
