[jira] [Commented] (ASTERIXDB-2453) Improve the Constant Merge Policy

["ASF subversion and git services (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/ASTERIXDB-2453?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16631178#comment-16631178 ] 

ASF subversion and git services commented on ASTERIXDB-2453:
------------------------------------------------------------

Commit 1aeb8b6cef3a50d7639749c96538ec2cecaaad9c in asterixdb's branch refs/heads/master from luochen01
[ https://git-wip-us.apache.org/repos/asf?p=asterixdb.git;h=1aeb8b6 ]

[ASTERIXDB-2453] Add Improved Constant Merge Policy

- user model changes: no
- storage format changes: no
- interface changes: no

Details:
- The current constant merge policy is unsuable because of its high
merge cost, i.e., O(N*N) where N is the number of flushes. This patch
replaces the previous constant merge policy with a more efficient policy
that still enforces a maximum number of components but greatly lowers
the merge cost.
- Extend AbstractLSMIndex with a method to return the total number of
flushes, based on the file name sequencer. This is required by the new
policy.

Change-Id: Ie5f83a4d5fdd3f036b823c906df1760f5110ae0a
Reviewed-on: https://asterix-gerrit.ics.uci.edu/2971
Sonar-Qube: Jenkins <je...@fulliautomatix.ics.uci.edu>
Tested-by: Jenkins <je...@fulliautomatix.ics.uci.edu>
Reviewed-by: Murtadha Hubail <mh...@apache.org>
Contrib: Jenkins <je...@fulliautomatix.ics.uci.edu>
Integration-Tests: Jenkins <je...@fulliautomatix.ics.uci.edu>


> Improve the Constant Merge Policy
> ---------------------------------
>
>                 Key: ASTERIXDB-2453
>                 URL: https://issues.apache.org/jira/browse/ASTERIXDB-2453
>             Project: Apache AsterixDB
>          Issue Type: Bug
>          Components: STO - Storage
>            Reporter: Chen Luo
>            Assignee: Chen Luo
>            Priority: Major
>
> The current constant merge policy has a very high merge cost (O(n*n), where n is the number of records), and is thus seldom used in practice. However, it still has a desirable property that read cost is always bounded. From the user's perspective, this policy is also easy to tune - only a single parameter of the number of components.
> To improve the write cost of the constant merge policy, we will adopt the idea of Binomial policy proposed by https://arxiv.org/abs/1407.3008. This policy significantly improves the merge cost to O(K*n^(1+1/K)), where K is the maximum number of components, and n is the total number of records (or flushes). Another desirable property is that this policy only has write cost O(n log n) (similar to the current prefix policy) when n is relatively small (the number of flushes < 4^K). 



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)