Github user cloud-fan commented on a diff in the pull request: https://github.com/apache/spark/pull/19783#discussion_r154848428 --- Diff: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/statsEstimation/EstimationUtils.scala --- @@ -114,4 +114,194 @@ 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 bins an array of bins for a given numeric equi-height histogram + * @return the number of the first bin into which a column values falls. + */ + def findFirstBinForValue(value: Double, bins: Array[HistogramBin]): Int = { + var binId = 0 + 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 bins an array of bins for a given numeric equi-height histogram + * @return the number of the last bin into which a column values falls. + */ + def findLastBinForValue(value: Double, bins: Array[HistogramBin]): Int = { + var binId = 0 + for (i <- bins.indices) { + if (value > bins(i).hi) { + // increment binId to point to next bin + binId += 1 + } + if ((value == bins(i).hi) && (i < bins.length - 1) && (value == bins(i + 1).lo)) { + // We assume the above 3 conditions will be evaluated from left to right sequentially. + // If the above 3 conditions are evaluated out-of-order, then out-of-bound error may happen. + // At that time, we should split the third condition into another if statement. + // increment binId since the value appears in 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) { + // set percentage to 1/NDV + 1.0 / curBin.ndv.toDouble + } else { + // Use proration since the range falls inside this bin. + (higherValue - lowerValue) / (curBin.hi - curBin.lo) --- End diff -- this is the only branch we need to specialize for `binId=0`.
--- --------------------------------------------------------------------- To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org For additional commands, e-mail: reviews-h...@spark.apache.org