----------------------------------------------------------- This is an automatically generated e-mail. To reply, visit: https://reviews.apache.org/r/60739/#review180024 -----------------------------------------------------------
Ship it! Ship It! - Amareshwari Sriramadasu On July 10, 2017, 10:37 a.m., Rajat Khandelwal wrote: > > ----------------------------------------------------------- > This is an automatically generated e-mail. To reply, visit: > https://reviews.apache.org/r/60739/ > ----------------------------------------------------------- > > (Updated July 10, 2017, 10:37 a.m.) > > > Review request for lens and Sushil Mohanty. > > > 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 > >
