Mailing-List: contact reviews-help@spark.apache.org; run by ezmlm
Precedence: bulk
From: gatorsmile <git@git.apache.org>
To: reviews@spark.apache.org
Reply-To: reviews@spark.apache.org
References: <git-pr-17415-spark@git.apache.org>
In-Reply-To: <git-pr-17415-spark@git.apache.org>
Subject: [GitHub] spark pull request #17415: [SPARK-19408][SQL] filter estimation on two colum...
Content-Type: text/plain
Message-Id: <20170331074041.7AF79DFF7C@git1-us-west.apache.org>
Date: Fri, 31 Mar 2017 07:40:41 +0000 (UTC)
archived-at: Fri, 31 Mar 2017 07:40:45 -0000

Github user gatorsmile commented on a diff in the pull request:

    https://github.com/apache/spark/pull/17415#discussion_r109104396
  
    --- Diff: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/statsEstimation/FilterEstimation.scala ---
    @@ -550,6 +565,140 @@ case class FilterEstimation(plan: Filter, catalystConf: CatalystConf) extends Lo
         Some(percent.toDouble)
       }
     
    +  /**
    +   * Returns a percentage of rows meeting a binary comparison expression containing two columns.
    +   * In SQL queries, we also see predicate expressions involving two columns
    +   * such as "column-1 (op) column-2" where column-1 and column-2 belong to same table.
    +   * Note that, if column-1 and column-2 belong to different tables, then it is a join
    +   * operator's work, NOT a filter operator's work.
    +   *
    +   * @param op a binary comparison operator such as =, <, <=, >, >=
    +   * @param attrLeft the left Attribute (or a column)
    +   * @param attrRight the right Attribute (or a column)
    +   * @param update a boolean flag to specify if we need to update ColumnStat of the given columns
    +   *               for subsequent conditions
    +   * @return an optional double value to show the percentage of rows meeting a given condition
    +   */
    +  def evaluateBinaryForTwoColumns(
    +      op: BinaryComparison,
    +      attrLeft: Attribute,
    +      attrRight: Attribute,
    +      update: Boolean): Option[Double] = {
    +
    +    if (!colStatsMap.contains(attrLeft)) {
    +      logDebug("[CBO] No statistics for " + attrLeft)
    +      return None
    +    }
    +    if (!colStatsMap.contains(attrRight)) {
    +      logDebug("[CBO] No statistics for " + attrRight)
    +      return None
    +    }
    +
    +    attrLeft.dataType match {
    +      case StringType | BinaryType =>
    +        // TODO: It is difficult to support other binary comparisons for String/Binary
    +        // type without min/max and advanced statistics like histogram.
    +        logDebug("[CBO] No range comparison statistics for String/Binary type " + attrLeft)
    +        return None
    +      case _ =>
    +    }
    +
    +    val colStatLeft = colStatsMap(attrLeft)
    +    val statsRangeLeft = Range(colStatLeft.min, colStatLeft.max, attrLeft.dataType)
    +      .asInstanceOf[NumericRange]
    +    val maxLeft = BigDecimal(statsRangeLeft.max)
    +    val minLeft = BigDecimal(statsRangeLeft.min)
    +    val ndvLeft = BigDecimal(colStatLeft.distinctCount)
    +
    +    val colStatRight = colStatsMap(attrRight)
    +    val statsRangeRight = Range(colStatRight.min, colStatRight.max, attrRight.dataType)
    +      .asInstanceOf[NumericRange]
    +    val maxRight = BigDecimal(statsRangeRight.max)
    +    val minRight = BigDecimal(statsRangeRight.min)
    +    val ndvRight = BigDecimal(colStatRight.distinctCount)
    +
    +    // determine the overlapping degree between predicate range and column's range
    +    val (noOverlap: Boolean, completeOverlap: Boolean) = op match {
    +      case _: LessThan =>
    +        (minLeft >= maxRight, maxLeft < minRight)
    +      case _: LessThanOrEqual =>
    +        (minLeft > maxRight, maxLeft <= minRight)
    +      case _: GreaterThan =>
    +        (maxLeft <= minRight, minLeft > maxRight)
    +      case _: GreaterThanOrEqual =>
    +        (maxLeft < minRight, minLeft >= maxRight)
    +      case _: EqualTo =>
    +        ((maxLeft < minRight) || (maxRight < minLeft),
    +          (minLeft == minRight) && (maxLeft == maxRight))
    +      case _: EqualNullSafe =>
    +        // For null-safe equality, we use a very restrictive condition to evaluate its overlap.
    +        // If null values exists, we set it to partial overlap.
    +        (((maxLeft < minRight) || (maxRight < minLeft))
    +            && colStatLeft.nullCount == 0 && colStatRight.nullCount == 0,
    +          ((minLeft == minRight) && (maxLeft == maxRight))
    +            && colStatLeft.nullCount == 0 && colStatRight.nullCount == 0
    +        )
    +    }
    +
    +    var percent = BigDecimal(1.0)
    +    if (noOverlap) {
    +      percent = 0.0
    +    } else if (completeOverlap) {
    +      percent = 1.0
    +    } else {
    +      // For partial overlap, we use an empirical value 1/3 as suggested by the book
    +      // "Database Systems, the complete book".
    +      percent = 1.0/3.0
    +
    +      if (update) {
    +        // Need to adjust new min/max after the filter condition is applied
    +
    +        val ndvLeft = BigDecimal(colStatLeft.distinctCount)
    +        var newNdvLeft = (ndvLeft * percent).setScale(0, RoundingMode.HALF_UP).toBigInt()
    +        if (newNdvLeft < 1) newNdvLeft = 1
    +        val ndvRight = BigDecimal(colStatLeft.distinctCount)
    +        var newNdvRight = (ndvRight * percent).setScale(0, RoundingMode.HALF_UP).toBigInt()
    +        if (newNdvRight < 1) newNdvRight = 1
    +
    +        var newMaxLeft = colStatLeft.max
    +        var newMinLeft = colStatLeft.min
    +        var newMaxRight = colStatRight.max
    +        var newMinRight = colStatRight.min
    +
    +        op match {
    +          case _: LessThan | _: LessThanOrEqual =>
    +            // the left side should be less than the right side.
    +            // If not, we need to adjust it to narrow the range.
    +            if (minLeft > minRight) newMinRight = colStatLeft.min
    +            if (maxLeft > maxRight) newMaxLeft = colStatRight.max
    +
    +          case _: GreaterThan | _: GreaterThanOrEqual =>
    +            // the left side should be greater than the right side.
    +            // If not, we need to adjust it to narrow the range.
    +            if (minLeft < minRight) newMinLeft = colStatRight.min
    +            if (maxLeft < maxRight) newMaxRight = colStatLeft.max
    +
    +          case _: EqualTo | _: EqualNullSafe =>
    +            // need to set new min to the larger min value, and
    +            // set the new max to the smaller max value.
    --- End diff --
    
    ```
                // Left = Right or Left <=> Right
                //      minLeft     <      minRight
                // 0 ------+******************+------->
                //              filtered      ^
                //                            |
                //                        newMinLeft
                //
                //      minRight    <=     minLeft
                // 0 ------+******************+------->
                //              filtered      ^
                //                            |
                //                        newMinRight
                //
                //      maxLeft     <      maxRight
                // 0 ------+******************+------->
                //         ^    filtered
                //         |
                //     newMaxRight
                //
                //      maxRight    <=     maxLeft
                // 0 ------+******************+------->
                //         ^    filtered
                //         |
                //     newMaxLeft
    ```


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---

---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org