[SPARK-17074] generate equi-height histogram for column

• Type: Sub-task
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 2.3.0
• Fix Version/s: 2.3.0
• Component/s: Optimizer, SQL
• Assignee: Zhenhua Wang
• Reporter: Ron Hu
• Created: 16/Aug/16 06:28
• Updated: 17/May/20 17:58
• Resolved: 14/Nov/17 15:42

Description

Equi-height histogram is effective in handling skewed data distribution.

For equi-height histogram, the heights of all bins(intervals) are the same. The default number of bins we use is 254.

Now we use a two-step method to generate an equi-height histogram:
1. use percentile_approx to get percentiles (end points of the equi-height bin intervals);
2. use a new aggregate function to get distinct counts in each of these bins.

Note that this method takes two table scans. In the future we may provide other algorithms which need only one table scan.

Issue Links

• blocks: SPARK-21322 support histogram in filter cardinality estimation
• blocks: SPARK-21984 Use histogram stats in join estimation
• incorporates: SPARK-18000 Aggregation function for computing bins (distinct value, count) pairs for equi-width histograms
• incorporates: SPARK-17881 Aggregation function for generating string histograms
• is blocked by: SPARK-17997 Aggregation function for counting distinct values for multiple intervals
• is blocked by: SPARK-22100 Make percentile_approx support date/timestamp type and change the output type to be the same as input type
• links to: [Github] Pull Request #19479 (wzhfy)