You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@asterixdb.apache.org by "Chen Luo (JIRA)" <ji...@apache.org> on 2017/06/06 22:03:18 UTC
[jira] [Updated] (ASTERIXDB-1933) Level-Based Merge Policy
[ https://issues.apache.org/jira/browse/ASTERIXDB-1933?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Chen Luo updated ASTERIXDB-1933:
--------------------------------
Description:
Currently, the only effective disk component merge policy in AsterixDB is prefix merge policy (and its invariant correlated prefix merge policy). This policy works by inspecting the disk components from the oldest to newest to find a sequence of components to merge.
However, one problem with this policy is that it takes O(n^2) complexity to merge n flushed disk component into a final disk component. Instead, the level-based merge policy can make the complexity as O(n logn).
The basic idea of this level-based merge policy is in https://docs.google.com/a/uci.edu/presentation/d/1PWw9fbf9J71YRipDPUmK9U3nx5wP7wDGNGPmazdgNfU/edit?usp=sharing.
was:
Currently, the only effective disk component merge policy in AsterixDB is prefix merge policy (and its invariant correlated prefix merge policy). This policy works by inspecting the disk components from the oldest to newest to find a sequence of components to merge.
However, one problem with this policy is that it takes O(n^2) complexity to merge n flushed disk component into a final disk component. Instead, the level-based merge policy can make the complexity as (n logn).
The basic idea of this level-based merge policy is in https://docs.google.com/a/uci.edu/presentation/d/1PWw9fbf9J71YRipDPUmK9U3nx5wP7wDGNGPmazdgNfU/edit?usp=sharing.
> Level-Based Merge Policy
> ------------------------
>
> Key: ASTERIXDB-1933
> URL: https://issues.apache.org/jira/browse/ASTERIXDB-1933
> Project: Apache AsterixDB
> Issue Type: Improvement
> Components: Storage
> Reporter: Chen Luo
> Assignee: Chen Luo
>
> Currently, the only effective disk component merge policy in AsterixDB is prefix merge policy (and its invariant correlated prefix merge policy). This policy works by inspecting the disk components from the oldest to newest to find a sequence of components to merge.
> However, one problem with this policy is that it takes O(n^2) complexity to merge n flushed disk component into a final disk component. Instead, the level-based merge policy can make the complexity as O(n logn).
> The basic idea of this level-based merge policy is in https://docs.google.com/a/uci.edu/presentation/d/1PWw9fbf9J71YRipDPUmK9U3nx5wP7wDGNGPmazdgNfU/edit?usp=sharing.
--
This message was sent by Atlassian JIRA
(v6.3.15#6346)