-----------------------------------------------------------
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
