>From Preetham Poluparthi <[email protected]>:
Preetham Poluparthi has uploaded this change for review. (
https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21388?usp=email )
Change subject: WIP: Improve cbo cost functions
......................................................................
WIP: Improve cbo cost functions
Change-Id: I2d131cd430775a0e7dbf10e7491f0fa2e0f5ed3c
---
A
asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/CBCost.java
A
asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/CBCostMethods.java
2 files changed, 601 insertions(+), 0 deletions(-)
git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb
refs/changes/88/21388/1
diff --git
a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/CBCost.java
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/CBCost.java
new file mode 100644
index 0000000..858b71d
--- /dev/null
+++
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/CBCost.java
@@ -0,0 +1,85 @@
+/*
+ * Copyright 2016-2022 Couchbase, Inc.
+ */
+
+package org.apache.asterix.optimizer.cost;
+
+public class CBCost extends Cost {
+
+ private static final int SEQ_IO_WEIGHT = 1;
+ private static final int RAND_IO_WEIGHT = 0;
+ // not using random costs any more because index access happens after
sorts. May consider removing this component in V2
+
+ private final double docsProcessed;
+ private final double docsProduced;
+ private final double docsSent;
+ private final double overFlow;
+ private final double ioSeq;
+ private final double ioRand;
+
+ public CBCost() {
+ this(0, 0, 0, 0, 0, 0);
+ }
+
+ public CBCost(double docsProcessed, double docsProduced, double docsSent,
double overFlow, double ioSeq,
+ double ioRand) {
+ this.docsProcessed = docsProcessed;
+ this.docsProduced = docsProduced;
+ this.docsSent = docsSent;
+ this.overFlow = overFlow;
+ this.ioSeq = ioSeq;
+ this.ioRand = ioRand;
+ }
+
+ @Override
+ public ICost zeroCost() {
+ return new CBCost();
+ }
+
+ @Override
+ public ICost maxCost() {
+ return new CBCost(MAX_CARD, MAX_CARD, MAX_CARD, MAX_CARD, 0, 0);
+ }
+
+ @Override
+ public ICost costAdd(ICost cost) {
+ CBCost cbCost = (CBCost) cost;
+ return new CBCost(docsProcessed + cbCost.docsProcessed, docsProduced +
cbCost.docsProduced,
+ docsSent + cbCost.docsSent, overFlow + cbCost.overFlow, ioSeq
+ cbCost.ioSeq, ioRand + cbCost.ioRand);
+ }
+
+ @Override
+ public double computeTotalCost() {
+ return docsProcessed + docsProduced + docsSent + overFlow + ioSeq *
SEQ_IO_WEIGHT + ioRand * RAND_IO_WEIGHT;
+ }
+
+ public double getDocsProcessed() {
+ return docsProcessed;
+ }
+
+ public double getDocsProduced() {
+ return docsProduced;
+ }
+
+ public double getDocsSent() {
+ return docsSent;
+ }
+
+ public double getOverFlow() {
+ return overFlow;
+ }
+
+ public double getIoSeq() {
+ return ioSeq;
+ }
+
+ public double getIoRand() {
+ return ioRand;
+ }
+
+ @Override
+ public String toString() {
+ return "{docsProcessed = " + docsProcessed + ", docsProduced = " +
docsProduced + ", docsSent = " + docsSent
+ + ", overFlow = " + overFlow + ", ioSeq = " + ioSeq + ",
ioRand = " + ioRand + '}';
+ }
+}
diff --git
a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/CBCostMethods.java
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/CBCostMethods.java
new file mode 100644
index 0000000..192f106
--- /dev/null
+++
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/CBCostMethods.java
@@ -0,0 +1,516 @@
+/*
+ * Copyright 2016-2022 Couchbase, Inc.
+ */
+
+package org.apache.asterix.optimizer.cost;
+
+import org.apache.asterix.metadata.entities.Index;
+import org.apache.asterix.optimizer.rules.cbo.AbstractPlanNode;
+import org.apache.asterix.optimizer.rules.cbo.JoinNode;
+import org.apache.asterix.optimizer.rules.cbo.JoinPlanNode;
+import org.apache.asterix.optimizer.rules.cbo.ScanPlanNode;
+import org.apache.hyracks.algebricks.common.utils.Pair;
+import org.apache.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import
org.apache.hyracks.algebricks.core.algebra.operators.logical.DistinctOperator;
+import
org.apache.hyracks.algebricks.core.algebra.operators.logical.GroupByOperator;
+import
org.apache.hyracks.algebricks.core.algebra.operators.logical.OrderOperator;
+
+public class CBCostMethods extends CostMethods {
+
+ public CBCostMethods(IOptimizationContext context) {
+ super(context);
+ }
+
+ @Override
+ public CBCost costFullScan(JoinNode jn) {
+ int limit = jn.getLimitVal();
+ double factor = 1.0;
+ double inputCard = jn.getOrigCardinality();
+ double outputCard = jn.getCardinality();
+ double documentSize = jn.getAvgDocSize(); //the entire row will come
out
+ double inputSize = jn.getInputSize(); // This is the size coming out
of the disk
+ if (!jn.getColumnar()) {
+ inputSize = documentSize;
+ }
+ double outputSize = jn.getOutputSize(); // this is what leaves after
the scan; only join and result vars are included here
+
+ if (limit > 0 && limit < outputCard) { // for single tables only
+ factor = limit / outputCard;
+ outputCard = limit;
+ }
+ double docsProcessed = factor * inputCard / DOP *
docSizeFactor(inputSize);
+ double docsProduced = outputCard / DOP * docSizeFactor(outputSize);
+
+ // Since we do not have exchanges at the logical plan level, docsSent
for the exchange above the
+ // scan will be computed by the logical operator above the scan which
will determine the properties
+ // of the exchange operator above the scan in the final physical plan.
+ double docsSent = 0;
+ double ioSeq = factor * inputCard / DOP * inputSize / blockSize;
+ double ioRand = 0;
+
+ return new CBCost(docsProcessed, docsProduced, docsSent, 0, ioSeq,
ioRand);
+ }
+
+ @Override
+ public CBCost costIndexScan(JoinNode jn, double indexSel) {
+ int limit = jn.getLimitVal();
+ double inputCard = jn.getOrigCardinality();
+ double outputCard = jn.getCardinality();
+ double inputSize = jn.getInputSize(); // original size of the dataset
+ double outputSize = jn.getOutputSize();
+
+ if (limit > 0 && limit < outputCard) {
+ indexSel = limit / inputCard;
+ }
+
+ double docsProcessed = inputCard * indexSel / DOP *
docSizeFactor(outputSize);
+ double docsProduced = inputCard * indexSel / DOP *
docSizeFactor(outputSize);
+ double docsSent = 0;
+ //double ioSeq = outputCard / DOP * outputSize / blockSize;
+ double ioSeq = inputCard * indexSel / DOP * outputSize / blockSize;
+ double ioRand = 0;
+ return new CBCost(docsProcessed, docsProduced, docsSent, 0, ioSeq,
ioRand);
+ }
+
+ public CBCost costIndexDataScan(JoinNode jn, double indexSel) {
+ int limit = jn.getLimitVal(); // stored earlier
+ double inputCard = jn.getOrigCardinality();
+ double outputCard = jn.getCardinality();
+ double inputSize = jn.getInputSize(); // original size of the dataset
+ double outputSize = jn.getOutputSize();
+
+ if (limit > 0 && limit < outputCard) {
+ indexSel = limit / inputCard;
+ }
+
+ // Duplicates RIDs will be removed by the distinct operator in case of
array indexes.
+ // We account for that with the unnestFactor, which is 1.0 for regular
indexes.
+ double docsProcessed = inputCard * indexSel / DOP /
jn.getUnnestFactor() * docSizeFactor(outputSize);
+ double docsProduced = inputCard * indexSel / DOP *
docSizeFactor(outputSize);
+ double docsSent = 0;
+
+ // Since we do not have exchanges at the logical plan level, docsSent
for the exchange above the
+ // scan will be computed by the logical operator above the scan which
will determine the properties
+ // of the exchange operator above the scan in the final physical plan.
+ double ioSeq = 0;
+ double ioRand = 0;
+
+ // Need to sort the RIDs before the data access. This happens in the
sort operator
+ // between the index scan and the data scan operator, so we cost it
here.
+ docsProcessed += costSort(docsProcessed, inputSize);
+
+ return new CBCost(docsProcessed, docsProduced, docsSent, 0, ioSeq,
ioRand);
+ }
+
+ @Override
+ public CBCost costHashJoin(JoinNode jn) {
+ JoinNode leftJn = jn.getLeftJn();
+ JoinNode rightJn = jn.getRightJn();
+
+ double probeCard = leftJn.getCardinality();
+ double probeSize = leftJn.getOutputSize();
+ double buildCard = rightJn.getCardinality();
+ double buildSize = rightJn.getOutputSize();
+ double joinCard = jn.getCardinality();
+ double joinSize = jn.getOutputSize();
+
+ double probeCardPerPartition = probeCard / DOP;
+ double buildCardPerPartition = buildCard / DOP;
+ double joinCardPerPartition = joinCard / DOP;
+
+ double probeSizeFactor = docSizeFactor(probeSize);
+ double buildSizeFactor = docSizeFactor(buildSize);
+ double joinSizeFactor = docSizeFactor(joinSize);
+
+ // Regular (not broadcast) hash join.
+ double docsProcessed = probeCardPerPartition * probeSizeFactor +
buildCardPerPartition * buildSizeFactor;
+
+ double overFlowCost =
+ computeHashJoinOverflowCost(probeCardPerPartition, probeSize,
buildCardPerPartition, buildSize);
+
+ double docsProduced = joinCardPerPartition * joinSizeFactor;
+
+ // Since we do not have exchanges at the logical plan level, docsSent
for the exchange above the
+ // join will be computed by the logical operator above the join which
will determine the properties
+ // of the exchange operator above the join in the final physical plan.
+ double docsSent = 0;
+
+ return new CBCost(docsProcessed, docsProduced, docsSent, overFlowCost,
0, 0);
+ }
+
+ // This will be used later in the final physical plan to assign costs to
the exchange and
+ // subtract it from the cost assigned to the hash join.
+ @Override
+ public CBCost computeHJProbeExchangeCost(JoinNode jn) {
+ JoinNode leftJn = jn.getLeftJn();
+ double probeCard = leftJn.getCardinality();
+ double probeSize = leftJn.getOutputSize();
+ double probeCardPerPartition = probeCard / DOP;
+ double probeSizeFactor = docSizeFactor(probeSize);
+ boolean probePartitioned = false;
+ double docsSent = 0;
+ if (!probePartitioned) {
+ docsSent += probeCardPerPartition * probeSizeFactor;
+ }
+ return new CBCost(0, 0, docsSent, 0, 0, 0);
+ }
+
+ // This will be used later in the final physical plan to assign costs to
the exchange and
+ // subtract it from the cost assigned to the hash join.
+ @Override
+ public CBCost computeHJBuildExchangeCost(JoinNode jn) {
+ JoinNode rightJn = jn.getRightJn();
+ double buildCard = rightJn.getCardinality();
+ double buildSize = rightJn.getOutputSize();
+ double buildCardPerPartition = buildCard / DOP;
+ double buildSizeFactor = docSizeFactor(buildSize);
+ boolean buildPartitioned = false;
+ double docsSent = 0;
+ if (!buildPartitioned) {
+ docsSent += buildCardPerPartition * buildSizeFactor;
+ }
+ return new CBCost(0, 0, docsSent, 0, 0, 0);
+ }
+
+ @Override
+ public CBCost costBroadcastHashJoin(JoinNode jn) {
+ JoinNode leftJn = jn.getLeftJn();
+ JoinNode rightJn = jn.getRightJn();
+
+ double probeCard = leftJn.getCardinality();
+ double probeSize = leftJn.getOutputSize();
+ double buildCard = rightJn.getCardinality();
+ double buildSize = rightJn.getOutputSize();
+ double joinCard = jn.getCardinality();
+ double joinSize = jn.getOutputSize();
+
+ double probeCardPerPartition = probeCard / DOP;
+ double buildCardPerPartition = buildCard; // The build side is
broadcast
+ double joinCardPerPartition = joinCard / DOP;
+
+ double probeSizeFactor = docSizeFactor(probeSize);
+ double buildSizeFactor = docSizeFactor(buildSize);
+ double joinSizeFactor = docSizeFactor(joinSize);
+
+ // Broadcast hash join.
+ double docsProcessed = probeCardPerPartition * probeSizeFactor +
buildCardPerPartition * buildSizeFactor;
+ double overFlowCost =
+ computeHashJoinOverflowCost(probeCardPerPartition, probeSize,
buildCardPerPartition, buildSize);
+
+ double docsProduced = joinCardPerPartition * joinSizeFactor;
+ // Since we do not have exchanges at the logical plan level, docsSent
for the exchange above the
+ // join will be computed by the logical operator above the join which
will determine the properties
+ // of the exchange operator above the join in the final physical plan.
+ double docsSent = 0;
+
+ return new CBCost(docsProcessed, docsProduced, docsSent, overFlowCost,
0, 0);
+ }
+
+ // This will be used later in the final physical plan to assign costs to
the exchange and
+ // subtract it from the cost assigned to the broadcast hash join.
+ @Override
+ public CBCost computeBHJBuildExchangeCost(JoinNode jn) {
+ JoinNode rightJn = jn.getRightJn();
+ double buildCard = rightJn.getCardinality();
+ double buildSize = rightJn.getOutputSize();
+ double buildCardPerPartition = buildCard;
+ double buildSizeFactor = docSizeFactor(buildSize);
+ double docsSent = buildCardPerPartition * buildSizeFactor;
+ return new CBCost(0, 0, docsSent, 0, 0, 0);
+ }
+
+ // This routine is the weakest. May need to revisit this multiple times.
+ @Override
+ public CBCost costIndexNLJoin(JoinNode jn, Index index) {
+ JoinNode leftJn = jn.getLeftJn();
+ JoinNode rightJn = jn.getRightJn();
+
+ double outerCard = leftJn.getCardinality();
+ double outerSize = leftJn.getOutputSize();
+ double innerCard = rightJn.getCardinality();
+ double innerSize = rightJn.getOutputSize();
+ double joinCard = jn.getCardinality();
+ double joinSize = jn.getOutputSize();
+
+ double outerCardPerPartition = outerCard; // outer side is broadcast
to all nodes
+ double innerCardPerPartition = innerCard / DOP;
+ double joinCardPerPartition = joinCard / DOP;
+
+ double outerSizeFactor = docSizeFactor(outerSize);
+ double innerSizeFactor = docSizeFactor(innerSize);
+ double joinSizeFactor = docSizeFactor(joinSize);
+
+ double origRightCard = rightJn.getOrigCardinality();
+ double tuplesTobeSortedPerInstance = joinCardPerPartition *
origRightCard / innerCard;
+ // innerCard/origRightCard is the selectivity for the right side.
+
+ // The probes from the outer side are processed by the nested join
+ // and sent down to the inner side. The result join tuples flow back
+ // up to the nested join.
+
+ double docsProcessed = outerCardPerPartition * outerSizeFactor;
+
+ double docsProduced = joinCardPerPartition * joinSizeFactor;
+
+ // Since we do not have exchanges at the logical plan level, docsSent
for the exchange above the
+ // join will be computed by the logical operator above the join which
will determine the properties
+ // of the exchange operator above the join in the final physical plan.
+ double docsSent = 0;
+ double ioSeq = joinCardPerPartition * innerSize / blockSize;
+ if (!index.isPrimaryIndex()) {
+ docsProcessed += costSort(tuplesTobeSortedPerInstance, joinSize);
+ docsProcessed += 5 * outerCardPerPartition * outerSizeFactor; //
empirical evidence
+ }
+ // we will assume that the outerCard is always sorted.
+ // This need not be the same if the outercard is already sorted. But
hard to tell this at the LO level.
+ if (outerCard > 1 && outerSideIsNotSorted(jn)) {
+ docsProcessed += costSort(4 * outerCard, outerSize); // had to
increase this cost by 4x from empirical evidence
+ }
+
+ return new CBCost(docsProcessed, docsProduced, docsSent, 0, ioSeq, 0);
+ }
+
+ private boolean outerSideIsNotSorted(JoinNode jn) {
+
+ JoinNode leftJn = jn.getLeftJn();
+ AbstractPlanNode pn = leftJn.getCheapestPlanNode();
+ if (pn instanceof JoinPlanNode) {
+ return true; // we cant tell here if the outer side is sorted or
not.
+ }
+ Index index = ((ScanPlanNode) pn).getSoleAccessIndex();
+
+ if (index == null) {
+ return true;
+ }
+
+ if (index.isPrimaryIndex()) {
+ return false;
+ }
+
+ return true;
+ }
+
+ // This will be used later in the final physical plan to assign costs to
the exchange and
+ // subtract it from the cost assigned to the index NL join.
+ @Override
+ public CBCost computeNLJOuterExchangeCost(JoinNode jn) {
+ JoinNode leftJn = jn.getLeftJn();
+ double outerCard = leftJn.getCardinality();
+ double outerSize = leftJn.getOutputSize();
+ double outerCardPerPartition = outerCard;
+ double outerSizeFactor = docSizeFactor(outerSize);
+ double docsSent = outerCardPerPartition * outerSizeFactor;
+ return new CBCost(0, 0, docsSent, 0, 0, 0);
+ }
+
+ @Override
+ public CBCost costCartesianProductJoin(JoinNode jn) {
+ JoinNode leftJn = jn.getLeftJn();
+ JoinNode rightJn = jn.getRightJn();
+
+ double leftCard = leftJn.getCardinality();
+ double leftSize = leftJn.getOutputSize();
+ double rightCard = rightJn.getCardinality();
+ double rightSize = rightJn.getOutputSize();
+ double joinCard = jn.getCardinality();
+ double joinSize = jn.getOutputSize();
+
+ double leftCardPerPartition = leftCard / DOP;
+ double rightCardPerPartition = rightCard; // the right side is
broadcast
+ double joinCardPerPartition = joinCard / DOP;
+
+ double leftSizeFactor = docSizeFactor(leftSize);
+ double rightSizeFactor = docSizeFactor(rightSize);
+ double joinSizeFactor = docSizeFactor(joinSize);
+
+ double docsProcessed = Math.max(leftCardPerPartition, Cost.MIN_CARD) *
leftSizeFactor
+ * Math.max(rightCardPerPartition, Cost.MIN_CARD) *
rightSizeFactor;
+ double docsProduced = joinCardPerPartition * joinSizeFactor;
+ // Since we do not have exchanges at the logical plan level, docsSent
for the exchange above the
+ // join will be computed by the logical operator above the join which
will determine the properties
+ // of the exchange operator above the join in the final physical plan.
+ double docsSent = 0;
+
+ return new CBCost(docsProcessed, docsProduced, docsSent, 0, 0, 0);
+ }
+
+ // This will be used later in the final physical plan to assign costs to
the exchange and
+ // subtract it from the cost assigned to the cartesian product join.
+ @Override
+ public CBCost computeCPRightExchangeCost(JoinNode jn) {
+ return computeBHJBuildExchangeCost(jn);
+ }
+
+ public CBCost costHashGroupBy(GroupByOperator groupByOperator) {
+ double inputCard, inputCardPerPartition;
+ double outputCard, outputCardPerPartition;
+ double inputSize = 1.0; // for now
+ double outputSize = 1.0; // for now
+
+ Pair<Double, Double> cards = getOpCards(groupByOperator);
+ inputCard = cards.getFirst();
+ outputCard = cards.getSecond();
+
+ if (groupByOperator.isGlobal()) {
+ inputCardPerPartition = outputCard * DOP;
+ } else {
+ inputCardPerPartition = inputCard / DOP;
+ }
+ outputCardPerPartition = outputCard;
+
+ double docsProcessed = inputCardPerPartition *
docSizeFactor(inputSize);
+ double docsProduced = outputCardPerPartition *
docSizeFactor(outputSize);
+ double docsSent = 0.0;
+ double overFlowCost =
+ computeHashGroupByOverflowCost(inputCardPerPartition,
inputSize, outputCardPerPartition, outputSize);
+
+ return new CBCost(docsProcessed, docsProduced, docsSent, overFlowCost,
0, 0);
+ }
+
+ public CBCost costSortGroupBy(GroupByOperator groupByOperator) {
+ double inputCard, inputCardPerPartition;
+ double outputCard, outputCardPerPartition;
+ double inputSize = 1.0; // for now
+ double outputSize = 1.0; // for now
+
+ Pair<Double, Double> cards = getOpCards(groupByOperator);
+ inputCard = cards.getFirst();
+ outputCard = cards.getSecond();
+
+ if (groupByOperator.isGlobal()) {
+ inputCardPerPartition = outputCard * DOP;
+ } else {
+ inputCardPerPartition = inputCard / DOP;
+ }
+ outputCardPerPartition = outputCard;
+
+ double docsProcessed = inputCardPerPartition *
docSizeFactor(inputSize);
+ docsProcessed += costSort(inputCardPerPartition, inputSize);
+ double docsProduced = outputCardPerPartition *
docSizeFactor(outputSize);
+ double docsSent = 0.0;
+ double overFlowCost = computeSortOverflowCost(inputCardPerPartition,
inputSize);
+
+ return new CBCost(docsProcessed, docsProduced, docsSent, overFlowCost,
0, 0);
+ }
+
+ public CBCost costDistinct(DistinctOperator distinctOp) {
+ double inputCard, inputCardPerPartition;
+ double outputCard, outputCardPerPartition;
+ double inputSize = 1.0; // for now
+ double outputSize = 1.0; // for now
+
+ Pair<Double, Double> cards = getOpCards(distinctOp);
+ inputCard = cards.getFirst();
+ outputCard = cards.getSecond();
+
+ inputCardPerPartition = inputCard / DOP;
+ outputCardPerPartition = outputCard / DOP;
+
+ double docsProcessed = inputCardPerPartition *
docSizeFactor(inputSize);
+ docsProcessed += costSort(inputCardPerPartition, inputSize);
+ double docsProduced = outputCardPerPartition *
docSizeFactor(outputSize);
+ double docsSent = 0.0;
+ double overFlowCost = computeSortOverflowCost(inputCardPerPartition,
inputSize);
+
+ return new CBCost(docsProcessed, docsProduced, docsSent, overFlowCost,
0, 0);
+ }
+
+ public CBCost costOrderBy(OrderOperator orderOp) {
+ double inputCard, inputCardPerPartition;
+ double outputCard, outputCardPerPartition;
+ double inputSize = 1.0; // for now
+ double outputSize = 1.0; // for now
+
+ Pair<Double, Double> cards = getOpCards(orderOp);
+ inputCard = cards.getFirst();
+ outputCard = cards.getSecond();
+
+ inputCardPerPartition = inputCard / DOP;
+ outputCardPerPartition = outputCard / DOP;
+
+ double docsProcessed = inputCardPerPartition *
docSizeFactor(inputSize);
+ docsProcessed += costSort(inputCardPerPartition, inputSize);
+ double docsProduced = outputCardPerPartition *
docSizeFactor(outputSize);
+ double docsSent = 0.0;
+ double overFlowCost = computeSortOverflowCost(inputCardPerPartition,
inputSize);
+
+ return new CBCost(docsProcessed, docsProduced, docsSent, overFlowCost,
0, 0);
+ }
+
+ private double docSizeFactor(double size) {
+ return 1.0;
+ //return Math.sqrt(size);
+ }
+
+ private double computeHashJoinOverflowCost(double probeCard, double
probeSize, double buildCard, double buildSize) {
+ double memoryUsed = buildCard * buildSize;
+ double probeSizeFactor = docSizeFactor(probeSize);
+ double buildSizeFactor = docSizeFactor(buildSize);
+
+ if (memoryUsed <= maxMemorySizeForJoin) {
+ return 0;
+ }
+
+ // memoryUsed > maxMemorySize
+ double fractionOverflow = 1.0 - maxMemorySizeForJoin / memoryUsed;
+
+ // The factor of 2 comes from having to write overflow tuples to disk
and
+ // read back the overflow tuples from disk.
+ double buildOverFlow = 2.0 * fractionOverflow * buildCard *
buildSizeFactor;
+
+ // The factor of 2 comes from having to write overflow tuples to disk
and
+ // read back the overflow tuples from disk.
+ double probeOverFlow = 2.0 * fractionOverflow * probeCard *
probeSizeFactor;
+
+ return (buildOverFlow + probeOverFlow);
+ }
+
+ private double computeHashGroupByOverflowCost(double inputCard, double
inputSize, double outputCard,
+ double outputSize) {
+ double memoryUsed = outputCard * outputSize;
+ double inputSizeFactor = docSizeFactor(inputSize);
+
+ if (memoryUsed <= maxMemorySizeForGroup) {
+ return 0;
+ }
+
+ // memoryUsed > maxMemorySize
+ double fractionOverflow = 1.0 - maxMemorySizeForGroup / memoryUsed;
+
+ // The factor of 2 comes from having to write overflow tuples to disk
and
+ // read back the overflow tuples from disk.
+ double overFlow = 2.0 * fractionOverflow * inputCard * inputSizeFactor;
+
+ return overFlow;
+ }
+
+ private double computeSortOverflowCost(double inputCard, double inputSize)
{
+ double memoryUsed = inputCard * inputSize;
+ double inputSizeFactor = docSizeFactor(inputSize);
+
+ if (memoryUsed <= maxMemorySizeForSort) {
+ return 0;
+ }
+
+ // memoryUsed > maxMemorySize
+ double fractionOverflow = 1.0 - maxMemorySizeForSort / memoryUsed;
+
+ // The factor of 2 comes from having to write overflow tuples to disk
and
+ // read back the overflow tuples from disk.
+ double overFlow = 2.0 * fractionOverflow * inputCard * inputSizeFactor;
+
+ return overFlow;
+ }
+
+ public double costSort(double inputCard, double inputSize) {
+ double docsProcessed = 0;
+ if (inputCard > 1) {
+ docsProcessed = inputCard * Math.log(inputCard) / Math.log(2); //
log to the base 2
+ // want to avoid -ve costs as log can return -ve values.
+ docsProcessed = Math.max(docsProcessed, 0);
+ }
+ docsProcessed *= docSizeFactor(inputSize);
+
+ return docsProcessed;
+ }
+}
--
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21388?usp=email
To unsubscribe, or for help writing mail filters, visit
https://asterix-gerrit.ics.uci.edu/settings?usp=email
Gerrit-MessageType: newchange
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Change-Id: I2d131cd430775a0e7dbf10e7491f0fa2e0f5ed3c
Gerrit-Change-Number: 21388
Gerrit-PatchSet: 1
Gerrit-Owner: Preetham Poluparthi <[email protected]>
