[
https://issues.apache.org/jira/browse/PHOENIX-4925?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Bin Shi updated PHOENIX-4925:
-----------------------------
Summary: Use Segment tree to organize Guide Post Info (was: Use
Segment/SUM tree to organize Guide Post Info)
> Use Segment tree to organize Guide Post Info
> --------------------------------------------
>
> Key: PHOENIX-4925
> URL: https://issues.apache.org/jira/browse/PHOENIX-4925
> Project: Phoenix
> Issue Type: Improvement
> Reporter: Bin Shi
> Assignee: Bin Shi
> Priority: Major
>
> As reported, Query compilation (for the sample queries showed below),
> especially deriving estimation and generating parallel scans from guide
> posts, becomes much slower after we introduced Phoenix Stats.
> a. SELECT f1__c FROM MyCustomBigObject__b ORDER BY Pk1__c
> b. SELECT f1__c FROM MyCustomBigObject__b WHERE nonpk1__c = ‘x’ ORDER BY
> Pk1__c
> c. SELECT f1__c FROM MyCustomBigObject__b WHERE pk2__c = ‘x’ ORDER BY
> pk1__c,pk2__c
> d. SELECT f1__c FROM MyCustomBigObject__b WHERE pk1__c = ‘x’ AND nonpk1__c
> ORDER BY pk1__c,pk2__c
> e. SELECT f1__c FROM MyCustomBigObject__b WHERE pk__c >= 'd' AND pk__c <=
> 'm' OR pk__c >= 'o' AND pk__c <= 'x' ORDER BY pk__c // pk__c is the only
> column to make the primary key.
>
> By using prefix encoding for guide post info, we have to decode and traverse
> guide posts sequentially, which causes time complexity in
> BaseResultIterators.getParallelScan(...) to be O(n) , where n is the total
> count of guide posts.
> According to PHOENIX-2417, to reduce footprint in client cache and over
> transmition, the prefix encoding is used as in-memory and over-the-wire
> encoding for guide post info.
> We can use something like Sum Tree (even Binary Indexed Tree) to address both
> memory and performance concerns. The guide posts are partitioned to k chunks
> (k=1024?), each chunk is encoded by prefix encoding and the encoded data is a
> leaf node of the tree. The inner node contains summary info (the count of
> rows, the data size) of the sub tree rooted at the inner node.
> With this tree like data structure, compared to the current data structure,
> the increased size (mainly coming from the n/k-1 inner nodes) is ignorable.
> The time complexity for queries a, b, c can be reduced to O(m) where m is the
> total count of regions; the time complexity for "EXPLAN" queries a, b, c can
> be reduced to O(m) too, and if we support "EXPLAIN (ESTIMATE ONLY)", it can
> even be reduced to O(1). For queries d and e, the time complexity to find the
> start of target scan ranges can be reduced to O(log(n/k)).
> The tree can also integrate AVL and B+ characteristics to support partial
> load/unload when interacting with stats client cache.
>
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
