[jira] [Commented] (HBASE-28043) Reduce seeks from beginning of block in StoreFileScanner.seekToPreviousRow

["Bryan Beaudreault (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/HBASE-28043?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17758625#comment-17758625 ] 

Bryan Beaudreault commented on HBASE-28043:
-------------------------------------------

The idea sounds solid, thanks for the design diagrams! One thing we should keep in mind is that it's very common to do 1-row reverse scans, as a {{{}getRowBefore(row){}}}. This is used heavily in meta region lookups. So lets make sure we design it such that we don't regress meta region lookups. Maybe we only do the previousRow lookup on the second seek, rather than the first.

> 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
>         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 2(N-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 (N-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)