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

Code before:
// Each distinct value is mapped to 'i' with a probability of 2^-(i+1).
// For example, a value is mapped to 0 with a probability of 1/2, to 1 with a probability of 1/4, to 2 with a probability of 1/8, and so on.
// This is achieved by hashing the input value and counting the trailing zeroes in the hash value.
// If we have a set of 'n' distinct values, the count of distinct values with 'r' trailing zeroes is n / 2^r.
// Therefore, the estimated count of distinct values is 2^r * count = n.
// The level-by-level approach increases the accuracy of the estimation by ensuring a minimum count of distinct values at each level.
// This way, the final estimation is less likely to be skewed by outliers.
// For more details, refer to the following papers:
//  1. https://www.vldb.org/conf/2001/P541.pdf
//  2. https://algo.inria.fr/flajolet/Publications/FlMa85.pdf
type FMSketch struct {
	// A set to store unique hashed values.
	hashset map[uint64]struct{}
	// A binary mask used to track the maximum number of trailing zeroes in the hashed values.
	// Also used to track the level of the sketch.
	// Every time the size of the hashset exceeds the maximum size, the mask will be moved to the next level.
	mask uint64
	// The maximum size of the hashset. If the size exceeds this value, the mask will be moved to the next level.
	// And the hashset will only keep the hashed values with trailing zeroes greater than or equal to the new mask.
	maxSize int
}

// NewFMSketch returns a new FM sketch.
func NewFMSketch(maxSize int) *FMSketch {
	return &FMSketch{
		hashset: make(map[uint64]struct{}),
		maxSize: maxSize,
	}
}

// Copy makes a copy for current FMSketch.
func (s *FMSketch) Copy() *FMSketch {
	if s == nil {
		return nil
	}
	return &FMSketch{
		hashset: maps.Clone(s.hashset),
		mask:    s.mask,
		maxSize: s.maxSize,
	}
}

// NDV returns the estimated number of distinct values (NDV) in the sketch.
func (s *FMSketch) NDV() int64 {
	if s == nil {
		return 0
	}
	// The estimated count of distinct values is 2^r * count, where 'r' is the maximum number of trailing zeroes observed and 'count' is the number of unique hashed values.
	// The fundamental idea is that the hash function maps the input domain onto a logarithmic scale.
	// This is achieved by hashing the input value and counting the number of trailing zeroes in the binary representation of the hash value.
	// So the count of distinct values with 'r' trailing zeroes is n / 2^r, where 'n' is the number of distinct values.

Review comment (suggestion):
NewFMSketch now allocates the hashset map with zero initial capacity. Previously the underlying set was created with an initial size (128), which avoids early growth rehashes/allocations for common cases. Consider giving the map a small initial capacity (e.g. min(maxSize, 128)) to reduce allocation churn during analyze.
```suggestion
	initialSize := maxSize
	if initialSize > 128 {
		initialSize = 128
	} else if initialSize < 0 {
		initialSize = 0
	}
	return &FMSketch{
		hashset: make(map[uint64]struct{}, initialSize),
```

Code after:
// Each distinct value is mapped to 'i' with a probability of 2^-(i+1).
// For example, a value is mapped to 0 with a probability of 1/2, to 1 with a probability of 1/4, to 2 with a probability of 1/8, and so on.
// This is achieved by hashing the input value and counting the trailing zeroes in the hash value.
// If we have a set of 'n' distinct values, the count of distinct values with 'r' trailing zeroes is n / 2^r.
// Therefore, the estimated count of distinct values is 2^r * count = n.
// The level-by-level approach increases the accuracy of the estimation by ensuring a minimum count of distinct values at each level.
// This way, the final estimation is less likely to be skewed by outliers.
// For more details, refer to the following papers:
//  1. https://www.vldb.org/conf/2001/P541.pdf
//  2. https://algo.inria.fr/flajolet/Publications/FlMa85.pdf
type FMSketch struct {
	// A set to store unique hashed values.
	hashset map[uint64]struct{}
	// A binary mask used to track the maximum number of trailing zeroes in the hashed values.
	// Also used to track the level of the sketch.
	// Every time the size of the hashset exceeds the maximum size, the mask will be moved to the next level.
	mask uint64
	// The maximum size of the hashset. If the size exceeds this value, the mask will be moved to the next level.
	// And the hashset will only keep the hashed values with trailing zeroes greater than or equal to the new mask.
	maxSize int
}

// NewFMSketch returns a new FM sketch.
func NewFMSketch(maxSize int) *FMSketch {
	return &FMSketch{
		hashset: make(map[uint64]struct{}, maxSize),
		maxSize: maxSize,
	}
}

// Copy makes a copy for current FMSketch.
func (s *FMSketch) Copy() *FMSketch {
	if s == nil {
		return nil
	}
	return &FMSketch{
		hashset: maps.Clone(s.hashset),
		mask:    s.mask,
		maxSize: s.maxSize,
	}
}

// NDV returns the estimated number of distinct values (NDV) in the sketch.
func (s *FMSketch) NDV() int64 {
	if s == nil {
		return 0
	}
	// The estimated count of distinct values is 2^r * count, where 'r' is the maximum number of trailing zeroes observed and 'count' is the number of unique hashed values.
	// The fundamental idea is that the hash function maps the input domain onto a logarithmic scale.
	// This is achieved by hashing the input value and counting the number of trailing zeroes in the binary representation of the hash value.
	// So the count of distinct values with 'r' trailing zeroes is n / 2^r, where 'n' is the number of distinct values.