Github user wzhfy commented on a diff in the pull request:
https://github.com/apache/spark/pull/19783#discussion_r153979575
--- Diff:
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/statsEstimation/EstimationUtils.scala
---
@@ -114,4 +114,197 @@ object EstimationUtils {
}
}
+ /**
+ * Returns the number of the first bin into which a column values falls
for a specified
+ * numeric equi-height histogram.
+ *
+ * @param value a literal value of a column
+ * @param histogram a numeric equi-height histogram
+ * @return the number of the first bin into which a column values falls.
+ */
+
+ def findFirstBinForValue(value: Double, histogram: Histogram): Int = {
+ var binId = 0
+ histogram.bins.foreach { bin =>
+ if (value > bin.hi) binId += 1
+ }
+ binId
+ }
+
+ /**
+ * Returns the number of the last bin into which a column values falls
for a specified
+ * numeric equi-height histogram.
+ *
+ * @param value a literal value of a column
+ * @param histogram a numeric equi-height histogram
+ * @return the number of the last bin into which a column values falls.
+ */
+
+ def findLastBinForValue(value: Double, histogram: Histogram): Int = {
+ var binId = 0
+ for (i <- 0 until histogram.bins.length) {
+ if (value > histogram.bins(i).hi) {
+ // increment binId to point to next bin
+ binId += 1
+ }
+ if ((value == histogram.bins(i).hi) && (i < histogram.bins.length -
1)) {
+ if (value == histogram.bins(i + 1).lo) {
+ // increment binId since the value appears into this bin and
next bin
+ binId += 1
+ }
+ }
+ }
+ binId
+ }
+
+ /**
+ * Returns a percentage of a bin holding values for column value in the
range of
+ * [lowerValue, higherValue]
+ *
+ * @param binId a given bin id in a specified histogram
+ * @param higherValue a given upper bound value of a specified column
value range
+ * @param lowerValue a given lower bound value of a specified column
value range
+ * @param histogram a numeric equi-height histogram
+ * @return the percentage of a single bin holding values in [lowerValue,
higherValue].
+ */
+
+ private def getOccupation(
+ binId: Int,
+ higherValue: Double,
+ lowerValue: Double,
+ histogram: Histogram): Double = {
+ val curBin = histogram.bins(binId)
+ if (binId == 0 && curBin.hi == curBin.lo) {
+ // the Min of the histogram occupies the whole first bin
+ 1.0
+ } else if (binId == 0 && curBin.hi != curBin.lo) {
+ if (higherValue == lowerValue) {
+ // in the case curBin.binNdv == 0, current bin is occupied by one
value, which
+ // is included in the previous bin
+ 1.0 / math.max(curBin.ndv.toDouble, 1)
+ } else {
+ (higherValue - lowerValue) / (curBin.hi - curBin.lo)
+ }
+ } else {
+ if (curBin.hi == curBin.lo) {
+ // the entire bin is covered in the range
+ 1.0
+ } else if (higherValue == lowerValue) {
+ // the literal value falls in this bin
+ 1.0 / math.max(curBin.ndv.toDouble, 1)
+ } else {
+ // Use proration since the range falls inside this bin.
+ math.min((higherValue - lowerValue) / (curBin.hi - curBin.lo), 1.0)
+ }
+ }
+ }
+
+ /**
+ * Returns the number of bins for column values in [lowerValue,
higherValue].
+ * The column value distribution is saved in an equi-height histogram.
+ *
+ * @param higherEnd a given upper bound value of a specified column
value range
+ * @param lowerEnd a given lower bound value of a specified column value
range
+ * @param histogram a numeric equi-height histogram
+ * @return the selectivity percentage for column values in [lowerValue,
higherValue].
+ */
+
+ def getOccupationBins(
+ higherEnd: Double,
+ lowerEnd: Double,
+ histogram: Histogram): Double = {
+ // find bins where current min and max locate
+ val minBinId = findFirstBinForValue(lowerEnd, histogram)
+ val maxBinId = findLastBinForValue(higherEnd, histogram)
+ assert(minBinId <= maxBinId)
+
+ // compute how much current [min, max] occupy the histogram, in the
number of bins
+ getOccupationBins(maxBinId, minBinId, higherEnd, lowerEnd, histogram)
+ }
+
+ /**
+ * Returns the number of bins for column values in [lowerValue,
higherValue].
+ * This is an overloaded method. The column value distribution is saved
in an
+ * equi-height histogram.
+ *
+ * @param higherId id of the high end bin holding the high end value of
a column range
+ * @param lowerId id of the low end bin holding the low end value of a
column range
+ * @param higherEnd a given upper bound value of a specified column
value range
+ * @param lowerEnd a given lower bound value of a specified column value
range
+ * @param histogram a numeric equi-height histogram
+ * @return the selectivity percentage for column values in [lowerEnd,
higherEnd].
+ */
+
+ def getOccupationBins(
+ higherId: Int,
+ lowerId: Int,
+ higherEnd: Double,
+ lowerEnd: Double,
+ histogram: Histogram): Double = {
+ if (lowerId == higherId) {
+ getOccupation(lowerId, higherEnd, lowerEnd, histogram)
+ } else {
+ // compute how much lowerEnd/higherEnd occupy its bin
+ val lowercurBin = histogram.bins(lowerId)
+ val lowerPart = getOccupation(lowerId, lowercurBin.hi, lowerEnd,
histogram)
+
+ // in case higherId > lowerId, higherId must be > 0
+ val highercurBin = histogram.bins(higherId)
+ val higherPart = getOccupation(higherId, higherEnd, highercurBin.lo,
+ histogram)
+ // the total length is lowerPart + higherPart + bins between them
+ higherId - lowerId - 1 + lowerPart + higherPart
+ }
+ }
+
+ /**
+ * Returns the number of distinct values, ndv, for column values in
[lowerEnd, higherEnd].
+ * The column value distribution is saved in an equi-height histogram.
+ *
+ * @param higherId id of the high end bin holding the high end value of
a column range
+ * @param lowerId id of the low end bin holding the low end value of a
column range
+ * @param higherEnd a given upper bound value of a specified column
value range
+ * @param lowerEnd a given lower bound value of a specified column value
range
+ * @param histogram a numeric equi-height histogram
+ * @return the number of distinct values, ndv, for column values in
[lowerEnd, higherEnd].
+ */
+
+ def getOccupationNdv(
+ higherId: Int,
+ lowerId: Int,
+ higherEnd: Double,
+ lowerEnd: Double,
+ histogram: Histogram)
+ : Long = {
+ val ndv: Double = if (higherEnd == lowerEnd) {
+ 1
+ } else if (lowerId == higherId) {
+ getOccupation(lowerId, higherEnd, lowerEnd, histogram) *
histogram.bins(lowerId).ndv
+ } else {
+ // compute how much lowerEnd/higherEnd occupy its bin
--- End diff --
typo: occupies its bin
---
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
