kylin-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From liy...@apache.org
Subject [5/6] kylin git commit: KYLIN-2729 Introduce greedy algorithm for cube planner
Date Sat, 23 Sep 2017 11:30:02 GMT
KYLIN-2729 Introduce greedy algorithm for cube planner

Signed-off-by: Li Yang <liyang@apache.org>


Project: http://git-wip-us.apache.org/repos/asf/kylin/repo
Commit: http://git-wip-us.apache.org/repos/asf/kylin/commit/01fe425f
Tree: http://git-wip-us.apache.org/repos/asf/kylin/tree/01fe425f
Diff: http://git-wip-us.apache.org/repos/asf/kylin/diff/01fe425f

Branch: refs/heads/master
Commit: 01fe425f1f4998d213fb89197781f1933821d0b2
Parents: e2029dd
Author: Zhong <nju_yaho@apache.org>
Authored: Tue Aug 22 14:58:18 2017 +0800
Committer: Li Yang <liyang@apache.org>
Committed: Sat Sep 23 18:16:48 2017 +0800

----------------------------------------------------------------------
 .../algorithm/greedy/GreedyAlgorithm.java       | 170 +++++++++++++++++++
 .../cuboid/algorithm/GreedyAlgorithmTest.java   |  58 +++++++
 2 files changed, 228 insertions(+)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/kylin/blob/01fe425f/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/greedy/GreedyAlgorithm.java
