[ https://issues.apache.org/jira/browse/LENS-1452?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16080178#comment-16080178 ]
Hadoop QA commented on LENS-1452: --------------------------------- Applied patch: [LENS-1452.01.patch|https://issues.apache.org/jira/secure/attachment/12876396/LENS-1452.01.patch] and ran command: mvn clean install -fae. Result: Success. Build Job: https://builds.apache.org/job/PreCommit-Lens-Build/1363/ > 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 > 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 (v6.4.14#64029)