Becker Ewing created HBASE-28043:
------------------------------------
Summary: 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
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)
See the attached diagrams for the current and proposed behavior.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
