{"action":"created","comment":{"url":"https://api.github.com/repos/apache/spark/pulls/comments/154850738","pull_request_review_id":81074213,"id":154850738,"diff_hunk":"@@ -114,4 +114,194 @@ object EstimationUtils {\n     }\n   }\n \n+  /**\n+   * Returns the number of the first bin into which a column values falls for a specified\n+   * numeric equi-height histogram.\n+   *\n+   * @param value a literal value of a column\n+   * @param bins an array of bins for a given numeric equi-height histogram\n+   * @return the number of the first bin into which a column values falls.\n+   */\n+  def findFirstBinForValue(value: Double, bins: Array[HistogramBin]): Int = {\n+    var binId = 0\n+    bins.foreach { bin =>\n+      if (value > bin.hi) binId += 1\n+    }\n+    binId\n+  }\n+\n+  /**\n+   * Returns the number of the last bin into which a column values falls for a specified\n+   * numeric equi-height histogram.\n+   *\n+   * @param value a literal value of a column\n+   * @param bins an array of bins for a given numeric equi-height histogram\n+   * @return the number of the last bin into which a column values falls.\n+   */\n+  def findLastBinForValue(value: Double, bins: Array[HistogramBin]): Int = {\n+    var binId = 0\n+    for (i <- bins.indices) {\n+      if (value > bins(i).hi) {\n+        // increment binId to point to next bin\n+        binId += 1\n+      }\n+      if ((value == bins(i).hi) && (i < bins.length - 1) && (value == bins(i + 1).lo)) {\n+        // We assume the above 3 conditions will be evaluated from left to right sequentially.\n+        // If the above 3 conditions are evaluated out-of-order, then out-of-bound error may happen.\n+        // At that time, we should split the third condition into another if statement.\n+        // increment binId since the value appears in this bin and next bin\n+        binId += 1\n+      }\n+    }\n+    binId\n+  }\n+\n+  /**\n+   * Returns a percentage of a bin holding values for column value in the range of\n+   * [lowerValue, higherValue]\n+   *\n+   * @param binId a given bin id in a specified histogram\n+   * @param higherValue a given upper bound value of a specified column value range\n+   * @param lowerValue a given lower bound value of a specified column value range\n+   * @param histogram a numeric equi-height histogram\n+   * @return the percentage of a single bin holding values in [lowerValue, higherValue].\n+   */\n+  private def getOccupation(\n+      binId: Int,\n+      higherValue: Double,\n+      lowerValue: Double,\n+      histogram: Histogram): Double = {\n+    val curBin = histogram.bins(binId)\n+    if (binId == 0 && curBin.hi == curBin.lo) {\n+      // the Min of the histogram occupies the whole first bin\n+      1.0\n+    } else if (binId == 0 && curBin.hi != curBin.lo) {\n+      if (higherValue == lowerValue) {\n+        // set percentage to 1/NDV\n+        1.0 / curBin.ndv.toDouble\n+      } else {\n+        // Use proration since the range falls inside this bin.\n+        (higherValue - lowerValue) / (curBin.hi - curBin.lo)\n+      }\n+    } else {\n+      if (curBin.hi == curBin.lo) {\n+        // the entire bin is covered in the range\n+        1.0\n+      } else if (higherValue == lowerValue) {\n+        // set percentage to 1/NDV\n+        1.0 / curBin.ndv.toDouble\n+      } else {\n+        // Use proration since the range falls inside this bin.\n+        math.min((higherValue - lowerValue) / (curBin.hi - curBin.lo), 1.0)\n+      }\n+    }\n+  }\n+\n+  /**\n+   * Returns the number of bins for column values in [lowerValue, higherValue].\n+   * The column value distribution is saved in an equi-height histogram.\n+   *\n+   * @param higherEnd a given upper bound value of a specified column value range\n+   * @param lowerEnd a given lower bound value of a specified column value range\n+   * @param histogram a numeric equi-height histogram\n+   * @return the selectivity percentage for column values in [lowerValue, higherValue].\n+   */\n+  def getOccupationBins(\n+      higherEnd: Double,\n+      lowerEnd: Double,\n+      histogram: Histogram): Double = {\n+    // find bins where current min and max locate\n+    val lowerBinId = findFirstBinForValue(lowerEnd, histogram.bins)\n+    val higherBinId = findLastBinForValue(higherEnd, histogram.bins)\n+    assert(lowerBinId <= higherBinId)\n+\n+    // compute how much current [lowerEnd, higherEnd] range occupies the histogram in the\n+    // number of bins\n+    getOccupationBins(higherBinId, lowerBinId, higherEnd, lowerEnd, histogram)\n+  }\n+\n+  /**\n+   * Returns the number of bins for column values in [lowerValue, higherValue].\n+   * This is an overloaded method. The column value distribution is saved in an\n+   * equi-height histogram.\n+   *\n+   * @param higherId id of the high end bin holding the high end value of a column range\n+   * @param lowerId id of the low end bin holding the low end value of a column range\n+   * @param higherEnd a given upper bound value of a specified column value range\n+   * @param lowerEnd a given lower bound value of a specified column value range\n+   * @param histogram a numeric equi-height histogram\n+   * @return the selectivity percentage for column values in [lowerEnd, higherEnd].","path":"sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/statsEstimation/EstimationUtils.scala","position":129,"original_position":129,"commit_id":"9d2a463f76ecd164dd15a834aa971a4d222113b6","original_commit_id":"9d2a463f76ecd164dd15a834aa971a4d222113b6","user":{"login":"cloud-fan","id":3182036,"avatar_url":"https://avatars3.githubusercontent.com/u/3182036?v=4","gravatar_id":"","url":"https://api.github.com/users/cloud-fan","html_url":"https://github.com/cloud-fan","followers_url":"https://api.github.com/users/cloud-fan/followers","following_url":"https://api.github.com/users/cloud-fan/following{/other_user}","gists_url":"https://api.github.com/users/cloud-fan/gists{/gist_id}","starred_url":"https://api.github.com/users/cloud-fan/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cloud-fan/subscriptions","organizations_url":"https://api.github.com/users/cloud-fan/orgs","repos_url":"https://api.github.com/users/cloud-fan/repos","events_url":"https://api.github.com/users/cloud-fan/events{/privacy}","received_events_url":"https://api.github.com/users/cloud-fan/received_events","type":"User","site_admin":false},"body":"this doesn't match the java doc: `Returns the number of bins...`","created_at":"2017-12-05T05:35:37Z","updated_at":"2017-12-05T05:35:37Z","html_url":"https://github.com/apache/spark/pull/19783#discussion_r154850738","pull_request_url":"https://api.github.com/repos/apache/spark/pulls/19783","author_association":"CONTRIBUTOR","_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/comments/154850738"},"html":{"href":"https://github.com/apache/spark/pull/19783#discussion_r154850738"},"pull_request":{"href":"https://api.github.com/repos/apache/spark/pulls/19783"}}},"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/19783","id":153512592,"html_url":"https://github.com/apache/spark/pull/19783","diff_url":"https://github.com/apache/spark/pull/19783.diff","patch_url":"https://github.com/apache/spark/pull/19783.patch","issue_url":"https://api.github.com/repos/apache/spark/issues/19783","number":19783,"state":"open","locked":false,"title":"[SPARK-21322][SQL] support histogram in filter cardinality estimation","user":{"login":"ron8hu","id":10659419,"avatar_url":"https://avatars3.githubusercontent.com/u/10659419?v=4","gravatar_id":"","url":"https://api.github.com/users/ron8hu","html_url":"https://github.com/ron8hu","followers_url":"https://api.github.com/users/ron8hu/followers","following_url":"https://api.github.com/users/ron8hu/following{/other_user}","gists_url":"https://api.github.com/users/ron8hu/gists{/gist_id}","starred_url":"https://api.github.com/users/ron8hu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ron8hu/subscriptions","organizations_url":"https://api.github.com/users/ron8hu/orgs","repos_url":"https://api.github.com/users/ron8hu/repos","events_url":"https://api.github.com/users/ron8hu/events{/privacy}","received_events_url":"https://api.github.com/users/ron8hu/received_events","type":"User","site_admin":false},"body":"## What changes were proposed in this pull request?\r\n\r\nHistogram is effective in dealing with skewed distribution. After we generate histogram information for column statistics, we need to adjust filter estimation based on histogram data structure.\r\n\r\n## How was this patch tested?\r\n\r\nWe revised all the unit test cases by including histogram data structure.\r\n\r\nPlease review http://spark.apache.org/contributing.html before opening a pull request.\r\n","created_at":"2017-11-19T19:59:32Z","updated_at":"2017-12-05T05:35:37Z","closed_at":null,"merged_at":null,"merge_commit_sha":"f95ed48cf9d7c8b56b3f19edfbd5cf0c08a5c8ef","assignee":null,"assignees":[],"requested_reviewers":[],"milestone":null,"commits_url":"https://api.github.com/repos/apache/spark/pulls/19783/commits","review_comments_url":"https://api.github.com/repos/apache/spark/pulls/19783/comments","review_comment_url":"https://api.github.com/repos/apache/spark/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/spark/issues/19783/comments","statuses_url":"https://api.github.com/repos/apache/spark/statuses/9d2a463f76ecd164dd15a834aa971a4d222113b6","head":{"label":"ron8hu:supportHistogram","ref":"supportHistogram","sha":"9d2a463f76ecd164dd15a834aa971a4d222113b6","user":{"login":"ron8hu","id":10659419,"avatar_url":"https://avatars3.githubusercontent.com/u/10659419?v=4","gravatar_id":"","url":"https://api.github.com/users/ron8hu","html_url":"https://github.com/ron8hu","followers_url":"https://api.github.com/users/ron8hu/followers","following_url":"https://api.github.com/users/ron8hu/following{/other_user}","gists_url":"https://api.github.com/users/ron8hu/gists{/gist_id}","starred_url":"https://api.github.com/users/ron8hu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ron8hu/subscriptions","organizations_url":"https://api.github.com/users/ron8hu/orgs","repos_url":"https://api.github.com/users/ron8hu/repos","events_url":"https://api.github.com/users/ron8hu/events{/privacy}","received_events_url":"https://api.github.com/users/ron8hu/received_events","type":"User","site_admin":false},"repo":{"id":67744891,"name":"spark","full_name":"ron8hu/spark","owner":{"login":"ron8hu","id":10659419,"avatar_url":"https://avatars3.githubusercontent.com/u/10659419?v=4","gravatar_id":"","url":"https://api.github.com/users/ron8hu","html_url":"https://github.com/ron8hu","followers_url":"https://api.github.com/users/ron8hu/followers","following_url":"https://api.github.com/users/ron8hu/following{/other_user}","gists_url":"https://api.github.com/users/ron8hu/gists{/gist_id}","starred_url":"https://api.github.com/users/ron8hu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ron8hu/subscriptions","organizations_url":"https://api.github.com/users/ron8hu/orgs","repos_url":"https://api.github.com/users/ron8hu/repos","events_url":"https://api.github.com/users/ron8hu/events{/privacy}","received_events_url":"https://api.github.com/users/ron8hu/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/ron8hu/spark","description":"Mirror of Apache Spark","fork":true,"url":"https://api.github.com/repos/ron8hu/spark","forks_url":"https://api.github.com/repos/ron8hu/spark/forks","keys_url":"https://api.github.com/repos/ron8hu/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/ron8hu/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/ron8hu/spark/teams","hooks_url":"https://api.github.com/repos/ron8hu/spark/hooks","issue_events_url":"https://api.github.com/repos/ron8hu/spark/issues/events{/number}","events_url":"https://api.github.com/repos/ron8hu/spark/events","assignees_url":"https://api.github.com/repos/ron8hu/spark/assignees{/user}","branches_url":"https://api.github.com/repos/ron8hu/spark/branches{/branch}","tags_url":"https://api.github.com/repos/ron8hu/spark/tags","blobs_url":"https://api.github.com/repos/ron8hu/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/ron8hu/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/ron8hu/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/ron8hu/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/ron8hu/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/ron8hu/spark/languages","stargazers_url":"https://api.github.com/repos/ron8hu/spark/stargazers","contributors_url":"https://api.github.com/repos/ron8hu/spark/contributors","subscribers_url":"https://api.github.com/repos/ron8hu/spark/subscribers","subscription_url":"https://api.github.com/repos/ron8hu/spark/subscription","commits_url":"https://api.github.com/repos/ron8hu/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/ron8hu/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/ron8hu/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/ron8hu/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/ron8hu/spark/contents/{+path}","compare_url":"https://api.github.com/repos/ron8hu/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/ron8hu/spark/merges","archive_url":"https://api.github.com/repos/ron8hu/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/ron8hu/spark/downloads","issues_url":"https://api.github.com/repos/ron8hu/spark/issues{/number}","pulls_url":"https://api.github.com/repos/ron8hu/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/ron8hu/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/ron8hu/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/ron8hu/spark/labels{/name}","releases_url":"https://api.github.com/repos/ron8hu/spark/releases{/id}","deployments_url":"https://api.github.com/repos/ron8hu/spark/deployments","created_at":"2016-09-08T22:30:43Z","updated_at":"2016-09-08T22:31:07Z","pushed_at":"2017-12-02T02:40:57Z","git_url":"git://github.com/ron8hu/spark.git","ssh_url":"git@github.com:ron8hu/spark.git","clone_url":"https://github.com/ron8hu/spark.git","svn_url":"https://github.com/ron8hu/spark","homepage":null,"size":261026,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":1,"license":{"key":"apache-2.0","name":"Apache License 2.0","spdx_id":"Apache-2.0","url":"https://api.github.com/licenses/apache-2.0"},"forks":0,"open_issues":1,"watchers":0,"default_branch":"master"}},"base":{"label":"apache:master","ref":"master","sha":"ee10ca7ec6cf7fbaab3f95a097b46936d97d0835","user":{"login":"apache","id":47359,"avatar_url":"https://avatars0.githubusercontent.com/u/47359?v=4","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"repo":{"id":17165658,"name":"spark","full_name":"apache/spark","owner":{"login":"apache","id":47359,"avatar_url":"https://avatars0.githubusercontent.com/u/47359?v=4","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/apache/spark","description":"Mirror of Apache Spark","fork":false,"url":"https://api.github.com/repos/apache/spark","forks_url":"https://api.github.com/repos/apache/spark/forks","keys_url":"https://api.github.com/repos/apache/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/apache/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/apache/spark/teams","hooks_url":"https://api.github.com/repos/apache/spark/hooks","issue_events_url":"https://api.github.com/repos/apache/spark/issues/events{/number}","events_url":"https://api.github.com/repos/apache/spark/events","assignees_url":"https://api.github.com/repos/apache/spark/assignees{/user}","branches_url":"https://api.github.com/repos/apache/spark/branches{/branch}","tags_url":"https://api.github.com/repos/apache/spark/tags","blobs_url":"https://api.github.com/repos/apache/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/apache/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/apache/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/apache/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/apache/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/apache/spark/languages","stargazers_url":"https://api.github.com/repos/apache/spark/stargazers","contributors_url":"https://api.github.com/repos/apache/spark/contributors","subscribers_url":"https://api.github.com/repos/apache/spark/subscribers","subscription_url":"https://api.github.com/repos/apache/spark/subscription","commits_url":"https://api.github.com/repos/apache/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/apache/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/apache/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/apache/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/apache/spark/contents/{+path}","compare_url":"https://api.github.com/repos/apache/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/apache/spark/merges","archive_url":"https://api.github.com/repos/apache/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/apache/spark/downloads","issues_url":"https://api.github.com/repos/apache/spark/issues{/number}","pulls_url":"https://api.github.com/repos/apache/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/apache/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/apache/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/apache/spark/labels{/name}","releases_url":"https://api.github.com/repos/apache/spark/releases{/id}","deployments_url":"https://api.github.com/repos/apache/spark/deployments","created_at":"2014-02-25T08:00:08Z","updated_at":"2017-12-05T04:35:32Z","pushed_at":"2017-12-05T05:06:28Z","git_url":"git://github.com/apache/spark.git","ssh_url":"git@github.com:apache/spark.git","clone_url":"https://github.com/apache/spark.git","svn_url":"https://github.com/apache/spark","homepage":null,"size":267262,"stargazers_count":15341,"watchers_count":15341,"language":"Scala","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":14235,"mirror_url":null,"archived":false,"open_issues_count":395,"license":{"key":"apache-2.0","name":"Apache License 2.0","spdx_id":"Apache-2.0","url":"https://api.github.com/licenses/apache-2.0"},"forks":14235,"open_issues":395,"watchers":15341,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/19783"},"html":{"href":"https://github.com/apache/spark/pull/19783"},"issue":{"href":"https://api.github.com/repos/apache/spark/issues/19783"},"comments":{"href":"https://api.github.com/repos/apache/spark/issues/19783/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/spark/pulls/19783/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/spark/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/spark/pulls/19783/commits"},"statuses":{"href":"https://api.github.com/repos/apache/spark/statuses/9d2a463f76ecd164dd15a834aa971a4d222113b6"}},"author_association":"CONTRIBUTOR"}}
{"actor":{"display_login":"cloud-fan"}}