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.
701 lines
26 KiB
701 lines
26 KiB
// Copyright 2017 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 core
|
|
|
|
import (
|
|
"math"
|
|
|
|
"github.com/pingcap/errors"
|
|
"github.com/pingcap/parser/ast"
|
|
"github.com/pingcap/parser/mysql"
|
|
"github.com/pingcap/tidb/expression"
|
|
"github.com/pingcap/tidb/planner/property"
|
|
"github.com/pingcap/tidb/planner/util"
|
|
"github.com/pingcap/tidb/statistics"
|
|
"github.com/pingcap/tidb/types"
|
|
"github.com/pingcap/tidb/util/logutil"
|
|
"github.com/pingcap/tidb/util/ranger"
|
|
"go.uber.org/zap"
|
|
)
|
|
|
|
func (p *basePhysicalPlan) StatsCount() float64 {
|
|
return p.stats.RowCount
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (p *LogicalTableDual) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
profile := &property.StatsInfo{
|
|
RowCount: float64(p.RowCount),
|
|
Cardinality: make(map[int64]float64, selfSchema.Len()),
|
|
}
|
|
for _, col := range selfSchema.Columns {
|
|
profile.Cardinality[col.UniqueID] = float64(p.RowCount)
|
|
}
|
|
p.stats = profile
|
|
return p.stats, nil
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (p *LogicalMemTable) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
statsTable := statistics.PseudoTable(p.TableInfo)
|
|
stats := &property.StatsInfo{
|
|
RowCount: float64(statsTable.Count),
|
|
Cardinality: make(map[int64]float64, len(p.TableInfo.Columns)),
|
|
HistColl: statsTable.GenerateHistCollFromColumnInfo(p.TableInfo.Columns, p.schema.Columns),
|
|
StatsVersion: statistics.PseudoVersion,
|
|
}
|
|
for _, col := range selfSchema.Columns {
|
|
stats.Cardinality[col.UniqueID] = float64(statsTable.Count)
|
|
}
|
|
p.stats = stats
|
|
return p.stats, nil
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (p *LogicalShow) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
// A fake count, just to avoid panic now.
|
|
p.stats = getFakeStats(selfSchema)
|
|
return p.stats, nil
|
|
}
|
|
|
|
func getFakeStats(schema *expression.Schema) *property.StatsInfo {
|
|
profile := &property.StatsInfo{
|
|
RowCount: 1,
|
|
Cardinality: make(map[int64]float64, schema.Len()),
|
|
}
|
|
for _, col := range schema.Columns {
|
|
profile.Cardinality[col.UniqueID] = 1
|
|
}
|
|
return profile
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (p *LogicalShowDDLJobs) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
// A fake count, just to avoid panic now.
|
|
p.stats = getFakeStats(selfSchema)
|
|
return p.stats, nil
|
|
}
|
|
|
|
func (p *baseLogicalPlan) recursiveDeriveStats() (*property.StatsInfo, error) {
|
|
if p.stats != nil {
|
|
return p.stats, nil
|
|
}
|
|
childStats := make([]*property.StatsInfo, len(p.children))
|
|
childSchema := make([]*expression.Schema, len(p.children))
|
|
for i, child := range p.children {
|
|
childProfile, err := child.recursiveDeriveStats()
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
childStats[i] = childProfile
|
|
childSchema[i] = child.Schema()
|
|
}
|
|
return p.self.DeriveStats(childStats, p.self.Schema(), childSchema)
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (p *baseLogicalPlan) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
if len(childStats) == 1 {
|
|
p.stats = childStats[0]
|
|
return p.stats, nil
|
|
}
|
|
if len(childStats) > 1 {
|
|
err := ErrInternal.GenWithStack("LogicalPlans with more than one child should implement their own DeriveStats().")
|
|
return nil, err
|
|
}
|
|
profile := &property.StatsInfo{
|
|
RowCount: float64(1),
|
|
Cardinality: make(map[int64]float64, selfSchema.Len()),
|
|
}
|
|
for _, col := range selfSchema.Columns {
|
|
profile.Cardinality[col.UniqueID] = 1
|
|
}
|
|
p.stats = profile
|
|
return profile, nil
|
|
}
|
|
|
|
// getColumnNDV computes estimated NDV of specified column using the original
|
|
// histogram of `DataSource` which is retrieved from storage(not the derived one).
|
|
func (ds *DataSource) getColumnNDV(colID int64) (ndv float64) {
|
|
hist, ok := ds.statisticTable.Columns[colID]
|
|
if ok && hist.Count > 0 {
|
|
factor := float64(ds.statisticTable.Count) / float64(hist.Count)
|
|
ndv = float64(hist.NDV) * factor
|
|
} else {
|
|
ndv = float64(ds.statisticTable.Count) * distinctFactor
|
|
}
|
|
return ndv
|
|
}
|
|
|
|
func (ds *DataSource) initStats() {
|
|
if ds.tableStats != nil {
|
|
return
|
|
}
|
|
if ds.statisticTable == nil {
|
|
ds.statisticTable = getStatsTable(ds.ctx, ds.tableInfo, ds.table.Meta().ID)
|
|
}
|
|
tableStats := &property.StatsInfo{
|
|
RowCount: float64(ds.statisticTable.Count),
|
|
Cardinality: make(map[int64]float64, ds.schema.Len()),
|
|
HistColl: ds.statisticTable.GenerateHistCollFromColumnInfo(ds.Columns, ds.schema.Columns),
|
|
StatsVersion: ds.statisticTable.Version,
|
|
}
|
|
if ds.statisticTable.Pseudo {
|
|
tableStats.StatsVersion = statistics.PseudoVersion
|
|
}
|
|
for _, col := range ds.schema.Columns {
|
|
tableStats.Cardinality[col.UniqueID] = ds.getColumnNDV(col.ID)
|
|
}
|
|
ds.tableStats = tableStats
|
|
ds.TblColHists = ds.statisticTable.ID2UniqueID(ds.TblCols)
|
|
}
|
|
|
|
func (ds *DataSource) deriveStatsByFilter(conds expression.CNFExprs, filledPaths []*util.AccessPath) *property.StatsInfo {
|
|
ds.initStats()
|
|
selectivity, nodes, err := ds.tableStats.HistColl.Selectivity(ds.ctx, conds, filledPaths)
|
|
if err != nil {
|
|
logutil.BgLogger().Debug("something wrong happened, use the default selectivity", zap.Error(err))
|
|
selectivity = SelectionFactor
|
|
}
|
|
stats := ds.tableStats.Scale(selectivity)
|
|
if ds.ctx.GetSessionVars().OptimizerSelectivityLevel >= 1 {
|
|
stats.HistColl = stats.HistColl.NewHistCollBySelectivity(ds.ctx.GetSessionVars().StmtCtx, nodes)
|
|
}
|
|
return stats
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (ds *DataSource) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
ds.initStats()
|
|
// PushDownNot here can convert query 'not (a != 1)' to 'a = 1'.
|
|
for i, expr := range ds.pushedDownConds {
|
|
ds.pushedDownConds[i] = expression.PushDownNot(ds.ctx, expr)
|
|
}
|
|
for _, path := range ds.possibleAccessPaths {
|
|
if path.IsTablePath {
|
|
continue
|
|
}
|
|
err := ds.fillIndexPath(path, ds.pushedDownConds)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
}
|
|
ds.stats = ds.deriveStatsByFilter(ds.pushedDownConds, ds.possibleAccessPaths)
|
|
for _, path := range ds.possibleAccessPaths {
|
|
if path.IsTablePath {
|
|
noIntervalRanges, err := ds.deriveTablePathStats(path, ds.pushedDownConds, false)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
// If we have point or empty range, just remove other possible paths.
|
|
if noIntervalRanges || len(path.Ranges) == 0 {
|
|
ds.possibleAccessPaths[0] = path
|
|
ds.possibleAccessPaths = ds.possibleAccessPaths[:1]
|
|
break
|
|
}
|
|
continue
|
|
}
|
|
noIntervalRanges := ds.deriveIndexPathStats(path, ds.pushedDownConds, false)
|
|
// If we have empty range, or point range on unique index, just remove other possible paths.
|
|
if (noIntervalRanges && path.Index.Unique) || len(path.Ranges) == 0 {
|
|
ds.possibleAccessPaths[0] = path
|
|
ds.possibleAccessPaths = ds.possibleAccessPaths[:1]
|
|
break
|
|
}
|
|
}
|
|
|
|
// TODO: implement UnionScan + IndexMerge
|
|
isReadOnlyTxn := true
|
|
txn, err := ds.ctx.Txn(false)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
if txn.Valid() && !txn.IsReadOnly() {
|
|
isReadOnlyTxn = false
|
|
}
|
|
// Consider the IndexMergePath. Now, we just generate `IndexMergePath` in DNF case.
|
|
isPossibleIdxMerge := len(ds.pushedDownConds) > 0 && len(ds.possibleAccessPaths) > 1
|
|
sessionAndStmtPermission := (ds.ctx.GetSessionVars().GetEnableIndexMerge() || len(ds.indexMergeHints) > 0) && !ds.ctx.GetSessionVars().StmtCtx.NoIndexMergeHint
|
|
// If there is an index path, we current do not consider `IndexMergePath`.
|
|
needConsiderIndexMerge := true
|
|
for i := 1; i < len(ds.possibleAccessPaths); i++ {
|
|
if len(ds.possibleAccessPaths[i].AccessConds) != 0 {
|
|
needConsiderIndexMerge = false
|
|
break
|
|
}
|
|
}
|
|
if isPossibleIdxMerge && sessionAndStmtPermission && needConsiderIndexMerge && isReadOnlyTxn {
|
|
ds.generateAndPruneIndexMergePath(ds.indexMergeHints != nil)
|
|
} else if len(ds.indexMergeHints) > 0 {
|
|
ds.indexMergeHints = nil
|
|
ds.ctx.GetSessionVars().StmtCtx.AppendWarning(errors.Errorf("IndexMerge is inapplicable or disabled"))
|
|
}
|
|
return ds.stats, nil
|
|
}
|
|
|
|
func (ds *DataSource) generateAndPruneIndexMergePath(needPrune bool) {
|
|
regularPathCount := len(ds.possibleAccessPaths)
|
|
ds.generateIndexMergeOrPaths()
|
|
// If without hints, it means that `enableIndexMerge` is true
|
|
if len(ds.indexMergeHints) == 0 {
|
|
return
|
|
}
|
|
// With hints and without generated IndexMerge paths
|
|
if regularPathCount == len(ds.possibleAccessPaths) {
|
|
ds.indexMergeHints = nil
|
|
ds.ctx.GetSessionVars().StmtCtx.AppendWarning(errors.Errorf("IndexMerge is inapplicable or disabled"))
|
|
return
|
|
}
|
|
// Do not need to consider the regular paths in find_best_task().
|
|
if needPrune {
|
|
ds.possibleAccessPaths = ds.possibleAccessPaths[regularPathCount:]
|
|
}
|
|
}
|
|
|
|
// DeriveStats implements LogicalPlan DeriveStats interface.
|
|
func (ts *LogicalTableScan) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (_ *property.StatsInfo, err error) {
|
|
// PushDownNot here can convert query 'not (a != 1)' to 'a = 1'.
|
|
for i, expr := range ts.AccessConds {
|
|
// TODO The expressions may be shared by TableScan and several IndexScans, there would be redundant
|
|
// `PushDownNot` function call in multiple `DeriveStats` then.
|
|
ts.AccessConds[i] = expression.PushDownNot(ts.ctx, expr)
|
|
}
|
|
ts.stats = ts.Source.deriveStatsByFilter(ts.AccessConds, nil)
|
|
sc := ts.SCtx().GetSessionVars().StmtCtx
|
|
// ts.Handle could be nil if PK is Handle, and PK column has been pruned.
|
|
if ts.Handle != nil {
|
|
ts.Ranges, err = ranger.BuildTableRange(ts.AccessConds, sc, ts.Handle.RetType)
|
|
} else {
|
|
isUnsigned := false
|
|
if ts.Source.tableInfo.PKIsHandle {
|
|
if pkColInfo := ts.Source.tableInfo.GetPkColInfo(); pkColInfo != nil {
|
|
isUnsigned = mysql.HasUnsignedFlag(pkColInfo.Flag)
|
|
}
|
|
}
|
|
ts.Ranges = ranger.FullIntRange(isUnsigned)
|
|
}
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
return ts.stats, nil
|
|
}
|
|
|
|
// DeriveStats implements LogicalPlan DeriveStats interface.
|
|
func (is *LogicalIndexScan) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
for i, expr := range is.AccessConds {
|
|
is.AccessConds[i] = expression.PushDownNot(is.ctx, expr)
|
|
}
|
|
is.stats = is.Source.deriveStatsByFilter(is.AccessConds, nil)
|
|
if len(is.AccessConds) == 0 {
|
|
is.Ranges = ranger.FullRange()
|
|
}
|
|
is.IdxCols, is.IdxColLens = expression.IndexInfo2PrefixCols(is.Columns, selfSchema.Columns, is.Index)
|
|
is.FullIdxCols, is.FullIdxColLens = expression.IndexInfo2Cols(is.Columns, selfSchema.Columns, is.Index)
|
|
if !is.Index.Unique && !is.Index.Primary && len(is.Index.Columns) == len(is.IdxCols) {
|
|
handleCol := is.getPKIsHandleCol(selfSchema)
|
|
if handleCol != nil && !mysql.HasUnsignedFlag(handleCol.RetType.Flag) {
|
|
is.IdxCols = append(is.IdxCols, handleCol)
|
|
is.IdxColLens = append(is.IdxColLens, types.UnspecifiedLength)
|
|
}
|
|
}
|
|
return is.stats, nil
|
|
}
|
|
|
|
// getIndexMergeOrPath generates all possible IndexMergeOrPaths.
|
|
func (ds *DataSource) generateIndexMergeOrPaths() {
|
|
usedIndexCount := len(ds.possibleAccessPaths)
|
|
for i, cond := range ds.pushedDownConds {
|
|
sf, ok := cond.(*expression.ScalarFunction)
|
|
if !ok || sf.FuncName.L != ast.LogicOr {
|
|
continue
|
|
}
|
|
var partialPaths = make([]*util.AccessPath, 0, usedIndexCount)
|
|
dnfItems := expression.FlattenDNFConditions(sf)
|
|
for _, item := range dnfItems {
|
|
cnfItems := expression.SplitCNFItems(item)
|
|
itemPaths := ds.accessPathsForConds(cnfItems, usedIndexCount)
|
|
if len(itemPaths) == 0 {
|
|
partialPaths = nil
|
|
break
|
|
}
|
|
partialPath := ds.buildIndexMergePartialPath(itemPaths)
|
|
if partialPath == nil {
|
|
partialPaths = nil
|
|
break
|
|
}
|
|
partialPaths = append(partialPaths, partialPath)
|
|
}
|
|
if len(partialPaths) > 1 {
|
|
possiblePath := ds.buildIndexMergeOrPath(partialPaths, i)
|
|
accessConds := make([]expression.Expression, 0, len(partialPaths))
|
|
for _, p := range partialPaths {
|
|
accessConds = append(accessConds, p.AccessConds...)
|
|
}
|
|
accessDNF := expression.ComposeDNFCondition(ds.ctx, accessConds...)
|
|
sel, _, err := ds.tableStats.HistColl.Selectivity(ds.ctx, []expression.Expression{accessDNF}, nil)
|
|
if err != nil {
|
|
logutil.BgLogger().Debug("something wrong happened, use the default selectivity", zap.Error(err))
|
|
sel = SelectionFactor
|
|
}
|
|
possiblePath.CountAfterAccess = sel * ds.tableStats.RowCount
|
|
ds.possibleAccessPaths = append(ds.possibleAccessPaths, possiblePath)
|
|
}
|
|
}
|
|
}
|
|
|
|
// isInIndexMergeHints checks whether current index or primary key is in IndexMerge hints.
|
|
func (ds *DataSource) isInIndexMergeHints(name string) bool {
|
|
if len(ds.indexMergeHints) == 0 {
|
|
return true
|
|
}
|
|
for _, hint := range ds.indexMergeHints {
|
|
if hint.indexHint == nil || len(hint.indexHint.IndexNames) == 0 {
|
|
return true
|
|
}
|
|
for _, hintName := range hint.indexHint.IndexNames {
|
|
if name == hintName.String() {
|
|
return true
|
|
}
|
|
}
|
|
}
|
|
return false
|
|
}
|
|
|
|
// accessPathsForConds generates all possible index paths for conditions.
|
|
func (ds *DataSource) accessPathsForConds(conditions []expression.Expression, usedIndexCount int) []*util.AccessPath {
|
|
var results = make([]*util.AccessPath, 0, usedIndexCount)
|
|
for i := 0; i < usedIndexCount; i++ {
|
|
path := &util.AccessPath{}
|
|
if ds.possibleAccessPaths[i].IsTablePath {
|
|
if !ds.isInIndexMergeHints("primary") {
|
|
continue
|
|
}
|
|
path.IsTablePath = true
|
|
noIntervalRanges, err := ds.deriveTablePathStats(path, conditions, true)
|
|
if err != nil {
|
|
logutil.BgLogger().Debug("can not derive statistics of a path", zap.Error(err))
|
|
continue
|
|
}
|
|
if len(path.AccessConds) == 0 {
|
|
// If AccessConds is empty, we ignore the access path.
|
|
continue
|
|
}
|
|
// If we have point or empty range, just remove other possible paths.
|
|
if noIntervalRanges || len(path.Ranges) == 0 {
|
|
if len(results) == 0 {
|
|
results = append(results, path)
|
|
} else {
|
|
results[0] = path
|
|
results = results[:1]
|
|
}
|
|
break
|
|
}
|
|
} else {
|
|
path.Index = ds.possibleAccessPaths[i].Index
|
|
if !ds.isInIndexMergeHints(path.Index.Name.L) {
|
|
continue
|
|
}
|
|
err := ds.fillIndexPath(path, conditions)
|
|
if err != nil {
|
|
logutil.BgLogger().Debug("can not derive statistics of a path", zap.Error(err))
|
|
continue
|
|
}
|
|
noIntervalRanges := ds.deriveIndexPathStats(path, conditions, true)
|
|
if len(path.AccessConds) == 0 {
|
|
// If AccessConds is empty, we ignore the access path.
|
|
continue
|
|
}
|
|
// If we have empty range, or point range on unique index, just remove other possible paths.
|
|
if (noIntervalRanges && path.Index.Unique) || len(path.Ranges) == 0 {
|
|
if len(results) == 0 {
|
|
results = append(results, path)
|
|
} else {
|
|
results[0] = path
|
|
results = results[:1]
|
|
}
|
|
break
|
|
}
|
|
}
|
|
results = append(results, path)
|
|
}
|
|
return results
|
|
}
|
|
|
|
// buildIndexMergePartialPath chooses the best index path from all possible paths.
|
|
// Now we just choose the index with most columns.
|
|
// We should improve this strategy, because it is not always better to choose index
|
|
// with most columns, e.g, filter is c > 1 and the input indexes are c and c_d_e,
|
|
// the former one is enough, and it is less expensive in execution compared with the latter one.
|
|
// TODO: improve strategy of the partial path selection
|
|
func (ds *DataSource) buildIndexMergePartialPath(indexAccessPaths []*util.AccessPath) *util.AccessPath {
|
|
if len(indexAccessPaths) == 1 {
|
|
return indexAccessPaths[0]
|
|
}
|
|
|
|
maxColsIndex := 0
|
|
maxCols := len(indexAccessPaths[0].IdxCols)
|
|
for i := 1; i < len(indexAccessPaths); i++ {
|
|
current := len(indexAccessPaths[i].IdxCols)
|
|
if current > maxCols {
|
|
maxColsIndex = i
|
|
maxCols = current
|
|
}
|
|
}
|
|
return indexAccessPaths[maxColsIndex]
|
|
}
|
|
|
|
// buildIndexMergeOrPath generates one possible IndexMergePath.
|
|
func (ds *DataSource) buildIndexMergeOrPath(partialPaths []*util.AccessPath, current int) *util.AccessPath {
|
|
indexMergePath := &util.AccessPath{PartialIndexPaths: partialPaths}
|
|
indexMergePath.TableFilters = append(indexMergePath.TableFilters, ds.pushedDownConds[:current]...)
|
|
indexMergePath.TableFilters = append(indexMergePath.TableFilters, ds.pushedDownConds[current+1:]...)
|
|
for _, path := range partialPaths {
|
|
if len(path.TableFilters) > 0 {
|
|
indexMergePath.TableFilters = append(indexMergePath.TableFilters, path.TableFilters...)
|
|
}
|
|
}
|
|
return indexMergePath
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (p *LogicalSelection) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
p.stats = childStats[0].Scale(SelectionFactor)
|
|
return p.stats, nil
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (p *LogicalUnionAll) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
p.stats = &property.StatsInfo{
|
|
Cardinality: make(map[int64]float64, selfSchema.Len()),
|
|
}
|
|
for _, childProfile := range childStats {
|
|
p.stats.RowCount += childProfile.RowCount
|
|
for _, col := range selfSchema.Columns {
|
|
p.stats.Cardinality[col.UniqueID] += childProfile.Cardinality[col.UniqueID]
|
|
}
|
|
}
|
|
return p.stats, nil
|
|
}
|
|
|
|
func deriveLimitStats(childProfile *property.StatsInfo, limitCount float64) *property.StatsInfo {
|
|
stats := &property.StatsInfo{
|
|
RowCount: math.Min(limitCount, childProfile.RowCount),
|
|
Cardinality: make(map[int64]float64, len(childProfile.Cardinality)),
|
|
}
|
|
for id, c := range childProfile.Cardinality {
|
|
stats.Cardinality[id] = math.Min(c, stats.RowCount)
|
|
}
|
|
return stats
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (p *LogicalLimit) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
p.stats = deriveLimitStats(childStats[0], float64(p.Count))
|
|
return p.stats, nil
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (lt *LogicalTopN) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
lt.stats = deriveLimitStats(childStats[0], float64(lt.Count))
|
|
return lt.stats, nil
|
|
}
|
|
|
|
// getCardinality will return the Cardinality of a couple of columns. We simply return the max one, because we cannot know
|
|
// the Cardinality for multi-dimension attributes properly. This is a simple and naive scheme of Cardinality estimation.
|
|
func getCardinality(cols []*expression.Column, schema *expression.Schema, profile *property.StatsInfo) float64 {
|
|
cardinality := 1.0
|
|
indices := schema.ColumnsIndices(cols)
|
|
if indices == nil {
|
|
logutil.BgLogger().Error("column not found in schema", zap.Any("columns", cols), zap.String("schema", schema.String()))
|
|
return cardinality
|
|
}
|
|
for _, idx := range indices {
|
|
// It is a very elementary estimation.
|
|
col := schema.Columns[idx]
|
|
cardinality = math.Max(cardinality, profile.Cardinality[col.UniqueID])
|
|
}
|
|
return cardinality
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (p *LogicalProjection) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
childProfile := childStats[0]
|
|
p.stats = &property.StatsInfo{
|
|
RowCount: childProfile.RowCount,
|
|
Cardinality: make(map[int64]float64, len(p.Exprs)),
|
|
}
|
|
for i, expr := range p.Exprs {
|
|
cols := expression.ExtractColumns(expr)
|
|
p.stats.Cardinality[selfSchema.Columns[i].UniqueID] = getCardinality(cols, childSchema[0], childProfile)
|
|
}
|
|
return p.stats, nil
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (la *LogicalAggregation) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
childProfile := childStats[0]
|
|
gbyCols := make([]*expression.Column, 0, len(la.GroupByItems))
|
|
for _, gbyExpr := range la.GroupByItems {
|
|
cols := expression.ExtractColumns(gbyExpr)
|
|
gbyCols = append(gbyCols, cols...)
|
|
}
|
|
cardinality := getCardinality(gbyCols, childSchema[0], childProfile)
|
|
la.stats = &property.StatsInfo{
|
|
RowCount: cardinality,
|
|
Cardinality: make(map[int64]float64, selfSchema.Len()),
|
|
}
|
|
// We cannot estimate the Cardinality for every output, so we use a conservative strategy.
|
|
for _, col := range selfSchema.Columns {
|
|
la.stats.Cardinality[col.UniqueID] = cardinality
|
|
}
|
|
la.inputCount = childProfile.RowCount
|
|
return la.stats, nil
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
// If the type of join is SemiJoin, the selectivity of it will be same as selection's.
|
|
// If the type of join is LeftOuterSemiJoin, it will not add or remove any row. The last column is a boolean value, whose Cardinality should be two.
|
|
// If the type of join is inner/outer join, the output of join(s, t) should be N(s) * N(t) / (V(s.key) * V(t.key)) * Min(s.key, t.key).
|
|
// N(s) stands for the number of rows in relation s. V(s.key) means the Cardinality of join key in s.
|
|
// This is a quite simple strategy: We assume every bucket of relation which will participate join has the same number of rows, and apply cross join for
|
|
// every matched bucket.
|
|
func (p *LogicalJoin) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
leftProfile, rightProfile := childStats[0], childStats[1]
|
|
leftJoinKeys, rightJoinKeys := p.GetJoinKeys()
|
|
helper := &fullJoinRowCountHelper{
|
|
cartesian: 0 == len(p.EqualConditions),
|
|
leftProfile: leftProfile,
|
|
rightProfile: rightProfile,
|
|
leftJoinKeys: leftJoinKeys,
|
|
rightJoinKeys: rightJoinKeys,
|
|
leftSchema: childSchema[0],
|
|
rightSchema: childSchema[1],
|
|
}
|
|
p.equalCondOutCnt = helper.estimate()
|
|
if p.JoinType == SemiJoin || p.JoinType == AntiSemiJoin {
|
|
p.stats = &property.StatsInfo{
|
|
RowCount: leftProfile.RowCount * SelectionFactor,
|
|
Cardinality: make(map[int64]float64, len(leftProfile.Cardinality)),
|
|
}
|
|
for id, c := range leftProfile.Cardinality {
|
|
p.stats.Cardinality[id] = c * SelectionFactor
|
|
}
|
|
return p.stats, nil
|
|
}
|
|
if p.JoinType == LeftOuterSemiJoin || p.JoinType == AntiLeftOuterSemiJoin {
|
|
p.stats = &property.StatsInfo{
|
|
RowCount: leftProfile.RowCount,
|
|
Cardinality: make(map[int64]float64, selfSchema.Len()),
|
|
}
|
|
for id, c := range leftProfile.Cardinality {
|
|
p.stats.Cardinality[id] = c
|
|
}
|
|
p.stats.Cardinality[selfSchema.Columns[selfSchema.Len()-1].UniqueID] = 2.0
|
|
return p.stats, nil
|
|
}
|
|
count := p.equalCondOutCnt
|
|
if p.JoinType == LeftOuterJoin {
|
|
count = math.Max(count, leftProfile.RowCount)
|
|
} else if p.JoinType == RightOuterJoin {
|
|
count = math.Max(count, rightProfile.RowCount)
|
|
}
|
|
cardinality := make(map[int64]float64, selfSchema.Len())
|
|
for id, c := range leftProfile.Cardinality {
|
|
cardinality[id] = math.Min(c, count)
|
|
}
|
|
for id, c := range rightProfile.Cardinality {
|
|
cardinality[id] = math.Min(c, count)
|
|
}
|
|
p.stats = &property.StatsInfo{
|
|
RowCount: count,
|
|
Cardinality: cardinality,
|
|
}
|
|
return p.stats, nil
|
|
}
|
|
|
|
type fullJoinRowCountHelper struct {
|
|
cartesian bool
|
|
leftProfile *property.StatsInfo
|
|
rightProfile *property.StatsInfo
|
|
leftJoinKeys []*expression.Column
|
|
rightJoinKeys []*expression.Column
|
|
leftSchema *expression.Schema
|
|
rightSchema *expression.Schema
|
|
}
|
|
|
|
func (h *fullJoinRowCountHelper) estimate() float64 {
|
|
if h.cartesian {
|
|
return h.leftProfile.RowCount * h.rightProfile.RowCount
|
|
}
|
|
leftKeyCardinality := getCardinality(h.leftJoinKeys, h.leftSchema, h.leftProfile)
|
|
rightKeyCardinality := getCardinality(h.rightJoinKeys, h.rightSchema, h.rightProfile)
|
|
count := h.leftProfile.RowCount * h.rightProfile.RowCount / math.Max(leftKeyCardinality, rightKeyCardinality)
|
|
return count
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (la *LogicalApply) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
leftProfile := childStats[0]
|
|
la.stats = &property.StatsInfo{
|
|
RowCount: leftProfile.RowCount,
|
|
Cardinality: make(map[int64]float64, selfSchema.Len()),
|
|
}
|
|
for id, c := range leftProfile.Cardinality {
|
|
la.stats.Cardinality[id] = c
|
|
}
|
|
if la.JoinType == LeftOuterSemiJoin || la.JoinType == AntiLeftOuterSemiJoin {
|
|
la.stats.Cardinality[selfSchema.Columns[selfSchema.Len()-1].UniqueID] = 2.0
|
|
} else {
|
|
for i := childSchema[0].Len(); i < selfSchema.Len(); i++ {
|
|
la.stats.Cardinality[selfSchema.Columns[i].UniqueID] = leftProfile.RowCount
|
|
}
|
|
}
|
|
return la.stats, nil
|
|
}
|
|
|
|
// Exists and MaxOneRow produce at most one row, so we set the RowCount of stats one.
|
|
func getSingletonStats(schema *expression.Schema) *property.StatsInfo {
|
|
ret := &property.StatsInfo{
|
|
RowCount: 1.0,
|
|
Cardinality: make(map[int64]float64, schema.Len()),
|
|
}
|
|
for _, col := range schema.Columns {
|
|
ret.Cardinality[col.UniqueID] = 1
|
|
}
|
|
return ret
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (p *LogicalMaxOneRow) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
p.stats = getSingletonStats(selfSchema)
|
|
return p.stats, nil
|
|
}
|
|
|
|
// DeriveStats implement LogicalPlan DeriveStats interface.
|
|
func (p *LogicalWindow) DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) {
|
|
childProfile := childStats[0]
|
|
p.stats = &property.StatsInfo{
|
|
RowCount: childProfile.RowCount,
|
|
Cardinality: make(map[int64]float64, selfSchema.Len()),
|
|
}
|
|
childLen := selfSchema.Len() - len(p.WindowFuncDescs)
|
|
for i := 0; i < childLen; i++ {
|
|
id := selfSchema.Columns[i].UniqueID
|
|
p.stats.Cardinality[id] = childProfile.Cardinality[id]
|
|
}
|
|
for i := childLen; i < selfSchema.Len(); i++ {
|
|
p.stats.Cardinality[selfSchema.Columns[i].UniqueID] = childProfile.RowCount
|
|
}
|
|
return p.stats, nil
|
|
}
|
|
|