Details
-
Improvement
-
Status: Patch Available
-
Major
-
Resolution: Unresolved
-
None
-
None
-
None
-
None
Description
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 MyCustomBigObjectb ORDER BY Pk1_c
b. SELECT f1_c FROM MyCustomBigObjectb WHERE nonpk1c = ‘x’ ORDER BY Pk1_c
c. SELECT f1_c FROM MyCustomBigObjectb WHERE pk2c = ‘x’ ORDER BY pk1c,pk2_c
d. SELECT f1_c FROM MyCustomBigObjectb WHERE pk1c = ‘x’ AND nonpk1c ORDER BY pk1c,pk2_c
e. SELECT f1_c FROM MyCustomBigObjectb WHERE pkc >= 'd' AND pkc <= 'm' OR pkc >= 'o' AND pkc <= 'x' ORDER BY pkc // 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.
Attachments
Attachments
Issue Links
- is a child of
-
PHOENIX-5058 Improvements to client side cache guideposts cache
-
- Open
-
- links to
