You are viewing a plain text version of this content. The canonical link for it is here.

Posted to issues@hbase.apache.org by "Nick Dimiduk (JIRA)" <ji...@apache.org> on 2016/02/26 23:04:18 UTC

[jira] [Created] (HBASE-15352) FST BlockEncoder

Nick Dimiduk created HBASE-15352:
------------------------------------

             Summary: FST BlockEncoder
                 Key: HBASE-15352
                 URL: https://issues.apache.org/jira/browse/HBASE-15352
             Project: HBase
          Issue Type: New Feature
          Components: regionserver
            Reporter: Nick Dimiduk
             Fix For: 2.0.0, 1.4.0


We could improve on the existing [PREFIX_TREE block|http://hbase.apache.org/devapidocs/org/apache/hadoop/hbase/codec/prefixtree/package-summary.html] encoder by upgrading the persistent data structure from a trie to a finite state transducer. This would theoretically allow us to reuse bytes not just for rowkey prefixes, but infixes and suffixes as well. My read of the literature means we may also be able to encode values as well, further reducing storage size when values are repeated (ie, a "customer id" field with very low cardinality -- probably happens a lot in our denormalized world). There's a really nice [blog post|http://blog.burntsushi.net/transducers/] about this data structure, and apparently our siblings in Lucene make heavy use of [their implementation|http://lucene.apache.org/core/5_5_0/core/org/apache/lucene/util/fst/package-summary.html#package_description].



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)