Review Request 60739: LENS-1452: Optimize Time Union candidate Algorithm

[Rajat Khandelwal <ra...@gmail.com>]

-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/60739/
-----------------------------------------------------------

Review request for lens.


Bugs: LENS-1452
    https://issues.apache.org/jira/browse/LENS-1452


Repository: lens


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: 
{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.


Diffs
-----

  lens-cube/src/main/java/org/apache/lens/cube/parse/CandidateCoveringSetsResolver.java 8e071621ec15f90094d346e2b6e109b82ea68348 


Diff: https://reviews.apache.org/r/60739/diff/1/


Testing
-------


Thanks,

Rajat Khandelwal