Repository: pingcap/tidb
File: pkg/statistics/histogram.go (Go)

Code before:
    │    │   │  │             │           │
 boundL  │   │histL         histR       boundR
         │   │
    lDatum  rDatum
*/
// The percentage of shaded area on the left side calculation formula is:
// leftPercent = (math.Pow(actualR-boundL, 2) - math.Pow(actualL-boundL, 2)) / math.Pow(histWidth, 2)
// You can find more details at https://github.com/pingcap/tidb/pull/47966#issuecomment-1778866876
func (hg *Histogram) OutOfRangeRowCount(
	sctx planctx.PlanContext,
	lDatum, rDatum *types.Datum,
	realtimeRowCount, modifyCount, histNDV int64,
) (result RowEstimate) {
	if hg.Len() == 0 {
		return DefaultRowEst(0)
	}

	// Step 1: Calculate "one value"
	// oneValue assumes "one value qualifies", and is used as a lower bound.
	// outOfRangeBetweenRate (default == 100) avoids an artificially low NDV.
	// TODO: If we have a large number of added rows, the NDV may be underestimated.
	oneValue := max(1.0, hg.NotNullCount()/float64(histNDV))
	if float64(histNDV) < outOfRangeBetweenRate {
		// If NDV is low, it may no longer be representative of the data since ANALYZE
		// was last run. Use a default value against realtimeRowCount.
		// If NDV is not representitative, then hg.NotNullCount may not be either.
		oneValue = max(min(oneValue, float64(realtimeRowCount)/outOfRangeBetweenRate), 1.0)
	}

	// Step 2: If modifications are not allowed, return the one value.
	// In OptObjectiveDeterminate mode, we can't rely on real time statistics, so default to assuming
	// one value qualifies.
	allowUseModifyCount := sctx.GetSessionVars().GetOptObjective() != vardef.OptObjectiveDeterminate
	if !allowUseModifyCount {
		return RowEstimate{Est: oneValue, MinEst: oneValue, MaxEst: oneValue}
	}

	// For bytes and string type, we need to cut the common prefix when converting them to scalar value.
	// Here we calculate the length of common prefix.
	commonPrefix := 0
	if hg.GetLower(0).Kind() == types.KindBytes || hg.GetLower(0).Kind() == types.KindString {
		// Calculate the common prefix length among the lower and upper bound of histogram and the range we want to estimate.
		commonPrefix = commonPrefixLength(hg.GetLower(0).GetBytes(),
			hg.GetUpper(hg.Len()-1).GetBytes(),
			lDatum.GetBytes(),
			rDatum.GetBytes())
	}

	// Convert the range we want to estimate to scalar value(float64)
	l := convertDatumToScalar(lDatum, commonPrefix)
	r := convertDatumToScalar(rDatum, commonPrefix)

Review comment (suggestion):
Typo in comment: "representitative" should be "representative".
```suggestion
		// If NDV is not representative, then hg.NotNullCount may not be either.
```

Code after:
	l = max(l, boundL)
	r = min(r, histL)
	// If there's no overlap after bounding, return 0.
	if l >= r {
		return 0
	}
	// NOTE: Ranges are squared to determine a triangular (linear) distribution rather than uniform.
	// Width of the histogram - squared to normalize to a percentage
	histWidthSq := math.Pow(histWidth, 2)
	// Right side of the predicate as distance from the left edge of the histogram
	rightRange := math.Pow(r-boundL, 2)
	// Left side of the predicate as distance from the left edge of the histogram
	leftRange := math.Pow(l-boundL, 2)
	return (rightRange - leftRange) / histWidthSq
}

// calculateRightOverlapPercent calculates the percentage for an out-of-range overlap
// on the right side of the histogram. The predicate range [l, r] overlaps with
// the region (histR, boundR), and we calculate the percentage of the shaded area.
func calculateRightOverlapPercent(l, r, histR, boundR, histWidth float64) float64 {
	if histWidth <= 0 {
		return 0
	}
	// bound the left/right ranges of the predicates to the "right triangle" of the histogram.
	l = max(l, histR)
	r = min(r, boundR)
	// If there's no overlap after bounding, return 0.
	if l >= r {
		return 0
	}
	// NOTE: Ranges are squared to determine a triangular (linear) distribution rather than uniform.
	// Width of the histogram - squared to normalize to a percentage
	histWidthSq := math.Pow(histWidth, 2)
	// Left side of the predicate as distance from the right edge of the histogram.
	leftRange := math.Pow(boundR-l, 2)
	// Right side of the predicate as distance from the right edge of the histogram.
	rightRange := math.Pow(boundR-r, 2)
	return (leftRange - rightRange) / histWidthSq
}

// OutOfRangeRowCount estimate the row count of part of [lDatum, rDatum] which is out of range of the histogram.
// Here we assume the density of data is decreasing from the lower/upper bound of the histogram toward outside.
// The maximum row count it can get is the modifyCount. It reaches the maximum when out-of-range width reaches histogram range width.
// As it shows below. To calculate the out-of-range row count, we need to calculate the percentage of the shaded area.
// Note that we assume histL-boundL == histR-histL == boundR-histR here.
/*
               /│             │\
             /  │             │  \
           /x│  │◄─histogram─►│    \
         / xx│  │    range    │      \
       / │xxx│  │             │        \