[
https://issues.apache.org/jira/browse/HBASE-9969?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13828502#comment-13828502
]
Chao Shi commented on HBASE-9969:
---------------------------------
I found it is hard to optimize the consecutive for loser tree. Doing a quick
comparison against the second minimal element is not possible, as the second
minimal element in the loser tree is not always "tree\[1\]" (consider the case
that the two top players meet in the quarterfinal in a tournament game).
I also noticed that loser tree has generally better performance on "reseek",
which is the use case my benchmark B in the first post (you know, SEEK_NEXT_ROW
will result in reseeks).
[~mcorgan], do you have any ideas regarding to mix the good of both? I have no
idea, as the two are so different.
Another optimization: as KVs are usually sharing common prefixes, we can skip
such common part during comparisons. I haven't thought on this carefully. Just
mention it here in case someone may have better thoughts based on it.
> 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: 9969-0.94.txt, KeyValueHeapBenchmark_v1.ods,
> KeyValueHeapBenchmark_v2.ods, hbase-9969-pq-v1.patch, hbase-9969-pq-v2.patch,
> hbase-9969-v2.patch, hbase-9969-v3.patch, 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)
