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 <nju_y...@apache.org> Authored: Thu Aug 17 20:40:35 2017 +0800 Committer: Zhong <nju_y...@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; + } +}