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

["Chen Luo (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/ASTERIXDB-2453?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Chen Luo resolved ASTERIXDB-2453.
---------------------------------
    Resolution: Fixed

> 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)