[ https://issues.apache.org/jira/browse/LENS-1452?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16080134#comment-16080134 ]
Rajat Khandelwal commented on LENS-1452: ---------------------------------------- Taking patch from reviewboard and attaching > 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)