Repository: lens Updated Branches: refs/heads/master 45521bf2c -> d4236668c
LENS-1452: Optimize Time Union candidate Algorithm Project: http://git-wip-us.apache.org/repos/asf/lens/repo Commit: http://git-wip-us.apache.org/repos/asf/lens/commit/d4236668 Tree: http://git-wip-us.apache.org/repos/asf/lens/tree/d4236668 Diff: http://git-wip-us.apache.org/repos/asf/lens/diff/d4236668 Branch: refs/heads/master Commit: d4236668c3eb3a8bded92046574618d5d2e38bcf Parents: 45521bf Author: Rajat Khandelwal <pro...@apache.org> Authored: Mon Jul 10 16:52:54 2017 +0530 Committer: Rajat Khandelwal <rajatgupt...@gmail.com> Committed: Mon Jul 10 16:52:54 2017 +0530 ---------------------------------------------------------------------- .../parse/CandidateCoveringSetsResolver.java | 47 +++++++++++++++++--- 1 file changed, 41 insertions(+), 6 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lens/blob/d4236668/lens-cube/src/main/java/org/apache/lens/cube/parse/CandidateCoveringSetsResolver.java ---------------------------------------------------------------------- diff --git a/lens-cube/src/main/java/org/apache/lens/cube/parse/CandidateCoveringSetsResolver.java b/lens-cube/src/main/java/org/apache/lens/cube/parse/CandidateCoveringSetsResolver.java index 8e07162..69d9562 100644 --- a/lens-cube/src/main/java/org/apache/lens/cube/parse/CandidateCoveringSetsResolver.java +++ b/lens-cube/src/main/java/org/apache/lens/cube/parse/CandidateCoveringSetsResolver.java @@ -26,6 +26,7 @@ import org.apache.lens.cube.error.LensCubeErrorCode; import org.apache.lens.cube.metadata.TimeRange; import org.apache.lens.server.api.error.LensException; +import com.google.common.collect.Lists; import lombok.extern.slf4j.Slf4j; @Slf4j @@ -124,16 +125,14 @@ public class CandidateCoveringSetsResolver implements ContextRewriter { } } // Get all covering fact sets - List<UnionCandidate> unionCoveringSet = - getCombinations(new ArrayList<>(allCandidatesPartiallyValid), cubeql); +// List<UnionCandidate> unionCoveringSet = getCombinations(new ArrayList<>(allCandidatesPartiallyValid), cubeql); + List<UnionCandidate> unionCoveringSet = getCombinationTailIterative(allCandidatesPartiallyValid, cubeql); // Sort the Collection based on no of elements unionCoveringSet.sort(Comparator.comparing(Candidate::getChildrenCount)); // prune candidate set which doesn't contain any common measure i if (!queriedMsrs.isEmpty()) { pruneUnionCoveringSetWithoutAnyCommonMeasure(unionCoveringSet, queriedMsrs); } - // prune redundant covering sets - pruneRedundantUnionCoveringSets(unionCoveringSet); // pruing done in the previous steps, now create union candidates candidateSet.addAll(unionCoveringSet); updateQueriableMeasures(candidateSet, qpcList); @@ -155,7 +154,7 @@ public class CandidateCoveringSetsResolver implements ContextRewriter { } } } - + @Deprecated private void pruneRedundantUnionCoveringSets(List<UnionCandidate> candidates) { for (int i = 0; i < candidates.size(); i++) { UnionCandidate current = candidates.get(i); @@ -168,7 +167,7 @@ public class CandidateCoveringSetsResolver implements ContextRewriter { } } } - + @Deprecated private List<UnionCandidate> getCombinations(final List<Candidate> candidates, CubeQueryContext cubeql) { List<UnionCandidate> combinations = new LinkedList<>(); int size = candidates.size(); @@ -193,6 +192,42 @@ public class CandidateCoveringSetsResolver implements ContextRewriter { return combinations; } + /** + * The following function is iterative rewrite of the following tail-recursive implementation: + * (ignoring cubeql for clarity) + * getCombinations(candidates) = getCombinationsTailRecursive(emptyList(), candidates) + * + * getCombinationsTailRecursive(incompleteCombinations: List[List[Candidate]], candidates: List[Candidate]) = + * head, tail = head and tail of linked List candidates + * add head to all elements of incompleteCombinations. + * complete = remove now complete combinations from incompleteCombinations + * return complete ++ getCombinationsTailRecursive(incompleteCombinations, tail) + * @param candidates + * @param cubeql + * @return + */ + private List<UnionCandidate> getCombinationTailIterative(List<Candidate> candidates, CubeQueryContext cubeql) { + LinkedList<Candidate> candidateLinkedList = Lists.newLinkedList(candidates); + List<List<Candidate>> incompleteCombinations = Lists.newArrayList(); + List<UnionCandidate> unionCandidates = Lists.newArrayList(); + + while(!candidateLinkedList.isEmpty()) { + Candidate candidate = candidateLinkedList.remove(); + incompleteCombinations.add(Lists.newArrayList()); + Iterator<List<Candidate>> iter = incompleteCombinations.iterator(); + while(iter.hasNext()) { + List<Candidate> incompleteCombination = iter.next(); + incompleteCombination.add(candidate); + UnionCandidate unionCandidate = new UnionCandidate(incompleteCombination, cubeql); + if (isCandidateCoveringTimeRanges(unionCandidate, cubeql.getTimeRanges())) { + unionCandidates.add(unionCandidate); + iter.remove(); + } + } + } + return unionCandidates; + } + private List<List<Candidate>> resolveJoinCandidates(List<Candidate> candidates, Set<QueriedPhraseContext> msrs) throws LensException { List<List<Candidate>> msrCoveringSets = new ArrayList<>();
