hbase-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Chao Shi (JIRA)" <j...@apache.org>
Subject [jira] [Created] (HBASE-9969) Improve KeyValueHeap using loser tree
Date Thu, 14 Nov 2013 08:55:20 GMT
Chao Shi created HBASE-9969:
-------------------------------

             Summary: Improve KeyValueHeap using loser tree
                 Key: HBASE-9969
                 URL: https://issues.apache.org/jira/browse/HBASE-9969
             Project: HBase
          Issue Type: Improvement
            Reporter: Chao Shi


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)

Mime
View raw message