[
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 variant 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 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.
> 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 variant 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)
