[
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 <[email protected]>
Tested-by: Jenkins <[email protected]>
Reviewed-by: Murtadha Hubail <[email protected]>
Contrib: Jenkins <[email protected]>
Integration-Tests: Jenkins <[email protected]>
> 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)