----------------------------------------------------------------------
diff --git a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/greedy/GreedyAlgorithm.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/greedy/GreedyAlgorithm.java
new file mode 100755
index 0000000..0d04cc2
--- /dev/null
+++ b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/greedy/GreedyAlgorithm.java
@@ -0,0 +1,170 @@
+/*
+ * 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.algorithm.greedy;
+
+import java.util.List;
+import java.util.Set;
+import java.util.concurrent.CountDownLatch;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.atomic.AtomicReference;
+
+import org.apache.kylin.cube.cuboid.algorithm.AbstractRecommendAlgorithm;
+import org.apache.kylin.cube.cuboid.algorithm.BenefitPolicy;
+import org.apache.kylin.cube.cuboid.algorithm.CuboidBenefitModel;
+import org.apache.kylin.cube.cuboid.algorithm.CuboidStats;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Sets;
+import com.google.common.util.concurrent.ThreadFactoryBuilder;
+
+/**
+* A simple implementation of the Greedy Algorithm , it chooses the cuboids which give
+* the greatest benefit based on expansion rate and time limitation.
+*/
+public class GreedyAlgorithm extends AbstractRecommendAlgorithm {
+    private static final Logger logger = LoggerFactory.getLogger(GreedyAlgorithm.class);
+
+    private static final int THREAD_NUM = 8;
+    private ExecutorService executor;
+
+    private Set<Long> selected = Sets.newLinkedHashSet();
+    private List<Long> remaining = Lists.newLinkedList();
+
+    public GreedyAlgorithm(final long timeout, BenefitPolicy benefitPolicy, CuboidStats cuboidStats)
{
+        super(timeout, benefitPolicy, cuboidStats);
+    }
+
+    @Override
+    public List<Long> recommend(double expansionRate) {
+        double spaceLimit = getCuboidStats().getBaseCuboidSize() * expansionRate;
+        return start(spaceLimit);
+    }
+
+    @Override
+    public List<Long> start(double spaceLimit) {
+        logger.info("Greedy Algorithm started.");
+        executor = Executors.newFixedThreadPool(THREAD_NUM,
+                new ThreadFactoryBuilder().setNameFormat("greedy-algorithm-benefit-calculator-pool-%d").build());
+
+        getBenefitPolicy().initBeforeStart();
+
+        //Initial mandatory cuboids
+        selected.clear();
+        double remainingSpace = spaceLimit;
+        for (Long mandatoryOne : getCuboidStats().getAllCuboidsForMandatory()) {
+            selected.add(mandatoryOne);
+            if (getCuboidStats().getCuboidSize(mandatoryOne) != null) {
+                remainingSpace -= getCuboidStats().getCuboidSize(mandatoryOne);
+            }
+        }
+        //Initial remaining cuboid set
+        remaining.clear();
+        remaining.addAll(getCuboidStats().getAllCuboidsForSelection());
+
+        long round = 0;
+        while (true) {
+            if (shouldCancel()) {
+                break;
+            }
+            // Choose one cuboId having the maximum benefit per unit space in all available
list
+            CuboidBenefitModel best = recommendBestOne();
+            // If return null, then we should finish the process and return
+            if (best == null) {
+                break;
+            }
+            // If we finally find the cuboid selected does not meet a minimum threshold of
benefit (for
+            // example, a cuboid with 0.99M roll up from a parent cuboid with 1M
+            // rows), then we should finish the process and return
+            if (!getBenefitPolicy().ifEfficient(best)) {
+                break;
+            }
+
+            remainingSpace -= getCuboidStats().getCuboidSize(best.getCuboidId());
+            // If we finally find there is no remaining space,  then we should finish the
process and return
+            if (remainingSpace <= 0) {
+                break;
+            }
+            selected.add(best.getCuboidId());
+            remaining.remove(best.getCuboidId());
+            getBenefitPolicy().propagateAggregationCost(best.getCuboidId(), selected);
+            round++;
+            if (logger.isInfoEnabled()) {
+                logger.info(String.format("Recommend in round %d : %s", round, best.toString()));
+            }
+        }
+
+        executor.shutdown();
+
+        List<Long> excluded = Lists.newArrayList(remaining);
+        remaining.retainAll(selected);
+        Preconditions.checkArgument(remaining.size() == 0,
+                "There should be no intersection between excluded list and selected list.");
+        logger.info("Greedy Algorithm finished.");
+
+        if (logger.isInfoEnabled()) {
+            logger.info("Excluded cuboidId size:" + excluded.size());
+            logger.info("Excluded cuboidId detail:");
+            for (Long cuboid : excluded) {
+                logger.info(String.format("cuboidId %d and Cost: %d and Space: %f", cuboid,
+                        getCuboidStats().getCuboidQueryCost(cuboid), getCuboidStats().getCuboidSize(cuboid)));
+            }
+            logger.info("Total Space:" + (spaceLimit - remainingSpace));
+            logger.info("Space Expansion Rate:" + (spaceLimit - remainingSpace) / getCuboidStats().getBaseCuboidSize());
+        }
+        return Lists.newArrayList(selected);
+    }
+
+    private CuboidBenefitModel recommendBestOne() {
+        final int selectedSize = selected.size();
+        final AtomicReference<CuboidBenefitModel> best = new AtomicReference<>();
+
+        final CountDownLatch counter = new CountDownLatch(remaining.size());
+        for (final Long cuboid : remaining) {
+            executor.submit(new Runnable() {
+                @Override
+                public void run() {
+                    CuboidBenefitModel currentBest = best.get();
+                    assert (selected.size() == selectedSize);
+                    CuboidBenefitModel.BenefitModel benefitModel = getBenefitPolicy().calculateBenefit(cuboid,
selected);
+                    if (benefitModel != null && (currentBest == null || currentBest.getBenefit()
== null
+                            || benefitModel.getBenefit() > currentBest.getBenefit()))
{
+                        while (!best.compareAndSet(currentBest,
+                                new CuboidBenefitModel(getCuboidStats().getCuboidModel(cuboid),
benefitModel))) {
+                            currentBest = best.get();
+                            if (benefitModel.getBenefit() <= currentBest.getBenefit())
{
+                                break;
+                            }
+                        }
+                    }
+                    counter.countDown();
+                }
+            });
+        }
+
+        try {
+            counter.await();
+        } catch (InterruptedException e) {
+        }
+        return best.get();
+    }
+}

http://git-wip-us.apache.org/repos/asf/kylin/blob/01fe425f/core-cube/src/test/java/org/apache/kylin/cube/cuboid/algorithm/GreedyAlgorithmTest.java
----------------------------------------------------------------------
diff --git a/core-cube/src/test/java/org/apache/kylin/cube/cuboid/algorithm/GreedyAlgorithmTest.java
b/core-cube/src/test/java/org/apache/kylin/cube/cuboid/algorithm/GreedyAlgorithmTest.java
new file mode 100755
index 0000000..0c9fbae
--- /dev/null
+++ b/core-cube/src/test/java/org/apache/kylin/cube/cuboid/algorithm/GreedyAlgorithmTest.java
@@ -0,0 +1,58 @@
+/*
+ * 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.algorithm;
+
+import java.util.List;
+
+import org.apache.kylin.cube.cuboid.algorithm.greedy.GreedyAlgorithm;
+import org.junit.Test;
+
+public class GreedyAlgorithmTest extends AlgorithmTestBase {
+
+    @Test
+    public void testBPUSCalculator() {
+        BenefitPolicy benefitPolicy = new BPUSCalculator(cuboidStats);
+        GreedyAlgorithm algorithm = new GreedyAlgorithm(-1, benefitPolicy, cuboidStats);
+
+        List<Long> recommendList = algorithm.recommend(10);
+        System.out.println("recommendList by BPUSCalculator: " + recommendList);
+        System.out.println("Cost evaluated for each query: " + getQueryCostRatio(cuboidStats,
recommendList));
+    }
+
+    @Test
+    public void testPBPUSCalculator() {
+        BenefitPolicy benefitPolicy = new PBPUSCalculator(cuboidStats);
+        GreedyAlgorithm algorithm = new GreedyAlgorithm(-1, benefitPolicy, cuboidStats);
+
+        List<Long> recommendList = algorithm.recommend(10);
+        System.out.println("recommendList by PBPUSCalculator:" + recommendList);
+        System.out.println("Cost evaluated for each query: " + getQueryCostRatio(cuboidStats,
recommendList));
+    }
+
+    @Test
+    public void testSPBPUSCalculator() {
+        BenefitPolicy benefitPolicy = new SPBPUSCalculator(cuboidStats);
+        GreedyAlgorithm algorithm = new GreedyAlgorithm(-1, benefitPolicy, cuboidStats);
+
+        List<Long> recommendList = algorithm.recommend(10);
+        System.out.println("recommendList by SPBPUSCalculator:" + recommendList);
+        System.out.println("Cost evaluated for each query: " + getQueryCostRatio(cuboidStats,
recommendList));
+    }
+
+}


Mime
View raw message