[
https://issues.apache.org/jira/browse/HBASE-9969?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13823176#comment-13823176
]
Matt Corgan commented on HBASE-9969:
------------------------------------
One problem with the current java.util.PriorityQueue is that it makes the wrong
assumption (for HBase) about where the next key will land in the queue. It
assumes a worst case scenario where each KV added to it is "sifted up" from the
end of the queue. I think in HBase it's best to assume that the next KV will
jump immediately to the front of the queue since many consecutive KV's are
often clumped together in a row. With 8 storefiles, the normal case would go
from ~3 comparisons down to 1. I think the behavior could be reversed by
negating the comparator.
Maybe the LoserTree could also benefit by optimistically assuming each new KV
will sort to the front and be the next result.
> Improve KeyValueHeap using loser tree
> -------------------------------------
>
> Key: HBASE-9969
> URL: https://issues.apache.org/jira/browse/HBASE-9969
> Project: HBase
> Issue Type: Improvement
> Components: Performance, regionserver
> Reporter: Chao Shi
> Assignee: Chao Shi
> Fix For: 0.98.0, 0.96.1
>
> Attachments: hbase-9969.patch, hbase-9969.patch,
> kvheap-benchmark.png, kvheap-benchmark.txt
>
>
> LoserTree is the better data structure than binary heap. It saves half of the
> comparisons on each next(), though the time complexity is on O(logN).
> Currently A scan or get will go through two KeyValueHeaps, one is merging KVs
> read from multiple HFiles in a single store, the other is merging results
> from multiple stores. This patch should improve the both cases whenever CPU
> is the bottleneck (e.g. scan with filter over cached blocks, HBASE-9811).
> All of the optimization work is done in KeyValueHeap and does not change its
> public interfaces. The new code looks more cleaner and simpler to understand.
--
This message was sent by Atlassian JIRA
(v6.1#6144)
