Mailing-List: contact issues-help@hbase.apache.org; run by ezmlm
Precedence: bulk
Date: Sat, 16 Nov 2013 01:22:19 +0000 (UTC)
From: "Lars Hofhansl (JIRA)" <jira@apache.org>
To: issues@hbase.apache.org
Message-ID: <JIRA.12679182.1384419274167.84374.1384564939412@arcas>
In-Reply-To: <JIRA.12679182.1384419274167@arcas>
References: <JIRA.12679182.1384419274167@arcas>
Subject: [jira] [Commented] (HBASE-9969) Improve KeyValueHeap using loser
 tree
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


    [ https://issues.apache.org/jira/browse/HBASE-9969?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13824319#comment-13824319 ] 

Lars Hofhansl commented on HBASE-9969:
--------------------------------------

I have not found a scenario, yet, where this is slower. Seems generally safe to pull into all branches.
And since we now "own" the heap implementation we can optimize this later as we see fit.

> 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, 0.94.15
>
>         Attachments: 9969-0.94.txt, 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)