[jira] [Commented] (LENS-1452) Optimize Time Union candidate Algorithm

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

    [ https://issues.apache.org/jira/browse/LENS-1452?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16353401#comment-16353401 ] 

Hudson commented on LENS-1452:
------------------------------

FAILURE: Integrated in Jenkins build Lens-Commit #1458 (See [https://builds.apache.org/job/Lens-Commit/1458/])
LENS-1452: Optimize Time Union candidate Algorithm (rajatgupta59: rev 6dca44661bf604ca1436c6cd1d3998405d0333a4)
* (edit) lens-cube/src/main/java/org/apache/lens/cube/parse/CandidateCoveringSetsResolver.java


> Optimize Time Union candidate Algorithm
> ---------------------------------------
>
>                 Key: LENS-1452
>                 URL: https://issues.apache.org/jira/browse/LENS-1452
>             Project: Apache Lens
>          Issue Type: Task
>          Components: cube
>            Reporter: Rajat Khandelwal
>            Assignee: Rajat Khandelwal
>            Priority: Major
>         Attachments: LENS-1452.01.patch
>
>
> Current algorithm: 
> * Create bitmap (equivalent to powerset)
> * from the powerset, add sets which can complete all time ranges as candidates
> * Prune sets which are contained in other sets
> Proposed change:
> The following recursion implemented iteratively: 
> {code}
>     (ignoring cubeql for clarity)
>     getCombinations(candidates) = getCombinationsRecursive(emptyList(), candidates)
>     getCombinationsRecursive(incompleteCombinations: List<List<Candidate>>, candidates: List<Candidate>) =
>     head, tail = head and tail of linked List candidates
>     add head to all elements of incompleteCombinations.
>     add {{ [head] }} as one incompleteCombination.
>     complete = remove now complete combinations from incompleteCombinations
>     return {{complete ++ getCombinationsTailRecursive(incompleteCombinations+[head], tail)}}
> {code}
> The improvement is, that redundant union candidates like {a,b,c} won't be generated if {a,b} is already covering time ranges. This will only generate minimal sets that cover time ranges. So the memory footprint isn't O( 2^n ) anymore. 



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)