hbase-dev 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,

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

View raw message