[
https://issues.apache.org/jira/browse/HBASE-9969?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13823336#comment-13823336
]
Matt Corgan commented on HBASE-9969:
------------------------------------
KeyValueHeapBenchmark.java
{code}
private List<KeyValue> randomKeyValues() {
List<KeyValue> kvs =
Lists.newArrayListWithExpectedSize(NUM_KEYS_PER_SCANNER);
for (int i = 0; i < NUM_KEYS_PER_SCANNER; i++) {
byte[] row = Bytes.toBytes(random.nextLong());
KeyValue kv = new KeyValue(row, FAMILY, null);
kvs.add(kv);
}
return kvs;
}
{code}
I wonder if you should make ~10 cols/row, and NUM_KEYS_PER_SCANNER/10 rows.
This should exacerbate the problem i mentioned above. Right now it's testing
the ideal scenario which almost never exists. In fact, with time series data
you have the exact opposite scenario where every Cell should go straight to the
front of the queue.
{quote}I don't quite understand this. The one I understood to improve is to
compare against the previous second top value (i.e. tree[1]) before going
through leaf to root comparisions. But this will add one more comparison on the
worst case.{quote}Could a slightly customized version of the algorithm
eliminate the extra comparison for the worst case scenario? Even if not, I
think the best case scenario happens 10x+ as often as worst case, so maybe it's
a good trade-off.
> 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-v2.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)
