[ https://issues.apache.org/jira/browse/HBASE-9969?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Matt Corgan updated HBASE-9969: ------------------------------- Attachment: hbase-9969-pq-v1.patch attaching hbase-9969-pq-v1.patch * adds KeyValueScannerPriorityQueue, which is a stripped down copy of PriorityQueue that we can play with * adds KeyValueScannerHeap (almost identical to KeyValueHeap, but uses the above) * includes LoserTreeKeyValueHeap and LoserTree * each of the 3 heaps implments BenchmarkableKeyValueHeap (not complete) * enhances KeyValueHeapBenchmark to benchmark all 3 implementations * always tests 1mm KVs, no matter how many scanners * sorts the input KVs, though that doesn't seem to matter much * does a few warmup runs One problem is that this goes from 1 to 3 implementations behind the same interface which may not get inlined as well. Absolute performance will therefore be lower, but hopefully performance will be comparable across the 3 implementations. > 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, hbase-9969-pq-v1.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)