// Copyright 2015 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 ( "fmt" "math" "strconv" "github.com/cznic/mathutil" "github.com/pingcap/tidb/expression" "github.com/pingcap/tidb/kv" "github.com/pingcap/tidb/planner/property" "github.com/pingcap/tidb/planner/util" "github.com/pingcap/tidb/sessionctx" "github.com/pingcap/tidb/types" "github.com/pingcap/tidb/util/stringutil" "github.com/pingcap/tipb/go-tipb" ) // Plan is the description of an execution flow. // It is created from ast.Node first, then optimized by the optimizer, // finally used by the executor to create a Cursor which executes the statement. type Plan interface { // Get the schema. Schema() *expression.Schema // Get the ID. ID() int // TP get the plan type. TP() string // Get the ID in explain statement ExplainID() fmt.Stringer // ExplainInfo returns operator information to be explained. ExplainInfo() string // replaceExprColumns replace all the column reference in the plan's expression node. replaceExprColumns(replace map[string]*expression.Column) SCtx() sessionctx.Context // property.StatsInfo will return the property.StatsInfo for this plan. statsInfo() *property.StatsInfo // OutputNames returns the outputting names of each column. OutputNames() types.NameSlice // SetOutputNames sets the outputting name by the given slice. SetOutputNames(names types.NameSlice) SelectBlockOffset() int } func enforceProperty(p *property.PhysicalProperty, tsk task, ctx sessionctx.Context) task { if p.IsEmpty() || tsk.plan() == nil { return tsk } tsk = finishCopTask(ctx, tsk) sortReqProp := &property.PhysicalProperty{TaskTp: property.RootTaskType, Items: p.Items, ExpectedCnt: math.MaxFloat64} sort := PhysicalSort{ByItems: make([]*util.ByItems, 0, len(p.Items))}.Init(ctx, tsk.plan().statsInfo(), tsk.plan().SelectBlockOffset(), sortReqProp) for _, col := range p.Items { sort.ByItems = append(sort.ByItems, &util.ByItems{Expr: col.Col, Desc: col.Desc}) } return sort.attach2Task(tsk) } // optimizeByShuffle insert `PhysicalShuffle` to optimize performance by running in a parallel manner. func optimizeByShuffle(pp PhysicalPlan, tsk task, ctx sessionctx.Context) task { if tsk.plan() == nil { return tsk } // Don't use `tsk.plan()` here, which will probably be different from `pp`. // Eg., when `pp` is `NominalSort`, `tsk.plan()` would be its child. switch p := pp.(type) { case *PhysicalWindow: if shuffle := optimizeByShuffle4Window(p, ctx); shuffle != nil { return shuffle.attach2Task(tsk) } } return tsk } func optimizeByShuffle4Window(pp *PhysicalWindow, ctx sessionctx.Context) *PhysicalShuffle { concurrency := ctx.GetSessionVars().WindowConcurrency if concurrency <= 1 { return nil } sort, ok := pp.Children()[0].(*PhysicalSort) if !ok { // Multi-thread executing on SORTED data source is not effective enough by current implementation. // TODO: Implement a better one. return nil } tail, dataSource := sort, sort.Children()[0] partitionBy := make([]*expression.Column, 0, len(pp.PartitionBy)) for _, item := range pp.PartitionBy { partitionBy = append(partitionBy, item.Col) } NDV := int(getCardinality(partitionBy, dataSource.Schema(), dataSource.statsInfo())) if NDV <= 1 { return nil } concurrency = mathutil.Min(concurrency, NDV) byItems := make([]expression.Expression, 0, len(pp.PartitionBy)) for _, item := range pp.PartitionBy { byItems = append(byItems, item.Col) } reqProp := &property.PhysicalProperty{ExpectedCnt: math.MaxFloat64} shuffle := PhysicalShuffle{ Concurrency: concurrency, Tail: tail, DataSource: dataSource, SplitterType: PartitionHashSplitterType, HashByItems: byItems, }.Init(ctx, pp.statsInfo(), pp.SelectBlockOffset(), reqProp) return shuffle } // LogicalPlan is a tree of logical operators. // We can do a lot of logical optimizations to it, like predicate pushdown and column pruning. type LogicalPlan interface { Plan // HashCode encodes a LogicalPlan to fast compare whether a LogicalPlan equals to another. // We use a strict encode method here which ensures there is no conflict. HashCode() []byte // PredicatePushDown pushes down the predicates in the where/on/having clauses as deeply as possible. // It will accept a predicate that is an expression slice, and return the expressions that can't be pushed. // Because it might change the root if the having clause exists, we need to return a plan that represents a new root. PredicatePushDown([]expression.Expression) ([]expression.Expression, LogicalPlan) // PruneColumns prunes the unused columns. PruneColumns([]*expression.Column) error // findBestTask converts the logical plan to the physical plan. It's a new interface. // It is called recursively from the parent to the children to create the result physical plan. // Some logical plans will convert the children to the physical plans in different ways, and return the one // with the lowest cost. findBestTask(prop *property.PhysicalProperty) (task, error) // BuildKeyInfo will collect the information of unique keys into schema. // Because this method is also used in cascades planner, we cannot use // things like `p.schema` or `p.children` inside it. We should use the `selfSchema` // and `childSchema` instead. BuildKeyInfo(selfSchema *expression.Schema, childSchema []*expression.Schema) // pushDownTopN will push down the topN or limit operator during logical optimization. pushDownTopN(topN *LogicalTopN) LogicalPlan // recursiveDeriveStats derives statistic info between plans. recursiveDeriveStats() (*property.StatsInfo, error) // DeriveStats derives statistic info for current plan node given child stats. // We need selfSchema, childSchema here because it makes this method can be used in // cascades planner, where LogicalPlan might not record its children or schema. DeriveStats(childStats []*property.StatsInfo, selfSchema *expression.Schema, childSchema []*expression.Schema) (*property.StatsInfo, error) // PreparePossibleProperties is only used for join and aggregation. Like group by a,b,c, all permutation of (a,b,c) is // valid, but the ordered indices in leaf plan is limited. So we can get all possible order properties by a pre-walking. PreparePossibleProperties(schema *expression.Schema, childrenProperties ...[][]*expression.Column) [][]*expression.Column // exhaustPhysicalPlans generates all possible plans that can match the required property. // It will return: // 1. All possible plans that can match the required property. // 2. Whether the SQL hint can work. Return true if there is no hint. exhaustPhysicalPlans(*property.PhysicalProperty) (physicalPlans []PhysicalPlan, hintCanWork bool) // ExtractCorrelatedCols extracts correlated columns inside the LogicalPlan. ExtractCorrelatedCols() []*expression.CorrelatedColumn // MaxOneRow means whether this operator only returns max one row. MaxOneRow() bool // Get all the children. Children() []LogicalPlan // SetChildren sets the children for the plan. SetChildren(...LogicalPlan) // SetChild sets the ith child for the plan. SetChild(i int, child LogicalPlan) } // PhysicalPlan is a tree of the physical operators. type PhysicalPlan interface { Plan // attach2Task makes the current physical plan as the father of task's physicalPlan and updates the cost of // current task. If the child's task is cop task, some operator may close this task and return a new rootTask. attach2Task(...task) task // ToPB converts physical plan to tipb executor. ToPB(ctx sessionctx.Context, storeType kv.StoreType) (*tipb.Executor, error) // getChildReqProps gets the required property by child index. GetChildReqProps(idx int) *property.PhysicalProperty // StatsCount returns the count of property.StatsInfo for this plan. StatsCount() float64 // Get all the children. Children() []PhysicalPlan // SetChildren sets the children for the plan. SetChildren(...PhysicalPlan) // SetChild sets the ith child for the plan. SetChild(i int, child PhysicalPlan) // ResolveIndices resolves the indices for columns. After doing this, the columns can evaluate the rows by their indices. ResolveIndices() error // Stats returns the StatsInfo of the plan. Stats() *property.StatsInfo // ExplainNormalizedInfo returns operator normalized information for generating digest. ExplainNormalizedInfo() string } type baseLogicalPlan struct { basePlan taskMap map[string]task self LogicalPlan maxOneRow bool children []LogicalPlan } func (p *baseLogicalPlan) MaxOneRow() bool { return p.maxOneRow } // ExplainInfo implements Plan interface. func (p *baseLogicalPlan) ExplainInfo() string { return "" } type basePhysicalPlan struct { basePlan childrenReqProps []*property.PhysicalProperty self PhysicalPlan children []PhysicalPlan } // ExplainInfo implements Plan interface. func (p *basePhysicalPlan) ExplainInfo() string { return "" } // ExplainInfo implements Plan interface. func (p *basePhysicalPlan) ExplainNormalizedInfo() string { return "" } func (p *basePhysicalPlan) GetChildReqProps(idx int) *property.PhysicalProperty { return p.childrenReqProps[idx] } func (p *baseLogicalPlan) getTask(prop *property.PhysicalProperty) task { key := prop.HashCode() return p.taskMap[string(key)] } func (p *baseLogicalPlan) storeTask(prop *property.PhysicalProperty, task task) { key := prop.HashCode() p.taskMap[string(key)] = task } // HasMaxOneRow returns if the LogicalPlan will output at most one row. func HasMaxOneRow(p LogicalPlan, childMaxOneRow []bool) bool { if len(childMaxOneRow) == 0 { // The reason why we use this check is that, this function // is used both in planner/core and planner/cascades. // In cascades planner, LogicalPlan may have no `children`. return false } switch x := p.(type) { case *LogicalLock, *LogicalLimit, *LogicalSort, *LogicalSelection, *LogicalApply, *LogicalProjection, *LogicalWindow, *LogicalAggregation: return childMaxOneRow[0] case *LogicalMaxOneRow: return true case *LogicalJoin: switch x.JoinType { case SemiJoin, AntiSemiJoin, LeftOuterSemiJoin, AntiLeftOuterSemiJoin: return childMaxOneRow[0] default: return childMaxOneRow[0] && childMaxOneRow[1] } } return false } // BuildKeyInfo implements LogicalPlan BuildKeyInfo interface. func (p *baseLogicalPlan) BuildKeyInfo(selfSchema *expression.Schema, childSchema []*expression.Schema) { childMaxOneRow := make([]bool, len(p.children)) for i := range p.children { childMaxOneRow[i] = p.children[i].MaxOneRow() } p.maxOneRow = HasMaxOneRow(p.self, childMaxOneRow) } // BuildKeyInfo implements LogicalPlan BuildKeyInfo interface. func (p *logicalSchemaProducer) BuildKeyInfo(selfSchema *expression.Schema, childSchema []*expression.Schema) { selfSchema.Keys = nil p.baseLogicalPlan.BuildKeyInfo(selfSchema, childSchema) } func newBasePlan(ctx sessionctx.Context, tp string, offset int) basePlan { ctx.GetSessionVars().PlanID++ id := ctx.GetSessionVars().PlanID return basePlan{ tp: tp, id: id, ctx: ctx, blockOffset: offset, } } func newBaseLogicalPlan(ctx sessionctx.Context, tp string, self LogicalPlan, offset int) baseLogicalPlan { return baseLogicalPlan{ taskMap: make(map[string]task), basePlan: newBasePlan(ctx, tp, offset), self: self, } } func newBasePhysicalPlan(ctx sessionctx.Context, tp string, self PhysicalPlan, offset int) basePhysicalPlan { return basePhysicalPlan{ basePlan: newBasePlan(ctx, tp, offset), self: self, } } func (p *baseLogicalPlan) ExtractCorrelatedCols() []*expression.CorrelatedColumn { return nil } // PruneColumns implements LogicalPlan interface. func (p *baseLogicalPlan) PruneColumns(parentUsedCols []*expression.Column) error { if len(p.children) == 0 { return nil } return p.children[0].PruneColumns(parentUsedCols) } // basePlan implements base Plan interface. // Should be used as embedded struct in Plan implementations. type basePlan struct { tp string id int ctx sessionctx.Context stats *property.StatsInfo blockOffset int } // OutputNames returns the outputting names of each column. func (p *basePlan) OutputNames() types.NameSlice { return nil } func (p *basePlan) SetOutputNames(names types.NameSlice) { } func (p *basePlan) replaceExprColumns(replace map[string]*expression.Column) { } // ID implements Plan ID interface. func (p *basePlan) ID() int { return p.id } // property.StatsInfo implements the Plan interface. func (p *basePlan) statsInfo() *property.StatsInfo { return p.stats } // ExplainInfo implements Plan interface. func (p *basePlan) ExplainInfo() string { return "N/A" } func (p *basePlan) ExplainID() fmt.Stringer { return stringutil.MemoizeStr(func() string { return p.tp + "_" + strconv.Itoa(p.id) }) } // TP implements Plan interface. func (p *basePlan) TP() string { return p.tp } func (p *basePlan) SelectBlockOffset() int { return p.blockOffset } // Stats implements Plan Stats interface. func (p *basePlan) Stats() *property.StatsInfo { return p.stats } // Schema implements Plan Schema interface. func (p *baseLogicalPlan) Schema() *expression.Schema { return p.children[0].Schema() } func (p *baseLogicalPlan) OutputNames() types.NameSlice { return p.children[0].OutputNames() } func (p *baseLogicalPlan) SetOutputNames(names types.NameSlice) { p.children[0].SetOutputNames(names) } // Schema implements Plan Schema interface. func (p *basePhysicalPlan) Schema() *expression.Schema { return p.children[0].Schema() } // Children implements LogicalPlan Children interface. func (p *baseLogicalPlan) Children() []LogicalPlan { return p.children } // Children implements PhysicalPlan Children interface. func (p *basePhysicalPlan) Children() []PhysicalPlan { return p.children } // SetChildren implements LogicalPlan SetChildren interface. func (p *baseLogicalPlan) SetChildren(children ...LogicalPlan) { p.children = children } // SetChildren implements PhysicalPlan SetChildren interface. func (p *basePhysicalPlan) SetChildren(children ...PhysicalPlan) { p.children = children } // SetChild implements LogicalPlan SetChild interface. func (p *baseLogicalPlan) SetChild(i int, child LogicalPlan) { p.children[i] = child } // SetChild implements PhysicalPlan SetChild interface. func (p *basePhysicalPlan) SetChild(i int, child PhysicalPlan) { p.children[i] = child } // Context implements Plan Context interface. func (p *basePlan) SCtx() sessionctx.Context { return p.ctx }