You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
50 lines
1.8 KiB
50 lines
1.8 KiB
// Copyright 2019 PingCAP, Inc.
|
|
//
|
|
// Licensed under the Apache License, Version 2.0 (the "License");
|
|
// you may not use this file except in compliance with the License.
|
|
// You may obtain a copy of the License at
|
|
//
|
|
// http://www.apache.org/licenses/LICENSE-2.0
|
|
//
|
|
// Unless required by applicable law or agreed to in writing, software
|
|
// distributed under the License is distributed on an "AS IS" BASIS,
|
|
// See the License for the specific language governing permissions and
|
|
// limitations under the License.
|
|
|
|
package statistics
|
|
|
|
import (
|
|
"math"
|
|
|
|
"github.com/cznic/mathutil"
|
|
)
|
|
|
|
// calculateEstimateNDV calculates the estimate ndv of a sampled data from a multisize with size total.
|
|
func calculateEstimateNDV(h *topNHelper, rowCount uint64) (ndv uint64, scaleRatio uint64) {
|
|
sampleSize, sampleNDV, onlyOnceItems := h.sampleSize, uint64(len(h.sorted)), h.onlyOnceItems
|
|
scaleRatio = rowCount / sampleSize
|
|
|
|
if onlyOnceItems == sampleSize {
|
|
// Assume this is a unique column, so do not scale up the count of elements
|
|
return rowCount, 1
|
|
} else if onlyOnceItems == 0 {
|
|
// Assume data only consists of sampled data
|
|
// Nothing to do, no change with scale ratio
|
|
return sampleNDV, scaleRatio
|
|
}
|
|
// Charikar, Moses, et al. "Towards estimation error guarantees for distinct values."
|
|
// Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. ACM, 2000.
|
|
// This is GEE in that paper.
|
|
// estimateNDV = sqrt(N/n) f_1 + sum_2..inf f_i
|
|
// f_i = number of elements occurred i times in sample
|
|
|
|
f1 := float64(onlyOnceItems)
|
|
n := float64(sampleSize)
|
|
N := float64(rowCount)
|
|
d := float64(sampleNDV)
|
|
|
|
ndv = uint64(math.Sqrt(N/n)*f1 + d - f1 + 0.5)
|
|
ndv = mathutil.MaxUint64(ndv, sampleNDV)
|
|
ndv = mathutil.MinUint64(ndv, rowCount)
|
|
return ndv, scaleRatio
|
|
}
|
|
|