asterixdb-notifications mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Chen Luo (JIRA)" <j...@apache.org>
Subject [jira] [Created] (ASTERIXDB-1933) Level-Based Merge Policy
Date Tue, 06 Jun 2017 22:03:18 GMT
Chen Luo created ASTERIXDB-1933:
-----------------------------------

             Summary: 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 (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)

Mime
View raw message