[LENS-1452] Optimize Time Union candidate Algorithm

• Type: Task
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Component/s: cube
• Assignee: Rajat Khandelwal
• Reporter: Rajat Khandelwal
• Created: 10/Jul/17 10:17
• Updated: 06/Feb/18 05:53
• Resolved: 10/Jul/17 11:23

Description

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:

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

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.