You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kylin.apache.org by xx...@apache.org on 2023/02/01 02:43:19 UTC

[kylin] branch KYLIN-5387 created (now 80621fad9b)

This is an automated email from the ASF dual-hosted git repository.

xxyu pushed a change to branch KYLIN-5387
in repository https://gitbox.apache.org/repos/asf/kylin.git


      at 80621fad9b KYLIN-5387 migrate cube planner1 to kylin5

This branch includes the following new commits:

     new 80621fad9b KYLIN-5387 migrate cube planner1 to kylin5

The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails.  The revisions
listed as "add" were already present in the repository and have only
been added to this reference.



[kylin] 01/01: KYLIN-5387 migrate cube planner1 to kylin5

Posted by xx...@apache.org.
This is an automated email from the ASF dual-hosted git repository.

xxyu pushed a commit to branch KYLIN-5387
in repository https://gitbox.apache.org/repos/asf/kylin.git

commit 80621fad9bb67eed93ca88847e3ec8de62615c89
Author: Kun Liu <li...@apache.org>
AuthorDate: Mon Jan 30 13:24:31 2023 +0800

    KYLIN-5387 migrate cube planner1 to kylin5
---
 .../src/components/monitor/batchJobs/handler.js    |   1 +
 .../src/components/monitor/batchJobs/locales.js    |   1 +
 .../org/apache/kylin/common/KylinConfigBase.java   |  55 ++
 .../org/apache/kylin/common/util/StringUtil.java   |   8 +
 .../kylin/job/common/SegmentBuildJobUtil.java      |   2 +-
 .../kylin/job/constant/ExecutableConstants.java    |   1 +
 .../kylin/metadata/cube/model/IndexPlan.java       |  40 +-
 .../kylin/metadata/cube/model/LayoutEntity.java    |   5 +-
 .../kylin/metadata/cube/model/NBatchConstants.java |   1 +
 .../kylin/metadata/cube/model/NDataSegment.java    |   2 +-
 .../kylin/metadata/cube/model/RuleBasedIndex.java  |  71 ++-
 .../cube/planner/CostBasePlannerUtils.java         | 197 +++++++
 .../algorithm/AbstractRecommendAlgorithm.java      |  82 +++
 .../cube/planner/algorithm/BPUSCalculator.java     | 175 +++++++
 .../cube/planner/algorithm/BenefitPolicy.java      |  51 ++
 .../cube/planner/algorithm/CuboidBenefitModel.java |  89 ++++
 .../algorithm/CuboidRecommendAlgorithm.java        |  50 ++
 .../cube/planner/algorithm/CuboidStats.java        | 303 +++++++++++
 .../cube/planner/algorithm/CuboidStatsUtil.java    | 447 ++++++++++++++++
 .../cube/planner/algorithm/PBPUSCalculator.java    |  55 ++
 .../cube/planner/algorithm/SPBPUSCalculator.java   |  44 ++
 .../planner/algorithm/genetic/BitsChromosome.java  | 117 +++++
 .../algorithm/genetic/BitsChromosomeHelper.java    | 122 +++++
 .../planner/algorithm/genetic/BitsMutation.java    |  59 +++
 .../algorithm/genetic/BitsOnePointCrossover.java   | 131 +++++
 .../genetic/CombinedStoppingCondition.java         |  47 ++
 .../algorithm/genetic/GeneticAlgorithm.java        | 137 +++++
 .../algorithm/genetic/RouletteWheelSelection.java  |  61 +++
 .../planner/algorithm/greedy/GreedyAlgorithm.java  | 162 ++++++
 .../cube/planner/CostBasePlannerUtilsTest.java     |  34 ++
 .../kylin/rest/response/ExecutableResponse.java    |   1 +
 .../planner/algorithm/ITAlgorithmTestBase.java     | 567 +++++++++++++++++++++
 .../planner/algorithm/ITGeneticAlgorithmTest.java  |  97 ++++
 .../planner/algorithm/ITGreedyAlgorithmTest.java   | 106 ++++
 .../kylin/rest/service/FusionIndexService.java     |  10 +-
 .../kylin/rest/service/IndexPlanService.java       |   8 +-
 .../apache/kylin/engine/spark/job/JobStepType.java |   6 +
 .../kylin/engine/spark/job/NSparkCubingJob.java    |  53 ++
 .../apache/kylin/engine/spark/job/StageType.java   |  16 +
 .../spark/merger/AfterBuildResourceMerger.java     |   2 +-
 .../merger/AfterMergeOrRefreshResourceMerger.java  |   7 +-
 .../spark/merger/SparkJobMetadataMerger.java       |  16 +-
 .../kylin/engine/spark/job/PartitionExec.scala     |   2 +-
 .../kylin/engine/spark/job/RDSegmentBuildJob.java  |   2 +-
 .../kylin/engine/spark/job/SegmentBuildJob.java    |  19 +-
 .../kylin/engine/spark/job/SegmentExec.scala       |   1 +
 .../apache/kylin/engine/spark/job/SegmentJob.java  |  81 ++-
 .../engine/spark/job/stage/build/BuildStage.scala  |  11 +-
 ...dFactTableView.scala => CostBasedPlanner.scala} |  40 +-
 .../job/stage/build/FlatTableAndDictBase.scala     |  46 +-
 .../stage/build/MaterializedFactTableView.scala    |   2 +-
 ...eView.scala => PartitionCostBasedPlanner.scala} |  54 +-
 .../PartitionMaterializedFactTableView.scala       |   2 +-
 .../engine/spark/model/SegmentFlatTableDesc.java   |   4 +
 .../spark/model/planner/CuboIdToLayoutUtils.java   | 160 ++++++
 .../spark/model/planner/FlatTableToCostUtils.java  | 536 +++++++++++++++++++
 .../model/planner/CuboIdToLayoutUtilsTest.java     | 215 ++++++++
 57 files changed, 4515 insertions(+), 99 deletions(-)

