# Histogram

+ In an equal-depth histogram, the number of values falling into each bucket is required to be equal.

![`smart`](Histogram_aa_001_20230915.png)

----------------------------------------------------
A histogram serves as a tool for characterizing the distribution of data within a column, enabling the optimizer to comprehend the distribution of specific values. Most database optimizers employ histograms to approximate range queries. Histograms segregate values into buckets based on their size and use straightforward metrics to characterize each bucket, such as the number of values contained within it. Two prevalent types of histograms, differentiated by their bucketing strategies, are equal-depth histograms (also known as equal-height histograms) and equal-width histograms. In an equal-width histogram, each bucket includes a single value alongside the cumulative frequency (i.e., the number of rows sharing that value in the dataset), whereas an equal-depth histogram requires tracking the number of distinct values, upper and lower bounds, and cumulative frequency for each bucket.

In the TiDB database, equal-depth histograms are predominantly employed for range query scenarios. In this type of histogram, each bucket contains an equal number of values. For example, given a dataset `{6, 9, 9, 12, 14, 16, 17, 17, 18, 19, 24, 25}` and dividing it into 4 buckets, the resultant equal-depth histogram would be as depicted, forming the buckets `[6, 9], [12, 16], [17, 18], [19, 25]`, each encompassing 3 values. It is evident that the bucket `[17, 18]` is denser compared to the bucket `[19, 25]`, potentially resulting in a larger response set for range queries involving denser buckets.

Let us now delve into the detailed implementation of histograms within the TiDB database.