[18/50] lens git commit: LENS-1452: Optimize Time Union candidate Algorithm

[raju]

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/6dca4466
Tree: http://git-wip-us.apache.org/repos/asf/lens/tree/6dca4466
Diff: http://git-wip-us.apache.org/repos/asf/lens/diff/6dca4466

Branch: refs/heads/master
Commit: 6dca44661bf604ca1436c6cd1d3998405d0333a4
Parents: 3769ef0
Author: Rajat Khandelwal 
Authored: Mon Jul 10 16:52:54 2017 +0530
Committer: Rajat Khandelwal 
Committed: Thu Jul 13 14:43:03 2017 +0530

--
 .../parse/CandidateCoveringSetsResolver.java| 47 +---
 1 file changed, 41 insertions(+), 6 deletions(-)
--


http://git-wip-us.apache.org/repos/asf/lens/blob/6dca4466/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 unionCoveringSet =
-getCombinations(new ArrayList<>(allCandidatesPartiallyValid), cubeql);
+//List unionCoveringSet = getCombinations(new 
ArrayList<>(allCandidatesPartiallyValid), cubeql);
+List 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 
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 getCombinations(final List 
candidates, CubeQueryContext cubeql) {
 List 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 getCombinationTailIterative(List 
candidates, CubeQueryContext cubeql) {
+LinkedList candidateLinkedList = 
Lists.newLinkedList(candidates);
+List incompleteCombinations = Lists.newArrayList();
+List unionCandidates = Lists.newArrayList();
+
+while(!candidateLinkedList.isEmpty()) {
+  Candidate candidate = candidateLinkedList.remove();
+  incompleteCombinations.add(Lists.newArrayList());
+  Iterator iter = incompleteCombinations.iterator();
+  while(iter.hasNext()) {
+List incompleteCombination = iter.next();
+incompleteCombination.add(candidate);
+UnionCandidate unionCandidate = new 
UnionCandidate(incompleteCombination, cubeql);
+if (isCandidateCoveringTimeRanges(unionCandidate, 

[12/12] lens git commit: LENS-1452: Optimize Time Union candidate Algorithm

[prongs]

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/6dca4466
Tree: http://git-wip-us.apache.org/repos/asf/lens/tree/6dca4466
Diff: http://git-wip-us.apache.org/repos/asf/lens/diff/6dca4466

Branch: refs/heads/current-release-line
Commit: 6dca44661bf604ca1436c6cd1d3998405d0333a4
Parents: 3769ef0
Author: Rajat Khandelwal 
Authored: Mon Jul 10 16:52:54 2017 +0530
Committer: Rajat Khandelwal 
Committed: Thu Jul 13 14:43:03 2017 +0530

--
 .../parse/CandidateCoveringSetsResolver.java| 47 +---
 1 file changed, 41 insertions(+), 6 deletions(-)
--


http://git-wip-us.apache.org/repos/asf/lens/blob/6dca4466/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 unionCoveringSet =
-getCombinations(new ArrayList<>(allCandidatesPartiallyValid), cubeql);
+//List unionCoveringSet = getCombinations(new 
ArrayList<>(allCandidatesPartiallyValid), cubeql);
+List 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 
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 getCombinations(final List 
candidates, CubeQueryContext cubeql) {
 List 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 getCombinationTailIterative(List 
candidates, CubeQueryContext cubeql) {
+LinkedList candidateLinkedList = 
Lists.newLinkedList(candidates);
+List incompleteCombinations = Lists.newArrayList();
+List unionCandidates = Lists.newArrayList();
+
+while(!candidateLinkedList.isEmpty()) {
+  Candidate candidate = candidateLinkedList.remove();
+  incompleteCombinations.add(Lists.newArrayList());
+  Iterator iter = incompleteCombinations.iterator();
+  while(iter.hasNext()) {
+List incompleteCombination = iter.next();
+incompleteCombination.add(candidate);
+UnionCandidate unionCandidate = new 
UnionCandidate(incompleteCombination, cubeql);
+if 

lens git commit: LENS-1452: Optimize Time Union candidate Algorithm

[prongs]

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 
Authored: Mon Jul 10 16:52:54 2017 +0530
Committer: Rajat Khandelwal 
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 unionCoveringSet =
-getCombinations(new ArrayList<>(allCandidatesPartiallyValid), cubeql);
+//List unionCoveringSet = getCombinations(new 
ArrayList<>(allCandidatesPartiallyValid), cubeql);
+List 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 
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 getCombinations(final List 
candidates, CubeQueryContext cubeql) {
 List 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 getCombinationTailIterative(List 
candidates, CubeQueryContext cubeql) {
+LinkedList candidateLinkedList = 
Lists.newLinkedList(candidates);
+List incompleteCombinations = Lists.newArrayList();
+List unionCandidates = Lists.newArrayList();
+
+while(!candidateLinkedList.isEmpty()) {
+  Candidate candidate = candidateLinkedList.remove();
+  incompleteCombinations.add(Lists.newArrayList());
+  Iterator iter = incompleteCombinations.iterator();
+  while(iter.hasNext()) {
+List incompleteCombination = iter.next();
+incompleteCombination.add(candidate);
+UnionCandidate unionCandidate = new