diff --git a/kystudio/src/components/monitor/batchJobs/handler.js b/kystudio/src/components/monitor/batchJobs/handler.js
index 0b27635e13..a1fe4fc0bf 100644
--- a/kystudio/src/components/monitor/batchJobs/handler.js
+++ b/kystudio/src/components/monitor/batchJobs/handler.js
@@ -23,6 +23,7 @@ export function getSubTasksName (that, name) {
     'Generate global dictionary': that.$t('generateGlobalDict'),
     'Generate flat table': that.$t('generateFlatTable'),
     'Save flat table': that.$t('saveFlatTable'),
+    'Cost based planner': that.$t('costBasedPlanner'),
     'Get flat table statistics': that.$t('getFlatTableStatistics'),
     'Generate global dictionary of computed columns': that.$t('generateDictOfCC'),
     'Merge flat table': that.$t('mergeFlatTable'),
diff --git a/kystudio/src/components/monitor/batchJobs/locales.js b/kystudio/src/components/monitor/batchJobs/locales.js
index d88c38ea8f..536ba33da8 100644
--- a/kystudio/src/components/monitor/batchJobs/locales.js
+++ b/kystudio/src/components/monitor/batchJobs/locales.js
@@ -110,6 +110,7 @@ export default {
     generateGlobalDict: 'Generate global dictionary',
     generateFlatTable: 'Generate flat table',
     saveFlatTable: 'Save flat table',
+    costBasedPlanner: 'Cost based planner',
     getFlatTableStatistics: 'Get flat table statistics',
     generateDictOfCC: 'Generate global dictionary of computed columns',
     mergeFlatTable: 'Merge flat table',
diff --git a/src/core-common/src/main/java/org/apache/kylin/common/KylinConfigBase.java b/src/core-common/src/main/java/org/apache/kylin/common/KylinConfigBase.java
index 95fa963d5e..0ef437c805 100644
--- a/src/core-common/src/main/java/org/apache/kylin/common/KylinConfigBase.java
+++ b/src/core-common/src/main/java/org/apache/kylin/common/KylinConfigBase.java
@@ -1005,6 +1005,12 @@ public abstract class KylinConfigBase implements Serializable {
         return new Path(getWritingClusterWorkingDir(flatTableDirSuffix));
     }
 
+    public Path getPlannerCostTableDir(String project, String dataFlowId, String segmentId) {
+        String path = getHdfsWorkingDirectory() + project + "/planner_cost_table/" + dataFlowId + PATH_DELIMITER
+                + segmentId;
+        return new Path(path);
+    }
+
     public Path getFactTableViewDir(String project, String dataflowId, String segmentId) {
         String path = getHdfsWorkingDirectory() + project + "/fact_table_view/" + dataflowId //
                 + PATH_DELIMITER + segmentId;
@@ -3719,4 +3725,53 @@ public abstract class KylinConfigBase implements Serializable {
     public boolean getDDLEnabled() {
         return Boolean.parseBoolean(getOptional("kylin.source.ddl.enabled", FALSE));
     }
+
+    // ============================================================================
+    // Cost case cuboid Planner
+    // ============================================================================
+
+    public boolean enableCostBasedIndexPlanner() {
+        // If we enable the cost base cuboid planner, we will recommend subset of layouts from the rule.
+        return Boolean.parseBoolean(getOptional("kylin.index.costbased.enabled", FALSE));
+    }
+
+    public int getCostBasedPlannerGreedyAlgorithmAutoThreshold() {
+        return Integer.parseInt(getOptional("kylin.index.costbased.algorithm-threshold-greedy", "8"));
+    }
+
+    public int getCostBasedPlannerGeneticAlgorithmAutoThreshold() {
+        return Integer.parseInt(getOptional("kylin.index.costbased.algorithm-threshold-genetic", "23"));
+    }
+
+    public double getCostBasedPlannerExpansionRateThreshold() {
+        return Double.parseDouble(getOptional("kylin.index.costbased.expansion-threshold", "15.0"));
+    }
+
+    public double getCostBasedPlannerBPUSMinBenefitRatio() {
+        return Double.parseDouble(getOptional("kylin.index.costbased.bpus-min-benefit-ratio", "0.01"));
+    }
+
+    public int getStatsHLLPrecision() {
+        return Integer.parseInt(getOptional("kylin.index.costbased.sampling-hll-precision", "14"));
+    }
+
+    public double getJobCuboidSizeRatio() {
+        return Double.parseDouble(getOptional("kylin.index.costbased.model-size-estimate-ratio", "0.25"));
+    }
+
+    public double getJobCuboidSizeCountDistinctRatio() {
+        return Double.parseDouble(getOptional("kylin.index.costbased.model-size-estimate-countdistinct-ratio", "0.5"));
+    }
+
+    public double getJobCuboidSizeTopNRatio() {
+        return Double.parseDouble(getOptional("kylin.index.costbased.model-size-estimate-topn-ratio", "0.5"));
+    }
+
+    public int getJobPerReducerHLLCuboidNumber() {
+        return Integer.parseInt(getOptional("kylin.index.costbased.per-reducer-hll-cuboid-number", "100"));
+    }
+
+    public int getJobHLLMaxReducerNumber() {
+        return Integer.parseInt(getOptional("kylin.index.costbased.hll-max-reducer-number", "1"));
+    }
 }
diff --git a/src/core-common/src/main/java/org/apache/kylin/common/util/StringUtil.java b/src/core-common/src/main/java/org/apache/kylin/common/util/StringUtil.java
index 5776a5895b..133f7ce13a 100644
--- a/src/core-common/src/main/java/org/apache/kylin/common/util/StringUtil.java
+++ b/src/core-common/src/main/java/org/apache/kylin/common/util/StringUtil.java
@@ -178,6 +178,14 @@ public class StringUtil {
         return r.toArray(new String[r.size()]);
     }
 
+    public static String[] split(String str, String splitBy) {
+        return str.split(splitBy);
+    }
+
+    public static String[] splitByComma(String str) {
+        return split(str, ",");
+    }
+
     // calculating length in UTF-8 of Java String without actually encoding it
     public static int utf8Length(CharSequence sequence) {
         int count = 0;
diff --git a/src/core-job/src/main/java/org/apache/kylin/job/common/SegmentBuildJobUtil.java b/src/core-job/src/main/java/org/apache/kylin/job/common/SegmentBuildJobUtil.java
index b5eaada3fe..8fd29dc637 100644
--- a/src/core-job/src/main/java/org/apache/kylin/job/common/SegmentBuildJobUtil.java
+++ b/src/core-job/src/main/java/org/apache/kylin/job/common/SegmentBuildJobUtil.java
@@ -32,7 +32,7 @@ import lombok.val;
 import lombok.extern.slf4j.Slf4j;
 
 /**
- *
+ * This is use to compute and set the job param for spark building segment
  **/
 @Slf4j
 public class SegmentBuildJobUtil extends ExecutableUtil {
diff --git a/src/core-job/src/main/java/org/apache/kylin/job/constant/ExecutableConstants.java b/src/core-job/src/main/java/org/apache/kylin/job/constant/ExecutableConstants.java
index 864f26d52a..93f2ced333 100644
--- a/src/core-job/src/main/java/org/apache/kylin/job/constant/ExecutableConstants.java
+++ b/src/core-job/src/main/java/org/apache/kylin/job/constant/ExecutableConstants.java
@@ -79,6 +79,7 @@ public final class ExecutableConstants {
     public static final String STAGE_NAME_MATERIALIZED_FACT_TABLE = "Materialize fact table view";
     public static final String STAGE_NAME_BUILD_DICT = "Generate global dictionary";
     public static final String STAGE_NAME_GENERATE_FLAT_TABLE = "Generate flat table";
+    public static final String STAGE_NAME_COST_BASED_PLANNER = "Cost based planner";
     public static final String STAGE_NAME_GATHER_FLAT_TABLE_STATS = "Get flat table statistics";
     public static final String STAGE_NAME_BUILD_LAYER = "Build indexes by layer";
     public static final String STAGE_NAME_REFRESH_COLUMN_BYTES = "Update flat table statistics";
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/IndexPlan.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/IndexPlan.java
index c004d53135..efead0fdb4 100644
--- a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/IndexPlan.java
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/IndexPlan.java
@@ -30,6 +30,7 @@ import java.util.Collection;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.HashSet;
+import java.util.HashMap;
 import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
 import java.util.List;
@@ -239,7 +240,7 @@ public class IndexPlan extends RootPersistentEntity implements Serializable, IEn
         if (ruleBasedIndex.getBaseLayoutEnabled() == null) {
             ruleBasedIndex.setBaseLayoutEnabled(getConfig().isBaseCuboidAlwaysValid());
         }
-        ruleBasedLayouts.addAll(ruleBasedIndex.genCuboidLayouts());
+        ruleBasedLayouts.addAll(ruleBasedIndex.genCuboidLayouts(true));
         if (config.base().isSystemConfig() && isCachedAndShared) {
             ruleBasedIndex.getCuboidScheduler().validateOrder();
         }
@@ -375,6 +376,26 @@ public class IndexPlan extends RootPersistentEntity implements Serializable, IEn
         return effectiveMeasures;
     }
 
+    public Map<Integer, Integer> getColumnIdToRowKeyId() {
+        int rowKeyId = 0;
+        Map<Integer, Integer> result = new HashMap<>();
+        for (Integer columnId : effectiveDimCols.keySet()) {
+            result.put(columnId, rowKeyId);
+            rowKeyId++;
+        }
+        return result;
+    }
+
+    public Map<Integer, Integer> getRowKeyIdToColumnId() {
+        int rowKeyId = 0;
+        Map<Integer, Integer> result = new HashMap<>();
+        for (Integer columnId : effectiveDimCols.keySet()) {
+            result.put(rowKeyId, columnId);
+            rowKeyId++;
+        }
+        return result;
+    }
+
     public Set<TblColRef> listAllTblColRefs() {
         return allColumns;
     }
@@ -415,8 +436,8 @@ public class IndexPlan extends RootPersistentEntity implements Serializable, IEn
         return getAllIndexes(true);
     }
 
-    /**
-     * Get a copy of all IndexEntity List, which is a time cost operation
+    /*
+        Get a copy of all IndexEntity List, which is a time cost operation
      */
     public List<IndexEntity> getAllIndexes(boolean withToBeDeletedIndexes) {
         Map<Long, Integer> retSubscriptMap = Maps.newHashMap();
@@ -431,7 +452,7 @@ public class IndexPlan extends RootPersistentEntity implements Serializable, IEn
             copy.getLayouts().forEach(layout -> layout.setInProposing(layouts.get(layout.getId()).isInProposing()));
             retSubscript++;
         }
-        for (LayoutEntity ruleBasedLayout : ruleBasedLayouts) {
+        for (LayoutEntity ruleBasedLayout : getRuleBaseLayouts()) {
             val ruleRelatedIndex = ruleBasedLayout.getIndex();
             if (!retSubscriptMap.containsKey(ruleRelatedIndex.getId())) {
                 val copy = JsonUtil.deepCopyQuietly(ruleRelatedIndex, IndexEntity.class);
@@ -480,7 +501,7 @@ public class IndexPlan extends RootPersistentEntity implements Serializable, IEn
         for (IndexEntity indexEntity : indexes) {
             indexEntity.getLayouts().forEach(layout -> classifyByIndexId(layout, resultMap, layout.isToBeDeleted()));
         }
-        for (LayoutEntity ruleBasedLayout : ruleBasedLayouts) {
+        for (LayoutEntity ruleBasedLayout : getRuleBaseLayouts()) {
             classifyByIndexId(ruleBasedLayout, resultMap, false);
         }
         for (IndexEntity indexEntity : toBeDeletedIndexes) {
@@ -594,8 +615,7 @@ public class IndexPlan extends RootPersistentEntity implements Serializable, IEn
         this.ruleBasedIndex = ruleBasedIndex;
 
         Set<LayoutEntity> targetSet = this.ruleBasedIndex.genCuboidLayouts();
-
-        this.ruleBasedLayouts = Lists.newArrayList(targetSet);
+        this.ruleBasedLayouts = Lists.newArrayList(this.ruleBasedIndex.genCuboidLayouts(true));
         if (markToBeDeleted && CollectionUtils.isNotEmpty(layoutsNotIn(targetSet, originSet))) {
             Set<LayoutEntity> toBeDeletedSet = layoutsNotIn(originSet, targetSet);
             if (CollectionUtils.isNotEmpty(toBeDeletedSet)) {
@@ -621,7 +641,7 @@ public class IndexPlan extends RootPersistentEntity implements Serializable, IEn
             ruleBasedIndex.setIndexStartId(nextAggregationIndexId);
             ruleBasedIndex.setLayoutIdMapping(Lists.newArrayList());
             ruleBasedIndex.genCuboidLayouts(ruleLayouts);
-            this.ruleBasedLayouts = Lists.newArrayList(ruleBasedIndex.genCuboidLayouts());
+            this.ruleBasedLayouts = Lists.newArrayList(ruleBasedIndex.genCuboidLayouts(true));
         }
         this.aggShardByColumns = aggShardByColumns;
         updateNextId();
@@ -634,7 +654,7 @@ public class IndexPlan extends RootPersistentEntity implements Serializable, IEn
             this.extendPartitionColumns = extendPartitionColumns;
             ruleBasedIndex.setLayoutIdMapping(Lists.newArrayList());
             ruleBasedIndex.genCuboidLayouts(ruleLayouts);
-            this.ruleBasedLayouts = Lists.newArrayList(ruleBasedIndex.genCuboidLayouts());
+            this.ruleBasedLayouts = Lists.newArrayList(ruleBasedIndex.genCuboidLayouts(true));
         }
         this.extendPartitionColumns = extendPartitionColumns;
         updateNextId();
@@ -741,7 +761,7 @@ public class IndexPlan extends RootPersistentEntity implements Serializable, IEn
             val newBlacklist = Sets.newHashSet(originBlacklist);
             newBlacklist.addAll(blacklist);
             ruleBasedIndex.setLayoutBlackList(newBlacklist);
-            this.ruleBasedLayouts = Lists.newArrayList(ruleBasedIndex.genCuboidLayouts());
+            this.ruleBasedLayouts = Lists.newArrayList(ruleBasedIndex.genCuboidLayouts(true));
         }
         updateNextId();
     }
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/LayoutEntity.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/LayoutEntity.java
index 0cd6c33326..d812214612 100644
--- a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/LayoutEntity.java
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/LayoutEntity.java
@@ -394,7 +394,10 @@ public class LayoutEntity implements IStorageAware, Serializable {
 
     @Override
     public String toString() {
-        return MoreObjects.toStringHelper(this).add("id", id).toString();
+        return MoreObjects.toStringHelper(this)
+                .add("id", id)
+                .add("colOrder", getColOrder().toString())
+                .toString();
     }
 
     public boolean isDraft() {
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/NBatchConstants.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/NBatchConstants.java
index a7b1260ce8..754769280b 100644
--- a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/NBatchConstants.java
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/NBatchConstants.java
@@ -23,6 +23,7 @@ public interface NBatchConstants {
     String P_SEGMENT_IDS = "segmentIds";
     String P_JOB_ID = "jobId";
     String P_JOB_TYPE = "jobType";
+    String P_JOB_ENABLE_PLANNER = "enablePlanner";
     String P_LAYOUT_IDS = "layoutIds";
     String P_TO_BE_DELETED_LAYOUT_IDS = "toBeDeletedLayoutIds";
     String P_CLASS_NAME = "className";
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/NDataSegment.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/NDataSegment.java
index eb7585347f..b0e4795c6d 100644
--- a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/NDataSegment.java
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/NDataSegment.java
@@ -723,7 +723,7 @@ public class NDataSegment implements ISegment, Serializable {
 
     @Override
     public String toString() {
-        return "NDataSegment [" + dataflow.getUuid() + "," + id + "," + segmentRange + "]";
+        return "NDataSegment [" + dataflow.getUuid() + "," + id + "," + segmentRange + "," + status + "]";
     }
 
     public String displayIdName() {
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/RuleBasedIndex.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/RuleBasedIndex.java
index 88fe1715a0..c59af3378b 100644
--- a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/RuleBasedIndex.java
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/RuleBasedIndex.java
@@ -20,6 +20,7 @@ package org.apache.kylin.metadata.cube.model;
 
 import java.io.Serializable;
 import java.math.BigInteger;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
@@ -29,13 +30,13 @@ import java.util.stream.Collectors;
 
 import org.apache.commons.collections.CollectionUtils;
 import org.apache.kylin.common.util.ImmutableBitSet;
-import org.apache.kylin.metadata.model.IStorageAware;
-import org.apache.kylin.metadata.model.TblColRef;
 import org.apache.kylin.metadata.cube.cuboid.CuboidScheduler;
 import org.apache.kylin.metadata.cube.cuboid.CuboidScheduler.ColOrder;
 import org.apache.kylin.metadata.cube.cuboid.NAggregationGroup;
 import org.apache.kylin.metadata.cube.model.IndexEntity.IndexIdentifier;
+import org.apache.kylin.metadata.model.IStorageAware;
 import org.apache.kylin.metadata.model.NDataModel;
+import org.apache.kylin.metadata.model.TblColRef;
 import org.springframework.beans.BeanUtils;
 
 import com.fasterxml.jackson.annotation.JsonAutoDetect;
@@ -101,6 +102,11 @@ public class RuleBasedIndex implements Serializable {
     @JsonProperty("layout_black_list")
     private Set<Long> layoutBlackList = new HashSet<>();
 
+    @Setter
+    @Getter
+    @JsonProperty("layout_cost_based_pruned_list")
+    private Set<Long> layoutsOfCostBasedList = null;
+
     @Setter
     @Getter
     @JsonProperty("scheduler_version")
@@ -191,7 +197,11 @@ public class RuleBasedIndex implements Serializable {
     }
 
     public Set<LayoutEntity> genCuboidLayouts() {
-        return genCuboidLayouts(Sets.newHashSet(), Sets.newHashSet(), true);
+        return genCuboidLayouts(Sets.newHashSet(), Sets.newHashSet(), true, false);
+    }
+
+    public Set<LayoutEntity> genCuboidLayouts(boolean useCostBasedList) {
+        return genCuboidLayouts(Sets.newHashSet(), Sets.newHashSet(), true, useCostBasedList);
     }
 
     public boolean getIndexUpdateEnabled() {
@@ -234,6 +244,30 @@ public class RuleBasedIndex implements Serializable {
         this.aggregationGroups = aggregationGroups;
     }
 
+    public Map<Integer, Integer> getColumnIdToRowKeyId() {
+        int rowKeyId = 0;
+        Map<Integer, Integer> result = new HashMap<>();
+        for (Integer columnId : dimensions) {
+            result.put(columnId, rowKeyId);
+            rowKeyId++;
+        }
+        return result;
+    }
+
+    public Map<Integer, Integer> getRowKeyIdToColumnId() {
+        int rowKeyId = 0;
+        Map<Integer, Integer> result = new HashMap<>();
+        for (Integer columnId : dimensions) {
+            result.put(rowKeyId, columnId);
+            rowKeyId++;
+        }
+        return result;
+    }
+
+    public int countOfIncludeDimension() {
+        return dimensions.size();
+    }
+
     public boolean isCachedAndShared() {
         return indexPlan != null && indexPlan.isCachedAndShared();
     }
@@ -256,15 +290,24 @@ public class RuleBasedIndex implements Serializable {
     }
 
     Set<LayoutEntity> genCuboidLayouts(Set<LayoutEntity> previousLayouts) {
-        return genCuboidLayouts(previousLayouts, Sets.newHashSet(), true);
+        return genCuboidLayouts(previousLayouts, Sets.newHashSet(), true, false);
     }
 
     Set<LayoutEntity> genCuboidLayouts(Set<LayoutEntity> previousLayouts, Set<LayoutEntity> needDelLayouts) {
-        return genCuboidLayouts(previousLayouts, needDelLayouts, true);
+        return genCuboidLayouts(previousLayouts, needDelLayouts, true, false);
     }
 
-    Set<LayoutEntity> genCuboidLayouts(Set<LayoutEntity> previousLayouts, Set<LayoutEntity> needDelLayouts,
-            boolean excludeDel) {
+    /**
+     *
+     * @param previousLayouts
+     * @param needDelLayouts In order to make no changes for the same layout,
+     *                       we can get the layout id from the previous `RuleBasedIndex` for `previousLayouts` and `needDelLayouts`
+     * @param excludeDel Whether to include the result of deleted layouts
+     * @param useCostBasedList Whether to use the the list of `layoutsOfCostBasedList`
+     * @return
+     */
+    private Set<LayoutEntity> genCuboidLayouts(Set<LayoutEntity> previousLayouts, Set<LayoutEntity> needDelLayouts,
+            boolean excludeDel, boolean useCostBasedList) {
 
         Set<LayoutEntity> genLayouts = Sets.newHashSet();
 
@@ -348,6 +391,18 @@ public class RuleBasedIndex implements Serializable {
         if (excludeDel) {
             genLayouts.removeIf(layout -> layoutBlackList.contains(layout.getId()));
         }
+
+        // If contains the `layout_cost_based_pruned_list`, will use layouts in the cost based planner list
+        if (useCostBasedList && layoutsOfCostBasedList != null) {
+            // use the recommend white list id
+            Set<LayoutEntity> result = Sets.newHashSet();
+            genLayouts.stream().forEach(layout -> {
+                if (layoutsOfCostBasedList.contains(layout.getId())) {
+                    result.add(layout);
+                }
+            });
+            genLayouts = result;
+        }
         return genLayouts;
     }
 
@@ -395,7 +450,7 @@ public class RuleBasedIndex implements Serializable {
     }
 
     public Set<LayoutEntity> getBlacklistLayouts() {
-        val allLayouts = genCuboidLayouts(Sets.newHashSet(), Sets.newHashSet(), false);
+        val allLayouts = genCuboidLayouts(Sets.newHashSet(), Sets.newHashSet(), false, false);
         val existLayouts = genCuboidLayouts();
         return allLayouts.stream().filter(layout -> !existLayouts.contains(layout)).collect(Collectors.toSet());
     }
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/CostBasePlannerUtils.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/CostBasePlannerUtils.java
new file mode 100644
index 0000000000..07139fb035
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/CostBasePlannerUtils.java
@@ -0,0 +1,197 @@
+/*
+ * 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.metadata.cube.planner;
+
+import java.math.BigInteger;
+import java.util.ArrayList;
+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.metadata.cube.cuboid.NAggregationGroup;
+import org.apache.kylin.metadata.cube.model.LayoutEntity;
+import org.apache.kylin.metadata.cube.model.RuleBasedIndex;
+import org.apache.kylin.metadata.cube.planner.algorithm.BenefitPolicy;
+import org.apache.kylin.metadata.cube.planner.algorithm.CuboidRecommendAlgorithm;
+import org.apache.kylin.metadata.cube.planner.algorithm.CuboidStats;
+import org.apache.kylin.metadata.cube.planner.algorithm.PBPUSCalculator;
+import org.apache.kylin.metadata.cube.planner.algorithm.genetic.GeneticAlgorithm;
+import org.apache.kylin.metadata.cube.planner.algorithm.greedy.GreedyAlgorithm;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Maps;
+
+public class CostBasePlannerUtils {
+    private static final Logger logger = LoggerFactory.getLogger(CostBasePlannerUtils.class);
+
+    public static Map<BigInteger, Long> getRecommendCuboidList(RuleBasedIndex ruleBasedIndex, KylinConfig kylinConf,
+            String modelName, Map<BigInteger, Long> cuboidRowCountMap, Map<BigInteger, Double> cuboidSizeMap) {
+        BigInteger baseCuboid = generateBaseCuboId(ruleBasedIndex);
+        Set<BigInteger> mandatoryCuboids = generateMandatoryCuboIds(ruleBasedIndex);
+        logger.info("Build cuboid stats model name {}, baseCuboid {}, mandatory cuboid {}, statistic cuboid {}",
+                modelName, baseCuboid, mandatoryCuboids, cuboidRowCountMap.keySet());
+        CuboidStats cuboidStats = new CuboidStats.Builder(modelName, baseCuboid, baseCuboid, cuboidRowCountMap,
+                cuboidSizeMap).setMandatoryCuboids(mandatoryCuboids)
+                        .setBPUSMinBenefitRatio(kylinConf.getCostBasedPlannerBPUSMinBenefitRatio()).build();
+        Map<BigInteger, Long> result = getRecommendCuboidList(cuboidStats, kylinConf, !mandatoryCuboids.isEmpty());
+        // if not recommend any cuboid and just apply all layouts with the rule base index
+        if (result == null || result.isEmpty()) {
+            result = new HashMap<>();
+            Set<LayoutEntity> allLayouts = ruleBasedIndex.genCuboidLayouts();
+            for (LayoutEntity layoutEntity : allLayouts) {
+                BigInteger cuboid = convertDimensionsToCuboId(layoutEntity.getDimsIds(),
+                        ruleBasedIndex.countOfIncludeDimension(), ruleBasedIndex.getColumnIdToRowKeyId());
+                result.put(cuboid, 0L);
+            }
+            logger.info("Not recommend any cuboid with the cost based method, and use the rule based cuboid {}",
+                    result.keySet());
+        }
+        return result;
+    }
+
+    private static BigInteger generateBaseCuboId(RuleBasedIndex ruleBasedIndex) {
+        int dimensionCount = ruleBasedIndex.countOfIncludeDimension();
+        List<Integer> dimensionIds = new ArrayList<>(ruleBasedIndex.getDimensions());
+        BigInteger cuboid = convertDimensionsToCuboId(dimensionIds, dimensionCount,
+                ruleBasedIndex.getColumnIdToRowKeyId());
+        return cuboid;
+    }
+
+    private static Set<BigInteger> generateMandatoryCuboIds(RuleBasedIndex ruleBasedIndex) {
+        Set<BigInteger> result = new HashSet<>();
+        if (ruleBasedIndex != null) {
+            int dimensionCount = ruleBasedIndex.countOfIncludeDimension();
+            for (NAggregationGroup aggregationGroup : ruleBasedIndex.getAggregationGroups()) {
+                Integer[] mandatoryDimensionIds = aggregationGroup.getSelectRule().getMandatoryDims();
+                // If there is no mandatory for the agg group, should not add the cuboid
+                if (mandatoryDimensionIds != null && mandatoryDimensionIds.length != 0) {
+                    BigInteger cuboid = convertDimensionsToCuboId(mandatoryDimensionIds, dimensionCount,
+                            ruleBasedIndex.getColumnIdToRowKeyId());
+                    result.add(cuboid);
+                }
+            }
+        }
+        return result;
+    }
+
+    private static Map<BigInteger, Long> getRecommendCuboidList(CuboidStats cuboidStats, KylinConfig kylinConf,
+            boolean ifForceRecommend) {
+        // default is 1<<7 = 128
+        long threshold1 = 1L << kylinConf.getCostBasedPlannerGreedyAlgorithmAutoThreshold() - 1;
+        // default is 1<<22 = 1024*1024*4
+        long threshold2 = 1L << kylinConf.getCostBasedPlannerGeneticAlgorithmAutoThreshold() - 1;
+        if (threshold1 >= threshold2) {
+            logger.error("Invalid Cube Planner Algorithm configuration");
+            return null;
+        }
+        int allCuboidCount = cuboidStats.getAllCuboidsForMandatory().size()
+                + cuboidStats.getAllCuboidsForSelection().size();
+
+        if (!ifForceRecommend && allCuboidCount < threshold1) {
+            logger.info("Not recommend cuboid, the all cuboid count is {}, the threshold1 is {}, force recommend {}",
+                    allCuboidCount, threshold1, ifForceRecommend);
+            return null;
+        }
+
+        BenefitPolicy benefitPolicy = new PBPUSCalculator(cuboidStats);
+        CuboidRecommendAlgorithm algorithm = null;
+
+        if (allCuboidCount <= threshold2) {
+            algorithm = new GreedyAlgorithm(-1, benefitPolicy, cuboidStats);
+        } else {
+            algorithm = new GeneticAlgorithm(-1, benefitPolicy, cuboidStats);
+        }
+        long startTime = System.currentTimeMillis();
+        logger.info("Cube Planner Algorithm started at {}", startTime);
+        List<BigInteger> recommendCuboidList = algorithm
+                .recommend(kylinConf.getCostBasedPlannerExpansionRateThreshold());
+        logger.info("Cube Planner Algorithm ended at {}, cost time {}", System.currentTimeMillis(),
+                System.currentTimeMillis() - startTime);
+
+        if (recommendCuboidList.size() < allCuboidCount) {
+            logger.info("Cube Planner Algorithm chooses {} most effective cuboids to build among of all {} cuboids.",
+                    recommendCuboidList.size(), allCuboidCount);
+        }
+        Map<BigInteger, Long> recommendCuboidsWithStats = Maps.newLinkedHashMap();
+        for (BigInteger cuboid : recommendCuboidList) {
+            if (cuboid.equals(BigInteger.ZERO)) {
+                // for zero cuboid, just simply recommend the cheapest cuboid.
+                handleCuboidZeroRecommend(cuboidStats, recommendCuboidsWithStats);
+            } else {
+                recommendCuboidsWithStats.put(cuboid, cuboidStats.getCuboidCount(cuboid));
+            }
+        }
+        return recommendCuboidsWithStats;
+    }
+
+    private static void handleCuboidZeroRecommend(CuboidStats cuboidStats,
+            Map<BigInteger, Long> recommendCuboidsWithStats) {
+        Map<BigInteger, Long> statistics = cuboidStats.getStatistics();
+        BigInteger cheapestCuboid = null;
+        Long cheapestCuboidCount = Long.MAX_VALUE;
+        for (Map.Entry<BigInteger, Long> cuboidStatsEntry : statistics.entrySet()) {
+            if (cuboidStatsEntry.getValue() < cheapestCuboidCount) {
+                cheapestCuboid = cuboidStatsEntry.getKey();
+                cheapestCuboidCount = cuboidStatsEntry.getValue();
+            }
+        }
+        if (cheapestCuboid != null) {
+            logger.info("recommend cuboid:{} instead of cuboid zero", cheapestCuboid);
+            recommendCuboidsWithStats.put(cheapestCuboid, cheapestCuboidCount);
+        }
+    }
+
+    /**
+     * convert the dimensionid list to cuboid
+     *
+     * @param dimensionIds
+     * @param dimensionCount
+     * @return
+     */
+    private static BigInteger convertDimensionsToCuboId(Integer[] dimensionIds, int dimensionCount,
+            Map<Integer, Integer> columnIdToRowkeyId) {
+        Preconditions.checkNotNull(dimensionIds);
+        Preconditions.checkArgument(dimensionIds.length != 0, "The length of dimensionIds must be greater than 0");
+        BigInteger cuboid = BigInteger.ZERO;
+        // If the dimension count is 12, the ids is [4,8,11]
+        // and the result is 00000000,00000000,00000000,10001001
+        for (Integer dimensionId : dimensionIds) {
+            if (!columnIdToRowkeyId.containsKey(dimensionId)) {
+                throw new RuntimeException("Can't find the rowkey id for the dimension id");
+            }
+            int rowkeyId = columnIdToRowkeyId.get(dimensionId);
+            if (rowkeyId >= dimensionCount) {
+                throw new RuntimeException("The rowkey id must less than the count of dimension");
+            }
+            // set `dimensionCount - 1 - rowkeyId`th bit to 1
+            cuboid = cuboid.setBit(dimensionCount - 1 - rowkeyId);
+        }
+        return cuboid;
+    }
+
+    public static BigInteger convertDimensionsToCuboId(List<Integer> dimensionIds, int dimensionCount,
+            Map<Integer, Integer> columnIdToRowkeyId) {
+        return convertDimensionsToCuboId(dimensionIds.toArray(new Integer[0]), dimensionCount, columnIdToRowkeyId);
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/AbstractRecommendAlgorithm.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/AbstractRecommendAlgorithm.java
new file mode 100644
index 0000000000..21981db619
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/AbstractRecommendAlgorithm.java
@@ -0,0 +1,82 @@
+/*
+ * 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.metadata.cube.planner.algorithm;
+
+import java.math.BigInteger;
+import java.util.List;
+import java.util.concurrent.atomic.AtomicBoolean;
+
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+public abstract class AbstractRecommendAlgorithm implements CuboidRecommendAlgorithm {
+    private static final Logger logger = LoggerFactory.getLogger(AbstractRecommendAlgorithm.class);
+
+    protected final CuboidStats cuboidStats;
+    protected final BenefitPolicy benefitPolicy;
+
+    private AtomicBoolean cancelRequested = new AtomicBoolean(false);
+    private AtomicBoolean canceled = new AtomicBoolean(false);
+
+    private long timeoutMillis;
+
+    public AbstractRecommendAlgorithm(final long timeout, BenefitPolicy benefitPolicy, CuboidStats cuboidStats) {
+        if (timeout <= 0) {
+            this.timeoutMillis = Long.MAX_VALUE;
+        } else {
+            this.timeoutMillis = timeout;
+        }
+        this.cuboidStats = cuboidStats;
+        this.benefitPolicy = benefitPolicy;
+    }
+
+    @Override
+    public List<BigInteger> recommend(double expansionRate) {
+        double spaceLimit = cuboidStats.getBaseCuboidSize() * expansionRate;
+        logger.info("space limit for the algorithm is {} with expansion rate {}", spaceLimit, expansionRate);
+        return start(spaceLimit);
+    }
+
+    @Override
+    public void cancel() {
+        cancelRequested.set(true);
+    }
+
+    /**
+     * Checks whether the algorithm has been canceled or timed out.
+     */
+    protected boolean shouldCancel() {
+        if (canceled.get()) {
+            return true;
+        }
+        if (cancelRequested.get()) {
+            canceled.set(true);
+            cancelRequested.set(false);
+            logger.warn("Algorithm is canceled.");
+            return true;
+        }
+        final long currentTimeMillis = System.currentTimeMillis();
+        if (currentTimeMillis > timeoutMillis) {
+            canceled.set(true);
+            logger.warn("Algorithm exceeds time limit.");
+            return true;
+        }
+        return false;
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/BPUSCalculator.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/BPUSCalculator.java
new file mode 100644
index 0000000000..689c1d682c
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/BPUSCalculator.java
@@ -0,0 +1,175 @@
+/*
+ * 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.metadata.cube.planner.algorithm;
+
+import java.math.BigInteger;
+import java.util.Locale;
+import java.util.Map;
+import java.util.Set;
+
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Maps;
+import com.google.common.collect.Sets;
+
+public class BPUSCalculator implements BenefitPolicy {
+    private static Logger logger = LoggerFactory.getLogger(BPUSCalculator.class);
+
+    protected final CuboidStats cuboidStats;
+    protected final ImmutableMap<BigInteger, Long> initCuboidAggCostMap;
+    protected final Map<BigInteger, Long> processCuboidAggCostMap;
+
+    public BPUSCalculator(CuboidStats cuboidStats) {
+        this.cuboidStats = cuboidStats;
+        this.initCuboidAggCostMap = ImmutableMap.copyOf(initCuboidAggCostMap());
+        this.processCuboidAggCostMap = Maps.newHashMap(initCuboidAggCostMap);
+    }
+
+    protected BPUSCalculator(CuboidStats cuboidStats, ImmutableMap<BigInteger, Long> initCuboidAggCostMap) {
+        this.cuboidStats = cuboidStats;
+        this.initCuboidAggCostMap = initCuboidAggCostMap;
+        this.processCuboidAggCostMap = Maps.newHashMap(initCuboidAggCostMap);
+    }
+
+    private Map<BigInteger, Long> initCuboidAggCostMap() {
+        Map<BigInteger, Long> cuboidAggCostMap = Maps.newHashMap();
+        //Initialize stats for mandatory cuboids
+        for (BigInteger cuboid : cuboidStats.getAllCuboidsForMandatory()) {
+            if (getCuboidCost(cuboid) != null) {
+                cuboidAggCostMap.put(cuboid, getCuboidCost(cuboid));
+            }
+        }
+
+        //Initialize stats for selection cuboids
+        long baseCuboidCost = getCuboidCost(cuboidStats.getBaseCuboid());
+        for (BigInteger cuboid : cuboidStats.getAllCuboidsForSelection()) {
+            long leastCost = baseCuboidCost;
+            for (Map.Entry<BigInteger, Long> cuboidTargetEntry : cuboidAggCostMap.entrySet()) {
+                // use the equal to check two value
+                if ((cuboid.or(cuboidTargetEntry.getKey())).equals(cuboidTargetEntry.getKey())) {
+                    if (leastCost > cuboidTargetEntry.getValue()) {
+                        leastCost = cuboidTargetEntry.getValue();
+                    }
+                }
+            }
+            cuboidAggCostMap.put(cuboid, leastCost);
+        }
+        return cuboidAggCostMap;
+    }
+
+    @Override
+    public CuboidBenefitModel.BenefitModel calculateBenefit(BigInteger cuboid, Set<BigInteger> selected) {
+        double totalCostSaving = 0;
+        int benefitCount = 0;
+        for (BigInteger descendant : cuboidStats.getAllDescendants(cuboid)) {
+            if (!selected.contains(descendant)) {
+                double costSaving = getCostSaving(descendant, cuboid);
+                if (costSaving > 0) {
+                    totalCostSaving += costSaving;
+                    benefitCount++;
+                }
+            }
+        }
+
+        double spaceCost = calculateSpaceCost(cuboid);
+        double benefitPerUnitSpace = totalCostSaving / spaceCost;
+        return new CuboidBenefitModel.BenefitModel(benefitPerUnitSpace, benefitCount);
+    }
+
+    @Override
+    public CuboidBenefitModel.BenefitModel calculateBenefitTotal(Set<BigInteger> cuboidsToAdd,
+            Set<BigInteger> selected) {
+        Set<BigInteger> selectedInner = Sets.newHashSet(selected);
+        Map<BigInteger, Long> cuboidAggCostMapCopy = Maps.newHashMap(processCuboidAggCostMap);
+        for (BigInteger cuboid : cuboidsToAdd) {
+            selectedInner.add(cuboid);
+            propagateAggregationCost(cuboid, selectedInner, cuboidAggCostMapCopy);
+        }
+        double totalCostSaving = 0;
+        int benefitCount = 0;
+        for (Map.Entry<BigInteger, Long> entry : cuboidAggCostMapCopy.entrySet()) {
+            if (entry.getValue() < processCuboidAggCostMap.get(entry.getKey())) {
+                totalCostSaving += processCuboidAggCostMap.get(entry.getKey()) - entry.getValue();
+                benefitCount++;
+            }
+        }
+
+        double benefitPerUnitSpace = totalCostSaving;
+        return new CuboidBenefitModel.BenefitModel(benefitPerUnitSpace, benefitCount);
+    }
+
+    protected double getCostSaving(BigInteger descendant, BigInteger cuboid) {
+        long cuboidCost = getCuboidCost(cuboid);
+        long descendantAggCost = getCuboidAggregationCost(descendant);
+        return (double) descendantAggCost - cuboidCost;
+    }
+
+    protected Long getCuboidCost(BigInteger cuboid) {
+        return cuboidStats.getCuboidCount(cuboid);
+    }
+
+    private long getCuboidAggregationCost(BigInteger cuboid) {
+        return processCuboidAggCostMap.get(cuboid);
+    }
+
+    @Override
+    public boolean ifEfficient(CuboidBenefitModel best) {
+        if (best.getBenefit() < getMinBenefitRatio()) {
+            logger.info(String.format(Locale.ROOT, "The recommended cuboid %s doesn't meet minimum benifit ratio %f",
+                    best, getMinBenefitRatio()));
+            return false;
+        }
+        return true;
+    }
+
+    public double getMinBenefitRatio() {
+        return cuboidStats.getBpusMinBenefitRatio();
+    }
+
+    @Override
+    public void propagateAggregationCost(BigInteger cuboid, Set<BigInteger> selected) {
+        propagateAggregationCost(cuboid, selected, processCuboidAggCostMap);
+    }
+
+    private void propagateAggregationCost(BigInteger cuboid, Set<BigInteger> selected,
+            Map<BigInteger, Long> processCuboidAggCostMap) {
+        long aggregationCost = getCuboidCost(cuboid);
+        Set<BigInteger> childrenCuboids = cuboidStats.getAllDescendants(cuboid);
+        for (BigInteger child : childrenCuboids) {
+            if (!selected.contains(child) && (aggregationCost < getCuboidAggregationCost(child))) {
+                processCuboidAggCostMap.put(child, aggregationCost);
+            }
+        }
+    }
+
+    /**
+     * Return the space cost of building a cuboid.
+     *
+     */
+    public double calculateSpaceCost(BigInteger cuboid) {
+        return cuboidStats.getCuboidCount(cuboid);
+    }
+
+    @Override
+    public BenefitPolicy getInstance() {
+        return new BPUSCalculator(this.cuboidStats, this.initCuboidAggCostMap);
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/BenefitPolicy.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/BenefitPolicy.java
new file mode 100644
index 0000000000..0909f71e06
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/BenefitPolicy.java
@@ -0,0 +1,51 @@
+/*
+ * 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.metadata.cube.planner.algorithm;
+
+import java.math.BigInteger;
+import java.util.Set;
+
+public interface BenefitPolicy {
+
+    /**
+     * @return a cloned instance with initial status
+     */
+    public BenefitPolicy getInstance();
+
+    /**
+     * @param selected should not be changed
+     *                 Will not change the inner instance status
+     */
+    public CuboidBenefitModel.BenefitModel calculateBenefit(BigInteger cuboid, Set<BigInteger> selected);
+
+    /**
+     * @param cuboidsToAdd should not be changed
+     * @param selected     should not be changed
+     *                     Will not change the inner instance status
+     */
+    public CuboidBenefitModel.BenefitModel calculateBenefitTotal(Set<BigInteger> cuboidsToAdd, Set<BigInteger> selected);
+
+    public boolean ifEfficient(CuboidBenefitModel best);
+
+    /**
+     * @param selected should not be changed
+     * Will update the inner instance status
+     */
+    public void propagateAggregationCost(BigInteger cuboid, Set<BigInteger> selected);
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/CuboidBenefitModel.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/CuboidBenefitModel.java
new file mode 100644
index 0000000000..bb666f106b
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/CuboidBenefitModel.java
@@ -0,0 +1,89 @@
+/*
+ * 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.metadata.cube.planner.algorithm;
+
+import java.math.BigInteger;
+
+public class CuboidBenefitModel {
+    private CuboidModel cuboidModel;
+    private BenefitModel benefitModel;
+
+    public CuboidBenefitModel(CuboidModel cuboidModel, BenefitModel benefitModel) {
+        this.cuboidModel = cuboidModel;
+        this.benefitModel = benefitModel;
+    }
+
+    public void reset(CuboidModel cuboidModel, BenefitModel benefitModel) {
+        this.cuboidModel = cuboidModel;
+        this.benefitModel = benefitModel;
+    }
+
+    public BigInteger getCuboidId() {
+        return cuboidModel == null ? null : cuboidModel.cuboidId;
+    }
+
+    public Double getBenefit() {
+        return benefitModel == null ? null : benefitModel.benefit;
+    }
+
+    @Override
+    public String toString() {
+        return "CuboidBenefitModel [cuboidModel=" + cuboidModel + ", benefitModel=" + benefitModel + "]";
+    }
+
+    public static class CuboidModel {
+        public final BigInteger cuboidId;
+
+        public final long recordCount;
+        public final double spaceSize;
+
+        public final double hitProbability;
+        public final long scanCount;
+
+        public CuboidModel(BigInteger cuboId, long recordCount, double spaceSize, double hitProbability,
+                long scanCount) {
+            this.cuboidId = cuboId;
+            this.recordCount = recordCount;
+            this.spaceSize = spaceSize;
+            this.hitProbability = hitProbability;
+            this.scanCount = scanCount;
+        }
+
+        @Override
+        public String toString() {
+            return "CuboidModel [cuboidId=" + cuboidId + ", recordCount=" + recordCount + ", spaceSize=" + spaceSize
+                    + ", hitProbability=" + hitProbability + ", scanCount=" + scanCount + "]";
+        }
+    }
+
+    public static class BenefitModel {
+        public final double benefit;
+        public final int benefitCount;
+
+        public BenefitModel(double benefit, int benefitCount) {
+            this.benefit = benefit;
+            this.benefitCount = benefitCount;
+        }
+
+        @Override
+        public String toString() {
+            return "BenefitModel [benefit=" + benefit + ", benefitCount=" + benefitCount + "]";
+        }
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/CuboidRecommendAlgorithm.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/CuboidRecommendAlgorithm.java
new file mode 100644
index 0000000000..e93e8e6f1d
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/CuboidRecommendAlgorithm.java
@@ -0,0 +1,50 @@
+/*
+ * 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.metadata.cube.planner.algorithm;
+
+import java.math.BigInteger;
+import java.util.List;
+
+/**
+ * Algorithm to calculate the cuboid benefit and recommend cost-effective cuboid list based on the cube statistics.
+ */
+public interface CuboidRecommendAlgorithm {
+
+    /**
+     * Return a list of recommended cuboids for the building segment based on expansionRate
+     *
+     */
+    List<BigInteger> recommend(double expansionRate);
+
+    /**
+     * Start the Algorithm running
+     *
+     * @param maxSpaceLimit
+     * @return
+     */
+    List<BigInteger> start(double maxSpaceLimit);
+
+    /**
+     * Cancel the Algorithm running
+     *
+     *  Users can call this method from another thread to can the Algorithm and return the result earlier
+     *
+     */
+    void cancel();
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/CuboidStats.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/CuboidStats.java
new file mode 100644
index 0000000000..5407a66c23
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/CuboidStats.java
@@ -0,0 +1,303 @@
+/*
+ * 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.metadata.cube.planner.algorithm;
+
+import java.math.BigInteger;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.kylin.common.util.Pair;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Maps;
+import com.google.common.collect.Sets;
+
+public class CuboidStats {
+    private static final Logger logger = LoggerFactory.getLogger(CuboidStats.class);
+
+    static final double WEIGHT_FOR_UN_QUERY = 0.2;
+    static final double BPUS_MIN_BENEFIT_RATIO = 0.001;
+
+    public static class Builder {
+
+        private static final long THRESHOLD_ROLL_UP_FOR_MANDATORY = 1000L;
+
+        // Required parameters
+        private String key;
+        private BigInteger nTotalCuboids;
+        private BigInteger baseCuboid;
+        private double queryUncertaintyRatio = WEIGHT_FOR_UN_QUERY;
+        private double bpusMinBenefitRatio = BPUS_MIN_BENEFIT_RATIO;
+        private Map<BigInteger, Long> statistics;
+        private Map<BigInteger, Double> size;
+
+        // Optional parameters - initialized to default values
+        private Set<BigInteger> mandatoryCuboids = null;
+        //// These two properties are for generating mandatory cuboids
+        private Map<BigInteger, Map<BigInteger, Pair<Long, Long>>> rollingUpCountSourceMap = null;
+
+        private Map<BigInteger, Long> hitFrequencyMap = null;
+        private Map<BigInteger, Map<BigInteger, Long>> scanCountSourceMap = null;
+
+        public Builder(String key, BigInteger nTotalCuboids, BigInteger baseCuboid, Map<BigInteger, Long> statistics,
+                Map<BigInteger, Double> size) {
+            this.key = key;
+            this.nTotalCuboids = nTotalCuboids;
+            this.baseCuboid = baseCuboid;
+            this.statistics = statistics;
+            this.size = size;
+        }
+
+        public Builder setQueryUncertaintyRatio(double queryUncertaintyRatio) {
+            this.queryUncertaintyRatio = queryUncertaintyRatio;
+            return this;
+        }
+
+        public Builder setBPUSMinBenefitRatio(double bpusMinBenefitRatio) {
+            this.bpusMinBenefitRatio = bpusMinBenefitRatio;
+            return this;
+        }
+
+        public Builder setRollingUpCountSourceMap(
+                Map<BigInteger, Map<BigInteger, Pair<Long, Long>>> rollingUpCountSourceMap) {
+            this.rollingUpCountSourceMap = rollingUpCountSourceMap;
+            return this;
+        }
+
+        public Builder setMandatoryCuboids(Set<BigInteger> mandatoryCuboids) {
+            this.mandatoryCuboids = mandatoryCuboids;
+            return this;
+        }
+
+        public Builder setHitFrequencyMap(Map<BigInteger, Long> hitFrequencyMap) {
+            this.hitFrequencyMap = hitFrequencyMap;
+            return this;
+        }
+
+        public Builder setScanCountSourceMap(Map<BigInteger, Map<BigInteger, Long>> scanCountSourceMap) {
+            this.scanCountSourceMap = scanCountSourceMap;
+            return this;
+        }
+
+        public Map<BigInteger, Double> estimateCuboidsSize(Map<BigInteger, Long> statistics) {
+            return null;
+        }
+
+        public CuboidStats build() {
+            Preconditions.checkNotNull(key, "key should not be null");
+            Preconditions.checkNotNull(baseCuboid, "baseCuboid should not be null");
+            Preconditions.checkNotNull(statistics, "statistics should not be null");
+            Preconditions.checkNotNull(size, "size should not be null");
+            Preconditions.checkNotNull(statistics.get(baseCuboid),
+                    "row count should exist for base cuboid " + baseCuboid);
+            Preconditions.checkState(statistics.keySet().equals(size.keySet()),
+                    "statistics & size should own the same key set");
+            statistics = CuboidStatsUtil.adjustCuboidStats(statistics);
+
+            if (hitFrequencyMap != null && rollingUpCountSourceMap != null) {
+                Map<BigInteger, Double> cuboidHitProbabilityMap = CuboidStatsUtil.calculateCuboidHitProbability(
+                        hitFrequencyMap.keySet(), hitFrequencyMap, nTotalCuboids, queryUncertaintyRatio);
+                Map<BigInteger, Long> srcCuboidsStats = CuboidStatsUtil.generateSourceCuboidStats(statistics,
+                        cuboidHitProbabilityMap, rollingUpCountSourceMap);
+
+                statistics.putAll(srcCuboidsStats);
+
+                Map<BigInteger, Double> estimatedSize = estimateCuboidsSize(statistics);
+                if (estimatedSize != null && !estimatedSize.isEmpty()) {
+                    size = Maps.newHashMap(estimatedSize);
+                }
+            }
+
+            if (mandatoryCuboids == null) {
+                mandatoryCuboids = Sets.newHashSet();
+            } else if (!mandatoryCuboids.isEmpty()) {
+                statistics.putAll(CuboidStatsUtil.complementRowCountForCuboids(statistics, mandatoryCuboids));
+            }
+
+            return new CuboidStats(key, baseCuboid, queryUncertaintyRatio, bpusMinBenefitRatio, mandatoryCuboids,
+                    statistics, size, hitFrequencyMap, scanCountSourceMap);
+        }
+    }
+
+    private String key;
+    private BigInteger baseCuboid;
+    private double bpusMinBenefitRatio;
+    private ImmutableSet<BigInteger> mandatoryCuboidSet;
+    private ImmutableSet<BigInteger> selectionCuboidSet;
+    private ImmutableMap<BigInteger, Long> cuboidCountMap;
+    private ImmutableMap<BigInteger, Double> cuboidSizeMap;
+    private ImmutableMap<BigInteger, Double> cuboidHitProbabilityMap;
+    private ImmutableMap<BigInteger, Long> cuboidScanCountMap;
+
+    private ImmutableMap<BigInteger, List<BigInteger>> directChildrenCache;
+    private Map<BigInteger, Set<BigInteger>> allDescendantsCache;
+
+    private CuboidStats(String key, BigInteger baseCuboidId, double queryUncertaintyRatio, double bpusMinBenefitRatio,
+            Set<BigInteger> mandatoryCuboids, Map<BigInteger, Long> statistics, Map<BigInteger, Double> size,
+            Map<BigInteger, Long> hitFrequencyMap, Map<BigInteger, Map<BigInteger, Long>> scanCountSourceMap) {
+
+        this.key = key;
+        this.baseCuboid = baseCuboidId;
+        this.bpusMinBenefitRatio = bpusMinBenefitRatio;
+        /** Initial mandatory cuboids */
+        Set<BigInteger> cuboidsForMandatory = Sets.newHashSet(mandatoryCuboids);
+        //Always add base cuboid.
+        if (!cuboidsForMandatory.contains(baseCuboid)) {
+            cuboidsForMandatory.add(baseCuboid);
+        }
+        logger.info("Mandatory cuboids: " + cuboidsForMandatory);
+
+        /** Initial selection cuboids */
+        Set<BigInteger> cuboidsForSelection = Sets.newHashSet(statistics.keySet());
+        cuboidsForSelection.removeAll(cuboidsForMandatory);
+
+        //There's no overlap between mandatoryCuboidSet and selectionCuboidSet
+        this.mandatoryCuboidSet = ImmutableSet.<BigInteger> builder().addAll(cuboidsForMandatory).build();
+        this.selectionCuboidSet = ImmutableSet.<BigInteger> builder().addAll(cuboidsForSelection).build();
+        if (selectionCuboidSet.isEmpty()) {
+            logger.warn("The selection set should not be empty!!!");
+        }
+
+        this.cuboidCountMap = ImmutableMap.<BigInteger, Long> builder().putAll(statistics).build();
+        this.cuboidSizeMap = ImmutableMap.<BigInteger, Double> builder().putAll(size).build();
+
+        /** Initialize the hit probability for each selection cuboid */
+        Map<BigInteger, Double> tmpCuboidHitProbabilityMap = CuboidStatsUtil.calculateCuboidHitProbability(
+                selectionCuboidSet, hitFrequencyMap, BigInteger.valueOf(selectionCuboidSet.size()),
+                queryUncertaintyRatio);
+        this.cuboidHitProbabilityMap = ImmutableMap.<BigInteger, Double> builder().putAll(tmpCuboidHitProbabilityMap)
+                .build();
+
+        /** Initialize the scan count when query for each selection cuboid + one base cuboid */
+        Map<BigInteger, Long> tmpCuboidScanCountMap = Maps.newHashMapWithExpectedSize(1 + selectionCuboidSet.size());
+        tmpCuboidScanCountMap.put(baseCuboid, getExpScanCount(baseCuboid, statistics, scanCountSourceMap));
+        for (BigInteger cuboid : selectionCuboidSet) {
+            tmpCuboidScanCountMap.put(cuboid, getExpScanCount(cuboid, statistics, scanCountSourceMap));
+        }
+        this.cuboidScanCountMap = ImmutableMap.<BigInteger, Long> builder().putAll(tmpCuboidScanCountMap).build();
+
+        this.directChildrenCache = ImmutableMap.<BigInteger, List<BigInteger>> builder()
+                .putAll(CuboidStatsUtil.createDirectChildrenCache(statistics.keySet())).build();
+
+        this.allDescendantsCache = Maps.newConcurrentMap();
+    }
+
+    private long getExpScanCount(BigInteger sourceCuboid, Map<BigInteger, Long> statistics,
+            Map<BigInteger, Map<BigInteger, Long>> scanCountSourceMap) {
+        Preconditions.checkNotNull(statistics.get(sourceCuboid),
+                "The statistics for source cuboid " + sourceCuboid + " does not exist!!!");
+        if (scanCountSourceMap == null || scanCountSourceMap.get(sourceCuboid) == null
+                || scanCountSourceMap.get(sourceCuboid).size() <= 0) {
+            return statistics.get(sourceCuboid);
+        } else {
+            //TODO some improvement can be done by assigning weights based on distance between source cuboid and target cuboid
+            Map<BigInteger, Long> scanCountTargetMap = scanCountSourceMap.get(sourceCuboid);
+            long totalEstScanCount = 0L;
+            for (Map.Entry<BigInteger, Long> subEntry : scanCountTargetMap.entrySet()) {
+                BigInteger targetCuboid = subEntry.getKey();
+                Preconditions.checkNotNull(statistics.get(targetCuboid),
+                        "The statistics for target cuboid " + targetCuboid + " does not exist!!!");
+                // Consider the ratio of row count between source cuboid and target cuboid
+                totalEstScanCount += subEntry.getValue() * statistics.get(sourceCuboid) / statistics.get(targetCuboid);
+            }
+            return totalEstScanCount / scanCountTargetMap.size();
+        }
+    }
+
+    public double getBpusMinBenefitRatio() {
+        return bpusMinBenefitRatio;
+    }
+
+    public Set<BigInteger> getAllDescendants(BigInteger cuboid) {
+        Set<BigInteger> allDescendants = Sets.newLinkedHashSet();
+        if (selectionCuboidSet.contains(cuboid)) {
+            if (allDescendantsCache.get(cuboid) != null) {
+                return allDescendantsCache.get(cuboid);
+            } else {
+                getAllDescendants(cuboid, allDescendants);
+                allDescendantsCache.put(cuboid, allDescendants);
+            }
+        }
+        return allDescendants;
+    }
+
+    private void getAllDescendants(BigInteger cuboid, Set<BigInteger> allDescendants) {
+        if (allDescendants.contains(cuboid)) {
+            return;
+        }
+        allDescendants.add(cuboid);
+        for (BigInteger directChild : directChildrenCache.get(cuboid)) {
+            getAllDescendants(directChild, allDescendants);
+        }
+    }
+
+    public ImmutableSet<BigInteger> getAllCuboidsForSelection() {
+        return selectionCuboidSet;
+    }
+
+    public ImmutableSet<BigInteger> getAllCuboidsForMandatory() {
+        return mandatoryCuboidSet;
+    }
+
+    public Long getCuboidQueryCost(BigInteger cuboid) {
+        return cuboidScanCountMap.get(cuboid);
+    }
+
+    public Long getCuboidCount(BigInteger cuboid) {
+        return cuboidCountMap.get(cuboid);
+    }
+
+    public Double getCuboidSize(BigInteger cuboid) {
+        return cuboidSizeMap.get(cuboid);
+    }
+
+    public double getCuboidHitProbability(BigInteger cuboid) {
+        if (mandatoryCuboidSet.contains(cuboid)) {
+            return 1;
+        } else {
+            return cuboidHitProbabilityMap.get(cuboid) == null ? 0 : cuboidHitProbabilityMap.get(cuboid);
+        }
+    }
+
+    public Map<BigInteger, Long> getStatistics() {
+        return cuboidCountMap;
+    }
+
+    public double getBaseCuboidSize() {
+        return getCuboidSize(baseCuboid);
+    }
+
+    public BigInteger getBaseCuboid() {
+        return baseCuboid;
+    }
+
+    public String getKey() {
+        return key;
+    }
+
+    public CuboidBenefitModel.CuboidModel getCuboidModel(BigInteger cuboid) {
+        return new CuboidBenefitModel.CuboidModel(cuboid, getCuboidCount(cuboid), getCuboidSize(cuboid),
+                getCuboidHitProbability(cuboid), getCuboidQueryCost(cuboid));
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/CuboidStatsUtil.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/CuboidStatsUtil.java
new file mode 100644
index 0000000000..b6cad3730d
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/CuboidStatsUtil.java
@@ -0,0 +1,447 @@
+/*
+ * 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.metadata.cube.planner.algorithm;
+
+import java.math.BigDecimal;
+import java.math.BigInteger;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.SortedSet;
+import java.util.TreeSet;
+
+import org.apache.kylin.common.util.Pair;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import com.google.common.collect.Lists;
+import com.google.common.collect.Maps;
+
+public class CuboidStatsUtil {
+
+    private static final Logger logger = LoggerFactory.getLogger(CuboidStatsUtil.class);
+
+    private CuboidStatsUtil() {
+        throw new IllegalStateException("Class CuboidStatsUtil is an utility class !");
+    }
+
+    /**
+     * According to the cuboid hit frequencies and query uncertainty ratio
+     * calculate each cuboid hit probability
+     * @param selectionCuboidSet subset of cuboid domain which needs probability
+     * @param nTotalCuboids number of cuboids needs to be considered, mainly for each cuboid's uncertainty weight
+     * */
+    public static Map<BigInteger, Double> calculateCuboidHitProbability(Set<BigInteger> selectionCuboidSet,
+            Map<BigInteger, Long> hitFrequencyMap, BigInteger nTotalCuboids, double queryUncertaintyRatio) {
+        Map<BigInteger, Double> cuboidHitProbabilityMap = Maps.newHashMapWithExpectedSize(selectionCuboidSet.size());
+        if (hitFrequencyMap == null || hitFrequencyMap.isEmpty()) {
+            double value = BigDecimal.valueOf(1.0).divide(new BigDecimal(nTotalCuboids), 15, BigDecimal.ROUND_HALF_EVEN)
+                    .doubleValue();
+            for (BigInteger cuboid : selectionCuboidSet) {
+                cuboidHitProbabilityMap.put(cuboid, value);
+            }
+        } else {
+            long totalHitFrequency = 0L;
+            for (Map.Entry<BigInteger, Long> hitFrequency : hitFrequencyMap.entrySet()) {
+                totalHitFrequency += hitFrequency.getValue();
+            }
+
+            final double unitUncertainProb = BigDecimal.valueOf(queryUncertaintyRatio)
+                    .divide(new BigDecimal(nTotalCuboids), 15, BigDecimal.ROUND_HALF_EVEN).doubleValue();
+            for (BigInteger cuboid : selectionCuboidSet) {
+                //Calculate hit probability for each cuboid
+                if (hitFrequencyMap.get(cuboid) != null) {
+                    if (totalHitFrequency != 0)
+                        cuboidHitProbabilityMap.put(cuboid, unitUncertainProb
+                                + (1 - queryUncertaintyRatio) * hitFrequencyMap.get(cuboid) / totalHitFrequency);
+                    else
+                        throw new ArithmeticException("/ by zero");
+                } else {
+                    cuboidHitProbabilityMap.put(cuboid, unitUncertainProb);
+                }
+            }
+        }
+
+        return cuboidHitProbabilityMap;
+    }
+
+    /**
+     * @param statistics for cuboid row count
+     * @param rollingUpSourceMap the key of the outer map is source cuboid,
+     *                           the key of the inner map is target cuboid,
+     *                                  if cube is optimized multiple times, target cuboid may change
+     *                           the first element of the pair is the rollup row count
+     *                           the second element of the pair is the return row count
+     * @return source cuboids with estimated row count
+     */
+    public static Map<BigInteger, Long> generateSourceCuboidStats(Map<BigInteger, Long> statistics,
+            Map<BigInteger, Double> cuboidHitProbabilityMap,
+            Map<BigInteger, Map<BigInteger, Pair<Long, Long>>> rollingUpSourceMap) {
+        Map<BigInteger, Long> srcCuboidsStats = Maps.newHashMap();
+        if (cuboidHitProbabilityMap == null || cuboidHitProbabilityMap.isEmpty() || rollingUpSourceMap == null
+                || rollingUpSourceMap.isEmpty()) {
+            return srcCuboidsStats;
+        }
+
+        for (BigInteger cuboid : cuboidHitProbabilityMap.keySet()) {
+            if (statistics.get(cuboid) != null) {
+                continue;
+            }
+            Map<BigInteger, Pair<Long, Long>> innerRollingUpTargetMap = rollingUpSourceMap.get(cuboid);
+            if (innerRollingUpTargetMap == null || innerRollingUpTargetMap.isEmpty()) {
+                continue;
+            }
+
+            long totalEstRowCount = 0L;
+            int nEffective = 0;
+            boolean ifHasStats = false;
+            // if ifHasStats equals true, then source cuboid row count = (1 - rollup ratio) * target cuboid row count
+            //                            else source cuboid row count = returned row count collected directly
+            for (BigInteger tgtCuboid : innerRollingUpTargetMap.keySet()) {
+                Pair<Long, Long> rollingupStats = innerRollingUpTargetMap.get(tgtCuboid);
+                if (statistics.get(tgtCuboid) != null) {
+                    if (!ifHasStats) {
+                        totalEstRowCount = 0L;
+                        nEffective = 0;
+                        ifHasStats = true;
+                    }
+                    double rollupRatio = calculateRollupRatio(rollingupStats);
+                    totalEstRowCount += (1 - rollupRatio) * statistics.get(tgtCuboid);
+                    nEffective++;
+                } else {
+                    if (ifHasStats) {
+                        continue;
+                    }
+                    totalEstRowCount += rollingupStats.getSecond();
+                    nEffective++;
+                }
+            }
+
+            if (nEffective != 0)
+                srcCuboidsStats.put(cuboid, totalEstRowCount / nEffective);
+            else
+                throw new ArithmeticException("/ by zero");
+        }
+        srcCuboidsStats.remove(BigInteger.ZERO);
+        adjustCuboidStats(srcCuboidsStats, statistics);
+        return srcCuboidsStats;
+    }
+
+    /**
+     * Complement row count for mandatory cuboids
+     * with its best parent's row count
+     * */
+    public static Map<BigInteger, Long> complementRowCountForCuboids(final Map<BigInteger, Long> statistics,
+            Set<BigInteger> cuboids) {
+        Map<BigInteger, Long> result = Maps.newHashMapWithExpectedSize(cuboids.size());
+
+        // Sort entries order by row count asc
+        SortedSet<Map.Entry<BigInteger, Long>> sortedStatsSet = new TreeSet<>(
+                new Comparator<Map.Entry<BigInteger, Long>>() {
+                    public int compare(Map.Entry<BigInteger, Long> o1, Map.Entry<BigInteger, Long> o2) {
+                        int ret = o1.getValue().compareTo(o2.getValue());
+                        return ret == 0 ? o1.getKey().compareTo(o2.getKey()) : ret;
+                    }
+                });
+        //sortedStatsSet.addAll(statistics.entrySet()); KYLIN-3580
+        for (Map.Entry<BigInteger, Long> entry : statistics.entrySet()) {
+            sortedStatsSet.add(entry);
+        }
+        for (BigInteger cuboid : cuboids) {
+            if (statistics.get(cuboid) == null) {
+                // Get estimate row count for mandatory cuboid
+                for (Map.Entry<BigInteger, Long> entry : sortedStatsSet) {
+                    if (isDescendant(cuboid, entry.getKey())) {
+                        result.put(cuboid, entry.getValue());
+                        break;
+                    }
+                }
+            } else {
+                result.put(cuboid, statistics.get(cuboid));
+            }
+        }
+
+        return result;
+    }
+
+    /**
+     * adjust cuboid row count, make sure parent not less than child
+     */
+    public static Map<BigInteger, Long> adjustCuboidStats(Map<BigInteger, Long> statistics) {
+        Map<BigInteger, Long> ret = Maps.newHashMapWithExpectedSize(statistics.size());
+
+        List<BigInteger> cuboids = Lists.newArrayList(statistics.keySet());
+        Collections.sort(cuboids);
+
+        for (BigInteger cuboid : cuboids) {
+            Long rowCount = statistics.get(cuboid);
+            for (BigInteger childCuboid : ret.keySet()) {
+                if (isDescendant(childCuboid, cuboid)) {
+                    Long childRowCount = ret.get(childCuboid);
+                    if (rowCount < childRowCount) {
+                        rowCount = childRowCount;
+                    }
+                }
+            }
+            ret.put(cuboid, rowCount);
+        }
+
+        return ret;
+    }
+
+    public static void adjustCuboidStats(Map<BigInteger, Long> mandatoryCuboidsWithStats,
+            Map<BigInteger, Long> statistics) {
+        List<BigInteger> mandatoryCuboids = Lists.newArrayList(mandatoryCuboidsWithStats.keySet());
+        Collections.sort(mandatoryCuboids);
+
+        List<BigInteger> selectedCuboids = Lists.newArrayList(statistics.keySet());
+        Collections.sort(selectedCuboids);
+
+        for (int i = 0; i < mandatoryCuboids.size(); i++) {
+            BigInteger mCuboid = mandatoryCuboids.get(i);
+            if (statistics.get(mCuboid) != null) {
+                mandatoryCuboidsWithStats.put(mCuboid, statistics.get(mCuboid));
+                continue;
+            }
+            int k = 0;
+            // Make sure mCuboid's row count larger than its children's row count in statistics
+            for (; k < selectedCuboids.size(); k++) {
+                BigInteger sCuboid = selectedCuboids.get(k);
+                if (sCuboid.compareTo(mCuboid) > 0) {
+                    // sCuboid > mCuboid
+                    break;
+                }
+                if (isDescendant(sCuboid, mCuboid)) {
+                    Long childRowCount = statistics.get(sCuboid);
+                    if (childRowCount > mandatoryCuboidsWithStats.get(mCuboid)) {
+                        mandatoryCuboidsWithStats.put(mCuboid, childRowCount);
+                    }
+                }
+            }
+            // Make sure mCuboid's row count larger than its children's row count in mandatoryCuboids
+            for (int j = 0; j < i; j++) {
+                BigInteger cCuboid = mandatoryCuboids.get(j);
+                if (isDescendant(cCuboid, mCuboid)) {
+                    Long childRowCount = mandatoryCuboidsWithStats.get(cCuboid);
+                    if (childRowCount > mandatoryCuboidsWithStats.get(mCuboid)) {
+                        mandatoryCuboidsWithStats.put(mCuboid, childRowCount);
+                    }
+                }
+            }
+            // Make sure mCuboid's row count lower than its parents' row count in statistics
+            for (; k < selectedCuboids.size(); k++) {
+                BigInteger sCuboid = selectedCuboids.get(k);
+                if (isDescendant(mCuboid, sCuboid)) {
+                    Long parentRowCount = statistics.get(sCuboid);
+                    if (parentRowCount < mandatoryCuboidsWithStats.get(mCuboid)) {
+                        mandatoryCuboidsWithStats.put(mCuboid, parentRowCount);
+                    }
+                }
+            }
+        }
+    }
+
+    public static Map<BigInteger, List<BigInteger>> createDirectChildrenCache(final Set<BigInteger> cuboidSet) {
+        /**
+         * Sort the list by ascending order:
+         * */
+        final List<BigInteger> cuboidList = Lists.newArrayList(cuboidSet);
+        Collections.sort(cuboidList);
+        /**
+         * Sort the list by ascending order:
+         * 1. the more bit count of its value, the bigger
+         * 2. the larger of its value, the bigger
+         * */
+        List<Integer> layerIdxList = Lists.newArrayListWithExpectedSize(cuboidList.size());
+        for (int i = 0; i < cuboidList.size(); i++) {
+            layerIdxList.add(i);
+        }
+        Collections.sort(layerIdxList, new Comparator<Integer>() {
+            @Override
+            public int compare(Integer i1, Integer i2) {
+                BigInteger o1 = cuboidList.get(i1);
+                BigInteger o2 = cuboidList.get(i2);
+                int nBitDiff = o1.bitCount() - o2.bitCount();
+                if (nBitDiff != 0) {
+                    return nBitDiff;
+                }
+                return o1.compareTo(o2);
+            }
+        });
+        /**
+         * Construct an index array for pointing the position in layerIdxList
+         * (layerCuboidList is for speeding up continuous iteration)
+         * */
+        int[] toLayerIdxArray = new int[layerIdxList.size()];
+        final List<BigInteger> layerCuboidList = Lists.newArrayListWithExpectedSize(cuboidList.size());
+        for (int i = 0; i < layerIdxList.size(); i++) {
+            int cuboidIdx = layerIdxList.get(i);
+            toLayerIdxArray[cuboidIdx] = i;
+            layerCuboidList.add(cuboidList.get(cuboidIdx));
+        }
+
+        int[] previousLayerLastIdxArray = new int[layerIdxList.size()];
+        int currentBitCount = 0;
+        int previousLayerLastIdx = -1;
+        for (int i = 0; i < layerIdxList.size(); i++) {
+            int cuboidIdx = layerIdxList.get(i);
+            // get bit count from the biginteger api
+            int nBits = cuboidList.get(cuboidIdx).bitCount();
+            if (nBits > currentBitCount) {
+                currentBitCount = nBits;
+                previousLayerLastIdx = i - 1;
+            }
+            previousLayerLastIdxArray[i] = previousLayerLastIdx;
+        }
+
+        Map<BigInteger, List<BigInteger>> directChildrenCache = Maps.newHashMap();
+        for (int i = 0; i < cuboidList.size(); i++) {
+            BigInteger currentCuboid = cuboidList.get(i);
+            LinkedList<BigInteger> directChildren = Lists.newLinkedList();
+            int lastLayerIdx = previousLayerLastIdxArray[toLayerIdxArray[i]];
+            /**
+             * Choose one of the two scan strategies
+             * 1. cuboids are sorted by its value, like 1,2,3,4,...
+             * 2. cuboids are layered and sorted, like 1,2,4,8,...,3,5,...
+             * */
+            if (i - 1 <= lastLayerIdx) {
+                /**
+                 * 1. Adding cuboid by descending order
+                 * */
+                for (int j = i - 1; j >= 0; j--) {
+                    checkAndAddDirectChild(directChildren, currentCuboid, cuboidList.get(j));
+                }
+            } else {
+                /**
+                 * 1. Adding cuboid by descending order
+                 * 2. Check from lower cuboid layer
+                 * */
+                for (int j = lastLayerIdx; j >= 0; j--) {
+                    checkAndAddDirectChild(directChildren, currentCuboid, layerCuboidList.get(j));
+                }
+            }
+            directChildrenCache.put(currentCuboid, directChildren);
+        }
+        return directChildrenCache;
+    }
+
+    private static void checkAndAddDirectChild(List<BigInteger> directChildren, BigInteger currentCuboid,
+            BigInteger checkedCuboid) {
+        if (isDescendant(checkedCuboid, currentCuboid)) {
+            boolean ifDirectChild = true;
+            for (BigInteger directChild : directChildren) {
+                if (isDescendant(checkedCuboid, directChild)) {
+                    ifDirectChild = false;
+                    break;
+                }
+            }
+            if (ifDirectChild) {
+                directChildren.add(checkedCuboid);
+            }
+        }
+    }
+
+    private static boolean isDescendant(BigInteger cuboidToCheck, BigInteger parentCuboid) {
+        return (cuboidToCheck.and(parentCuboid)).equals(cuboidToCheck);
+    }
+
+    // TODO: this is used for cube planner2
+    /**
+     * The formula for calculating the benefit of cube optimization according to recommended cuboids is as follows:
+     * query benefit + space benefit
+     * | query benefit = (rollupBenefit - rollupCost) / rollupInputCount
+     * | space benefit = (curTotalSize - recomTotalSize) / spaceLimit
+     * @return the benefit of cube optimization according to recommended cuboids
+     */
+    //    public static OptimizationBenefit calculateOptimizationBenefit(Map<Long, Long> statistics,
+    //                                                                   Map<Long, Double> cuboidsSize, CuboidScheduler curCuboidScheduler, CuboidScheduler recomCuboidScheduler,
+    //                                                                   Map<Long, Double> cuboidHitProbabilityMap, double spaceLimit, double spaceBenefitRatio) {
+    //        if (cuboidHitProbabilityMap == null || cuboidHitProbabilityMap.isEmpty()) {
+    //            return OptimizationBenefit.ZERO;
+    //        }
+    //
+    //        Set<Long> currentCuboids = curCuboidScheduler.getAllCuboidIds();
+    //        Set<Long> recommendCuboids = recomCuboidScheduler.getAllCuboidIds();
+    //
+    //        double rollupBenefit = 0.0;
+    //        {// compute the benefits of added cuboids in recommendCuboids
+    //            Set<Long> recommendCuboidsOnly = Sets.newHashSet(recommendCuboids);
+    //            recommendCuboidsOnly.removeAll(currentCuboids);
+    //            logger.info("Added cuboids {}", recommendCuboidsOnly);
+    //            for (Long cuboid : recommendCuboidsOnly) {
+    //                Long pCuboid = curCuboidScheduler.findBestMatchCuboid(cuboid);
+    //                long rollupCount = statistics.get(pCuboid) - statistics.get(cuboid);
+    //                rollupBenefit += rollupCount * cuboidHitProbabilityMap.get(cuboid);
+    //            }
+    //        }
+    //
+    //        double rollupCost = 0.0;
+    //        {// compute the cost of removed cuboids in currentCuboids
+    //            Set<Long> currentCuboidsOnly = Sets.newHashSet(currentCuboids);
+    //            currentCuboidsOnly.removeAll(recommendCuboids);
+    //            logger.info("Removed cuboids {}", currentCuboidsOnly);
+    //            for (Long cuboid : currentCuboidsOnly) {
+    //                Long pCuboid = recomCuboidScheduler.findBestMatchCuboid(cuboid);
+    //                long rollupCount = statistics.get(pCuboid) - statistics.get(cuboid);
+    //                rollupCost += rollupCount * cuboidHitProbabilityMap.get(cuboid);
+    //            }
+    //        }
+    //
+    //        double rollupInputCount = 0.0;
+    //        {// compute the total rollup input count
+    //            for (Long cuboid : currentCuboids) {
+    //                Long rowCount = statistics.get(cuboid);
+    //                rollupInputCount += rowCount * cuboidHitProbabilityMap.get(cuboid);
+    //            }
+    //
+    //            Set<Long> recommendCuboidsOnly = Sets.newHashSet(recommendCuboids);
+    //            recommendCuboidsOnly.removeAll(currentCuboids);
+    //            for (Long cuboid : recommendCuboidsOnly) {
+    //                Long pCuboid = curCuboidScheduler.findBestMatchCuboid(cuboid);
+    //                Long rowCount = statistics.get(pCuboid);
+    //                rollupInputCount += rowCount * cuboidHitProbabilityMap.get(cuboid);
+    //            }
+    //        }
+    //
+    //        double curTotalSize = 0.0;
+    //        {// compute the total size of current cuboids
+    //            for (Long cuboid : currentCuboids) {
+    //                curTotalSize += cuboidsSize.get(cuboid);
+    //            }
+    //        }
+    //
+    //        double recomTotalSize = 0.0;
+    //        {// compute the total size of recommended cuboids
+    //            for (Long cuboid : recommendCuboids) {
+    //                recomTotalSize += cuboidsSize.get(cuboid);
+    //            }
+    //        }
+    //
+    //        return new OptimizationBenefit(rollupBenefit, rollupCost, rollupInputCount, curTotalSize, recomTotalSize,
+    //                spaceLimit, spaceBenefitRatio);
+    //    }
+
+    private static double calculateRollupRatio(Pair<Long, Long> rollupStats) {
+        double rollupInputCount = (double) rollupStats.getFirst() + rollupStats.getSecond();
+        return rollupInputCount == 0 ? 0 : 1.0 * rollupStats.getFirst() / rollupInputCount;
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/PBPUSCalculator.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/PBPUSCalculator.java
new file mode 100644
index 0000000000..68bacf5a3b
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/PBPUSCalculator.java
@@ -0,0 +1,55 @@
+/*
+ * 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.metadata.cube.planner.algorithm;
+
+import java.math.BigInteger;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableMap;
+
+public class PBPUSCalculator extends BPUSCalculator {
+
+    public PBPUSCalculator(final CuboidStats cuboidStats) {
+        super(cuboidStats);
+    }
+
+    protected PBPUSCalculator(CuboidStats cuboidStats, ImmutableMap<BigInteger, Long> initCuboidAggCostMap) {
+        super(cuboidStats, initCuboidAggCostMap);
+    }
+
+    @Override
+    protected double getCostSaving(BigInteger descendant, BigInteger cuboid) {
+        return getCuboidHitProbability(descendant) * super.getCostSaving(descendant, cuboid);
+    }
+
+    protected double getCuboidHitProbability(BigInteger cuboid) {
+        return cuboidStats.getCuboidHitProbability(cuboid);
+    }
+
+    public double getMinBenefitRatio() {
+        int cuboidDomainSize = cuboidStats.getAllCuboidsForSelection().size();
+        Preconditions.checkArgument(cuboidDomainSize > 0, "The set of cuboids for selection is empty!!!");
+        return super.getMinBenefitRatio() / cuboidDomainSize;
+    }
+
+    @Override
+    public BenefitPolicy getInstance() {
+        return new PBPUSCalculator(this.cuboidStats, this.initCuboidAggCostMap);
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/SPBPUSCalculator.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/SPBPUSCalculator.java
new file mode 100644
index 0000000000..fae674cc77
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/SPBPUSCalculator.java
@@ -0,0 +1,44 @@
+/*
+ * 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.metadata.cube.planner.algorithm;
+
+import java.math.BigInteger;
+
+import com.google.common.collect.ImmutableMap;
+
+public class SPBPUSCalculator extends PBPUSCalculator {
+
+    public SPBPUSCalculator(final CuboidStats cuboidStats) {
+        super(cuboidStats);
+    }
+
+    protected SPBPUSCalculator(CuboidStats cuboidStats, ImmutableMap<BigInteger, Long> initCuboidAggCostMap) {
+        super(cuboidStats, initCuboidAggCostMap);
+    }
+
+    @Override
+    protected Long getCuboidCost(BigInteger cuboid) {
+        return cuboidStats.getCuboidQueryCost(cuboid);
+    }
+
+    @Override
+    public BenefitPolicy getInstance() {
+        return new SPBPUSCalculator(this.cuboidStats, this.initCuboidAggCostMap);
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/BitsChromosome.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/BitsChromosome.java
new file mode 100644
index 0000000000..3e2e85c4a7
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/BitsChromosome.java
@@ -0,0 +1,117 @@
+/*
+ * 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.metadata.cube.planner.algorithm.genetic;
+
+import java.math.BigInteger;
+import java.util.BitSet;
+
+import org.apache.commons.math3.genetics.Chromosome;
+import org.apache.kylin.metadata.cube.planner.algorithm.BenefitPolicy;
+import org.apache.kylin.metadata.cube.planner.algorithm.CuboidBenefitModel;
+
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
+
+public class BitsChromosome extends Chromosome {
+
+    /**
+     * Global unmodified
+     */
+    private final BitsChromosomeHelper helper;
+
+    /**
+     * BitSet representing the chromosome
+     */
+    private final BitSet representation;
+    private final ImmutableSet<BigInteger> cuboids;
+
+    private final BenefitPolicy benefitPolicy;
+
+    private final double spaceCost;
+
+    public BitsChromosome(final BitSet representation, final BenefitPolicy benefitPolicy, BitsChromosomeHelper helper) {
+        this.helper = helper;
+
+        this.representation = representation;
+        this.cuboids = ImmutableSet.copyOf(helper.toCuboidList(representation));
+
+        this.benefitPolicy = benefitPolicy;
+
+        this.spaceCost = helper.getCuboidSize(Sets.newHashSet(cuboids));
+    }
+
+    public BitsChromosome newBitsChromosome(BitSet newRepresentation) {
+        return new BitsChromosome(newRepresentation, benefitPolicy.getInstance(), helper);
+    }
+
+    public BitSet getRepresentation() {
+        return representation;
+    }
+
+    /**
+     * Returns the length of the chromosome.
+     *
+     * @return the length of the chromosome
+     */
+    public int getLength() {
+        return helper.getLength();
+    }
+
+    public ImmutableSet<BigInteger> getCuboids() {
+        return cuboids;
+    }
+
+    @Override
+    public synchronized double fitness() {
+        CuboidBenefitModel.BenefitModel benefitModel = benefitPolicy.calculateBenefitTotal(cuboids,
+                helper.getMandatoryCuboids());
+        double totalBenefit = benefitModel.benefit;
+        if (spaceCost > helper.spaceLimit) {
+            totalBenefit = totalBenefit * helper.spaceLimit / spaceCost;
+        }
+        return totalBenefit;
+    }
+
+    @Override
+    protected boolean isSame(final Chromosome another) {
+        return this.equals(another);
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o)
+            return true;
+        if (o == null || getClass() != o.getClass())
+            return false;
+
+        BitsChromosome that = (BitsChromosome) o;
+
+        if (helper != null ? !helper.equals(that.helper) : that.helper != null)
+            return false;
+        return representation != null ? representation.equals(that.representation) : that.representation == null;
+
+    }
+
+    @Override
+    public int hashCode() {
+        int result = helper != null ? helper.hashCode() : 0;
+        result = 31 * result + (representation != null ? representation.hashCode() : 0);
+        return result;
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/BitsChromosomeHelper.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/BitsChromosomeHelper.java
new file mode 100644
index 0000000000..5e305878fc
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/BitsChromosomeHelper.java
@@ -0,0 +1,122 @@
+/*
+ * 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.metadata.cube.planner.algorithm.genetic;
+
+import java.math.BigInteger;
+import java.util.BitSet;
+import java.util.Collections;
+import java.util.List;
+import java.util.Set;
+
+import org.apache.kylin.metadata.cube.planner.algorithm.CuboidStats;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Lists;
+
+public class BitsChromosomeHelper {
+
+    public final double spaceLimit;
+    private final CuboidStats cuboidStats;
+    private final CuboidEncoder cuboidEncoder;
+
+    public BitsChromosomeHelper(final double spaceLimit, final CuboidStats cuboidStats) {
+        this.spaceLimit = spaceLimit;
+        this.cuboidStats = cuboidStats;
+        this.cuboidEncoder = new CuboidEncoder(cuboidStats.getAllCuboidsForSelection());
+    }
+
+    public ImmutableSet<BigInteger> getMandatoryCuboids() {
+        return cuboidStats.getAllCuboidsForMandatory();
+    }
+
+    public List<BigInteger> toCuboidList(BitSet bits) {
+        return cuboidEncoder.toCuboidList(bits);
+    }
+
+    public double getCuboidSize(Set<BigInteger> cuboids) {
+        double ret = 0;
+        for (BigInteger cuboid : cuboids) {
+            ret += cuboidStats.getCuboidSize(cuboid);
+        }
+        return ret;
+    }
+
+    public double getCuboidSizeByBitIndex(int index) {
+        return cuboidStats.getCuboidSize(cuboidEncoder.cuboidDomain.get(index));
+    }
+
+    public int getLength() {
+        return cuboidEncoder.cuboidDomain.size();
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o)
+            return true;
+        if (o == null || getClass() != o.getClass())
+            return false;
+
+        BitsChromosomeHelper that = (BitsChromosomeHelper) o;
+
+        return cuboidEncoder != null ? cuboidEncoder.equals(that.cuboidEncoder) : that.cuboidEncoder == null;
+
+    }
+
+    @Override
+    public int hashCode() {
+        return cuboidEncoder != null ? cuboidEncoder.hashCode() : 0;
+    }
+
+    private static class CuboidEncoder {
+        public final ImmutableList<BigInteger> cuboidDomain;
+
+        public CuboidEncoder(Set<BigInteger> cuboidSet) {
+            List<BigInteger> cuboidList = Lists.newArrayList(cuboidSet);
+            Collections.sort(cuboidList, Collections.reverseOrder());
+            this.cuboidDomain = ImmutableList.copyOf(cuboidList);
+        }
+
+        public List<BigInteger> toCuboidList(BitSet bits) {
+            List<BigInteger> cuboids = Lists.newArrayListWithExpectedSize(bits.cardinality());
+            for (int i = bits.nextSetBit(0); i >= 0; i = bits.nextSetBit(i + 1)) {
+                cuboids.add(cuboidDomain.get(i));
+            }
+            return cuboids;
+        }
+
+        @Override
+        public boolean equals(Object o) {
+            if (this == o)
+                return true;
+            if (o == null || getClass() != o.getClass())
+                return false;
+
+            CuboidEncoder that = (CuboidEncoder) o;
+
+            return cuboidDomain != null ? cuboidDomain.equals(that.cuboidDomain) : that.cuboidDomain == null;
+
+        }
+
+        @Override
+        public int hashCode() {
+            return cuboidDomain != null ? cuboidDomain.hashCode() : 0;
+        }
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/BitsMutation.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/BitsMutation.java
new file mode 100644
index 0000000000..1a218b4109
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/BitsMutation.java
@@ -0,0 +1,59 @@
+/*
+ * 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.metadata.cube.planner.algorithm.genetic;
+
+import java.util.BitSet;
+
+import org.apache.commons.math3.exception.MathIllegalArgumentException;
+import org.apache.commons.math3.exception.util.DummyLocalizable;
+import org.apache.commons.math3.genetics.Chromosome;
+import org.apache.commons.math3.genetics.GeneticAlgorithm;
+import org.apache.commons.math3.genetics.MutationPolicy;
+
+/**
+ * Modified from the BinaryMutation.java in https://github.com/apache/commons-math
+ * <p>
+ * Mutation for {@link BitsChromosome}s. Randomly changes one gene.
+ */
+public class BitsMutation implements MutationPolicy {
+
+    /**
+     * Mutate the given chromosome. Randomly changes one gene.
+     *
+     * @param original the original chromosome.
+     * @return the mutated chromosome.
+     * @throws IllegalArgumentException if <code>original</code> is not an instance of {@link BitsChromosome}.
+     */
+    public Chromosome mutate(Chromosome original) throws IllegalArgumentException {
+        if (!(original instanceof BitsChromosome)) {
+            throw new MathIllegalArgumentException(new DummyLocalizable("bits mutation only works on BitsChromosome"));
+        }
+
+        BitsChromosome origChrom = (BitsChromosome) original;
+        BitSet newNey = (BitSet) origChrom.getRepresentation().clone();
+
+        // randomly select a gene
+        int geneIndex = GeneticAlgorithm.getRandomGenerator().nextInt(origChrom.getLength());
+        // change it
+        newNey.set(geneIndex, !newNey.get(geneIndex));
+
+        Chromosome newChrom = origChrom.newBitsChromosome(newNey);
+        return newChrom;
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/BitsOnePointCrossover.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/BitsOnePointCrossover.java
new file mode 100644
index 0000000000..2087003dcb
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/BitsOnePointCrossover.java
@@ -0,0 +1,131 @@
+/*
+ * 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.metadata.cube.planner.algorithm.genetic;
+
+import java.util.BitSet;
+
+import org.apache.commons.math3.exception.DimensionMismatchException;
+import org.apache.commons.math3.exception.MathIllegalArgumentException;
+import org.apache.commons.math3.exception.util.DummyLocalizable;
+import org.apache.commons.math3.genetics.Chromosome;
+import org.apache.commons.math3.genetics.ChromosomePair;
+import org.apache.commons.math3.genetics.CrossoverPolicy;
+import org.apache.commons.math3.genetics.GeneticAlgorithm;
+
+/**
+ * Modified from the OnePointCrossover.java in https://github.com/apache/commons-math
+ * <p>
+ * One point crossover policy. A random crossover point is selected and the
+ * first part from each parent is copied to the corresponding child, and the
+ * second parts are copied crosswise.
+ * <p>
+ * Example:
+ * <pre>
+ * -C- denotes a crossover point
+ *                   -C-                                 -C-
+ * p1 = (1 0 1 0 0 1  | 0 1 1)    X    p2 = (0 1 1 0 1 0  | 1 1 1)
+ *      \------------/ \-----/              \------------/ \-----/
+ *            ||         (*)                       ||        (**)
+ *            VV         (**)                      VV        (*)
+ *      /------------\ /-----\              /------------\ /-----\
+ * c1 = (1 0 1 0 0 1  | 1 1 1)    X    c2 = (0 1 1 0 1 0  | 0 1 1)
+ * </pre>
+ * <p>
+ * This policy works only on {@link BitsChromosome}, and therefore it
+ * is parameterized by T. Moreover, the chromosomes must have same lengths.
+ */
+public class BitsOnePointCrossover implements CrossoverPolicy {
+
+    /**
+     * Performs one point crossover. A random crossover point is selected and the
+     * first part from each parent is copied to the corresponding child, and the
+     * second parts are copied crosswise.
+     * <p>
+     * Example:
+     * <pre>
+     * -C- denotes a crossover point
+     *                   -C-                                 -C-
+     * p1 = (1 0 1 0 0 1  | 0 1 1)    X    p2 = (0 1 1 0 1 0  | 1 1 1)
+     *      \------------/ \-----/              \------------/ \-----/
+     *            ||         (*)                       ||        (**)
+     *            VV         (**)                      VV        (*)
+     *      /------------\ /-----\              /------------\ /-----\
+     * c1 = (1 0 1 0 0 1  | 1 1 1)    X    c2 = (0 1 1 0 1 0  | 0 1 1)
+     * </pre>
+     *
+     * @param first  first parent (p1)
+     * @param second second parent (p2)
+     * @return pair of two children (c1,c2)
+     * @throws IllegalArgumentException     if one of the chromosomes is
+     *                                      not an instance of {@link BitsChromosome}
+     * @throws MathIllegalArgumentException if the length of the two chromosomes is different
+     */
+    @SuppressWarnings("unchecked") // OK because of instanceof checks
+    public ChromosomePair crossover(final Chromosome first, final Chromosome second)
+            throws DimensionMismatchException, MathIllegalArgumentException {
+
+        if (!(first instanceof BitsChromosome && second instanceof BitsChromosome)) {
+            throw new MathIllegalArgumentException(
+                    new DummyLocalizable("bits one-point crossover only works on BitsChromosome"));
+        }
+        return crossover((BitsChromosome) first, (BitsChromosome) second);
+    }
+
+    /**
+     * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
+     *
+     * @param first  the first chromosome.
+     * @param second the second chromosome.
+     * @return the pair of new chromosomes that resulted from the crossover.
+     * @throws DimensionMismatchException if the length of the two chromosomes is different
+     */
+    private ChromosomePair crossover(final BitsChromosome first, final BitsChromosome second)
+            throws DimensionMismatchException {
+        final int length = first.getLength();
+        if (length != second.getLength()) {
+            throw new DimensionMismatchException(second.getLength(), length);
+        }
+
+        final BitSet parent1Key = first.getRepresentation();
+        final BitSet parent2Key = second.getRepresentation();
+
+        final BitSet child1Key = new BitSet(length);
+        final BitSet child2Key = new BitSet(length);
+
+        // select a crossover point at random (0 and length makes no sense)
+        final int crossoverIndex = 1 + (GeneticAlgorithm.getRandomGenerator().nextInt(length - 2));
+
+        BitSet a = (BitSet) parent1Key.clone();
+        a.clear(crossoverIndex, length);
+        BitSet b = (BitSet) parent2Key.clone();
+        b.clear(0, crossoverIndex);
+
+        BitSet c = (BitSet) parent1Key.clone();
+        c.clear(crossoverIndex, length);
+        BitSet d = (BitSet) parent2Key.clone();
+        d.clear(0, crossoverIndex);
+
+        child1Key.or(a);
+        child1Key.or(d);
+
+        child2Key.or(c);
+        child2Key.or(b);
+        return new ChromosomePair(first.newBitsChromosome(child1Key), second.newBitsChromosome(child2Key));
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/CombinedStoppingCondition.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/CombinedStoppingCondition.java
new file mode 100644
index 0000000000..97d5c4b273
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/CombinedStoppingCondition.java
@@ -0,0 +1,47 @@
+/*
+ * 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.metadata.cube.planner.algorithm.genetic;
+
+import java.util.List;
+
+import org.apache.commons.math3.genetics.Population;
+import org.apache.commons.math3.genetics.StoppingCondition;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+public class CombinedStoppingCondition implements StoppingCondition {
+    private static final Logger logger = LoggerFactory.getLogger(GeneticAlgorithm.class);
+
+    private List<StoppingCondition> conditions;
+
+    public CombinedStoppingCondition(List<StoppingCondition> conditions) {
+        this.conditions = conditions;
+    }
+
+    @Override
+    public boolean isSatisfied(Population population) {
+        for (StoppingCondition condition : conditions) {
+            if (condition.isSatisfied(population)) {
+                logger.info("Stopping condition {} is satisfied", condition);
+                return true;
+            }
+        }
+        return false;
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/GeneticAlgorithm.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/GeneticAlgorithm.java
new file mode 100644
index 0000000000..09935cc899
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/GeneticAlgorithm.java
@@ -0,0 +1,137 @@
+/*
+ * 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.metadata.cube.planner.algorithm.genetic;
+
+import java.math.BigInteger;
+import java.util.BitSet;
+import java.util.List;
+import java.util.Locale;
+
+import org.apache.commons.math3.genetics.Chromosome;
+import org.apache.commons.math3.genetics.ElitisticListPopulation;
+import org.apache.commons.math3.genetics.FixedGenerationCount;
+import org.apache.commons.math3.genetics.Population;
+import org.apache.commons.math3.genetics.StoppingCondition;
+import org.apache.kylin.metadata.cube.planner.algorithm.AbstractRecommendAlgorithm;
+import org.apache.kylin.metadata.cube.planner.algorithm.BenefitPolicy;
+import org.apache.kylin.metadata.cube.planner.algorithm.CuboidStats;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import com.google.common.collect.Lists;
+
+public class GeneticAlgorithm extends AbstractRecommendAlgorithm {
+
+    private static final Logger logger = LoggerFactory.getLogger(GeneticAlgorithm.class);
+
+    private final org.apache.commons.math3.genetics.GeneticAlgorithm geneticAlgorithm;
+
+    /**
+     * the rate of crossover for the algorithm.
+     */
+    private final double crossoverRate = 0.9;
+    /**
+     * the rate of mutation for the algorithm.
+     */
+    private final double mutationRate = 0.001;
+    /**
+     * the init population size.
+     */
+    private final int populationSize = 500;
+    /**
+     * the max population size.
+     */
+    private final int maxPopulationSize = 510;
+
+    public GeneticAlgorithm(final long timeout, BenefitPolicy benefitPolicy, CuboidStats cuboidStats) {
+        super(timeout, benefitPolicy, cuboidStats);
+        this.geneticAlgorithm = new org.apache.commons.math3.genetics.GeneticAlgorithm(new BitsOnePointCrossover(),
+                crossoverRate, new BitsMutation(), mutationRate, new RouletteWheelSelection());
+    }
+
+    @Override
+    public List<BigInteger> start(double maxSpaceLimit) {
+        logger.debug("Genetic Algorithm started.");
+
+        //Initial mandatory cuboids
+        double remainingSpace = maxSpaceLimit;
+        for (BigInteger mandatoryOne : cuboidStats.getAllCuboidsForMandatory()) {
+            if (cuboidStats.getCuboidSize(mandatoryOne) != null) {
+                remainingSpace -= cuboidStats.getCuboidSize(mandatoryOne);
+            }
+        }
+
+        BitsChromosomeHelper helper = new BitsChromosomeHelper(remainingSpace, cuboidStats);
+
+        //Generate a population randomly
+        Population initial = initRandomPopulation(helper);
+
+        //Set stopping condition
+        List<StoppingCondition> conditions = Lists.newArrayList();
+        conditions.add(new FixedGenerationCount(550));
+        CombinedStoppingCondition stopCondition = new CombinedStoppingCondition(conditions);
+
+        //Start the evolution
+        Population current = geneticAlgorithm.evolve(initial, stopCondition);
+        BitsChromosome chromosome = (BitsChromosome) current.getFittestChromosome();
+        logger.debug("Genetic Algorithm finished.");
+        List<BigInteger> finalList = Lists.newArrayList();
+        finalList.addAll(helper.getMandatoryCuboids());
+        finalList.addAll(chromosome.getCuboids());
+
+        double totalSpace = 0;
+        if (logger.isTraceEnabled()) {
+            for (BigInteger cuboid : finalList) {
+                Double unitSpace = cuboidStats.getCuboidSize(cuboid);
+                if (unitSpace != null) {
+                    logger.trace(String.format(Locale.ROOT, "cuboidId %d and Space: %f", cuboid, unitSpace));
+                    totalSpace += unitSpace;
+                } else {
+                    logger.trace(String.format(Locale.ROOT, "mandatory cuboidId %d", cuboid));
+                }
+            }
+            logger.trace("Total Space:" + totalSpace);
+            logger.trace("Space Expansion Rate:" + totalSpace / cuboidStats.getBaseCuboidSize());
+        }
+        return finalList;
+    }
+
+    protected Population initRandomPopulation(BitsChromosomeHelper helper) {
+        List<Chromosome> chromosomeList = Lists.newArrayListWithCapacity(populationSize);
+
+        while (chromosomeList.size() < populationSize) {
+            BitSet bitSetForSelection = new BitSet(helper.getLength());
+
+            //Initialize selection genes
+            double totalSpace = 0;
+            while (totalSpace < helper.spaceLimit) {
+                int j = org.apache.commons.math3.genetics.GeneticAlgorithm.getRandomGenerator()
+                        .nextInt(helper.getLength());
+                if (!bitSetForSelection.get(j)) {
+                    totalSpace += helper.getCuboidSizeByBitIndex(j);
+                    bitSetForSelection.set(j);
+                }
+            }
+
+            Chromosome chromosome = new BitsChromosome(bitSetForSelection, benefitPolicy.getInstance(), helper);
+            chromosomeList.add(chromosome);
+        }
+        return new ElitisticListPopulation(chromosomeList, maxPopulationSize, 0.8);
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/RouletteWheelSelection.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/RouletteWheelSelection.java
new file mode 100644
index 0000000000..f7fdfcfd12
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/genetic/RouletteWheelSelection.java
@@ -0,0 +1,61 @@
+/*
+ * 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.metadata.cube.planner.algorithm.genetic;
+
+import java.util.List;
+
+import org.apache.commons.math3.genetics.Chromosome;
+import org.apache.commons.math3.genetics.ChromosomePair;
+import org.apache.commons.math3.genetics.GeneticAlgorithm;
+import org.apache.commons.math3.genetics.ListPopulation;
+import org.apache.commons.math3.genetics.Population;
+import org.apache.commons.math3.genetics.SelectionPolicy;
+
+import com.google.common.collect.Lists;
+
+public class RouletteWheelSelection implements SelectionPolicy {
+    @Override
+    public ChromosomePair select(Population population) throws IllegalArgumentException {
+        // create a copy of the chromosome list
+        List<Chromosome> chromosomes = Lists.newArrayList(((ListPopulation) population).getChromosomes());
+
+        double maxFitness = 0;
+        double totalFitness = 0;
+        for (Chromosome o : chromosomes) {
+            double fitness = o.getFitness();
+            totalFitness += fitness;
+            if (fitness > maxFitness) {
+                maxFitness = fitness;
+            }
+        }
+        return new ChromosomePair(rouletteWheel(chromosomes, totalFitness), rouletteWheel(chromosomes, totalFitness));
+    }
+
+    private Chromosome rouletteWheel(final List<Chromosome> chromosomes, final double totalFitness) {
+        double rnd = (GeneticAlgorithm.getRandomGenerator().nextDouble() * totalFitness);
+        double runningScore = 0;
+        for (Chromosome o : chromosomes) {
+            if (rnd >= runningScore && rnd <= runningScore + o.getFitness()) {
+                return o;
+            }
+            runningScore += o.getFitness();
+        }
+        return null;
+    }
+}
diff --git a/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/greedy/GreedyAlgorithm.java b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/greedy/GreedyAlgorithm.java
new file mode 100644
index 0000000000..a1b454d2b8
--- /dev/null
+++ b/src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/planner/algorithm/greedy/GreedyAlgorithm.java
@@ -0,0 +1,162 @@
+/*
+ * 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.metadata.cube.planner.algorithm.greedy;
+
+import java.math.BigInteger;
+import java.util.List;
+import java.util.Locale;
+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.metadata.cube.planner.algorithm.AbstractRecommendAlgorithm;
+import org.apache.kylin.metadata.cube.planner.algorithm.BenefitPolicy;
+import org.apache.kylin.metadata.cube.planner.algorithm.CuboidBenefitModel;
+import org.apache.kylin.metadata.cube.planner.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<BigInteger> selected = Sets.newLinkedHashSet();
+    private List<BigInteger> remaining = Lists.newLinkedList();
+
+    public GreedyAlgorithm(final long timeout, BenefitPolicy benefitPolicy, CuboidStats cuboidStats) {
+        super(timeout, benefitPolicy, cuboidStats);
+    }
+
+    @Override
+    public List<BigInteger> start(double spaceLimit) {
+        logger.info("Greedy Algorithm started.");
+        executor = Executors.newFixedThreadPool(THREAD_NUM,
+                new ThreadFactoryBuilder().setNameFormat("greedy-algorithm-benefit-calculator-pool-%d").build());
+
+        //Initial mandatory cuboids
+        selected.clear();
+        double remainingSpace = spaceLimit;
+        for (BigInteger mandatoryOne : cuboidStats.getAllCuboidsForMandatory()) {
+            selected.add(mandatoryOne);
+            if (cuboidStats.getCuboidSize(mandatoryOne) != null) {
+                remainingSpace -= cuboidStats.getCuboidSize(mandatoryOne);
+            }
+        }
+        //Initial remaining cuboid set
+        remaining.clear();
+        remaining.addAll(cuboidStats.getAllCuboidsForSelection());
+
+        long round = 0;
+        while (!shouldCancel()) {
+            // 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) {
+                logger.info("Greedy algorithm ends due to cannot find next best one");
+                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 (!benefitPolicy.ifEfficient(best)) {
+                logger.info("Greedy algorithm ends due to the benefit of the best one is not efficient {}",
+                        best.getBenefit());
+                break;
+            }
+
+            remainingSpace -= cuboidStats.getCuboidSize(best.getCuboidId());
+            // If we finally find there is no remaining space,  then we should finish the process and return
+            if (remainingSpace <= 0) {
+                logger.info("Greedy algorithm ends due to there's no remaining space");
+                break;
+            }
+            selected.add(best.getCuboidId());
+            remaining.remove(best.getCuboidId());
+            benefitPolicy.propagateAggregationCost(best.getCuboidId(), selected);
+            round++;
+            if (logger.isTraceEnabled()) {
+                logger.trace(String.format(Locale.ROOT, "Recommend in round %d : %s", round, best.toString()));
+            }
+        }
+
+        executor.shutdown();
+
+        List<BigInteger> excluded = Lists.newArrayList(remaining);
+        remaining.retainAll(selected);
+        Preconditions.checkArgument(remaining.isEmpty(),
+                "There should be no intersection between excluded list and selected list.");
+        logger.info("Greedy Algorithm finished.");
+
+        if (logger.isTraceEnabled()) {
+            logger.trace("Excluded cuboidId size: {}", excluded.size());
+            logger.trace("Excluded cuboidId detail:");
+            for (BigInteger cuboid : excluded) {
+                logger.trace("cuboidId {} and Cost: {} and Space: {}", cuboid, cuboidStats.getCuboidQueryCost(cuboid),
+                        cuboidStats.getCuboidSize(cuboid));
+            }
+            logger.trace("Total Space: {}", spaceLimit - remainingSpace);
+            logger.trace("Space Expansion Rate: {}", (spaceLimit - remainingSpace) / cuboidStats.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 BigInteger cuboid : remaining) {
+            executor.submit(() -> {
+                CuboidBenefitModel currentBest = best.get();
+                assert (selected.size() == selectedSize);
+                CuboidBenefitModel.BenefitModel benefitModel = benefitPolicy.calculateBenefit(cuboid, selected);
+                if (benefitModel != null && (currentBest == null || currentBest.getBenefit() == null
+                        || benefitModel.benefit > currentBest.getBenefit())) {
+                    while (!best.compareAndSet(currentBest,
+                            new CuboidBenefitModel(cuboidStats.getCuboidModel(cuboid), benefitModel))) {
+                        currentBest = best.get();
+                        if (benefitModel.benefit <= currentBest.getBenefit()) {
+                            break;
+                        }
+                    }
+                }
+                counter.countDown();
+            });
+        }
+
+        try {
+            counter.await();
+        } catch (InterruptedException e) {
+        }
+        return best.get();
+    }
+}
diff --git a/src/core-metadata/src/test/java/org/apache/kylin/metadata/cube/planner/CostBasePlannerUtilsTest.java b/src/core-metadata/src/test/java/org/apache/kylin/metadata/cube/planner/CostBasePlannerUtilsTest.java
new file mode 100644
index 0000000000..647d43ef7c
--- /dev/null
+++ b/src/core-metadata/src/test/java/org/apache/kylin/metadata/cube/planner/CostBasePlannerUtilsTest.java
@@ -0,0 +1,34 @@
+package org.apache.kylin.metadata.cube.planner;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.math.BigInteger;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.junit.Test;
+
+import com.google.common.collect.Lists;
+
+public class CostBasePlannerUtilsTest {
+
+    private Map<Integer, Integer> getMap(int dimensionCount) {
+        Map<Integer, Integer> result = new HashMap<>();
+        for (int i = 0; i < dimensionCount; i++) {
+            result.put(i, i);
+        }
+        return result;
+    }
+
+    @Test
+    public void testConvertDimensionsToCuboId() {
+        int maxCountDimension = 12;
+        List<Integer> dimensionIds = Lists.newArrayList(4, 8, 11);
+        BigInteger result = CostBasePlannerUtils.convertDimensionsToCuboId(dimensionIds, maxCountDimension, getMap(12));
+        long expected = 0;
+        expected = 1 << (12 - 1 - 4) | 1 << (12 - 1 - 8) | 1 << (12 - 1 - 11);
+        BigInteger expectedInteger = BigInteger.valueOf(expected);
+        assertEquals(expectedInteger, result);
+    }
+}
\ No newline at end of file
diff --git a/src/data-loading-service/src/main/java/org/apache/kylin/rest/response/ExecutableResponse.java b/src/data-loading-service/src/main/java/org/apache/kylin/rest/response/ExecutableResponse.java
index 4a0ea0f381..bd2eb2f404 100644
--- a/src/data-loading-service/src/main/java/org/apache/kylin/rest/response/ExecutableResponse.java
+++ b/src/data-loading-service/src/main/java/org/apache/kylin/rest/response/ExecutableResponse.java
@@ -284,6 +284,7 @@ public class ExecutableResponse implements Comparable<ExecutableResponse> {
                 continue;
             }
 
+            // TODO calc the result for the frontend
             final String indexCountString = task.getParam(NBatchConstants.P_INDEX_COUNT);
             final String indexSuccess = stage.getOutput(segmentId).getExtra()
                     .getOrDefault(NBatchConstants.P_INDEX_SUCCESS_COUNT, "");
diff --git a/src/kylin-it/src/test/java/org/apache/kylin/metadata/cube/planner/algorithm/ITAlgorithmTestBase.java b/src/kylin-it/src/test/java/org/apache/kylin/metadata/cube/planner/algorithm/ITAlgorithmTestBase.java
new file mode 100644
index 0000000000..d3c3b73b05
--- /dev/null
+++ b/src/kylin-it/src/test/java/org/apache/kylin/metadata/cube/planner/algorithm/ITAlgorithmTestBase.java
@@ -0,0 +1,567 @@
+/*
+ * 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.metadata.cube.planner.algorithm;
+
+import java.io.BufferedReader;
+import java.io.FileInputStream;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.io.PrintWriter;
+import java.io.Serializable;
+import java.math.BigInteger;
+import java.nio.charset.StandardCharsets;
+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.Objects;
+import java.util.Set;
+
+import org.apache.commons.lang.StringUtils;
+import org.apache.kylin.common.util.StringUtil;
+import org.junit.After;
+import org.junit.Before;
+
+import com.fasterxml.jackson.annotation.JsonIgnore;
+import com.fasterxml.jackson.annotation.JsonProperty;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ComparisonChain;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Maps;
+import com.google.common.collect.Sets;
+
+public class ITAlgorithmTestBase {
+
+    public final static Comparator<BigInteger> CuboidSelectComparator = new Comparator<BigInteger>() {
+        @Override
+        public int compare(BigInteger o1, BigInteger o2) {
+            return ComparisonChain.start().compare(o1.bitCount(), o2.bitCount()).compare(o1, o2).result();
+        }
+    };
+
+    private static class TreeNode implements Serializable {
+        @JsonProperty("cuboid_id")
+        BigInteger cuboidId;
+        @JsonIgnore
+        int level;
+        @JsonProperty("children")
+        List<TreeNode> children = Lists.newArrayList();
+
+        public BigInteger getCuboidId() {
+            return cuboidId;
+        }
+
+        public int getLevel() {
+            return level;
+        }
+
+        public List<TreeNode> getChildren() {
+            return children;
+        }
+
+        TreeNode(BigInteger cuboidId, int level) {
+            this.cuboidId = cuboidId;
+            this.level = level;
+        }
+
+        void addChild(BigInteger childId, int parentlevel) {
+            this.children.add(new TreeNode(childId, parentlevel + 1));
+        }
+
+        @Override
+        public int hashCode() {
+            return Objects.hash(cuboidId, level);
+        }
+
+        @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;
+        }
+    }
+
+    public static class CuboidTree implements Serializable {
+        private int treeLevels;
+
+        private TreeNode root;
+
+        private Comparator<BigInteger> cuboidComparator;
+
+        private Map<BigInteger, TreeNode> index = new HashMap<>();
+
+        static CuboidTree createFromCuboids(List<BigInteger> allCuboidIds) {
+            return createFromCuboids(allCuboidIds, CuboidSelectComparator);
+        }
+
+        public static CuboidTree createFromCuboids(List<BigInteger> allCuboidIds,
+                Comparator<BigInteger> 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<BigInteger>() {
+                @Override
+                public int compare(BigInteger o1, BigInteger o2) {
+                    return o2.compareTo(o1);
+                }
+            });
+            BigInteger basicCuboidId = allCuboidIds.get(0);
+            CuboidTree cuboidTree = new CuboidTree(cuboidComparator);
+            cuboidTree.setRoot(basicCuboidId);
+
+            for (BigInteger cuboidId : allCuboidIds) {
+                cuboidTree.addCuboid(cuboidId);
+            }
+            cuboidTree.buildIndex();
+            return cuboidTree;
+        }
+
+        private CuboidTree(Comparator<BigInteger> cuboidComparator) {
+            this.cuboidComparator = cuboidComparator;
+        }
+
+        public Set<BigInteger> getAllCuboidIds() {
+            return index.keySet();
+        }
+
+        public List<BigInteger> getSpanningCuboid(BigInteger cuboidId) {
+            TreeNode node = index.get(cuboidId);
+            if (node == null) {
+                throw new IllegalArgumentException("the cuboid:" + cuboidId + " is not exist in the tree");
+            }
+
+            List<BigInteger> result = Lists.newArrayList();
+            for (TreeNode child : node.children) {
+                result.add(child.cuboidId);
+            }
+            return result;
+        }
+
+        public BigInteger findBestMatchCuboid(BigInteger cuboidId) {
+            // exactly match
+            if (isValid(cuboidId)) {
+                return cuboidId;
+            }
+
+            return findBestParent(cuboidId).cuboidId;
+        }
+
+        public boolean isValid(BigInteger cuboidId) {
+            return index.containsKey(cuboidId);
+        }
+
+        private int getCuboidCount(BigInteger cuboidId) {
+            int r = 1;
+            for (BigInteger child : getSpanningCuboid(cuboidId)) {
+                r += getCuboidCount(child);
+            }
+            return r;
+        }
+
+        public void print(PrintWriter out) {
+            int dimensionCnt = root.cuboidId.bitCount();
+            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(BigInteger cuboidID, int dimensionCount, int depth, PrintWriter out) {
+            StringBuffer sb = new StringBuffer();
+            for (int i = 0; i < depth; i++) {
+                sb.append("    ");
+            }
+            String cuboidName = getDisplayName(cuboidID, dimensionCount);
+            sb.append("|---- Cuboid ").append(cuboidName).append("(" + cuboidID + ")");
+            out.println(sb.toString());
+        }
+
+        private String getDisplayName(BigInteger cuboidID, int dimensionCount) {
+            StringBuilder sb = new StringBuilder();
+            for (int i = 0; i < dimensionCount; ++i) {
+
+                if ((cuboidID.and((BigInteger.valueOf(1L << i))).equals(BigInteger.ZERO))) {
+                    sb.append('0');
+                } else {
+                    sb.append('1');
+                }
+            }
+            return StringUtils.reverse(sb.toString());
+        }
+
+        private void setRoot(BigInteger 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(BigInteger cuboidId) {
+            TreeNode parent = findBestParent(cuboidId);
+            if (parent != null && !parent.cuboidId.equals(cuboidId)) {
+                parent.addChild(cuboidId, parent.level);
+                this.treeLevels = Math.max(this.treeLevels, parent.level + 1);
+            }
+        }
+
+        private TreeNode findBestParent(BigInteger 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(BigInteger 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(BigInteger cuboidId, BigInteger parentCuboid) {
+            return (cuboidId.and(parentCuboid.not())).equals(BigInteger.ZERO);
+        }
+    }
+
+    private static class CuboidCostComparator implements Comparator<BigInteger>, Serializable {
+        private Map<BigInteger, Long> cuboidStatistics;
+
+        public CuboidCostComparator(Map<BigInteger, Long> cuboidStatistics) {
+            Preconditions.checkArgument(cuboidStatistics != null,
+                    "the input " + cuboidStatistics + " should not be null!!!");
+            this.cuboidStatistics = cuboidStatistics;
+        }
+
+        @Override
+        public int compare(BigInteger cuboid1, BigInteger cuboid2) {
+            Long rowCnt1 = cuboidStatistics.get(cuboid1);
+            Long rowCnt2 = cuboidStatistics.get(cuboid2);
+            if (rowCnt2 == null || rowCnt1 == null) {
+                return CuboidSelectComparator.compare(cuboid1, cuboid2);
+            }
+            return Long.compare(rowCnt1, rowCnt2);
+        }
+    }
+
+    public CuboidStats cuboidStats;
+
+    private Set<BigInteger> mandatoryCuboids;
+
+    @Before
+    public void setUp() throws Exception {
+
+        mandatoryCuboids = Sets.newHashSet();
+        mandatoryCuboids.add(BigInteger.valueOf(3000L));
+        mandatoryCuboids.add(BigInteger.valueOf(1888L));
+        mandatoryCuboids.add(BigInteger.valueOf(88L));
+        cuboidStats = new CuboidStats.Builder("test", BigInteger.valueOf(4095L), BigInteger.valueOf(4095L),
+                simulateCount(), simulateSpaceSize()).setMandatoryCuboids(mandatoryCuboids)
+                        .setHitFrequencyMap(simulateHitFrequency()).setScanCountSourceMap(simulateScanCount()).build();
+    }
+
+    @After
+    public void after() throws Exception {
+    }
+
+    /** better if closer to 1, worse if closer to 0*/
+    public double getQueryCostRatio(CuboidStats cuboidStats, List<BigInteger> recommendList) {
+        CuboidTree cuboidTree = CuboidTree.createFromCuboids(recommendList,
+                new CuboidCostComparator(cuboidStats.getStatistics()));
+        double queryCostBest = 0;
+        for (BigInteger cuboidId : cuboidStats.getAllCuboidsForSelection()) {
+            if (cuboidStats.getCuboidQueryCost(cuboidId) != null) {
+                queryCostBest += cuboidStats.getCuboidHitProbability(cuboidId) * cuboidStats.getCuboidCount(cuboidId);
+                //                queryCostBest += cuboidStats.getCuboidHitProbability(cuboidId) * cuboidStats.getCuboidQueryCost(cuboidId);
+            }
+        }
+
+        double queryCost = 0;
+        for (BigInteger cuboidId : cuboidStats.getAllCuboidsForSelection()) {
+            BigInteger matchCuboidId = cuboidTree.findBestMatchCuboid(cuboidId);
+            if (cuboidStats.getCuboidQueryCost(matchCuboidId) != null) {
+                queryCost += cuboidStats.getCuboidHitProbability(cuboidId) * cuboidStats.getCuboidCount(matchCuboidId);
+                //                queryCost += cuboidStats.getCuboidHitProbability(cuboidId) * cuboidStats.getCuboidQueryCost(matchCuboidId);
+            }
+        }
+
+        return queryCostBest / queryCost;
+    }
+
+    protected Map<BigInteger, Long> simulateCount() {
+        Map<BigInteger, Long> countMap = Maps.newHashMap();
+        BufferedReader br = null;
+
+        try {
+
+            String sCurrentLine;
+
+            br = new BufferedReader(new InputStreamReader(new FileInputStream("src/test/resources/statistics.txt"),
+                    StandardCharsets.UTF_8));
+
+            while ((sCurrentLine = br.readLine()) != null) {
+                String[] statPair = StringUtil.split(sCurrentLine, " ");
+                countMap.put(BigInteger.valueOf(Long.valueOf(statPair[0])), Long.valueOf(statPair[1]));
+            }
+
+        } catch (IOException e) {
+            e.printStackTrace();
+        } finally {
+            try {
+                if (br != null)
+                    br.close();
+            } catch (IOException ex) {
+                ex.printStackTrace();
+            }
+        }
+
+        return countMap;
+    }
+
+    protected Map<BigInteger, Double> simulateSpaceSize() {
+        Map<BigInteger, Double> sizeMap = Maps.newHashMap();
+        Map<BigInteger, Long> countMap = simulateCount();
+        for (Map.Entry<BigInteger, Long> entry : countMap.entrySet()) {
+            sizeMap.put(entry.getKey(), entry.getValue() * 1.0);
+        }
+        return sizeMap;
+    }
+
+    protected Map<BigInteger, Long> simulateHitFrequency() {
+        Map<BigInteger, Long> hitFrequencyMap = Maps.newHashMap();
+
+        hitFrequencyMap.put(BigInteger.valueOf(4095L), 10L);
+        hitFrequencyMap.put(BigInteger.valueOf(3849L), 15L);
+        hitFrequencyMap.put(BigInteger.valueOf(3780L), 31L);
+
+        hitFrequencyMap.put(BigInteger.valueOf(3459L), 16L);
+        hitFrequencyMap.put(BigInteger.valueOf(3145L), 29L);
+
+        hitFrequencyMap.put(BigInteger.valueOf(2861L), 21L);
+        hitFrequencyMap.put(BigInteger.valueOf(2768L), 40L);
+
+        hitFrequencyMap.put(BigInteger.valueOf(1528L), 10L);
+        hitFrequencyMap.put(BigInteger.valueOf(1440L), 9L);
+        hitFrequencyMap.put(BigInteger.valueOf(1152L), 21L);
+
+        hitFrequencyMap.put(BigInteger.valueOf(256L), 23L);
+
+        hitFrequencyMap.put(BigInteger.valueOf(128L), 7L);
+        hitFrequencyMap.put(BigInteger.valueOf(272L), 8L);
+        hitFrequencyMap.put(BigInteger.valueOf(288L), 10L);
+        hitFrequencyMap.put(BigInteger.valueOf(384L), 2L);
+        hitFrequencyMap.put(BigInteger.valueOf(320L), 3L);
+        hitFrequencyMap.put(BigInteger.valueOf(432L), 5L);
+        hitFrequencyMap.put(BigInteger.valueOf(258L), 8L);
+        hitFrequencyMap.put(BigInteger.valueOf(336L), 10L);
+        hitFrequencyMap.put(BigInteger.valueOf(274L), 22L);
+        hitFrequencyMap.put(BigInteger.valueOf(488L), 41L);
+        hitFrequencyMap.put(BigInteger.valueOf(352L), 10L);
+
+        hitFrequencyMap.put(BigInteger.valueOf(16L), 1L);
+        hitFrequencyMap.put(BigInteger.valueOf(32L), 5L);
+        hitFrequencyMap.put(BigInteger.valueOf(34L), 1L);
+
+        hitFrequencyMap.put(BigInteger.valueOf(2L), 21L);
+
+        return hitFrequencyMap;
+    }
+
+    protected Map<BigInteger, Map<BigInteger, Long>> simulateScanCount() {
+        Map<BigInteger, Map<BigInteger, Long>> scanCountMap = Maps.newLinkedHashMap();
+        scanCountMap.put(BigInteger.valueOf(4094L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(4095L), 1833041L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(3849L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(3849L), 276711L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(3780L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(3780L), 129199L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(3459L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(3459L), 168109L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(3145L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(3145L), 299991L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(2861L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(2861L), 2121L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(2768L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(2768L), 40231L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(256L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(256L), 1L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(16L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(16L), 1L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(32L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(32L), 2L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(128L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(128L), 3L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(272L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(272L), 2L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(288L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(288L), 3L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(2L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(2L), 1L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(384L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(384L), 2L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(320L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(320L), 3L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(432L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(432L), 5L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(1152L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(1152L), 21L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(258L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(258L), 2L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(1440L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(1440L), 9L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(336L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(336L), 2L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(336L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(336L), 2L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(274L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(274L), 1L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(488L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(488L), 16L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(352L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(352L), 3L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(1528L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(1528L), 21L);
+            }
+        });
+        scanCountMap.put(BigInteger.valueOf(34L), new HashMap<BigInteger, Long>() {
+            {
+                put(BigInteger.valueOf(34L), 1L);
+            }
+        });
+
+        return scanCountMap;
+    }
+}
\ No newline at end of file
diff --git a/src/kylin-it/src/test/java/org/apache/kylin/metadata/cube/planner/algorithm/ITGeneticAlgorithmTest.java b/src/kylin-it/src/test/java/org/apache/kylin/metadata/cube/planner/algorithm/ITGeneticAlgorithmTest.java
new file mode 100644
index 0000000000..761b9e6ed2
--- /dev/null
+++ b/src/kylin-it/src/test/java/org/apache/kylin/metadata/cube/planner/algorithm/ITGeneticAlgorithmTest.java
@@ -0,0 +1,97 @@
+/*
+ * 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.metadata.cube.planner.algorithm;
+
+import static org.junit.Assert.assertEquals;
+
+import java.math.BigInteger;
+import java.util.BitSet;
+import java.util.List;
+import java.util.Set;
+
+import org.apache.commons.math3.genetics.Chromosome;
+import org.apache.kylin.metadata.cube.planner.algorithm.genetic.BitsChromosome;
+import org.apache.kylin.metadata.cube.planner.algorithm.genetic.BitsChromosomeHelper;
+import org.apache.kylin.metadata.cube.planner.algorithm.genetic.GeneticAlgorithm;
+import org.junit.Test;
+
+import com.google.common.collect.Sets;
+
+public class ITGeneticAlgorithmTest extends ITAlgorithmTestBase {
+
+    @Test
+    public void testChromosomeIsSame() {
+        BenefitPolicy benefitPolicy = new BPUSCalculator(cuboidStats);
+
+        double maxSpaceLimit = cuboidStats.getBaseCuboidSize() * 10;
+        BitsChromosomeHelper helper = new BitsChromosomeHelper(maxSpaceLimit, cuboidStats);
+
+        double maxSpaceLimit1 = cuboidStats.getBaseCuboidSize() * 12;
+        BitsChromosomeHelper helper1 = new BitsChromosomeHelper(maxSpaceLimit1, cuboidStats);
+
+        BitSet representation = new BitSet();
+        representation.set(10);
+        Chromosome chromosome = new BitsChromosome(representation, benefitPolicy, helper);
+        Set<Chromosome> chromosomeSet = Sets.newHashSet(chromosome);
+
+        BitSet representation1 = new BitSet();
+        representation1.set(10);
+        chromosomeSet.add(((BitsChromosome) chromosome).newBitsChromosome(representation1));
+        assertEquals(1, chromosomeSet.size());
+
+        BitSet representation2 = new BitSet();
+        representation2.set(12);
+        chromosomeSet.add(((BitsChromosome) chromosome).newBitsChromosome(representation2));
+        assertEquals(2, chromosomeSet.size());
+
+        BitSet representation3 = new BitSet();
+        representation3.set(12);
+        chromosomeSet.add(new BitsChromosome(representation3, benefitPolicy, helper1));
+        assertEquals(2, chromosomeSet.size());
+    }
+
+    @Test
+    public void testBPUSCalculator() {
+        BenefitPolicy benefitPolicy = new BPUSCalculator(cuboidStats);
+        GeneticAlgorithm algorithm = new GeneticAlgorithm(-1, benefitPolicy, cuboidStats);
+
+        List<BigInteger> 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);
+        GeneticAlgorithm algorithm = new GeneticAlgorithm(-1, benefitPolicy, cuboidStats);
+
+        List<BigInteger> 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);
+        GeneticAlgorithm algorithm = new GeneticAlgorithm(-1, benefitPolicy, cuboidStats);
+
+        List<BigInteger> recommendList = algorithm.recommend(10);
+        System.out.println("recommendList by SPBPUSCalculator:" + recommendList);
+        System.out.println("Cost evaluated for each query: " + getQueryCostRatio(cuboidStats, recommendList));
+    }
+}
diff --git a/src/kylin-it/src/test/java/org/apache/kylin/metadata/cube/planner/algorithm/ITGreedyAlgorithmTest.java b/src/kylin-it/src/test/java/org/apache/kylin/metadata/cube/planner/algorithm/ITGreedyAlgorithmTest.java
new file mode 100644
index 0000000000..de5b170c2b
--- /dev/null
+++ b/src/kylin-it/src/test/java/org/apache/kylin/metadata/cube/planner/algorithm/ITGreedyAlgorithmTest.java
@@ -0,0 +1,106 @@
+/*
+ * 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.metadata.cube.planner.algorithm;
+
+import java.math.BigInteger;
+import java.util.List;
+import java.util.function.Function;
+import java.util.stream.Collectors;
+
+import org.apache.kylin.metadata.cube.planner.algorithm.greedy.GreedyAlgorithm;
+import org.assertj.core.util.Lists;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class ITGreedyAlgorithmTest extends ITAlgorithmTestBase {
+    @Test
+    public void testBPUSCalculator() {
+        BenefitPolicy benefitPolicy = new BPUSCalculator(cuboidStats);
+        GreedyAlgorithm algorithm = new GreedyAlgorithm(-1, benefitPolicy, cuboidStats);
+
+        List<BigInteger> recommendList = algorithm.recommend(10);
+        // The result is copy from the result of 3.1 test
+        List<Integer> expected = Lists.newArrayList(1888, 3000, 88, 4095, 258, 1152, 1456, 274, 448, 34, 386, 336, 1528,
+                290, 322, 434, 1410, 1514, 338, 1976, 1458, 984, 1530, 770, 2040, 1962, 786, 890, 1978, 257, 260, 1994,
+                2042, 273, 289, 276, 385, 292, 321, 388, 1513, 324, 259, 2368, 305, 262, 1532, 401, 337, 2306, 1529,
+                3560, 275, 2384, 1531, 278, 3576, 2041, 1534, 2322, 1980, 3578, 4088, 2046, 2043, 3582, 2047, 4090,
+                2352, 2448, 291, 876, 422, 352, 2338, 387, 769, 308, 323, 2434, 404, 3583, 326, 2370, 1961, 2044, 1444,
+                4092, 435, 2482, 1664, 2037, 340, 3976, 492, 800, 3498, 1451, 3572, 438, 1454, 496, 889, 2920, 4081,
+                872, 1457, 811, 1256, 370, 3504, 2858, 48, 466, 814, 371, 2418, 374, 4094, 1928, 400, 1963, 1992, 1460,
+                988, 891, 4010, 2938);
+        List<BigInteger> expectedBigInteger = expected.stream().map(new Function<Integer, BigInteger>() {
+            @Override
+            public BigInteger apply(Integer integer) {
+                return new BigInteger(integer.toString());
+            }
+        }).collect(Collectors.toList());
+        Assert.assertEquals(expectedBigInteger, recommendList);
+        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<BigInteger> recommendList = algorithm.recommend(10);
+        // The result is copy from the result of 3.1 test
+        List<Integer> expected = Lists.newArrayList(1888, 3000, 88, 4095, 2, 1152, 258, 274, 336, 1440, 488, 34, 432,
+                1528, 386, 290, 322, 434, 1410, 1514, 338, 1976, 1458, 984, 1530, 770, 2040, 1962, 786, 890, 1978, 257,
+                260, 1994, 2768, 2042, 273, 256, 289, 276, 385, 292, 352, 321, 388, 288, 1513, 324, 259, 305, 262, 1532,
+                401, 272, 2306, 337, 1529, 3560, 3780, 128, 275, 1531, 278, 3576, 3145, 2041, 1534, 2322, 384, 3578,
+                1980, 3459, 4013, 2043, 2046, 4088, 320, 32, 3582, 4090, 2047, 3977, 2352, 2448, 291, 876, 422, 2338,
+                387, 769, 308, 323, 2434, 1168, 2384, 2861, 404, 326, 2370, 1961, 2044, 1444, 435, 3583, 2482, 1664,
+                340);
+        List<BigInteger> expectedBigInteger = expected.stream().map(new Function<Integer, BigInteger>() {
+            @Override
+            public BigInteger apply(Integer integer) {
+                return new BigInteger(integer.toString());
+            }
+        }).collect(Collectors.toList());
+        Assert.assertEquals(expectedBigInteger, recommendList);
+        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<BigInteger> recommendList = algorithm.recommend(10);
+        // The result is copy from the result of 3.1 test
+        List<Integer> expected = Lists.newArrayList(1888, 3000, 88, 4095, 256, 2, 288, 128, 272, 1152, 258, 274, 336,
+                384, 352, 1440, 432, 488, 34, 1528, 386, 768, 290, 322, 434, 1664, 1410, 1960, 784, 1514, 338, 1976,
+                832, 1458, 1992, 1530, 888, 770, 2040, 1962, 786, 890, 1978, 257, 260, 2768, 1994, 2042, 2304, 273, 289,
+                276, 385, 292, 321, 388, 2336, 1513, 324, 259, 305, 2320, 3780, 262, 401, 1532, 337, 3576, 2306, 1529,
+                3145, 275, 4094, 1531, 2861, 3459, 3849, 2041, 2043, 2047, 291, 323, 3583, 435, 2037, 969, 811, 953,
+                370, 4081, 466, 491, 1457, 339, 1961, 1963, 1459, 891, 497, 889, 1535, 1680, 1210, 308, 1515, 1690);
+        List<BigInteger> expectedBigInteger = expected.stream().map(new Function<Integer, BigInteger>() {
+            @Override
+            public BigInteger apply(Integer integer) {
+                return new BigInteger(integer.toString());
+            }
+        }).collect(Collectors.toList());
+        Assert.assertEquals(expectedBigInteger, recommendList);
+        System.out.println("recommendList by SPBPUSCalculator:" + recommendList);
+        System.out.println("Cost evaluated for each query: " + getQueryCostRatio(cuboidStats, recommendList));
+    }
+}
diff --git a/src/modeling-service/src/main/java/org/apache/kylin/rest/service/FusionIndexService.java b/src/modeling-service/src/main/java/org/apache/kylin/rest/service/FusionIndexService.java
index 491c17120a..80043d3fd5 100644
--- a/src/modeling-service/src/main/java/org/apache/kylin/rest/service/FusionIndexService.java
+++ b/src/modeling-service/src/main/java/org/apache/kylin/rest/service/FusionIndexService.java
@@ -34,8 +34,6 @@ import org.apache.kylin.common.util.JsonUtil;
 import org.apache.kylin.common.util.Pair;
 import org.apache.kylin.job.constant.JobStatusEnum;
 import org.apache.kylin.job.execution.JobTypeEnum;
-import org.apache.kylin.rest.response.AggIndexResponse;
-import org.apache.kylin.rest.response.DiffRuleBasedIndexResponse;
 import org.apache.kylin.metadata.cube.cuboid.NAggregationGroup;
 import org.apache.kylin.metadata.cube.model.IndexEntity;
 import org.apache.kylin.metadata.cube.model.IndexEntity.Range;
@@ -53,7 +51,9 @@ import org.apache.kylin.rest.aspect.Transaction;
 import org.apache.kylin.rest.request.AggShardByColumnsRequest;
 import org.apache.kylin.rest.request.CreateTableIndexRequest;
 import org.apache.kylin.rest.request.UpdateRuleBasedCuboidRequest;
+import org.apache.kylin.rest.response.AggIndexResponse;
 import org.apache.kylin.rest.response.BuildIndexResponse;
+import org.apache.kylin.rest.response.DiffRuleBasedIndexResponse;
 import org.apache.kylin.rest.response.IndexResponse;
 import org.apache.kylin.streaming.manager.StreamingJobManager;
 import org.apache.kylin.streaming.metadata.StreamingJobMeta;
@@ -416,7 +416,8 @@ public class FusionIndexService extends BasicService {
             String modelId) {
         if ((streamResponse.getDecreaseLayouts() > 0 || streamResponse.getIncreaseLayouts() > 0)
                 && checkStreamingJobAndSegments(project, modelId)) {
-            throw new KylinException(ServerErrorCode.STREAMING_INDEX_UPDATE_DISABLE, MsgPicker.getMsg().getStreamingIndexesEdit());
+            throw new KylinException(ServerErrorCode.STREAMING_INDEX_UPDATE_DISABLE,
+                    MsgPicker.getMsg().getStreamingIndexesEdit());
         }
     }
 
@@ -434,7 +435,8 @@ public class FusionIndexService extends BasicService {
     private static void checkStreamingIndexEnabled(String project, NDataModel model) throws KylinException {
         if (NDataModel.ModelType.STREAMING == model.getModelType()
                 && checkStreamingJobAndSegments(project, model.getUuid())) {
-            throw new KylinException(ServerErrorCode.STREAMING_INDEX_UPDATE_DISABLE, MsgPicker.getMsg().getStreamingIndexesDelete());
+            throw new KylinException(ServerErrorCode.STREAMING_INDEX_UPDATE_DISABLE,
+                    MsgPicker.getMsg().getStreamingIndexesDelete());
         }
     }
 
diff --git a/src/modeling-service/src/main/java/org/apache/kylin/rest/service/IndexPlanService.java b/src/modeling-service/src/main/java/org/apache/kylin/rest/service/IndexPlanService.java
index 04b1a93bb3..e45016aeeb 100644
--- a/src/modeling-service/src/main/java/org/apache/kylin/rest/service/IndexPlanService.java
+++ b/src/modeling-service/src/main/java/org/apache/kylin/rest/service/IndexPlanService.java
@@ -260,7 +260,7 @@ public class IndexPlanService extends BasicService implements TableIndexPlanSupp
         return createTableIndex(project, request.getModelId(), newLayout, request.isLoadData());
     }
 
-    public BuildIndexResponse createTableIndex(String project, String modelId, LayoutEntity newLayout,
+    private BuildIndexResponse createTableIndex(String project, String modelId, LayoutEntity newLayout,
             boolean loadData) {
         NIndexPlanManager indexPlanManager = getManager(NIndexPlanManager.class, project);
         val jobManager = getManager(JobManager.class, project);
@@ -272,6 +272,7 @@ public class IndexPlanService extends BasicService implements TableIndexPlanSupp
         }
         int layoutIndex = indexPlan.getWhitelistLayouts().indexOf(newLayout);
         if (layoutIndex != -1) {
+            // find the target layout in this index plan
             indexPlanManager.updateIndexPlan(indexPlan.getUuid(), copyForWrite -> {
                 val oldLayout = copyForWrite.getWhitelistLayouts().get(layoutIndex);
                 oldLayout.setManual(true);
@@ -281,6 +282,8 @@ public class IndexPlanService extends BasicService implements TableIndexPlanSupp
             modelChangeSupporters.forEach(listener -> listener.onUpdate(project, modelId));
             return new BuildIndexResponse(BuildIndexResponse.BuildIndexType.NO_LAYOUT);
         } else {
+            // create a new index for this layout
+            // update this index plan with the new layout
             indexPlanManager.updateIndexPlan(indexPlan.getUuid(), copyForWrite -> {
                 val newCuboid = new IndexEntity();
                 newCuboid.setId(newLayout.getId() - 1);
@@ -456,11 +459,13 @@ public class IndexPlanService extends BasicService implements TableIndexPlanSupp
     public AggIndexResponse calculateAggIndexCount(UpdateRuleBasedCuboidRequest request) {
         aclEvaluate.checkProjectWritePermission(request.getProject());
         val maxCount = getConfig().getCubeAggrGroupMaxCombination();
+        // The agg group for updates which includes all agg group for the index
         List<NAggregationGroup> aggregationGroups = request.getAggregationGroups();
         val indexPlan = getIndexPlan(request.getProject(), request.getModelId()).copy();
         AggIndexCombResult totalResult;
         AggIndexCombResult aggIndexResult;
 
+        // Filter the invalid agg group
         val aggregationGroupsCopy = aggregationGroups.stream()
                 .filter(aggGroup -> aggGroup.getIncludes() != null && aggGroup.getIncludes().length != 0)
                 .collect(Collectors.toList());
@@ -484,7 +489,6 @@ public class IndexPlanService extends BasicService implements TableIndexPlanSupp
                                     StringUtils.join(notExistCols.iterator(), ",")));
                 }
             }
-
             indexPlan.setRuleBasedIndex(ruleBasedIndex);
         } catch (OutOfMaxCombinationException oe) {
             invalid = true;
diff --git a/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/job/JobStepType.java b/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/job/JobStepType.java
index 38f14c56b9..8191f57fe8 100644
--- a/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/job/JobStepType.java
+++ b/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/job/JobStepType.java
@@ -25,9 +25,11 @@ import org.apache.kylin.job.SecondStorageStepFactory;
 import org.apache.kylin.job.execution.AbstractExecutable;
 import org.apache.kylin.job.execution.DefaultExecutable;
 import org.apache.kylin.job.execution.DefaultExecutableOnModel;
+import org.apache.kylin.metadata.cube.model.NBatchConstants;
 
 import static org.apache.kylin.engine.spark.job.StageType.BUILD_DICT;
 import static org.apache.kylin.engine.spark.job.StageType.BUILD_LAYER;
+import static org.apache.kylin.engine.spark.job.StageType.COST_BASED_PLANNER;
 import static org.apache.kylin.engine.spark.job.StageType.GATHER_FLAT_TABLE_STATS;
 import static org.apache.kylin.engine.spark.job.StageType.GENERATE_FLAT_TABLE;
 import static org.apache.kylin.engine.spark.job.StageType.MATERIALIZED_FACT_TABLE;
@@ -83,6 +85,10 @@ public enum JobStepType {
             MATERIALIZED_FACT_TABLE.createStage(parent, config);
             BUILD_DICT.createStage(parent, config);
             GENERATE_FLAT_TABLE.createStage(parent, config);
+            String enablePlanner = parent.getParam(NBatchConstants.P_JOB_ENABLE_PLANNER);
+            if (enablePlanner != null && Boolean.valueOf(enablePlanner)) {
+                COST_BASED_PLANNER.createStage(parent, config);
+            }
             GATHER_FLAT_TABLE_STATS.createStage(parent, config);
             BUILD_LAYER.createStage(parent, config);
             REFRESH_COLUMN_BYTES.createStage(parent, config);
diff --git a/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/job/NSparkCubingJob.java b/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/job/NSparkCubingJob.java
index 00dfe98882..c4179d9368 100644
--- a/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/job/NSparkCubingJob.java
+++ b/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/job/NSparkCubingJob.java
@@ -42,6 +42,7 @@ import org.apache.kylin.job.execution.ExecutableParams;
 import org.apache.kylin.job.execution.JobSchedulerModeEnum;
 import org.apache.kylin.job.execution.JobTypeEnum;
 import org.apache.kylin.job.factory.JobFactory;
+import org.apache.kylin.metadata.cube.model.IndexPlan;
 import org.apache.kylin.metadata.cube.model.LayoutEntity;
 import org.apache.kylin.metadata.cube.model.NBatchConstants;
 import org.apache.kylin.metadata.cube.model.NDataSegment;
@@ -164,6 +165,9 @@ public class NSparkCubingJob extends DefaultExecutableOnModel {
         if (CollectionUtils.isNotEmpty(buckets)) {
             job.setParam(NBatchConstants.P_BUCKETS, ExecutableParams.toBucketParam(buckets));
         }
+
+        enableCostBasedPlannerIfNeed(df, segments, job);
+
         job.setParam(NBatchConstants.P_JOB_ID, jobId);
         job.setParam(NBatchConstants.P_PROJECT_NAME, df.getProject());
         job.setParam(NBatchConstants.P_TARGET_MODEL, job.getTargetSubject());
@@ -422,4 +426,53 @@ public class NSparkCubingJob extends DefaultExecutableOnModel {
         private final AbstractExecutable secondStorage;
         private final AbstractExecutable cleanUpTransactionalTable;
     }
+
+    private static void enableCostBasedPlannerIfNeed(NDataflow df, Set<NDataSegment> segments, NSparkCubingJob job) {
+        // need run the cost based planner:
+        // 1. config enable the cube planner
+        // 2. the model dose not have the `layout_cost_based_pruned_list`
+        // 3. rule index has agg group
+        // 4. just only one segment to be built/refresh(other case will throw exception)
+        IndexPlan indexPlan = df.getIndexPlan();
+        KylinConfig kylinConfig = indexPlan.getConfig();
+        boolean needCostRecommendIndex = indexPlan.getRuleBasedIndex() != null
+                && indexPlan.getRuleBasedIndex().getLayoutsOfCostBasedList() == null
+                && !indexPlan.getRuleBasedIndex().getAggregationGroups().isEmpty();
+        if (kylinConfig.enableCostBasedIndexPlanner() && needCostRecommendIndex
+                && canEnablePlannerJob(job.getJobType())) {
+            // must run the cost based planner
+            if (segments.size() == 1) {
+                if (noBuildingSegmentExist(df.getProject(), job.getTargetSubject(), kylinConfig)) {
+                    // check the count of rowkey:
+                    // if the count of row key exceed the 63, throw exception
+                    if (indexPlan.getRuleBasedIndex().countOfIncludeDimension() > (Long.SIZE - 1)) {
+                        throw new RuntimeException(String.format(
+                                "The count of row key %d can't be larger than 63, when use the cube planner",
+                                indexPlan.getRuleBasedIndex().countOfIncludeDimension()));
+                    }
+                    // Add the parameter `P_JOB_ENABLE_PLANNER` which is used to decide whether to use the  cube planner
+                    job.setParam(NBatchConstants.P_JOB_ENABLE_PLANNER, Boolean.TRUE.toString());
+                } else {
+                    throw new RuntimeException(
+                            "There are running job for this model when submit the build job with cost based planner, "
+                                    + "please wait for other jobs to finish or cancel them");
+                }
+            } else {
+                throw new RuntimeException("The number of segments to be built or refreshed must be 1, "
+                        + "This is the first time to submit build job with enable cost based planner");
+            }
+        }
+    }
+
+    private static boolean noBuildingSegmentExist(String project, String modelId, KylinConfig kylinConfig) {
+        NDataflowManager nDataflowManager = NDataflowManager.getInstance(kylinConfig, project);
+        NDataflow dataflow = nDataflowManager.getDataflow(modelId);
+        // There are no other tasks in building
+        return dataflow.getSegments(SegmentStatusEnum.NEW).size() <= 1;
+    }
+
+    private static boolean canEnablePlannerJob(JobTypeEnum jobType) {
+        // just support: INC_BUILD and INDEX_REFRESH to recommend/prune index
+        return JobTypeEnum.INC_BUILD.equals(jobType) || JobTypeEnum.INDEX_REFRESH.equals(jobType);
+    }
 }
diff --git a/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/job/StageType.java b/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/job/StageType.java
index 431ab31693..6bc41da5ed 100644
--- a/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/job/StageType.java
+++ b/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/job/StageType.java
@@ -32,6 +32,7 @@ import org.apache.kylin.engine.spark.job.stage.StageExec;
 import org.apache.kylin.engine.spark.job.stage.WaiteForResource;
 import org.apache.kylin.engine.spark.job.stage.build.BuildDict;
 import org.apache.kylin.engine.spark.job.stage.build.BuildLayer;
+import org.apache.kylin.engine.spark.job.stage.build.CostBasedPlanner;
 import org.apache.kylin.engine.spark.job.stage.build.GatherFlatTableStats;
 import org.apache.kylin.engine.spark.job.stage.build.GenerateFlatTable;
 import org.apache.kylin.engine.spark.job.stage.build.MaterializedFactTableView;
@@ -39,6 +40,7 @@ import org.apache.kylin.engine.spark.job.stage.build.RefreshColumnBytes;
 import org.apache.kylin.engine.spark.job.stage.build.RefreshSnapshots;
 import org.apache.kylin.engine.spark.job.stage.build.partition.PartitionBuildDict;
 import org.apache.kylin.engine.spark.job.stage.build.partition.PartitionBuildLayer;
+import org.apache.kylin.engine.spark.job.stage.build.partition.PartitionCostBasedPlanner;
 import org.apache.kylin.engine.spark.job.stage.build.partition.PartitionGatherFlatTableStats;
 import org.apache.kylin.engine.spark.job.stage.build.partition.PartitionGenerateFlatTable;
 import org.apache.kylin.engine.spark.job.stage.build.partition.PartitionMaterializedFactTableView;
@@ -120,6 +122,20 @@ public enum StageType {
             return new NStageForBuild(ExecutableConstants.STAGE_NAME_GENERATE_FLAT_TABLE);
         }
     },
+    COST_BASED_PLANNER {
+        @Override
+        public StageExec create(SparkApplication jobContext, NDataSegment dataSegment, BuildParam buildParam) {
+            if (isPartitioned(jobContext)) {
+                return new PartitionCostBasedPlanner((SegmentJob) jobContext, dataSegment, buildParam);
+            }
+            return new CostBasedPlanner((SegmentJob) jobContext, dataSegment, buildParam);
+        }
+
+        @Override
+        protected StageBase create(NSparkExecutable parent, KylinConfig config) {
+            return new NStageForBuild(ExecutableConstants.STAGE_NAME_COST_BASED_PLANNER);
+        }
+    },
     GATHER_FLAT_TABLE_STATS {
         @Override
         public StageExec create(SparkApplication jobContext, NDataSegment dataSegment, BuildParam buildParam) {
diff --git a/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/merger/AfterBuildResourceMerger.java b/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/merger/AfterBuildResourceMerger.java
index 117d381df8..428245a70b 100644
--- a/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/merger/AfterBuildResourceMerger.java
+++ b/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/merger/AfterBuildResourceMerger.java
@@ -52,6 +52,7 @@ public class AfterBuildResourceMerger extends SparkJobMetadataMerger {
     @Override
     public NDataLayout[] merge(String dataflowId, Set<String> segmentId, Set<Long> layoutIds,
             ResourceStore remoteResourceStore, JobTypeEnum jobType, Set<Long> partitions) {
+        // TODO checker the input layouts
         switch (jobType) {
         case INDEX_BUILD:
         case SUB_PARTITION_BUILD:
@@ -110,7 +111,6 @@ public class AfterBuildResourceMerger extends SparkJobMetadataMerger {
         dfUpdate.setToUpdateSegs(theSeg);
         dfUpdate.setToRemoveSegs(toRemoveSegments.toArray(new NDataSegment[toRemoveSegments.size()]));
         dfUpdate.setToAddOrUpdateLayouts(theSeg.getSegDetails().getLayouts().toArray(new NDataLayout[0]));
-
         localDataflowManager.updateDataflow(dfUpdate);
         updateIndexPlan(flowName, remoteStore);
         return dfUpdate.getToAddOrUpdateLayouts();
diff --git a/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/merger/AfterMergeOrRefreshResourceMerger.java b/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/merger/AfterMergeOrRefreshResourceMerger.java
index b9b4414685..3028a615fc 100644
--- a/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/merger/AfterMergeOrRefreshResourceMerger.java
+++ b/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/merger/AfterMergeOrRefreshResourceMerger.java
@@ -26,21 +26,23 @@ import java.util.Set;
 import org.apache.commons.collections.CollectionUtils;
 import org.apache.kylin.common.KylinConfig;
 import org.apache.kylin.common.persistence.ResourceStore;
+import org.apache.kylin.engine.spark.ExecutableUtils;
 import org.apache.kylin.job.execution.AbstractExecutable;
 import org.apache.kylin.job.execution.JobTypeEnum;
-import org.apache.kylin.metadata.model.SegmentStatusEnum;
-import org.apache.kylin.engine.spark.ExecutableUtils;
 import org.apache.kylin.metadata.cube.model.NDataLayout;
 import org.apache.kylin.metadata.cube.model.NDataSegment;
 import org.apache.kylin.metadata.cube.model.NDataflow;
 import org.apache.kylin.metadata.cube.model.NDataflowManager;
 import org.apache.kylin.metadata.cube.model.NDataflowUpdate;
 import org.apache.kylin.metadata.cube.model.PartitionStatusEnum;
+import org.apache.kylin.metadata.model.SegmentStatusEnum;
 
 import com.clearspring.analytics.util.Lists;
 
 import lombok.val;
+import lombok.extern.slf4j.Slf4j;
 
+@Slf4j
 public class AfterMergeOrRefreshResourceMerger extends SparkJobMetadataMerger {
 
     public AfterMergeOrRefreshResourceMerger(KylinConfig config, String project) {
@@ -170,6 +172,7 @@ public class AfterMergeOrRefreshResourceMerger extends SparkJobMetadataMerger {
     @Override
     public NDataLayout[] merge(String dataflowId, Set<String> segmentIds, Set<Long> layoutIds,
             ResourceStore remoteResourceStore, JobTypeEnum jobType, Set<Long> partitions) {
+        // TODO checker the input layouts
         if (CollectionUtils.isNotEmpty(partitions)) {
             return mergeMultiPartitionModel(dataflowId, segmentIds, layoutIds, remoteResourceStore, jobType,
                     partitions);
diff --git a/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/merger/SparkJobMetadataMerger.java b/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/merger/SparkJobMetadataMerger.java
index e9cf08bec7..8403c976ab 100644
--- a/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/merger/SparkJobMetadataMerger.java
+++ b/src/spark-project/engine-spark/src/main/java/org/apache/kylin/engine/spark/merger/SparkJobMetadataMerger.java
@@ -33,7 +33,6 @@ import org.apache.kylin.job.dao.JobStatisticsManager;
 import org.apache.kylin.job.execution.AbstractExecutable;
 import org.apache.kylin.job.execution.JobTypeEnum;
 import org.apache.kylin.job.execution.NExecutableManager;
-import org.apache.kylin.metadata.project.ProjectInstance;
 import org.apache.kylin.metadata.cube.model.IndexPlan;
 import org.apache.kylin.metadata.cube.model.LayoutEntity;
 import org.apache.kylin.metadata.cube.model.LayoutPartition;
@@ -45,6 +44,7 @@ import org.apache.kylin.metadata.cube.model.NIndexPlanManager;
 import org.apache.kylin.metadata.cube.model.PartitionStatusEnum;
 import org.apache.kylin.metadata.cube.model.SegmentPartition;
 import org.apache.kylin.metadata.model.NTableMetadataManager;
+import org.apache.kylin.metadata.project.ProjectInstance;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
@@ -214,6 +214,20 @@ public abstract class SparkJobMetadataMerger extends MetadataMerger {
         NIndexPlanManager indexPlanManager = NIndexPlanManager.getInstance(getConfig(), getProject());
         indexPlanManager.updateIndexPlan(dfId, copyForWrite -> {
             copyForWrite.setLayoutBucketNumMapping(remoteIndexPlan.getLayoutBucketNumMapping());
+            // This is used for the cube planner
+            // In the function of `updateIndexPlanIfNeed`, we may add recommended index for this index plan.
+            // We need to update the `RuleBasedIndex` for the index plan to kylin metadata
+            val remoteRuleIndex = remoteIndexPlan.getRuleBasedIndex();
+            val currentRuleIndex = copyForWrite.getRuleBasedIndex();
+            if (remoteRuleIndex != null && currentRuleIndex != null) {
+                // remote store has the recommended index
+                // current store does not contain the recommended index
+                if (remoteRuleIndex.getLayoutsOfCostBasedList() != null
+                        && currentRuleIndex.getLayoutsOfCostBasedList() == null) {
+                    currentRuleIndex.setLayoutsOfCostBasedList(remoteRuleIndex.getLayoutsOfCostBasedList());
+                }
+                copyForWrite.setRuleBasedIndex(currentRuleIndex);
+            }
         });
     }
 }
diff --git a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/PartitionExec.scala b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/PartitionExec.scala
index 324e981191..887b252c01 100644
--- a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/PartitionExec.scala
+++ b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/PartitionExec.scala
@@ -137,7 +137,7 @@ private[job] trait PartitionExec {
           dataLayout.setByteSize(partitions.map(_.getByteSize).sum)
           dataLayout
         }.toSeq
-
+        logInfo(s"Partition segment $segmentId update the data layouts $dataLayouts")
         updateDataLayouts(manager, dataLayouts)
       }
     }
diff --git a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/RDSegmentBuildJob.java b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/RDSegmentBuildJob.java
index 1a553eaf9b..f4809375ab 100644
--- a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/RDSegmentBuildJob.java
+++ b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/RDSegmentBuildJob.java
@@ -65,6 +65,6 @@ public class RDSegmentBuildJob extends SegmentJob implements ResourceDetect {
 
     private void writeCountDistinct() {
         ResourceDetectUtils.write(new Path(rdSharedPath, ResourceDetectUtils.countDistinctSuffix()), //
-                ResourceDetectUtils.findCountDistinctMeasure(readOnlyLayouts));
+                ResourceDetectUtils.findCountDistinctMeasure(getReadOnlyLayouts()));
     }
 }
diff --git a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/SegmentBuildJob.java b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/SegmentBuildJob.java
index a6be082423..b9663c8d26 100644
--- a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/SegmentBuildJob.java
+++ b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/SegmentBuildJob.java
@@ -29,10 +29,10 @@ import org.apache.kylin.common.KylinConfig;
 import org.apache.kylin.common.persistence.transaction.UnitOfWork;
 import org.apache.kylin.common.util.HadoopUtil;
 import org.apache.kylin.engine.spark.builder.SnapshotBuilder;
-import org.apache.kylin.engine.spark.job.LogJobInfoUtils;
 import org.apache.kylin.engine.spark.job.exec.BuildExec;
 import org.apache.kylin.engine.spark.job.stage.BuildParam;
 import org.apache.kylin.engine.spark.job.stage.StageExec;
+import org.apache.kylin.metadata.cube.model.NBatchConstants;
 import org.apache.kylin.metadata.cube.model.NDataSegment;
 import org.apache.kylin.metadata.cube.model.NDataflow;
 import org.apache.kylin.metadata.cube.model.NDataflowManager;
@@ -50,6 +50,7 @@ import java.util.stream.Stream;
 
 import static org.apache.kylin.engine.spark.job.StageType.BUILD_DICT;
 import static org.apache.kylin.engine.spark.job.StageType.BUILD_LAYER;
+import static org.apache.kylin.engine.spark.job.StageType.COST_BASED_PLANNER;
 import static org.apache.kylin.engine.spark.job.StageType.GATHER_FLAT_TABLE_STATS;
 import static org.apache.kylin.engine.spark.job.StageType.GENERATE_FLAT_TABLE;
 import static org.apache.kylin.engine.spark.job.StageType.MATERIALIZED_FACT_TABLE;
@@ -60,11 +61,22 @@ import static org.apache.kylin.engine.spark.job.StageType.WAITE_FOR_RESOURCE;
 @Slf4j
 public class SegmentBuildJob extends SegmentJob {
 
+    private boolean usePlanner = false;
+
     public static void main(String[] args) {
         SegmentBuildJob segmentBuildJob = new SegmentBuildJob();
         segmentBuildJob.execute(args);
     }
 
+    @Override
+    protected final void extraInit() {
+        super.extraInit();
+        String enablePlanner = getParam(NBatchConstants.P_JOB_ENABLE_PLANNER);
+        if (enablePlanner != null && Boolean.valueOf(enablePlanner)) {
+            usePlanner = true;
+        }
+    }
+
     @Override
     protected String generateInfo() {
         return LogJobInfoUtils.dfBuildJobInfo();
@@ -135,6 +147,11 @@ public class SegmentBuildJob extends SegmentJob {
                 MATERIALIZED_FACT_TABLE.createStage(this, seg, buildParam, exec);
                 BUILD_DICT.createStage(this, seg, buildParam, exec);
                 GENERATE_FLAT_TABLE.createStage(this, seg, buildParam, exec);
+                // enable cost based planner according to the parameter
+                if (usePlanner) {
+                    COST_BASED_PLANNER.createStage(this, seg, buildParam, exec);
+                }
+
                 GATHER_FLAT_TABLE_STATS.createStage(this, seg, buildParam, exec);
                 BUILD_LAYER.createStage(this, seg, buildParam, exec);
 
diff --git a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/SegmentExec.scala b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/SegmentExec.scala
index 800c90e853..e0f635acad 100644
--- a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/SegmentExec.scala
+++ b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/SegmentExec.scala
@@ -229,6 +229,7 @@ trait SegmentExec extends Logging {
           dataLayout.setByteSize(taskStats.numBytes)
           dataLayout
         }
+        logInfo(s"Segment $segmentId update the data layouts $dataLayouts")
         updateDataLayouts(manager, dataLayouts)
       }
     }
diff --git a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/SegmentJob.java b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/SegmentJob.java
index 479428f09a..8d9925cc43 100644
--- a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/SegmentJob.java
+++ b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/SegmentJob.java
@@ -20,8 +20,10 @@ package org.apache.kylin.engine.spark.job;
 
 import java.util.Arrays;
 import java.util.Collections;
+import java.util.HashSet;
 import java.util.LinkedHashSet;
 import java.util.List;
+import java.util.Map;
 import java.util.Objects;
 import java.util.Set;
 import java.util.function.Predicate;
@@ -29,6 +31,7 @@ import java.util.stream.Collectors;
 
 import org.apache.commons.lang3.StringUtils;
 import org.apache.hadoop.fs.Path;
+import org.apache.kylin.common.persistence.transaction.UnitOfWork;
 import org.apache.kylin.engine.spark.application.SparkApplication;
 import org.apache.kylin.engine.spark.scheduler.JobRuntime;
 import org.apache.kylin.job.execution.ExecutableParams;
@@ -38,12 +41,19 @@ import org.apache.kylin.metadata.cube.model.NBatchConstants;
 import org.apache.kylin.metadata.cube.model.NDataSegment;
 import org.apache.kylin.metadata.cube.model.NDataflow;
 import org.apache.kylin.metadata.cube.model.NDataflowManager;
+import org.apache.kylin.metadata.cube.model.NIndexPlanManager;
 import org.apache.kylin.metadata.job.JobBucket;
 import org.apache.spark.tracker.BuildContext;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Maps;
+import com.google.common.collect.Sets;
+
+import lombok.val;
 
 public abstract class SegmentJob extends SparkApplication {
 
@@ -54,9 +64,8 @@ public abstract class SegmentJob extends SparkApplication {
     protected IndexPlan indexPlan;
 
     protected String dataflowId;
-
-    protected Set<LayoutEntity> readOnlyLayouts;
-
+    // In order to support the cube planner, `readOnlyLayouts` can be changed
+    private Set<LayoutEntity> readOnlyLayouts;
     protected Set<NDataSegment> readOnlySegments;
 
     // Resource detection results output path
@@ -76,8 +85,72 @@ public abstract class SegmentJob extends SparkApplication {
         return readOnlyLayouts;
     }
 
+    private Set<LayoutEntity> recommendAggLayouts = new HashSet<>();
+
+    private Set<LayoutEntity> getRecommendAggLayouts() {
+        return recommendAggLayouts;
+    }
+
+    public void setRecommendAggLayouts(Set<LayoutEntity> aggIndexLayouts) {
+        recommendAggLayouts.clear();
+        recommendAggLayouts.addAll(aggIndexLayouts);
+    }
+
+    public boolean updateIndexPlanIfNeed() {
+        // when run the cube planner, there will be some recommended index layouts for this model
+        if (getRecommendAggLayouts().size() != 0) {
+            UnitOfWork.doInTransactionWithRetry(() -> {
+                // update and add the recommended index layout to the index plan
+                val recommendAggLayouts = Lists.newArrayList(getRecommendAggLayouts());
+                NIndexPlanManager indexPlanManager = NIndexPlanManager.getInstance(config, project);
+                logger.debug("Update the index plan and add recommended agg index {}", recommendAggLayouts);
+                indexPlanManager.updateIndexPlan(dataflowId, copyForWrite -> {
+                    // construct the map: layout -> id
+                    val allRuleLayouts = copyForWrite.getRuleBasedIndex().genCuboidLayouts();
+                    Map<LayoutEntity, Long> layouts2Id = Maps.newHashMap();
+                    allRuleLayouts.forEach(layoutEntity -> {
+                        layouts2Id.put(layoutEntity, layoutEntity.getId());
+                    });
+                    logger.debug("All rule base layouts {}", allRuleLayouts);
+                    Set<Long> costBasedResult = Sets.newHashSet();
+                    for (LayoutEntity layoutEntity : recommendAggLayouts) {
+                        if (layouts2Id.containsKey(layoutEntity)) {
+                            costBasedResult.add(layouts2Id.get(layoutEntity));
+                        } else {
+                            logger.debug("Can't find the layout {} in the rule base index", layoutEntity);
+                        }
+                    }
+                    // reset the rule base layouts
+                    logger.debug("Set the rule pruning cost based list layouts {}", costBasedResult);
+                    val ruleBaseIndex = copyForWrite.getRuleBasedIndex();
+                    ruleBaseIndex.setLayoutsOfCostBasedList(costBasedResult);
+                    copyForWrite.setRuleBasedIndex(ruleBaseIndex);
+                });
+                return null;
+            }, project);
+            updateJobLayoutsIfNeed();
+            return true;
+        } else {
+            logger.info("There is no recommended agg index");
+            return false;
+        }
+    }
+
+    private void updateJobLayoutsIfNeed() {
+        // update this job layouts when there are recommended index layouts for this build
+        NDataflowManager dataflowManager = NDataflowManager.getInstance(config, project);
+        // get the new index plan
+        indexPlan = dataflowManager.getDataflow(dataflowId).getIndexPlan();
+        // get the new layout
+        val newJobLayouts = indexPlan.getAllLayouts();
+        logger.debug("Update Job layouts count from {} to {}", readOnlyLayouts.size(), newJobLayouts.size());
+        readOnlyLayouts = new HashSet<>(newJobLayouts);
+        // rewrite the `P_LAYOUT_IDS` parameters
+        setParam(NBatchConstants.P_LAYOUT_IDS, NSparkCubingUtil.ids2Str(NSparkCubingUtil.toLayoutIds(readOnlyLayouts)));
+    }
+
     @Override
-    protected final void extraInit() {
+    protected void extraInit() {
         partialBuild = Boolean.parseBoolean(getParam(NBatchConstants.P_PARTIAL_BUILD));
         Set<String> segmentIDs = Arrays.stream(getParam(NBatchConstants.P_SEGMENT_IDS).split(COMMA))
                 .collect(Collectors.toCollection(LinkedHashSet::new));
diff --git a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/BuildStage.scala b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/BuildStage.scala
index 49d53d7b31..414335d9fa 100644
--- a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/BuildStage.scala
+++ b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/BuildStage.scala
@@ -60,7 +60,12 @@ abstract class BuildStage(private val jobContext: SegmentJob,
   protected final val sparkSession = jobContext.getSparkSession
   protected final val resourceContext = jobContext.getBuildContext
   protected final val runtime = jobContext.getRuntime
-  protected final val readOnlyLayouts = jobContext.getReadOnlyLayouts
+
+  // These parameters can be changed when running the cube planner, should use the
+  // `def` to get the latest data
+  protected def readOnlyLayouts = jobContext.getReadOnlyLayouts
+  private def spanningTree = buildParam.getSpanningTree
+  private def flatTableDesc = buildParam.getFlatTableDesc
 
   // Needed variables from data segment.
   protected final val segmentId = dataSegment.getId
@@ -69,10 +74,6 @@ abstract class BuildStage(private val jobContext: SegmentJob,
   protected final val dataModel = dataSegment.getModel
   protected final val storageType = dataModel.getStorageType
 
-  private lazy val spanningTree = buildParam.getSpanningTree
-
-  private lazy val flatTableDesc = buildParam.getFlatTableDesc
-
   private lazy val flatTable = buildParam.getBuildFlatTable
 
   private lazy val flatTableDS: Dataset[Row] = buildParam.getFlatTable
diff --git a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/MaterializedFactTableView.scala b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/CostBasedPlanner.scala
similarity index 57%
copy from src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/MaterializedFactTableView.scala
copy to src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/CostBasedPlanner.scala
index 584538f47d..08ba41e46d 100644
--- a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/MaterializedFactTableView.scala
+++ b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/CostBasedPlanner.scala
@@ -25,33 +25,29 @@ import org.apache.kylin.engine.spark.smarter.IndexDependencyParser
 import org.apache.kylin.metadata.cube.cuboid.AdaptiveSpanningTree
 import org.apache.kylin.metadata.cube.cuboid.AdaptiveSpanningTree.AdaptiveTreeBuilder
 import org.apache.kylin.metadata.cube.model.NDataSegment
-import org.apache.spark.sql.{Dataset, Row}
 
-class MaterializedFactTableView(jobContext: SegmentJob, dataSegment: NDataSegment, buildParam: BuildParam)
+class CostBasedPlanner(jobContext: SegmentJob, dataSegment: NDataSegment, buildParam: BuildParam)
   extends FlatTableAndDictBase(jobContext, dataSegment, buildParam) {
-
   override def execute(): Unit = {
-    logInfo(s"Build SEGMENT $segmentId")
-    val spanTree = new AdaptiveSpanningTree(config, new AdaptiveTreeBuilder(dataSegment, readOnlyLayouts))
-    buildParam.setSpanningTree(spanTree)
-
-    val flatTableDesc: SegmentFlatTableDesc = if (jobContext.isPartialBuild) {
-      val parser = new IndexDependencyParser(dataModel)
-      val relatedTableAlias =
-        parser.getRelatedTablesAlias(jobContext.getReadOnlyLayouts)
-      new SegmentFlatTableDesc(config, dataSegment, spanningTree, relatedTableAlias)
-    } else {
-      new SegmentFlatTableDesc(config, dataSegment, spanningTree)
-    }
-    buildParam.setFlatTableDesc(flatTableDesc)
+    val (cost, sourceCount) = generateCostTable()
+    getRecommendedLayoutAndUpdateMetadata(cost, sourceCount)
 
-    val factTableDS: Dataset[Row] = newFactTableDS()
-    buildParam.setFactTableDS(factTableDS)
+    val result = jobContext.updateIndexPlanIfNeed()
+    if (result) {
+      // update span tree and table desc with the new build job layouts
+      val spanTree = new AdaptiveSpanningTree(config, new AdaptiveTreeBuilder(dataSegment, readOnlyLayouts))
+      buildParam.setSpanningTree(spanTree)
 
-    val fastFactTableDS: Dataset[Row] = newFastFactTableDS()
-    buildParam.setFastFactTableDS(fastFactTableDS)
-    if (buildParam.isSkipMaterializedFactTableView) {
-      onStageSkipped()
+      // update table desc with new span tree
+      val flatTableDesc: SegmentFlatTableDesc = if (jobContext.isPartialBuild) {
+        val parser = new IndexDependencyParser(dataModel)
+        val relatedTableAlias =
+          parser.getRelatedTablesAlias(readOnlyLayouts)
+        new SegmentFlatTableDesc(config, dataSegment, spanningTree, relatedTableAlias)
+      } else {
+        new SegmentFlatTableDesc(config, dataSegment, spanningTree)
+      }
+      buildParam.setFlatTableDesc(flatTableDesc)
     }
   }
 }
diff --git a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/FlatTableAndDictBase.scala b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/FlatTableAndDictBase.scala
index 4de752d79e..d28f4e2fec 100644
--- a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/FlatTableAndDictBase.scala
+++ b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/FlatTableAndDictBase.scala
@@ -18,8 +18,10 @@
 
 package org.apache.kylin.engine.spark.job.stage.build
 
+import java.math.BigInteger
 import java.util.{Locale, Objects}
 
+import com.google.common.collect.Sets
 import org.apache.commons.lang3.StringUtils
 import org.apache.hadoop.fs.Path
 import org.apache.kylin.common.util.HadoopUtil
@@ -32,9 +34,11 @@ import org.apache.kylin.engine.spark.job.NSparkCubingUtil.convertFromDot
 import org.apache.kylin.engine.spark.job.stage.{BuildParam, StageExec}
 import org.apache.kylin.engine.spark.job.{FiltersUtil, SegmentJob, TableMetaManager}
 import org.apache.kylin.engine.spark.model.SegmentFlatTableDesc
+import org.apache.kylin.engine.spark.model.planner.{CuboIdToLayoutUtils, FlatTableToCostUtils}
 import org.apache.kylin.engine.spark.utils.LogEx
 import org.apache.kylin.engine.spark.utils.SparkDataSource._
 import org.apache.kylin.metadata.cube.model.NDataSegment
+import org.apache.kylin.metadata.cube.planner.CostBasePlannerUtils
 import org.apache.kylin.metadata.model._
 import org.apache.kylin.query.util.QueryUtil
 import org.apache.spark.sql.KapFunctions.dict_encode_v3
@@ -65,8 +69,11 @@ abstract class FlatTableAndDictBase(private val jobContext: SegmentJob,
 
   import FlatTableAndDictBase._
 
-  protected lazy val spanningTree = buildParam.getSpanningTree
-  protected lazy val tableDesc = buildParam.getFlatTableDesc
+  // These parameters can be changed when running the cube planner, should use the
+  // `def` to get the latest data
+  protected def spanningTree = buildParam.getSpanningTree
+
+  protected def tableDesc = buildParam.getFlatTableDesc
 
   protected lazy final val indexPlan = tableDesc.getIndexPlan
   protected lazy final val segmentRange = tableDesc.getSegmentRange
@@ -141,6 +148,41 @@ abstract class FlatTableAndDictBase(private val jobContext: SegmentJob,
     changeSchemeToColumnId(flatTableDS, tableDesc)
   }
 
+  protected def generateCostTable(): (java.util.Map[BigInteger, java.lang.Long], Long) = {
+    val rowkeyCount = indexPlan.getRuleBasedIndex.countOfIncludeDimension()
+    val stepDesc = s"Segment $segmentId generate the cost for the planner from the flat table, " +
+      s"rowkey count is $rowkeyCount"
+    logInfo(stepDesc)
+    sparkSession.sparkContext.setJobDescription(stepDesc)
+    // get the cost from the flat table
+    val javaRddFlatTable = FLAT_TABLE.javaRDD
+    // log dimension and table desc
+    logInfo(s"Segment $segmentId calculate the cost, the dimension in rule index is: " +
+      s"${indexPlan.getRuleBasedIndex.getDimensions}, " +
+      s"the column in flat table is: ${tableDesc.getColumnIds}")
+    val cuboIdsCost = FlatTableToCostUtils.generateCost(javaRddFlatTable, config, indexPlan.getRuleBasedIndex, tableDesc)
+    // get the count for the flat table
+    val sourceCount = FLAT_TABLE.count()
+    logInfo(s"The total source count is $sourceCount")
+    sparkSession.sparkContext.setJobDescription(null)
+    val cuboIdToRowCount = FlatTableToCostUtils.getCuboidRowCountMapFromSampling(cuboIdsCost)
+    (cuboIdToRowCount, sourceCount)
+  }
+
+  protected def getRecommendedLayoutAndUpdateMetadata(cuboIdToRowCount: java.util.Map[BigInteger, java.lang.Long],
+                                                      sourceCount: Long): Unit = {
+    logDebug(s"Segment $segmentId get the row count cost $cuboIdToRowCount")
+    val cuboIdToSize = FlatTableToCostUtils.
+      getCuboidSizeMapFromSampling(cuboIdToRowCount, sourceCount, indexPlan.getRuleBasedIndex, config, tableDesc)
+    logDebug(s"Segment $segmentId get the size cost $cuboIdToSize")
+    val cuboids = CostBasePlannerUtils.
+      getRecommendCuboidList(indexPlan.getRuleBasedIndex, config, dataModel.getAlias, cuboIdToRowCount, cuboIdToSize)
+    logDebug(s"Segment $segmentId get the recommended cuboid ${cuboids.keySet()}")
+    val allRecommendedLayouts = CuboIdToLayoutUtils.convertCuboIdsToLayoutEntity(cuboids, indexPlan.getRuleBasedIndex)
+    logInfo(s"Segment $segmentId get ${allRecommendedLayouts.size()} recommended layouts with duplicate layouts removed.")
+    jobContext.setRecommendAggLayouts(allRecommendedLayouts)
+  }
+
   protected def generateFlatTable(): Dataset[Row] = {
     val recoveredDS = tryRecoverFTDS()
     if (recoveredDS.nonEmpty) {
diff --git a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/MaterializedFactTableView.scala b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/MaterializedFactTableView.scala
index 584538f47d..f467058559 100644
--- a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/MaterializedFactTableView.scala
+++ b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/MaterializedFactTableView.scala
@@ -38,7 +38,7 @@ class MaterializedFactTableView(jobContext: SegmentJob, dataSegment: NDataSegmen
     val flatTableDesc: SegmentFlatTableDesc = if (jobContext.isPartialBuild) {
       val parser = new IndexDependencyParser(dataModel)
       val relatedTableAlias =
-        parser.getRelatedTablesAlias(jobContext.getReadOnlyLayouts)
+        parser.getRelatedTablesAlias(readOnlyLayouts)
       new SegmentFlatTableDesc(config, dataSegment, spanningTree, relatedTableAlias)
     } else {
       new SegmentFlatTableDesc(config, dataSegment, spanningTree)
diff --git a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/partition/PartitionMaterializedFactTableView.scala b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/partition/PartitionCostBasedPlanner.scala
similarity index 57%
copy from src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/partition/PartitionMaterializedFactTableView.scala
copy to src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/partition/PartitionCostBasedPlanner.scala
index 75063e3596..3aac410594 100644
--- a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/partition/PartitionMaterializedFactTableView.scala
+++ b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/partition/PartitionCostBasedPlanner.scala
@@ -18,6 +18,8 @@
 
 package org.apache.kylin.engine.spark.job.stage.build.partition
 
+import java.util.stream.Collectors
+
 import org.apache.kylin.engine.spark.job.SegmentJob
 import org.apache.kylin.engine.spark.job.stage.BuildParam
 import org.apache.kylin.engine.spark.model.PartitionFlatTableDesc
@@ -26,39 +28,31 @@ import org.apache.kylin.metadata.cube.cuboid.PartitionSpanningTree
 import org.apache.kylin.metadata.cube.cuboid.PartitionSpanningTree.PartitionTreeBuilder
 import org.apache.kylin.metadata.cube.model.NDataSegment
 import org.apache.kylin.metadata.job.JobBucket
-import org.apache.spark.sql.{Dataset, Row}
-
-import java.util.stream.Collectors
 
-class PartitionMaterializedFactTableView(jobContext: SegmentJob, dataSegment: NDataSegment, buildParam: BuildParam)
+class PartitionCostBasedPlanner(jobContext: SegmentJob, dataSegment: NDataSegment, buildParam: BuildParam)
   extends PartitionFlatTableAndDictBase(jobContext, dataSegment, buildParam) {
-
-
   override def execute(): Unit = {
-    logInfo(s"Build SEGMENT $segmentId")
-    val spanTree = new PartitionSpanningTree(config,
-      new PartitionTreeBuilder(dataSegment, readOnlyLayouts, jobId, partitions,
-        jobContext.getReadOnlyBuckets.stream.filter(_.getSegmentId.equals(segmentId)).collect(Collectors.toSet[JobBucket])))
-    buildParam.setPartitionSpanningTree(spanTree)
-
-    val tableDesc = if (jobContext.isPartialBuild) {
-      val parser = new IndexDependencyParser(dataModel)
-      val relatedTableAlias =
-        parser.getRelatedTablesAlias(jobContext.getReadOnlyLayouts)
-      new PartitionFlatTableDesc(config, dataSegment, spanTree, relatedTableAlias, jobId, partitions)
-    } else {
-      new PartitionFlatTableDesc(config, dataSegment, spanTree, jobId, partitions)
-    }
-    buildParam.setTableDesc(tableDesc)
-
-    val factTableDS: Dataset[Row] = newFactTableDS()
-    buildParam.setFactTableDS(factTableDS)
-
-    val fastFactTableDS: Dataset[Row] = newFastFactTableDS()
-    buildParam.setFastFactTableDS(fastFactTableDS)
-
-    if (buildParam.isSkipMaterializedFactTableView) {
-      onStageSkipped()
+    val (cost, sourceCount) = generateCostTable()
+    getRecommendedLayoutAndUpdateMetadata(cost, sourceCount)
+    //    jobContext.addMockIndex()
+    val result = jobContext.updateIndexPlanIfNeed()
+    if (result) {
+      // update span tree and table desc with the new build job layouts
+      val spanTree = new PartitionSpanningTree(config,
+        new PartitionTreeBuilder(dataSegment, readOnlyLayouts, jobId, partitions,
+          jobContext.getReadOnlyBuckets.stream.filter(_.getSegmentId.equals(segmentId)).collect(Collectors.toSet[JobBucket])))
+      buildParam.setPartitionSpanningTree(spanTree)
+
+      // update table desc with new span tree
+      val tableDesc = if (jobContext.isPartialBuild) {
+        val parser = new IndexDependencyParser(dataModel)
+        val relatedTableAlias =
+          parser.getRelatedTablesAlias(readOnlyLayouts)
+        new PartitionFlatTableDesc(config, dataSegment, spanTree, relatedTableAlias, jobId, partitions)
+      } else {
+        new PartitionFlatTableDesc(config, dataSegment, spanTree, jobId, partitions)
+      }
+      buildParam.setTableDesc(tableDesc)
     }
   }
 }
diff --git a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/partition/PartitionMaterializedFactTableView.scala b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/partition/PartitionMaterializedFactTableView.scala
index 75063e3596..e8f2fca99f 100644
--- a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/partition/PartitionMaterializedFactTableView.scala
+++ b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/job/stage/build/partition/PartitionMaterializedFactTableView.scala
@@ -44,7 +44,7 @@ class PartitionMaterializedFactTableView(jobContext: SegmentJob, dataSegment: ND
     val tableDesc = if (jobContext.isPartialBuild) {
       val parser = new IndexDependencyParser(dataModel)
       val relatedTableAlias =
-        parser.getRelatedTablesAlias(jobContext.getReadOnlyLayouts)
+        parser.getRelatedTablesAlias(readOnlyLayouts)
       new PartitionFlatTableDesc(config, dataSegment, spanTree, relatedTableAlias, jobId, partitions)
     } else {
       new PartitionFlatTableDesc(config, dataSegment, spanTree, jobId, partitions)
diff --git a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/model/SegmentFlatTableDesc.java b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/model/SegmentFlatTableDesc.java
index 0cb125fcb7..02900e3feb 100644
--- a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/model/SegmentFlatTableDesc.java
+++ b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/model/SegmentFlatTableDesc.java
@@ -138,6 +138,10 @@ public class SegmentFlatTableDesc {
         return config.getFlatTableDir(project, dataflowId, segmentId);
     }
 
+    public Path getPlannerCostTablePath() {
+        return config.getPlannerCostTableDir(project, dataflowId, segmentId);
+    }
+
     public Path getFactTableViewPath() {
         return config.getFactTableViewDir(project, dataflowId, segmentId);
     }
diff --git a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/model/planner/CuboIdToLayoutUtils.java b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/model/planner/CuboIdToLayoutUtils.java
new file mode 100644
index 0000000000..73b8d4bb4c
--- /dev/null
+++ b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/model/planner/CuboIdToLayoutUtils.java
@@ -0,0 +1,160 @@
+/*
+ * 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.engine.spark.model.planner;
+
+import java.math.BigInteger;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.kylin.metadata.cube.cuboid.NAggregationGroup;
+import org.apache.kylin.metadata.cube.model.LayoutEntity;
+import org.apache.kylin.metadata.cube.model.RuleBasedIndex;
+
+import com.google.common.collect.Lists;
+
+public class CuboIdToLayoutUtils {
+    /**
+     * convert the cuboids to layout entity
+     * @param cuboids
+     * @param ruleBasedIndex
+     * @return
+     */
+    public static Set<LayoutEntity> convertCuboIdsToLayoutEntity(Map<BigInteger, Long> cuboids,
+            RuleBasedIndex ruleBasedIndex) {
+        // convert the cuboid to each agg group
+        Set<LayoutEntity> result = new HashSet<>();
+        List<NAggregationGroup> aggregationGroups = ruleBasedIndex != null ? ruleBasedIndex.getAggregationGroups()
+                : Lists.newArrayList();
+        for (NAggregationGroup group : aggregationGroups) {
+            // dimension order in this agg group
+            List<Integer> dimensionOrder = Lists.newArrayList(group.getIncludes());
+            // measure order in this agg group
+            List<Integer> measuresIds = Lists.newArrayList(group.getMeasures());
+            Set<List<Integer>> colOrders = convertCuboIdsToColOrders(cuboids, ruleBasedIndex.countOfIncludeDimension(),
+                    measuresIds, ruleBasedIndex.getRowKeyIdToColumnId(), dimensionOrder);
+            for (List<Integer> colOrder : colOrders) {
+                result.add(createRecommendAggIndexLayout(colOrder));
+            }
+        }
+
+        // base agg layout for each agg group
+        for (NAggregationGroup group : aggregationGroups) {
+            List<Integer> colOrders = Lists.newArrayList();
+            // all dimension in the agg
+            colOrders.addAll(Lists.newArrayList(group.getIncludes()));
+            // all measure in this agg
+            colOrders.addAll(Lists.newArrayList(group.getMeasures()));
+            result.add(createRecommendAggIndexLayout(colOrders));
+        }
+        return result;
+    }
+
+    /**
+     * create recommend agg layout base on the colOrder.
+     * @param colOrder
+     * @return LayoutEntity or null
+     *  null: if the measures in the colOrder can't match the measures in this Index Plan
+     */
+    private static LayoutEntity createRecommendAggIndexLayout(List<Integer> colOrder) {
+        LayoutEntity newAddIndexLayout = new LayoutEntity();
+        // The layout is not the manual
+        newAddIndexLayout.setManual(false);
+        newAddIndexLayout.setColOrder(colOrder);
+        newAddIndexLayout.setUpdateTime(System.currentTimeMillis());
+        newAddIndexLayout.setBase(false);
+        newAddIndexLayout.initalId(true);
+        return newAddIndexLayout;
+    }
+
+    /**
+     * convert the cuboids to column order set which contain dimension ids and measure ids
+     * @param cuboids
+     * @param dimensionCount
+     * @param measuresIds
+     * @return
+     */
+    protected static Set<List<Integer>> convertCuboIdsToColOrders(Map<BigInteger, Long> cuboids, int dimensionCount,
+            List<Integer> measuresIds, Map<Integer, Integer> rowkeyIdToColumnId, List<Integer> sortOfDims) {
+        Set<List<Integer>> result = new HashSet<>();
+        for (BigInteger cuboid : cuboids.keySet()) {
+            // 1. get the dimension with order
+            // convert the cuboid to the order of dimension which is sorted by the order of `sortOfDims`
+            List<Integer> colOrder = convertLongToDimensionColOrder(cuboid, dimensionCount, rowkeyIdToColumnId,
+                    sortOfDims);
+            if (colOrder.isEmpty()) {
+                // If the cuboid can't match the `sortOfDims`, and will not get the column order for this layout
+                continue;
+            }
+            // 2. get the measure with order
+            // In the current cube planner, each layout should contains all of the measures in the model
+            colOrder.addAll(measuresIds);
+            result.add(colOrder);
+        }
+        return result;
+    }
+
+    /**
+     * convert the cuboid to the column order which just contains the dimension ids
+     *
+     * @param cuboid
+     * @param maxDimensionCount
+     * @return
+     */
+    public static List<Integer> convertLongToDimensionColOrder(BigInteger cuboid, int maxDimensionCount,
+            Map<Integer, Integer> rowkeyIdToColumnId, List<Integer> sortOfDims) {
+        // If cuboid is 00000000,00000000,00000000,10001001, and the max dimension count is 12
+        // It will be converted to [4,8,11]
+        List<Integer> colOrder = new ArrayList<>();
+        for (int rowkeyId = 0; rowkeyId < maxDimensionCount; rowkeyId++) {
+            int rightShift = maxDimensionCount - rowkeyId - 1;
+            boolean exist = cuboid.testBit(rightShift);
+            if (exist) {
+                if (!rowkeyIdToColumnId.containsKey(rowkeyId)) {
+                    throw new RuntimeException("Can't find the column id from the rowkey id");
+                }
+                int columnId = rowkeyIdToColumnId.get(rowkeyId);
+                if (sortOfDims.indexOf(columnId) < 0) {
+                    // can't find the dimension in the sorted dimension
+                    // this cuboid is not recommended from the rule base index
+                    // just skip and ignore it
+                    colOrder.clear();
+                    break;
+                }
+                colOrder.add(columnId);
+            }
+        }
+        if (!colOrder.isEmpty()) {
+            // sort the dimension by the sortOfDims
+            Collections.sort(colOrder, new Comparator<Integer>() {
+                @Override
+                public int compare(Integer o1, Integer o2) {
+                    int index1 = sortOfDims.indexOf(o1);
+                    int index2 = sortOfDims.indexOf(o2);
+                    return index1 - index2;
+                }
+            });
+        }
+        return colOrder;
+    }
+}
diff --git a/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/model/planner/FlatTableToCostUtils.java b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/model/planner/FlatTableToCostUtils.java
new file mode 100644
index 0000000000..e4a5bafa63
--- /dev/null
+++ b/src/spark-project/engine-spark/src/main/scala/org/apache/kylin/engine/spark/model/planner/FlatTableToCostUtils.java
@@ -0,0 +1,536 @@
+/*
+ * 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.engine.spark.model.planner;
+
+import java.io.IOException;
+import java.math.BigInteger;
+import java.nio.ByteBuffer;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.kylin.common.KylinConfig;
+import org.apache.kylin.common.util.ByteArray;
+import org.apache.kylin.common.util.Bytes;
+import org.apache.kylin.engine.spark.model.SegmentFlatTableDesc;
+import org.apache.kylin.measure.BufferedMeasureCodec;
+import org.apache.kylin.measure.hllc.HLLCounter;
+import org.apache.kylin.measure.hllc.RegisterType;
+import org.apache.kylin.metadata.cube.model.IndexPlan;
+import org.apache.kylin.metadata.cube.model.LayoutEntity;
+import org.apache.kylin.metadata.cube.model.RuleBasedIndex;
+import org.apache.kylin.metadata.cube.planner.CostBasePlannerUtils;
+import org.apache.kylin.metadata.datatype.DataType;
+import org.apache.kylin.metadata.model.FunctionDesc;
+import org.apache.kylin.metadata.model.MeasureDesc;
+import org.apache.kylin.metadata.model.NDataModel;
+import org.apache.kylin.metadata.model.TblColRef;
+import org.apache.spark.Partitioner;
+import org.apache.spark.api.java.JavaPairRDD;
+import org.apache.spark.api.java.JavaRDD;
+import org.apache.spark.api.java.function.Function;
+import org.apache.spark.api.java.function.Function2;
+import org.apache.spark.api.java.function.PairFlatMapFunction;
+import org.apache.spark.sql.Row;
+
+import com.google.common.collect.Lists;
+import com.google.common.collect.Maps;
+import com.google.common.hash.HashFunction;
+import com.google.common.hash.Hasher;
+import com.google.common.hash.Hashing;
+
+import lombok.extern.slf4j.Slf4j;
+import scala.Tuple2;
+
+@Slf4j
+public class FlatTableToCostUtils {
+
+    private static LayoutEntity createMockRuleBaseLayout(RuleBasedIndex ruleBasedIndex) {
+        // create a mock base layout which include all dimensions in the rule index without order
+        LayoutEntity baseLayouts = new LayoutEntity();
+        baseLayouts.setColOrder(ruleBasedIndex.getDimensions());
+        return baseLayouts;
+    }
+
+    public static Map<BigInteger, HLLCounter> generateCost(JavaRDD<Row> input, KylinConfig kylinConfig,
+            RuleBasedIndex ruleBasedIndex, SegmentFlatTableDesc flatTableDesc) throws IOException {
+        // step1: convert each cell to string data type, and get RDD[String[]]
+        JavaRDD<String[]> flatTableRDD = input.map(new Function<Row, String[]>() {
+            @Override
+            public String[] call(Row row) throws Exception {
+                String[] result = new String[row.length()];
+                for (int i = 0; i < row.length(); i++) {
+                    final Object o = row.get(i);
+                    if (o != null) {
+                        result[i] = o.toString();
+                    } else {
+                        result[i] = null;
+                    }
+                }
+                return result;
+            }
+        });
+        // step2: calculate the cost for each partition, and get the new RDD.
+        // The key is cuboid, and the value is the data encoded from the hll for each partition.
+        int rowKeyCount = ruleBasedIndex.countOfIncludeDimension();
+        // layouts from the rule index(agg group)
+        Set<LayoutEntity> inputLayouts = ruleBasedIndex.genCuboidLayouts();
+        // add the mock layout which include all of the dimensions in the rule index
+        inputLayouts.add(createMockRuleBaseLayout(ruleBasedIndex));
+        BigInteger[] inputCuboids = getCuboIdsFromLayouts(Lists.newArrayList(inputLayouts), rowKeyCount,
+                ruleBasedIndex.getColumnIdToRowKeyId());
+        // rowkey id ->  column index in the flat table of the flat dataset.
+        int[] rowkeyColumnIndexes = getRowkeyColumnIndexes(ruleBasedIndex, flatTableDesc);
+
+        int hllPrecision = kylinConfig.getStatsHLLPrecision();
+        log.info("The row key count is {}, and the index/column map is {}", rowKeyCount,
+                Lists.newArrayList(rowkeyColumnIndexes));
+        JavaPairRDD<BigInteger, byte[]> costRddByPartition = flatTableRDD.mapPartitionsToPair(
+                new FlatOutputFunction(hllPrecision, rowKeyCount, inputCuboids, rowkeyColumnIndexes));
+
+        // step3: reduce by cuboid, and merge hll data
+        // The key is the cuboid, the value is data encoded from the hll
+        int partitionNum = getCuboidHLLCounterReducerNum(inputCuboids.length, kylinConfig);
+        log.info("Get the partition count for the HLL reducer: {}", partitionNum);
+        JavaPairRDD<BigInteger, byte[]> costRDD = costRddByPartition.reduceByKey(new Partitioner() {
+            private int num = partitionNum;
+            private BigInteger bigIntegerMod = BigInteger.valueOf(num);
+
+            @Override
+            public int numPartitions() {
+                return num;
+            }
+
+            @Override
+            public int getPartition(Object key) {
+                // key is the biginteger
+                BigInteger value = (BigInteger) key;
+                return value.mod(bigIntegerMod).intValue();
+            }
+        }, new Function2<byte[], byte[], byte[]>() {
+            private int precision = hllPrecision;
+
+            @Override
+            public byte[] call(byte[] array1, byte[] array2) throws Exception {
+                // hll1
+                HLLCounter hll1 = new HLLCounter(precision);
+                ByteBuffer buffer1 = ByteBuffer.wrap(array1, 0, array1.length);
+                hll1.readRegisters(buffer1);
+                // hll2
+                HLLCounter hll2 = new HLLCounter(precision);
+                ByteBuffer buffer2 = ByteBuffer.wrap(array2, 0, array2.length);
+                hll2.readRegisters(buffer2);
+
+                // merge two hll
+                hll1.merge(hll2);
+                ByteBuffer hllBuf = ByteBuffer.allocate(BufferedMeasureCodec.DEFAULT_BUFFER_SIZE);
+                hll1.writeRegisters(hllBuf);
+                byte[] value = new byte[hllBuf.position()];
+                System.arraycopy(hllBuf.array(), 0, value, 0, hllBuf.position());
+                return value;
+            }
+        });
+        // step4: collect the final result, and convert value(text) to hll
+        // The key is the cuboid, and the value is the estimated statistics
+        Map<BigInteger, HLLCounter> resultCost = Maps.newHashMap();
+        for (Tuple2<BigInteger, byte[]> pair : costRDD.collect()) {
+            HLLCounter hll = new HLLCounter(kylinConfig.getStatsHLLPrecision());
+            // value
+            ByteArray byteArray = new ByteArray(pair._2);
+            hll.readRegisters(byteArray.asBuffer());
+            // put key and value
+            resultCost.put(pair._1, hll);
+        }
+        // log data
+        if (log.isDebugEnabled()) {
+            logMapperAndCuboidStatistics(resultCost, 100);
+        }
+        return resultCost;
+    }
+
+    /**
+     * @return reducer number for calculating hll
+     */
+    private static int getCuboidHLLCounterReducerNum(int nCuboids, KylinConfig kylinConfig) {
+        int shardBase = (nCuboids - 1) / kylinConfig.getJobPerReducerHLLCuboidNumber() + 1;
+        int hllMaxReducerNumber = kylinConfig.getJobHLLMaxReducerNumber();
+        if (shardBase > hllMaxReducerNumber) {
+            shardBase = hllMaxReducerNumber;
+        }
+        return Math.max(shardBase, 1);
+    }
+
+    private static BigInteger[] getCuboIdsFromLayouts(List<LayoutEntity> allLayouts, int dimensionCount,
+            Map<Integer, Integer> columnIdToRowkeyId) {
+        Set<BigInteger> set = new HashSet<>();
+        for (LayoutEntity layoutEntity : allLayouts) {
+            BigInteger cuboId = CostBasePlannerUtils.convertDimensionsToCuboId(layoutEntity.getDimsIds(),
+                    dimensionCount, columnIdToRowkeyId);
+            set.add(cuboId);
+        }
+        return set.toArray(new BigInteger[set.size()]);
+    }
+
+    private static int[] getRowkeyColumnIndexes(RuleBasedIndex ruleBasedIndex, SegmentFlatTableDesc flatTableDesc) {
+        int rowKeyCount = ruleBasedIndex.countOfIncludeDimension();
+        List<Integer> columnIds = flatTableDesc.getColumnIds();
+        int[] rowkeyColumnIndexes = new int[rowKeyCount];
+        Map<Integer, Integer> rowkeyIdToColumnId = ruleBasedIndex.getRowKeyIdToColumnId();
+        for (int rowkeyId = 0; rowkeyId < rowKeyCount; rowkeyId++) {
+            if (!rowkeyIdToColumnId.containsKey(rowkeyId)) {
+                throw new RuntimeException("Can't find the column id from the rowkey id");
+            }
+            int columnId = rowkeyIdToColumnId.get(rowkeyId);
+            int index = columnIds.indexOf(columnId);
+            if (index >= 0) {
+                // find the i-th dimension in the index-th column in the flat table or flat data set
+                rowkeyColumnIndexes[rowkeyId] = index;
+            } else {
+                // not find the column id
+                throw new RuntimeException(
+                        String.format("Can't find the column id %d, column ids %s", columnId, columnIds.toString()));
+            }
+        }
+        return rowkeyColumnIndexes;
+    }
+
+    private static class FlatOutputFunction implements PairFlatMapFunction<Iterator<String[]>, BigInteger, byte[]> {
+        private transient volatile boolean initialized = false;
+        private transient CuboidStatCalculator cuboidStatCalculator;
+        private final int samplingPercent = 100;
+        private final int hllPrecision;
+        private final int rowKeyCount;
+        private final BigInteger[] cuboidIds;
+        private final int[] rowkeyColumnIndexes;
+
+        public FlatOutputFunction(int hllPrecision, int rowKeyCount, BigInteger[] cuboidIds,
+                int[] rowkeyColumnIndexes) {
+            this.hllPrecision = hllPrecision;
+            this.rowKeyCount = rowKeyCount;
+            this.cuboidIds = cuboidIds;
+            this.rowkeyColumnIndexes = rowkeyColumnIndexes;
+        }
+
+        private Integer[][] getCuboidBitSet(BigInteger[] cuboidIds, int nRowKey) {
+            Integer[][] allCuboidsBitSet = new Integer[cuboidIds.length][];
+            for (int j = 0; j < cuboidIds.length; j++) {
+                BigInteger cuboidId = cuboidIds[j];
+
+                allCuboidsBitSet[j] = new Integer[cuboidId.bitCount()];
+                int position = 0;
+                for (int i = 0; i < nRowKey; i++) {
+                    BigInteger bigMask = BigInteger.ZERO.setBit(nRowKey - 1 - i);
+                    if ((bigMask.and(cuboidId).compareTo(BigInteger.ZERO)) > 0) {
+                        // bigMask & cuboid > 0
+                        allCuboidsBitSet[j][position] = i;
+                        position++;
+                    }
+                }
+            }
+            return allCuboidsBitSet;
+        }
+
+        private HLLCounter[] getInitCuboidsHLL(int cuboidSize, int hllPrecision) {
+            HLLCounter[] cuboidsHLL = new HLLCounter[cuboidSize];
+            for (int i = 0; i < cuboidSize; i++) {
+                cuboidsHLL[i] = new HLLCounter(hllPrecision, RegisterType.DENSE);
+            }
+            return cuboidsHLL;
+        }
+
+        private void init() {
+            Integer[][] cuboidsBitSet = getCuboidBitSet(cuboidIds, rowKeyCount);
+            HLLCounter[] cuboidsHLL = getInitCuboidsHLL(cuboidIds.length, hllPrecision);
+            cuboidStatCalculator = new CuboidStatCalculator(rowkeyColumnIndexes, cuboidIds, cuboidsBitSet, true,
+                    cuboidsHLL);
+            initialized = true;
+        }
+
+        @Override
+        public Iterator<Tuple2<BigInteger, byte[]>> call(Iterator<String[]> iterator) throws Exception {
+            if (initialized == false) {
+                // just sync this object
+                synchronized (this) {
+                    if (initialized == false) {
+                        init();
+                    }
+                }
+            }
+
+            // One tuple is a cost pair, the left is the cuboid and the right is the cost
+            int rowCount = 0;
+            while (iterator.hasNext()) {
+                String[] row = iterator.next();
+                if (rowCount % 100 < samplingPercent) {
+                    cuboidStatCalculator.putRow(row);
+                }
+                rowCount++;
+            }
+
+            List<Tuple2<BigInteger, byte[]>> result = Lists.newArrayList();
+            ByteBuffer hllBuf = ByteBuffer.allocate(BufferedMeasureCodec.DEFAULT_BUFFER_SIZE);
+            BigInteger[] cuboidIds = cuboidStatCalculator.getCuboidIds();
+            HLLCounter[] cuboidsHLL = cuboidStatCalculator.getHLLCounters();
+            HLLCounter hll;
+            for (int i = 0; i < cuboidIds.length; i++) {
+                // key
+                BigInteger outputKey = cuboidIds[i];
+                // value
+                hll = cuboidsHLL[i];
+                hllBuf.clear();
+                hll.writeRegisters(hllBuf);
+                byte[] value = new byte[hllBuf.position()];
+                System.arraycopy(hllBuf.array(), 0, value, 0, hllBuf.position());
+                result.add(new Tuple2<BigInteger, byte[]>(outputKey, value));
+            }
+            return result.iterator();
+        }
+    }
+
+    static class CuboidStatCalculator {
+        private final int nRowKey;
+        private final int[] rowkeyColIndex;
+        private final BigInteger[] cuboidIds;
+        private final Integer[][] cuboidsBitSet;
+        private HLLCounter[] cuboidsHLL;
+
+        //about details of the new algorithm, please see KYLIN-2518
+        private final boolean isNewAlgorithm;
+        private final HashFunction hf;
+        private long[] rowHashCodesLong;
+
+        public CuboidStatCalculator(int[] rowkeyColIndex, BigInteger[] cuboidIds, Integer[][] cuboidsBitSet,
+                boolean isUsePutRowKeyToHllNewAlgorithm, HLLCounter[] cuboidsHLL) {
+            this.nRowKey = rowkeyColIndex.length;
+            this.rowkeyColIndex = rowkeyColIndex;
+            this.cuboidIds = cuboidIds;
+            this.cuboidsBitSet = cuboidsBitSet;
+            this.isNewAlgorithm = isUsePutRowKeyToHllNewAlgorithm;
+            if (!isNewAlgorithm) {
+                this.hf = Hashing.murmur3_32();
+            } else {
+                rowHashCodesLong = new long[nRowKey];
+                this.hf = Hashing.murmur3_128();
+            }
+            this.cuboidsHLL = cuboidsHLL;
+        }
+
+        public void putRow(final String[] row) {
+            String[] copyRow = Arrays.copyOf(row, row.length);
+
+            if (isNewAlgorithm) {
+                putRowKeyToHLLNew(copyRow);
+            } else {
+                putRowKeyToHLLOld(copyRow);
+            }
+        }
+
+        private void putRowKeyToHLLOld(String[] row) {
+            //generate hash for each row key column
+            byte[][] rowHashCodes = new byte[nRowKey][];
+            for (int i = 0; i < nRowKey; i++) {
+                Hasher hc = hf.newHasher();
+                String colValue = row[rowkeyColIndex[i]];
+                if (colValue != null) {
+                    rowHashCodes[i] = hc.putString(colValue).hash().asBytes();
+                } else {
+                    rowHashCodes[i] = hc.putInt(0).hash().asBytes();
+                }
+            }
+
+            // user the row key column hash to get a consolidated hash for each cuboid
+            for (int i = 0, n = cuboidsBitSet.length; i < n; i++) {
+                Hasher hc = hf.newHasher();
+                for (int position = 0; position < cuboidsBitSet[i].length; position++) {
+                    hc.putBytes(rowHashCodes[cuboidsBitSet[i][position]]);
+                }
+
+                cuboidsHLL[i].add(hc.hash().asBytes());
+            }
+        }
+
+        private void putRowKeyToHLLNew(String[] row) {
+            //generate hash for each row key column
+            for (int i = 0; i < nRowKey; i++) {
+                Hasher hc = hf.newHasher();
+                String colValue = row[rowkeyColIndex[i]];
+                if (colValue == null)
+                    colValue = "0";
+                byte[] bytes = hc.putString(colValue).hash().asBytes();
+                //add column ordinal to the hash value to distinguish between (a,b) and (b,a)
+                rowHashCodesLong[i] = (Bytes.toLong(bytes) + i);
+            }
+
+            // user the row key column hash to get a consolidated hash for each cuboid
+            for (int i = 0, n = cuboidsBitSet.length; i < n; i++) {
+                long value = 0;
+                for (int position = 0; position < cuboidsBitSet[i].length; position++) {
+                    value += rowHashCodesLong[cuboidsBitSet[i][position]];
+                }
+                cuboidsHLL[i].addHashDirectly(value);
+            }
+        }
+
+        public HLLCounter[] getHLLCounters() {
+            return cuboidsHLL;
+        }
+
+        public BigInteger[] getCuboidIds() {
+            return cuboidIds;
+        }
+    }
+
+    private static void logMapperAndCuboidStatistics(Map<BigInteger, HLLCounter> cuboidHLLMap, int samplingPercentage) {
+        log.debug("Total cuboid number: \t" + cuboidHLLMap.size());
+        log.debug("Sampling percentage: \t" + samplingPercentage);
+        log.debug("The following statistics are collected based on sampling data.");
+
+        List<BigInteger> allCuboids = Lists.newArrayList(cuboidHLLMap.keySet());
+        Collections.sort(allCuboids);
+        for (BigInteger i : allCuboids) {
+            log.debug("Cuboid " + i + " row count is: \t " + cuboidHLLMap.get(i).getCountEstimate());
+        }
+    }
+
+    public static Map<BigInteger, Long> getCuboidRowCountMapFromSampling(Map<BigInteger, HLLCounter> hllcMap) {
+        Map<BigInteger, Long> cuboidRowCountMap = Maps.newHashMap();
+        for (Map.Entry<BigInteger, HLLCounter> entry : hllcMap.entrySet()) {
+            // No need to adjust according sampling percentage. Assumption is that data set is far
+            // more than cardinality. Even a percentage of the data should already see all cardinalities.
+            cuboidRowCountMap.put(entry.getKey(), entry.getValue().getCountEstimate());
+        }
+        return cuboidRowCountMap;
+    }
+
+    private static Map<BigInteger, Double> getCuboidSizeMapFromSamplingByCount(Map<BigInteger, Long> rowCountMap,
+            long sourceCount, RuleBasedIndex ruleBasedIndex, KylinConfig kylinConfig,
+            SegmentFlatTableDesc segmentFlatTableDesc) {
+        // use the row count to replace the size
+        Map<BigInteger, Double> cuboidSizeMap = Maps.newHashMap();
+        for (Map.Entry<BigInteger, Long> entry : rowCountMap.entrySet()) {
+            double value = entry.getValue();
+            cuboidSizeMap.put(entry.getKey(), value);
+        }
+        return cuboidSizeMap;
+    }
+
+    public static Map<BigInteger, Double> getCuboidSizeMapFromSampling(Map<BigInteger, Long> rowCountMap,
+            long sourceCount, RuleBasedIndex ruleBasedIndex, KylinConfig kylinConfig,
+            SegmentFlatTableDesc segmentFlatTableDesc) {
+        // replace the size with the row count
+        return getCuboidSizeMapFromSamplingByCount(rowCountMap, sourceCount, ruleBasedIndex, kylinConfig,
+                segmentFlatTableDesc);
+        //        final List<Integer> rowkeyColumnSize = getRowkeyColumnSize(indexPlan, segmentFlatTableDesc);
+        //        // base id and base size
+        //        final long baseCuboid = CostBasePlannerUtils.generateBaseCuboId(indexPlan);
+        //        Preconditions.checkNotNull(rowCountMap.get(baseCuboid));
+        //        final Long baseCuboIDRowCount = rowCountMap.get(baseCuboid);
+        //
+        //        Map<Long, Double> cuboidSizeMap = Maps.newHashMap();
+        //        for (Map.Entry<Long, Long> entry : rowCountMap.entrySet()) {
+        //            cuboidSizeMap.put(entry.getKey(),
+        //                    estimateCuboidStorageSize(indexPlan.getEffectiveMeasures().values(), entry.getKey(),
+        //                            entry.getValue(), baseCuboid, baseCuboIDRowCount, rowkeyColumnSize, sourceCount,
+        //                            kylinConfig));
+        //        }
+        //        if (kylinConfig.enableJobCuboidSizeOptimize()) {
+        //            optimizeSizeMap(cuboidSizeMap);
+        //        }
+        //        return cuboidSizeMap;
+    }
+
+    private static List<Integer> getRowkeyColumnSize(IndexPlan indexPlan, SegmentFlatTableDesc flatTableDesc) {
+        int rowKeyCount = indexPlan.getRuleBasedIndex().countOfIncludeDimension();
+        List<Integer> columnIds = flatTableDesc.getColumnIds();
+        List<TblColRef> tblColRefs = flatTableDesc.getColumns();
+        List<Integer> rowkeyColumnSize = Lists.newArrayList();
+
+        for (int i = 0; i < rowKeyCount; i++) {
+            int index = columnIds.indexOf(i);
+            if (index >= 0) {
+                // find the i-th dimension in the index-th column in the flat table or flat data set.
+                TblColRef tblColRef = tblColRefs.get(index);
+                // get DimensionEncoding for this table column ref.
+                // TODO: how estimate dimension size (string type)
+                // Noe we just use the row count as the weight
+                int length = 0;
+                rowkeyColumnSize.add(length);
+            } else {
+                // not find the column id
+                throw new RuntimeException(
+                        String.format("Can't find the column id %d, column ids %s", i, columnIds.toString()));
+            }
+        }
+        // the index means column id for the dimension, the value is the estimated size for this dimension
+        return rowkeyColumnSize;
+    }
+
+    private static double estimateCuboidStorageSize(Set<NDataModel.Measure> measureDescs, long cuboidId, long rowCount,
+            long baseCuboidId, long baseCuboidCount, List<Integer> rowKeyColumnLength, long sourceRowCount,
+            KylinConfig kylinConfig) {
+        // row key header
+        int rowkeyLength = 8; // 8 or 10
+        long mask = Long.highestOneBit(baseCuboidId);
+        // actual: the parentCuboidIdActualLength is rowkey count
+        long parentCuboidIdActualLength = (long) Long.SIZE - Long.numberOfLeadingZeros(baseCuboidId);
+        // dimension length
+        for (int i = 0; i < parentCuboidIdActualLength; i++) {
+            if ((mask & cuboidId) > 0) {
+                rowkeyLength += rowKeyColumnLength.get(i); //colIO.getColumnLength(columnList.get(i));
+            }
+            mask = mask >> 1;
+        }
+        // measure size
+        int normalSpace = rowkeyLength;
+        int countDistinctSpace = 0;
+        double percentileSpace = 0;
+        int topNSpace = 0;
+        for (MeasureDesc measureDesc : measureDescs) {
+            if (rowCount == 0)
+                break;
+            DataType returnType = measureDesc.getFunction().getReturnDataType();
+            if (measureDesc.getFunction().getExpression().equals(FunctionDesc.FUNC_COUNT_DISTINCT)) {
+                long estimateDistinctCount = sourceRowCount / rowCount;
+                estimateDistinctCount = estimateDistinctCount == 0 ? 1L : estimateDistinctCount;
+                countDistinctSpace += returnType.getStorageBytesEstimate(estimateDistinctCount);
+            } else if (measureDesc.getFunction().getExpression().equals(FunctionDesc.FUNC_PERCENTILE)) {
+                percentileSpace += returnType.getStorageBytesEstimate(baseCuboidCount * 1.0 / rowCount);
+            } else if (measureDesc.getFunction().getExpression().equals(FunctionDesc.FUNC_TOP_N)) {
+                long estimateTopNCount = sourceRowCount / rowCount;
+                estimateTopNCount = estimateTopNCount == 0 ? 1L : estimateTopNCount;
+                topNSpace += returnType.getStorageBytesEstimate(estimateTopNCount);
+            } else {
+                normalSpace += returnType.getStorageBytesEstimate();
+            }
+        }
+
+        double cuboidSizeRatio = kylinConfig.getJobCuboidSizeRatio();
+        double cuboidSizeMemHungryRatio = kylinConfig.getJobCuboidSizeCountDistinctRatio();
+        double cuboidSizeTopNRatio = kylinConfig.getJobCuboidSizeTopNRatio();
+
+        double ret = (1.0 * normalSpace * rowCount * cuboidSizeRatio
+                + 1.0 * countDistinctSpace * rowCount * cuboidSizeMemHungryRatio + 1.0 * percentileSpace * rowCount
+                + 1.0 * topNSpace * rowCount * cuboidSizeTopNRatio) / (1024L * 1024L);
+        return ret;
+    }
+}
diff --git a/src/spark-project/engine-spark/src/test/java/org/apache/kylin/engine/spark/model/planner/CuboIdToLayoutUtilsTest.java b/src/spark-project/engine-spark/src/test/java/org/apache/kylin/engine/spark/model/planner/CuboIdToLayoutUtilsTest.java
new file mode 100644
index 0000000000..57194050ae
--- /dev/null
+++ b/src/spark-project/engine-spark/src/test/java/org/apache/kylin/engine/spark/model/planner/CuboIdToLayoutUtilsTest.java
@@ -0,0 +1,215 @@
+/*
+ * 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.engine.spark.model.planner;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.math.BigInteger;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Random;
+import java.util.Set;
+
+import org.apache.kylin.metadata.cube.planner.CostBasePlannerUtils;
+import org.junit.Test;
+
+import com.google.common.collect.Lists;
+
+public class CuboIdToLayoutUtilsTest {
+
+    private Map<Integer, Integer> getMap(int dimensionCount) {
+        Map<Integer, Integer> result = new HashMap<>();
+        for (int i = 0; i < dimensionCount; i++) {
+            result.put(i, i);
+        }
+        return result;
+    }
+
+    private List<Integer> getSortList(int dimensionCount) {
+        List<Integer> result = new ArrayList<>();
+        for (int i = 0; i < dimensionCount; i++) {
+            result.add(i);
+        }
+        return result;
+    }
+
+    @Test
+    public void testConvertCuboIdsToColOrders() {
+        int maxCountDimension = 12;
+        Map<Long, Long> cuboids = new HashMap<>();
+        Map<BigInteger, Long> bigIntegerCuboIds = new HashMap<>();
+        long cuboid = 1 << 0 | 1 << 3 | 1 << 7;
+        cuboids.put(cuboid, (long) 0);
+        bigIntegerCuboIds.put(BigInteger.valueOf(cuboid), (long) 0);
+        cuboid = 1 << 4 | 1 << 10 | 1 << 5;
+        cuboids.put(cuboid, (long) 0);
+        bigIntegerCuboIds.put(BigInteger.valueOf(cuboid), (long) 0);
+        List<Integer> measureIds = new ArrayList<>();
+        measureIds.add(1001);
+        measureIds.add(1002);
+        measureIds.add(1003);
+
+        Set<List<Integer>> result = CuboIdToLayoutUtils.convertCuboIdsToColOrders(bigIntegerCuboIds, maxCountDimension,
+                measureIds, getMap(maxCountDimension), getSortList(maxCountDimension));
+        Set<List<Integer>> expected = new LinkedHashSet<>();
+        expected.add(Lists.newArrayList(11 - 7, 11 - 3, 11 - 0, 1001, 1002, 1003));
+        expected.add(Lists.newArrayList(11 - 10, 11 - 5, 11 - 4, 1001, 1002, 1003));
+        assertEquals(expected, result);
+    }
+
+    @Test
+    public void testConvertCuboIdsToColOrdersWithReverseOrder() {
+        int maxCountDimension = 12;
+        Map<BigInteger, Long> cuboids = new HashMap<>();
+        long cuboid = 1 << 0 | 1 << 3 | 1 << 7;
+        BigInteger bigIntegerCuboId = BigInteger.valueOf(cuboid);
+        cuboids.put(bigIntegerCuboId, (long) 0);
+        cuboid = 1 << 4 | 1 << 10 | 1 << 5;
+        bigIntegerCuboId = BigInteger.valueOf(cuboid);
+        cuboids.put(bigIntegerCuboId, (long) 0);
+        List<Integer> measureIds = new ArrayList<>();
+        measureIds.add(1001);
+        measureIds.add(1002);
+        measureIds.add(1003);
+        List<Integer> sortOrder = getSortList(maxCountDimension);
+        Collections.reverse(sortOrder);
+        Set<List<Integer>> result = CuboIdToLayoutUtils.convertCuboIdsToColOrders(cuboids, maxCountDimension,
+                measureIds, getMap(maxCountDimension), sortOrder);
+        Set<List<Integer>> expected = new LinkedHashSet<>();
+        expected.add(Lists.newArrayList(11 - 0, 11 - 3, 11 - 7, 1001, 1002, 1003));
+        expected.add(Lists.newArrayList(11 - 4, 11 - 5, 11 - 10, 1001, 1002, 1003));
+        assertEquals(expected, result);
+    }
+
+    @Test
+    public void testConvertCuboIdsToColOrdersWithEmptyOrder() {
+        int maxCountDimension = 12;
+        Map<BigInteger, Long> cuboids = new HashMap<>();
+        long cuboid = 1 << 0 | 1 << 3 | 1 << 7;
+        BigInteger bigIntegerCuboId = BigInteger.valueOf(cuboid);
+        cuboids.put(bigIntegerCuboId, (long) 0);
+        cuboid = 1 << 4 | 1 << 10 | 1 << 5;
+        bigIntegerCuboId = BigInteger.valueOf(cuboid);
+        cuboids.put(bigIntegerCuboId, (long) 0);
+        List<Integer> measureIds = new ArrayList<>();
+        measureIds.add(1001);
+        measureIds.add(1002);
+        measureIds.add(1003);
+        List<Integer> sortOrder = getSortList(maxCountDimension - 8);
+        Collections.reverse(sortOrder);
+        Set<List<Integer>> result = CuboIdToLayoutUtils.convertCuboIdsToColOrders(cuboids, maxCountDimension,
+                measureIds, getMap(maxCountDimension), sortOrder);
+        Set<List<Integer>> expected = new LinkedHashSet<>();
+        assertEquals(expected, result);
+    }
+
+    @Test
+    public void testConvertCuboIdsToColOrdersWithMultiOrder() {
+        int maxCountDimension = 12;
+        Map<BigInteger, Long> cuboids = new HashMap<>();
+        long cuboid = 1 << 0 | 1 << 3 | 1 << 7;
+        BigInteger bigIntegerCuboId = BigInteger.valueOf(cuboid);
+        cuboids.put(bigIntegerCuboId, (long) 0);
+        cuboid = 1 << 4 | 1 << 10 | 1 << 5;
+        bigIntegerCuboId = BigInteger.valueOf(cuboid);
+        cuboids.put(bigIntegerCuboId, (long) 0);
+        List<Integer> measureIds = new ArrayList<>();
+        measureIds.add(1001);
+        measureIds.add(1002);
+        measureIds.add(1003);
+        List<Integer> sortOrder = getSortList(maxCountDimension);
+        // order1: 0,1,2,3,4,5,6,7,8,9,10,11
+        Set<List<Integer>> result = CuboIdToLayoutUtils.convertCuboIdsToColOrders(cuboids, maxCountDimension,
+                measureIds, getMap(maxCountDimension), sortOrder);
+        Set<List<Integer>> expected = new LinkedHashSet<>();
+        expected.add(Lists.newArrayList(11 - 7, 11 - 3, 11 - 0, 1001, 1002, 1003)); // 4,8,11
+        expected.add(Lists.newArrayList(11 - 10, 11 - 5, 11 - 4, 1001, 1002, 1003)); // 1,6,7
+        // order2: 11,10,9,8,7,6,5,4,3,2,1,0
+        Collections.reverse(sortOrder);
+        result.addAll(CuboIdToLayoutUtils.convertCuboIdsToColOrders(cuboids, maxCountDimension, measureIds,
+                getMap(maxCountDimension), sortOrder));
+        expected.add(Lists.newArrayList(11 - 0, 11 - 3, 11 - 7, 1001, 1002, 1003)); // 11,8,4
+        expected.add(Lists.newArrayList(11 - 4, 11 - 5, 11 - 10, 1001, 1002, 1003)); // 7,6,1
+        assertEquals(expected, result);
+    }
+
+    @Test
+    public void randomTestForDimensionWithCuboid() {
+        int maxCountDimension = 63;
+        Random random = new Random();
+        for (int i = 0; i < 100; i++) {
+            long cuboId = random.nextLong();
+            if (cuboId < 0) {
+                cuboId = Math.abs(cuboId);
+            }
+            BigInteger bigIntegerCuboId = BigInteger.valueOf(cuboId);
+            List<Integer> dimensionIds = CuboIdToLayoutUtils.convertLongToDimensionColOrder(bigIntegerCuboId,
+                    maxCountDimension, getMap(maxCountDimension), getSortList(maxCountDimension));
+            BigInteger expected = CostBasePlannerUtils.convertDimensionsToCuboId(dimensionIds, maxCountDimension,
+                    getMap(maxCountDimension));
+            assertEquals(expected, BigInteger.valueOf(cuboId));
+        }
+    }
+
+    @Test
+    public void testConvertLongToOrder() {
+        // max id = 11
+        int maxCountDimension = 12;
+        long cuboid = 1 << 0 | 1 << 3 | 1 << 7;
+        BigInteger bigIntegerCuboId = BigInteger.valueOf(cuboid);
+        List<Integer> result = CuboIdToLayoutUtils.convertLongToDimensionColOrder(bigIntegerCuboId, maxCountDimension,
+                getMap(maxCountDimension), getSortList(maxCountDimension));
+        List<Integer> expected = Lists.newArrayList(11 - 7, 11 - 3, 11 - 0);
+        assertEquals(expected, result);
+
+        cuboid = 1 << 4 | 1 << 10 | 1 << 5;
+        bigIntegerCuboId = BigInteger.valueOf(cuboid);
+        result = CuboIdToLayoutUtils.convertLongToDimensionColOrder(bigIntegerCuboId, maxCountDimension,
+                getMap(maxCountDimension), getSortList(maxCountDimension));
+        expected = Lists.newArrayList(11 - 10, 11 - 5, 11 - 4);
+        assertEquals(expected, result);
+    }
+
+    @Test
+    public void testMore64DimensionCase() {
+        int maxCountDimension = 100;
+        BigInteger cuboid = BigInteger.ZERO;
+        cuboid = cuboid.setBit(0);
+        cuboid = cuboid.setBit(3);
+        cuboid = cuboid.setBit(7);
+        cuboid = cuboid.setBit(77);
+        List<Integer> result = CuboIdToLayoutUtils.convertLongToDimensionColOrder(cuboid, maxCountDimension,
+                getMap(maxCountDimension), getSortList(maxCountDimension));
+        List<Integer> expected = Lists.newArrayList(99 - 77, 99 - 7, 99 - 3, 99 - 0);
+        assertEquals(expected, result);
+
+        cuboid = BigInteger.ZERO;
+        cuboid = cuboid.setBit(4);
+        cuboid = cuboid.setBit(10);
+        cuboid = cuboid.setBit(5);
+        cuboid = cuboid.setBit(88);
+        result = CuboIdToLayoutUtils.convertLongToDimensionColOrder(cuboid, maxCountDimension,
+                getMap(maxCountDimension), getSortList(maxCountDimension));
+        expected = Lists.newArrayList(99 - 88, 99 - 10, 99 - 5, 99 - 4);
+        assertEquals(expected, result);
+    }
+}
\ No newline at end of file