You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kylin.apache.org by nj...@apache.org on 2017/08/17 12:41:51 UTC
[23/23] kylin git commit: APACHE-KYLIN-2728: Introduce a new cuboid
scheduler based on cuboid tree rather than static rules
APACHE-KYLIN-2728: Introduce a new cuboid scheduler based on cuboid tree rather than static rules
Project: http://git-wip-us.apache.org/repos/asf/kylin/repo
Commit: http://git-wip-us.apache.org/repos/asf/kylin/commit/41a7b7ee
Tree: http://git-wip-us.apache.org/repos/asf/kylin/tree/41a7b7ee
Diff: http://git-wip-us.apache.org/repos/asf/kylin/diff/41a7b7ee
Branch: refs/heads/yaho-cube-planner
Commit: 41a7b7ee8fbea6995a124763d13aa9c3e27b9eff
Parents: 721c64d
Author: Zhong <nj...@apache.org>
Authored: Thu Aug 17 20:40:35 2017 +0800
Committer: Zhong <nj...@apache.org>
Committed: Thu Aug 17 20:40:35 2017 +0800
----------------------------------------------------------------------
.../org/apache/kylin/cube/CubeInstance.java | 132 +++++++-
.../kylin/cube/cuboid/CuboidModeEnum.java | 48 +++
.../kylin/cube/cuboid/TreeCuboidScheduler.java | 313 +++++++++++++++++++
.../cube/cuboid/TreeCuboidSchedulerTest.java | 148 +++++++++
4 files changed, 638 insertions(+), 3 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/kylin/blob/41a7b7ee/core-cube/src/main/java/org/apache/kylin/cube/CubeInstance.java
----------------------------------------------------------------------
diff --git a/core-cube/src/main/java/org/apache/kylin/cube/CubeInstance.java b/core-cube/src/main/java/org/apache/kylin/cube/CubeInstance.java
index 6369b38..3f8bbbe 100644
--- a/core-cube/src/main/java/org/apache/kylin/cube/CubeInstance.java
+++ b/core-cube/src/main/java/org/apache/kylin/cube/CubeInstance.java
@@ -18,16 +18,26 @@
package org.apache.kylin.cube;
+import static org.apache.kylin.cube.cuboid.CuboidModeEnum.CURRENT;
+import static org.apache.kylin.cube.cuboid.CuboidModeEnum.RECOMMEND;
+
import java.io.IOException;
+import java.util.HashMap;
+import java.util.HashSet;
import java.util.List;
+import java.util.Map;
import java.util.Set;
import org.apache.kylin.common.KylinConfig;
import org.apache.kylin.common.KylinConfigExt;
import org.apache.kylin.common.persistence.ResourceStore;
import org.apache.kylin.common.persistence.RootPersistentEntity;
+import org.apache.kylin.common.util.CompressionUtils;
+import org.apache.kylin.common.util.JsonUtil;
import org.apache.kylin.common.util.Pair;
+import org.apache.kylin.cube.cuboid.CuboidModeEnum;
import org.apache.kylin.cube.cuboid.CuboidScheduler;
+import org.apache.kylin.cube.cuboid.TreeCuboidScheduler;
import org.apache.kylin.cube.model.CubeDesc;
import org.apache.kylin.metadata.model.ColumnDesc;
import org.apache.kylin.metadata.model.DataModelDesc;
@@ -94,6 +104,15 @@ public class CubeInstance extends RootPersistentEntity implements IRealization,
@JsonProperty("create_time_utc")
private long createTimeUTC;
+ @JsonProperty("cuboidBytes")
+ private byte[] cuboidBytes;
+
+ @JsonProperty("cuboid_bytes_recommend")
+ private byte[] cuboidBytesRecommend;
+
+ @JsonProperty("last_optimized")
+ private long lastOptimized;
+
// cuboid scheduler lazy built
transient private CuboidScheduler cuboidScheduler;
@@ -107,7 +126,14 @@ public class CubeInstance extends RootPersistentEntity implements IRealization,
synchronized (this) {
if (cuboidScheduler == null) {
- cuboidScheduler = getDescriptor().getInitialCuboidScheduler();
+ Map<Long, Long> cuboidsWithRowCnt = getCuboids();
+ if (cuboidsWithRowCnt == null) {
+ cuboidScheduler = getDescriptor().getInitialCuboidScheduler();
+ } else {
+ cuboidScheduler = new TreeCuboidScheduler(getDescriptor(),
+ Lists.newArrayList(cuboidsWithRowCnt.keySet()),
+ new TreeCuboidScheduler.CuboidCostComparator(cuboidsWithRowCnt));
+ }
}
}
return cuboidScheduler;
@@ -143,7 +169,8 @@ public class CubeInstance extends RootPersistentEntity implements IRealization,
// in a temporary broken state, so that user can edit and fix it. Broken state is often due to
// schema changes at source.
public boolean allowBrokenDescriptor() {
- return (getStatus() == RealizationStatusEnum.DISABLED || getStatus() == RealizationStatusEnum.DESCBROKEN) && segments.isEmpty();
+ return (getStatus() == RealizationStatusEnum.DISABLED || getStatus() == RealizationStatusEnum.DESCBROKEN)
+ && segments.isEmpty();
}
public String getResourcePath() {
@@ -303,6 +330,104 @@ public class CubeInstance extends RootPersistentEntity implements IRealization,
this.createTimeUTC = createTimeUTC;
}
+ public Set<Long> getCuboidsByMode(String cuboidModeName) {
+ return getCuboidsByMode(CuboidModeEnum.getByModeName(cuboidModeName));
+ }
+
+ public Set<Long> getCuboidsByMode(CuboidModeEnum cuboidMode) {
+ if (cuboidMode == null || cuboidMode == CURRENT) {
+ return getCuboidScheduler().getAllCuboidIds();
+ }
+ Set<Long> cuboidsRecommend = getCuboidsRecommend();
+ if (cuboidsRecommend == null || cuboidMode == RECOMMEND) {
+ return cuboidsRecommend;
+ }
+ Set<Long> currentCuboids = getCuboidScheduler().getAllCuboidIds();
+ switch (cuboidMode) {
+ case RECOMMEND_EXISTING:
+ cuboidsRecommend.retainAll(currentCuboids);
+ return cuboidsRecommend;
+ case RECOMMEND_MISSING:
+ cuboidsRecommend.removeAll(currentCuboids);
+ return cuboidsRecommend;
+ case RECOMMEND_MISSING_WITH_BASE:
+ cuboidsRecommend.removeAll(currentCuboids);
+ currentCuboids.add(getCuboidScheduler().getBaseCuboidId());
+ return cuboidsRecommend;
+ default:
+ return null;
+ }
+ }
+
+ public HashMap<Long, Long> getCuboids() {
+ if (cuboidBytes == null)
+ return null;
+ byte[] uncompressed;
+ try {
+ uncompressed = CompressionUtils.decompress(cuboidBytes);
+ String str = new String(uncompressed, "UTF-8");
+ HashMap<Long, Long> cuboids = JsonUtil.readValue(str, HashMap.class);
+ return cuboids.isEmpty() ? null : cuboids;
+ } catch (Exception e) {
+ throw new RuntimeException(e);
+ }
+ }
+
+ public void setCuboids(HashMap<Long, Long> cuboids) {
+ if (cuboids == null)
+ return;
+ if (cuboids.isEmpty()) {
+ cuboidBytes = null;
+ return;
+ }
+
+ try {
+ String str = JsonUtil.writeValueAsString(cuboids);
+ byte[] compressed = CompressionUtils.compress(str.getBytes("UTF-8"));
+ cuboidBytes = compressed;
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ }
+
+ public HashSet<Long> getCuboidsRecommend() {
+ if (cuboidBytesRecommend == null)
+ return null;
+ byte[] uncompressed;
+ try {
+ uncompressed = CompressionUtils.decompress(cuboidBytesRecommend);
+ String str = new String(uncompressed, "UTF-8");
+ HashSet<Long> cuboids = JsonUtil.readValue(str, HashSet.class);
+ return cuboids.isEmpty() ? null : cuboids;
+ } catch (Exception e) {
+ throw new RuntimeException(e);
+ }
+ }
+
+ public void setCuboidsRecommend(HashSet<Long> cuboids) {
+ if (cuboids == null)
+ return;
+ if (cuboids.isEmpty()) {
+ cuboidBytesRecommend = null;
+ return;
+ }
+ try {
+ String str = JsonUtil.writeValueAsString(cuboids);
+ byte[] compressed = CompressionUtils.compress(str.getBytes("UTF-8"));
+ cuboidBytesRecommend = compressed;
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ }
+
+ /**
+ * Get cuboid level count except base cuboid
+ * @return
+ */
+ public int getBuildLevel() {
+ return getCuboidScheduler().getCuboidsByLayer().size() - 1;
+ }
+
@Override
public CapabilityResult isCapable(SQLDigest digest) {
CapabilityResult result = CubeCapabilityChecker.check(this, digest);
@@ -377,7 +502,8 @@ public class CubeInstance extends RootPersistentEntity implements IRealization,
if (!this.getDescriptor().getModel().getPartitionDesc().isPartitioned())
return false;
- return this.getDescriptor().getAutoMergeTimeRanges() != null && this.getDescriptor().getAutoMergeTimeRanges().length > 0;
+ return this.getDescriptor().getAutoMergeTimeRanges() != null
+ && this.getDescriptor().getAutoMergeTimeRanges().length > 0;
}
public Pair<Long, Long> autoMergeCubeSegments() throws IOException {
http://git-wip-us.apache.org/repos/asf/kylin/blob/41a7b7ee/core-cube/src/main/java/org/apache/kylin/cube/cuboid/CuboidModeEnum.java
----------------------------------------------------------------------
diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/CuboidModeEnum.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/CuboidModeEnum.java
new file mode 100644
index 0000000..f55c9db
--- /dev/null
+++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/CuboidModeEnum.java
@@ -0,0 +1,48 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+*/
+
+package org.apache.kylin.cube.cuboid;
+
+import com.google.common.base.Strings;
+
+public enum CuboidModeEnum {
+ CURRENT("CURRENT"), RECOMMEND("RECOMMEND"), RECOMMEND_EXISTING("RECOMMEND_EXISTING"), RECOMMEND_MISSING(
+ "RECOMMEND_MISSING"), RECOMMEND_MISSING_WITH_BASE("RECOMMEND_MISSING_WITH_BASE");
+
+ private final String modeName;
+
+ CuboidModeEnum(String modeName) {
+ this.modeName = modeName;
+ }
+
+ public String toString() {
+ return modeName;
+ }
+
+ public static CuboidModeEnum getByModeName(String modeName) {
+ if (Strings.isNullOrEmpty(modeName)) {
+ return null;
+ }
+ for (CuboidModeEnum mode : CuboidModeEnum.values()) {
+ if (mode.modeName.equals(modeName.toUpperCase())) {
+ return mode;
+ }
+ }
+ return null;
+ }
+}
http://git-wip-us.apache.org/repos/asf/kylin/blob/41a7b7ee/core-cube/src/main/java/org/apache/kylin/cube/cuboid/TreeCuboidScheduler.java
----------------------------------------------------------------------
diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/TreeCuboidScheduler.java b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/TreeCuboidScheduler.java
new file mode 100644
index 0000000..73f4824
--- /dev/null
+++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/TreeCuboidScheduler.java
@@ -0,0 +1,313 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+*/
+
+package org.apache.kylin.cube.cuboid;
+
+import java.io.PrintWriter;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import javax.annotation.Nullable;
+
+import org.apache.kylin.cube.CubeInstance;
+import org.apache.kylin.cube.model.CubeDesc;
+
+import com.fasterxml.jackson.annotation.JsonIgnore;
+import com.fasterxml.jackson.annotation.JsonProperty;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Function;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+
+public class TreeCuboidScheduler extends CuboidScheduler {
+
+ final private CuboidTree cuboidTree;
+
+ public TreeCuboidScheduler(CubeDesc cubeDesc, List<Long> allCuboidIds, Comparator<Long> cuboidComparator) {
+ super(cubeDesc);
+ cuboidTree = CuboidTree.createFromCuboids(allCuboidIds, cuboidComparator);
+ }
+
+ @Override
+ public Set<Long> getAllCuboidIds() {
+ return cuboidTree.getAllCuboidIds();
+ }
+
+ @Override
+ public int getCuboidCount() {
+ return cuboidTree.getCuboidCount(Cuboid.getBaseCuboidId(cubeDesc));
+ }
+
+ @Override
+ public List<Long> getSpanningCuboid(long cuboidId) {
+ return cuboidTree.getSpanningCuboid(cuboidId);
+ }
+
+ @Override
+ public long findBestMatchCuboid(long cuboidId) {
+ return cuboidTree.findBestMatchCuboid(cuboidId);
+ }
+
+ public static class CuboidTree {
+ private int treeLevels;
+
+ private TreeNode root;
+
+ private Comparator<Long> cuboidComparator;
+
+ private Map<Long, TreeNode> index = new HashMap<>();
+
+ @VisibleForTesting
+ static CuboidTree createFromCuboids(List<Long> allCuboidIds) {
+ return createFromCuboids(allCuboidIds, Cuboid.cuboidSelectComparator);
+ }
+
+ @VisibleForTesting
+ static CuboidTree createFromCuboids(List<Long> allCuboidIds, Comparator<Long> cuboidComparator) {
+ // sort the cuboid ids in descending order, so that don't need to adjust
+ // the cuboid tree when adding cuboid id to the tree.
+ Collections.sort(allCuboidIds, new Comparator<Long>() {
+ @Override
+ public int compare(Long o1, Long o2) {
+ return Long.compare(o2, o1);
+ }
+ });
+ long basicCuboidId = allCuboidIds.get(0);
+ CuboidTree cuboidTree = new CuboidTree(cuboidComparator);
+ cuboidTree.setRoot(basicCuboidId);
+
+ for (long cuboidId : allCuboidIds) {
+ cuboidTree.addCuboid(cuboidId);
+ }
+ cuboidTree.buildIndex();
+ return cuboidTree;
+ }
+
+ private CuboidTree(Comparator<Long> cuboidComparator) {
+ this.cuboidComparator = cuboidComparator;
+ }
+
+ public Set<Long> getAllCuboidIds() {
+ return index.keySet();
+ }
+
+ public List<Long> getSpanningCuboid(long cuboidId) {
+ TreeNode node = index.get(cuboidId);
+ if (node == null) {
+ throw new IllegalArgumentException("the cuboid:" + cuboidId + " is not exist in the tree");
+ }
+
+ return Lists.transform(node.children, new Function<TreeNode, Long>() {
+ @Nullable
+ @Override
+ public Long apply(@Nullable TreeNode input) {
+ return input.cuboidId;
+ }
+ });
+ }
+
+ public long findBestMatchCuboid(long cuboidId) {
+ // exactly match
+ if (index.containsKey(cuboidId)) {
+ return cuboidId;
+ }
+
+ return findBestParent(cuboidId).cuboidId;
+ }
+
+ private int getCuboidCount(long cuboidId) {
+ int r = 1;
+ for (Long child : getSpanningCuboid(cuboidId)) {
+ r += getCuboidCount(child);
+ }
+ return r;
+ }
+
+ public void print(PrintWriter out) {
+ int dimensionCnt = Long.bitCount(root.cuboidId);
+ doPrint(root, dimensionCnt, 0, out);
+ }
+
+ private void doPrint(TreeNode node, int dimensionCount, int depth, PrintWriter out) {
+ printCuboid(node.cuboidId, dimensionCount, depth, out);
+
+ for (TreeNode child : node.children) {
+ doPrint(child, dimensionCount, depth + 1, out);
+ }
+ }
+
+ private void printCuboid(long cuboidID, int dimensionCount, int depth, PrintWriter out) {
+ StringBuffer sb = new StringBuffer();
+ for (int i = 0; i < depth; i++) {
+ sb.append(" ");
+ }
+ String cuboidName = Cuboid.getDisplayName(cuboidID, dimensionCount);
+ sb.append("|---- Cuboid ").append(cuboidName).append("(" + cuboidID + ")");
+ out.println(sb.toString());
+ }
+
+ private void setRoot(long basicCuboidId) {
+ this.root = new TreeNode(basicCuboidId, 0);
+ this.treeLevels = 0;
+ }
+
+ private void buildIndex() {
+ LinkedList<TreeNode> queue = new LinkedList<>();
+ queue.add(root);
+ while (!queue.isEmpty()) {
+ TreeNode node = queue.removeFirst();
+ index.put(node.cuboidId, node);
+ for (TreeNode child : node.children) {
+ queue.add(child);
+ }
+ }
+ }
+
+ private void addCuboid(long cuboidId) {
+ TreeNode parent = findBestParent(cuboidId);
+ if (parent != null && parent.cuboidId != cuboidId) {
+ parent.addChild(cuboidId, parent.level);
+ this.treeLevels = Math.max(this.treeLevels, parent.level + 1);
+ }
+ }
+
+ private TreeNode findBestParent(long cuboidId) {
+ TreeNode bestParent = doFindBestParent(cuboidId, root);
+ if (bestParent == null) {
+ throw new IllegalStateException("Cannot find the parent of the cuboid:" + cuboidId);
+ }
+ return bestParent;
+ }
+
+ private TreeNode doFindBestParent(long cuboidId, TreeNode parentCuboid) {
+ if (!canDerive(cuboidId, parentCuboid.cuboidId)) {
+ return null;
+ }
+
+ List<TreeNode> candidates = Lists.newArrayList();
+ for (TreeNode childCuboid : parentCuboid.children) {
+ TreeNode candidate = doFindBestParent(cuboidId, childCuboid);
+ if (candidate != null) {
+ candidates.add(candidate);
+ }
+ }
+ if (candidates.isEmpty()) {
+ candidates.add(parentCuboid);
+ }
+
+ return Collections.min(candidates, new Comparator<TreeNode>() {
+ @Override
+ public int compare(TreeNode o1, TreeNode o2) {
+ return cuboidComparator.compare(o1.cuboidId, o2.cuboidId);
+ }
+ });
+ }
+
+ private boolean canDerive(long cuboidId, long parentCuboid) {
+ return (cuboidId & ~parentCuboid) == 0;
+ }
+ }
+
+ public static class TreeNode {
+ @JsonProperty("cuboid_id")
+ long cuboidId;
+ @JsonIgnore
+ int level;
+ @JsonProperty("children")
+ List<TreeNode> children = new ArrayList<>();
+
+ public long getCuboidId() {
+ return cuboidId;
+ }
+
+ public int getLevel() {
+ return level;
+ }
+
+ public List<TreeNode> getChildren() {
+ return children;
+ }
+
+ TreeNode(long cuboidId, int level) {
+ this.cuboidId = cuboidId;
+ this.level = level;
+ }
+
+ void addChild(long childId, int parentlevel) {
+ this.children.add(new TreeNode(childId, parentlevel + 1));
+ }
+
+ @Override
+ public int hashCode() {
+ final int prime = 31;
+ int result = 1;
+ result = prime * result + (int) (cuboidId ^ (cuboidId >>> 32));
+ result = prime * result + level;
+ return result;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj == null)
+ return false;
+ if (getClass() != obj.getClass())
+ return false;
+ TreeNode other = (TreeNode) obj;
+ if (cuboidId != other.cuboidId)
+ return false;
+ if (level != other.level)
+ return false;
+ return true;
+ }
+ }
+
+ /**
+ * Compare cuboid according to the cuboid data row count
+ */
+ public static class CuboidCostComparator implements Comparator<Long> {
+ private Map<Long, Long> cuboidStatistics;
+
+ public CuboidCostComparator(Map<Long, Long> cuboidStatistics) {
+ Preconditions.checkArgument(cuboidStatistics != null,
+ "the input " + cuboidStatistics + " should not be null!!!");
+ this.cuboidStatistics = cuboidStatistics;
+ }
+
+ @Override
+ public int compare(Long cuboid1, Long cuboid2) {
+ Long rowCnt1 = cuboidStatistics.get(cuboid1);
+ Long rowCnt2 = cuboidStatistics.get(cuboid2);
+ if (rowCnt2 == null || rowCnt1 == null) {
+ return Cuboid.cuboidSelectComparator.compare(cuboid1, cuboid2);
+ }
+ return Long.compare(rowCnt1, rowCnt2);
+ }
+ }
+
+ public String getResponsibleKey() {
+ return CubeInstance.class.getName() + "-" + cubeDesc.getName();
+ }
+}
http://git-wip-us.apache.org/repos/asf/kylin/blob/41a7b7ee/core-cube/src/test/java/org/apache/kylin/cube/cuboid/TreeCuboidSchedulerTest.java
----------------------------------------------------------------------
diff --git a/core-cube/src/test/java/org/apache/kylin/cube/cuboid/TreeCuboidSchedulerTest.java b/core-cube/src/test/java/org/apache/kylin/cube/cuboid/TreeCuboidSchedulerTest.java
new file mode 100644
index 0000000..41fa807
--- /dev/null
+++ b/core-cube/src/test/java/org/apache/kylin/cube/cuboid/TreeCuboidSchedulerTest.java
@@ -0,0 +1,148 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+*/
+
+package org.apache.kylin.cube.cuboid;
+
+import static org.junit.Assert.assertEquals;
+
+import java.io.PrintWriter;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.Map;
+import java.util.Random;
+
+import org.apache.kylin.cube.cuboid.TreeCuboidScheduler.CuboidTree;
+import org.junit.Test;
+
+import com.google.common.collect.Maps;
+
+public class TreeCuboidSchedulerTest {
+
+ @Test
+ public void testCreateCuboidTree() {
+ long basicCuboid = getBaseCuboid(10);
+ List<Long> cuboids = genRandomCuboids(basicCuboid, 200);
+ CuboidTree cuboidTree = CuboidTree.createFromCuboids(cuboids);
+ PrintWriter out = new PrintWriter(System.out);
+ cuboidTree.print(out);
+ out.flush();
+ }
+
+ @Test
+ public void testSpanningChild() {
+ long basicCuboid = getBaseCuboid(10);
+ List<Long> cuboids = genRandomCuboids(basicCuboid, 50);
+ long testCuboid = cuboids.get(10);
+ System.out.println(cuboids);
+ CuboidTree cuboidTree = CuboidTree.createFromCuboids(cuboids);
+ PrintWriter out = new PrintWriter(System.out);
+ cuboidTree.print(out);
+ out.flush();
+
+ List<Long> spanningChildren = cuboidTree.getSpanningCuboid(testCuboid);
+ System.out.println(testCuboid + ":" + spanningChildren);
+ }
+
+ @Test
+ public void testFindBestMatchCuboid() {
+ CuboidTree cuboidTree = createCuboidTree1();
+ PrintWriter out = new PrintWriter(System.out);
+ cuboidTree.print(out);
+ out.flush();
+
+ assertEquals(503L, cuboidTree.findBestMatchCuboid(503L));
+
+ long bestMatch1 = cuboidTree.findBestMatchCuboid(Long.parseLong("100000000", 2));
+ assertEquals(263, bestMatch1);
+
+ long bestMatch2 = cuboidTree.findBestMatchCuboid(Long.parseLong("100010000", 2));
+ assertEquals(304, bestMatch2);
+ }
+
+ private List<Long> genRandomCuboids(long basicCuboidId, int count) {
+ Random random = new Random();
+ List<Long> result = new ArrayList<>();
+ result.add(basicCuboidId);
+ for (int i = 0; i < count; i++) {
+ result.add(random.nextLong() & basicCuboidId);
+ }
+ return result;
+ }
+
+ private long getBaseCuboid(int dimensionCnt) {
+ if (dimensionCnt > 64) {
+ throw new IllegalArgumentException("the dimension count cannot exceed 64");
+ }
+ long result = 0;
+ for (int i = 0; i < dimensionCnt; i++) {
+ result |= (1 << i);
+ }
+ return result;
+ }
+
+ private CuboidTree createCuboidTree1() {
+ List<Long> cuboids = Arrays.asList(504L, 511L, 447L, 383L, 503L, 440L, 496L, 376L, 439L, 487L, 375L, 319L, 432L,
+ 480L, 368L, 312L, 423L, 455L, 311L, 359L, 416L, 448L, 304L, 352L, 391L, 295L, 327L, 384L, 288L, 320L,
+ 263L);
+ return CuboidTree.createFromCuboids(cuboids,
+ new TreeCuboidScheduler.CuboidCostComparator(simulateStatistics()));
+ }
+
+ private Map<Long, Long> simulateStatistics() {
+ Map<Long, Long> countMap = Maps.newHashMap();
+ countMap.put(511L, 1000000L);
+
+ countMap.put(504L, 900000L);
+ countMap.put(447L, 990000L);
+ countMap.put(383L, 991000L);
+ countMap.put(503L, 980000L);
+
+ countMap.put(440L, 800000L);
+ countMap.put(496L, 890000L);
+ countMap.put(376L, 891000L);
+ countMap.put(439L, 751000L);
+ countMap.put(487L, 751000L);
+ countMap.put(375L, 741000L);
+ countMap.put(319L, 740000L);
+
+ countMap.put(432L, 600000L);
+ countMap.put(480L, 690000L);
+ countMap.put(368L, 691000L);
+ countMap.put(312L, 651000L);
+ countMap.put(423L, 651000L);
+ countMap.put(455L, 541000L);
+ countMap.put(311L, 540000L);
+ countMap.put(359L, 530000L);
+
+ countMap.put(416L, 400000L);
+ countMap.put(448L, 490000L);
+ countMap.put(304L, 491000L);
+ countMap.put(352L, 451000L);
+ countMap.put(391L, 351000L);
+ countMap.put(295L, 141000L);
+ countMap.put(327L, 240000L);
+
+ countMap.put(384L, 100000L);
+ countMap.put(288L, 90000L);
+ countMap.put(320L, 91000L);
+ countMap.put(263L, 51000L);
+
+ return countMap;
+ }
+}