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.
	histNDV = max(histNDV, 1)
	oneValue := 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):
Spelling error: "representitative" should be "representative".
```suggestion
		// If NDV is not representative, then hg.NotNullCount may not be either.
```

Code after:
         / xx│  │    range    │      \
       / │xxx│  │             │        \
     /   │xxx│  │             │          \
────┴────┴───┴──┴─────────────┴───────────┴─────
    ▲    ▲   ▲  ▲             ▲           ▲
    │    │   │  │             │           │
 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 a default of "one value"
	// oneValue assumes "one value qualifies", and is used as a lower bound.
	histNDV = max(histNDV, 1)
	oneValue := hg.NotNullCount() / float64(histNDV)

	// 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}
	}

	// Step 3: Adjust oneValue if the NDV is low
	// 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.
	if float64(histNDV) < outOfRangeBetweenRate {
		oneValue = max(min(oneValue, float64(realtimeRowCount)/outOfRangeBetweenRate), 1.0)
	}
	// Step 4: Calculate how much of the statistics share a common prefix.
	// 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.
	// TODO: If the common prefix is large, we may underestimate the out-of-range
	// portion because we can't distinguish the values with the same 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(),