Uploaded image for project: 'HBase'
  1. HBase
  2. HBASE-9969

Improve KeyValueHeap using loser tree

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Closed
    • Major
    • Resolution: Won't Fix
    • None
    • None
    • Performance, regionserver
    • None

    Description

      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.

      Attachments

        1. hbase-9969-pq-v2.patch
          53 kB
          Matt Corgan
        2. KeyValueHeapBenchmark_v2.ods
          7 kB
          Matt Corgan
        3. KeyValueHeapBenchmark_v1.ods
          7 kB
          Matt Corgan
        4. hbase-9969-pq-v1.patch
          54 kB
          Matt Corgan
        5. hbase-9969-v3.patch
          28 kB
          Chao Shi
        6. 9969-0.94.txt
          27 kB
          Lars Hofhansl
        7. hbase-9969-v2.patch
          28 kB
          Chao Shi
        8. hbase-9969.patch
          25 kB
          Chao Shi
        9. kvheap-benchmark.txt
          0.8 kB
          Chao Shi
        10. kvheap-benchmark.png
          16 kB
          Chao Shi
        11. hbase-9969.patch
          25 kB
          Chao Shi

        Activity

          People

            Unassigned Unassigned
            stepinto Chao Shi
            Votes:
            0 Vote for this issue
            Watchers:
            17 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: