[
https://issues.apache.org/jira/browse/HBASE-9969?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Chao Shi updated HBASE-9969:
----------------------------
Attachment: kvheap-benchmark.txt
kvheap-benchmark.png
hbase-9969.patch
I ran two benchmarks:
A) KeyValueHeapBenchmark class included in the patch
It simply constructs a KeyValueHeap from several
CollectionBackedKeyValueScanner and sees how many next/reseek calls per second.
||scanners|| lt-next || lt-reseek || pq-next || pq-reseek ||
|1|17543859.6|3058104|18181818.2|1798561.2|
|2|11299435|5102040.8|11173184.4|3053435.1|
|3|8547008.5|4854368.9|7915567.3|2859866.5|
|4|7936507.9|4866180|5891016.2|2507837|
|5|6711409.4|4739336.5|4748338.1|2296738.6|
"lt-" denotes LoserTree based KeyValueHeap.
"pq-" denotes PriorityQueue based KeyValueHeap.
A complete result (with up to 19 scanners) is attached.
B) ColumnPaginationFilter with offset=1M
I ran a mini-cluster and put a huge number of columns on a single row. Thes
columns are uniformly written to several HFiles. Then query using
ColumnPaginationFilter with offset = 1M. Blocks are cached, so it is CPU
intensive. Qualifiers and values are 4 byte integers. Row key is "test_row".
Blocks are not compressed.
The below table shows how long the scan takes.
|| hfiles || lt || pq ||
| 1 | 749.8 ms | 986.69 ms |
| 2 |1511.28 ms | 2190.97 ms |
| 3 |2392.8 ms | 4029.8 ms |
| 4 | 3318.8 ms | 5760.22 ms
> 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
> Attachments: 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)
