[
https://issues.apache.org/jira/browse/PHOENIX-4925?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16880750#comment-16880750
]
Bin Shi commented on PHOENIX-4925:
----------------------------------
[~lhofhansl]
I totally I agree with your opinion. The purpose of introducing a variant
Segment tree into Phoenix Stats is not only for quick size estimation but also
for decoupling he granularity stored in SYSTEM.STATS from both the granularity
stored on the client and the granularity of the scanning. A leaf node of this
variant segment tree is grouped into a guide post chunk which is not only the
minimal unit for compression/encoding but also the minimal unit for scan. The
guide posts of a chunk isn't necessary to be loaded into the tree and into the
stats cache. If guide posts of a chunk isn't loaded from SYSTEM.STATS, the
chunk /the leaf node will just contain the accumulative estimation info and the
key range of that chunk.
This Jira has the right link https://salesforce.quip.com/taWiALFmhquO to the
design doc, and I have double checked that you have full access with your
salesforce account. Actually, it has been set to share with anyone who has this
link. Could you try one more time to open the doc at
[https://salesforce.quip.com/taWiALFmhquO?|https://salesforce.quip.com/taWiALFmhquO]
Let me know if you still can't open it.
> Use a Variant 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
> Attachments: PHOENIX-4925.phoenix-stats.0502.patch,
> PHOENIX-4925.phoenix-stats.0510.patch
>
> Time Spent: 13h 40m
> Remaining Estimate: 0h
>
> 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 Segment 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)
