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.
2319 lines
88 KiB
2319 lines
88 KiB
// Copyright 2018 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 cascades
|
|
|
|
import (
|
|
"math"
|
|
|
|
"github.com/pingcap/parser/ast"
|
|
"github.com/pingcap/parser/mysql"
|
|
"github.com/pingcap/tidb/expression"
|
|
"github.com/pingcap/tidb/expression/aggregation"
|
|
"github.com/pingcap/tidb/kv"
|
|
plannercore "github.com/pingcap/tidb/planner/core"
|
|
"github.com/pingcap/tidb/planner/memo"
|
|
"github.com/pingcap/tidb/planner/util"
|
|
"github.com/pingcap/tidb/sessionctx"
|
|
"github.com/pingcap/tidb/types"
|
|
"github.com/pingcap/tidb/util/ranger"
|
|
"github.com/pingcap/tidb/util/set"
|
|
)
|
|
|
|
// Transformation defines the interface for the transformation rules.
|
|
type Transformation interface {
|
|
// GetPattern gets the cached pattern of the rule.
|
|
GetPattern() *memo.Pattern
|
|
// Match is used to check whether the GroupExpr satisfies all the requirements of the transformation rule.
|
|
//
|
|
// The pattern only identifies the operator type, some transformation rules also need
|
|
// detailed information for certain plan operators to decide whether it is applicable.
|
|
Match(expr *memo.ExprIter) bool
|
|
// OnTransform does the real work of the optimization rule.
|
|
//
|
|
// newExprs indicates the new GroupExprs generated by the transformationrule. Multiple GroupExprs may be
|
|
// returned, e.g, EnumeratePath would convert DataSource to several possible assess paths.
|
|
//
|
|
// eraseOld indicates that the returned GroupExpr must be better than the old one, so we can remove it from Group.
|
|
//
|
|
// eraseAll indicates that the returned GroupExpr must be better than all other candidates in the Group, e.g, we can
|
|
// prune all other access paths if we found the filter is constantly false.
|
|
OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error)
|
|
}
|
|
|
|
// TransformationRuleBatch is a batch of transformation rules.
|
|
type TransformationRuleBatch map[memo.Operand][]Transformation
|
|
|
|
// DefaultRuleBatches contain all the transformation rules.
|
|
// Each batch will be applied to the memo independently.
|
|
var DefaultRuleBatches = []TransformationRuleBatch{
|
|
TiDBLayerOptimizationBatch,
|
|
TiKVLayerOptimizationBatch,
|
|
PostTransformationBatch,
|
|
}
|
|
|
|
// TiDBLayerOptimizationBatch does the optimization in the TiDB layer.
|
|
var TiDBLayerOptimizationBatch = TransformationRuleBatch{
|
|
memo.OperandSelection: {
|
|
NewRulePushSelDownSort(),
|
|
NewRulePushSelDownProjection(),
|
|
NewRulePushSelDownAggregation(),
|
|
NewRulePushSelDownJoin(),
|
|
NewRulePushSelDownUnionAll(),
|
|
NewRulePushSelDownWindow(),
|
|
NewRuleMergeAdjacentSelection(),
|
|
},
|
|
memo.OperandAggregation: {
|
|
NewRuleMergeAggregationProjection(),
|
|
NewRuleEliminateSingleMaxMin(),
|
|
NewRuleEliminateOuterJoinBelowAggregation(),
|
|
NewRuleTransformAggregateCaseToSelection(),
|
|
NewRuleTransformAggToProj(),
|
|
},
|
|
memo.OperandLimit: {
|
|
NewRuleTransformLimitToTopN(),
|
|
NewRulePushLimitDownProjection(),
|
|
NewRulePushLimitDownUnionAll(),
|
|
NewRulePushLimitDownOuterJoin(),
|
|
NewRuleMergeAdjacentLimit(),
|
|
NewRuleTransformLimitToTableDual(),
|
|
},
|
|
memo.OperandProjection: {
|
|
NewRuleEliminateProjection(),
|
|
NewRuleMergeAdjacentProjection(),
|
|
NewRuleEliminateOuterJoinBelowProjection(),
|
|
},
|
|
memo.OperandTopN: {
|
|
NewRulePushTopNDownProjection(),
|
|
NewRulePushTopNDownOuterJoin(),
|
|
NewRulePushTopNDownUnionAll(),
|
|
NewRuleMergeAdjacentTopN(),
|
|
},
|
|
memo.OperandApply: {
|
|
NewRuleTransformApplyToJoin(),
|
|
NewRulePullSelectionUpApply(),
|
|
},
|
|
}
|
|
|
|
// TiKVLayerOptimizationBatch does the optimization related to TiKV layer.
|
|
// For example, rules about pushing down Operators like Selection, Limit,
|
|
// Aggregation into TiKV layer should be inside this batch.
|
|
var TiKVLayerOptimizationBatch = TransformationRuleBatch{
|
|
memo.OperandDataSource: {
|
|
NewRuleEnumeratePaths(),
|
|
},
|
|
memo.OperandSelection: {
|
|
NewRulePushSelDownTiKVSingleGather(),
|
|
NewRulePushSelDownTableScan(),
|
|
NewRulePushSelDownIndexScan(),
|
|
NewRuleMergeAdjacentSelection(),
|
|
},
|
|
memo.OperandAggregation: {
|
|
NewRulePushAggDownGather(),
|
|
},
|
|
memo.OperandLimit: {
|
|
NewRulePushLimitDownTiKVSingleGather(),
|
|
},
|
|
memo.OperandTopN: {
|
|
NewRulePushTopNDownTiKVSingleGather(),
|
|
},
|
|
}
|
|
|
|
// PostTransformationBatch does the transformation which is related to
|
|
// the constraints of the execution engine of TiDB.
|
|
// For example, TopN/Sort only support `order by` columns in TiDB layer,
|
|
// as for scalar functions, we need to inject a Projection for them
|
|
// below the TopN/Sort.
|
|
var PostTransformationBatch = TransformationRuleBatch{
|
|
memo.OperandProjection: {
|
|
NewRuleEliminateProjection(),
|
|
NewRuleMergeAdjacentProjection(),
|
|
},
|
|
memo.OperandTopN: {
|
|
NewRuleInjectProjectionBelowTopN(),
|
|
},
|
|
}
|
|
|
|
type baseRule struct {
|
|
pattern *memo.Pattern
|
|
}
|
|
|
|
// Match implements Transformation Interface.
|
|
func (r *baseRule) Match(expr *memo.ExprIter) bool {
|
|
return true
|
|
}
|
|
|
|
// GetPattern implements Transformation Interface.
|
|
func (r *baseRule) GetPattern() *memo.Pattern {
|
|
return r.pattern
|
|
}
|
|
|
|
// PushSelDownTableScan pushes the selection down to TableScan.
|
|
type PushSelDownTableScan struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushSelDownTableScan creates a new Transformation PushSelDownTableScan.
|
|
// The pattern of this rule is: `Selection -> TableScan`
|
|
func NewRulePushSelDownTableScan() Transformation {
|
|
rule := &PushSelDownTableScan{}
|
|
ts := memo.NewPattern(memo.OperandTableScan, memo.EngineTiKVOrTiFlash)
|
|
p := memo.BuildPattern(memo.OperandSelection, memo.EngineTiKVOrTiFlash, ts)
|
|
rule.pattern = p
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
//
|
|
// It transforms `sel -> ts` to one of the following new exprs:
|
|
// 1. `newSel -> newTS`
|
|
// 2. `newTS`
|
|
//
|
|
// Filters of the old `sel` operator are removed if they are used to calculate
|
|
// the key ranges of the `ts` operator.
|
|
func (r *PushSelDownTableScan) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
sel := old.GetExpr().ExprNode.(*plannercore.LogicalSelection)
|
|
ts := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalTableScan)
|
|
if ts.Handle == nil {
|
|
return nil, false, false, nil
|
|
}
|
|
accesses, remained := ranger.DetachCondsForColumn(ts.SCtx(), sel.Conditions, ts.Handle)
|
|
if accesses == nil {
|
|
return nil, false, false, nil
|
|
}
|
|
newTblScan := plannercore.LogicalTableScan{
|
|
Source: ts.Source,
|
|
Handle: ts.Handle,
|
|
AccessConds: ts.AccessConds.Shallow(),
|
|
}.Init(ts.SCtx(), ts.SelectBlockOffset())
|
|
newTblScan.AccessConds = append(newTblScan.AccessConds, accesses...)
|
|
tblScanExpr := memo.NewGroupExpr(newTblScan)
|
|
if len(remained) == 0 {
|
|
// `sel -> ts` is transformed to `newTS`.
|
|
return []*memo.GroupExpr{tblScanExpr}, true, false, nil
|
|
}
|
|
schema := old.GetExpr().Group.Prop.Schema
|
|
tblScanGroup := memo.NewGroupWithSchema(tblScanExpr, schema)
|
|
newSel := plannercore.LogicalSelection{Conditions: remained}.Init(sel.SCtx(), sel.SelectBlockOffset())
|
|
selExpr := memo.NewGroupExpr(newSel)
|
|
selExpr.Children = append(selExpr.Children, tblScanGroup)
|
|
// `sel -> ts` is transformed to `newSel ->newTS`.
|
|
return []*memo.GroupExpr{selExpr}, true, false, nil
|
|
}
|
|
|
|
// PushSelDownIndexScan pushes a Selection down to IndexScan.
|
|
type PushSelDownIndexScan struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushSelDownIndexScan creates a new Transformation PushSelDownIndexScan.
|
|
// The pattern of this rule is `Selection -> IndexScan`.
|
|
func NewRulePushSelDownIndexScan() Transformation {
|
|
rule := &PushSelDownIndexScan{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandSelection,
|
|
memo.EngineTiKVOnly,
|
|
memo.NewPattern(memo.OperandIndexScan, memo.EngineTiKVOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// It will transform `Selection -> IndexScan` to:
|
|
//
|
|
// `IndexScan(with a new access range)` or
|
|
// `Selection -> IndexScan(with a new access range)`
|
|
// or just keep the two GroupExprs unchanged.
|
|
func (r *PushSelDownIndexScan) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
sel := old.GetExpr().ExprNode.(*plannercore.LogicalSelection)
|
|
is := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalIndexScan)
|
|
if len(is.IdxCols) == 0 {
|
|
return nil, false, false, nil
|
|
}
|
|
conditions := sel.Conditions
|
|
if is.AccessConds != nil {
|
|
// If we have already pushed some conditions down here,
|
|
// we merge old AccessConds with new conditions,
|
|
// to make sure this rule can be applied more than once.
|
|
conditions = make([]expression.Expression, len(sel.Conditions)+len(is.AccessConds))
|
|
copy(conditions, sel.Conditions)
|
|
copy(conditions[len(sel.Conditions):], is.AccessConds)
|
|
}
|
|
res, err := ranger.DetachCondAndBuildRangeForIndex(is.SCtx(), conditions, is.IdxCols, is.IdxColLens)
|
|
if err != nil {
|
|
return nil, false, false, err
|
|
}
|
|
if len(res.AccessConds) == len(is.AccessConds) {
|
|
// There is no condition can be pushed down as range,
|
|
// or the pushed down conditions are the same with before.
|
|
sameConds := true
|
|
for i := range res.AccessConds {
|
|
if !res.AccessConds[i].Equal(is.SCtx(), is.AccessConds[i]) {
|
|
sameConds = false
|
|
break
|
|
}
|
|
}
|
|
if sameConds {
|
|
return nil, false, false, nil
|
|
}
|
|
}
|
|
// TODO: `res` still has some unused fields: EqOrInCount, IsDNFCond.
|
|
newIs := plannercore.LogicalIndexScan{
|
|
Source: is.Source,
|
|
IsDoubleRead: is.IsDoubleRead,
|
|
EqCondCount: res.EqCondCount,
|
|
AccessConds: res.AccessConds,
|
|
Ranges: res.Ranges,
|
|
Index: is.Index,
|
|
Columns: is.Columns,
|
|
FullIdxCols: is.FullIdxCols,
|
|
FullIdxColLens: is.FullIdxColLens,
|
|
IdxCols: is.IdxCols,
|
|
IdxColLens: is.IdxColLens,
|
|
}.Init(is.SCtx(), is.SelectBlockOffset())
|
|
isExpr := memo.NewGroupExpr(newIs)
|
|
|
|
if len(res.RemainedConds) == 0 {
|
|
return []*memo.GroupExpr{isExpr}, true, false, nil
|
|
}
|
|
isGroup := memo.NewGroupWithSchema(isExpr, old.Children[0].GetExpr().Group.Prop.Schema)
|
|
newSel := plannercore.LogicalSelection{Conditions: res.RemainedConds}.Init(sel.SCtx(), sel.SelectBlockOffset())
|
|
selExpr := memo.NewGroupExpr(newSel)
|
|
selExpr.SetChildren(isGroup)
|
|
return []*memo.GroupExpr{selExpr}, true, false, nil
|
|
}
|
|
|
|
// PushSelDownTiKVSingleGather pushes the selection down to child of TiKVSingleGather.
|
|
type PushSelDownTiKVSingleGather struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushSelDownTiKVSingleGather creates a new Transformation PushSelDownTiKVSingleGather.
|
|
// The pattern of this rule is `Selection -> TiKVSingleGather -> Any`.
|
|
func NewRulePushSelDownTiKVSingleGather() Transformation {
|
|
any := memo.NewPattern(memo.OperandAny, memo.EngineTiKVOrTiFlash)
|
|
tg := memo.BuildPattern(memo.OperandTiKVSingleGather, memo.EngineTiDBOnly, any)
|
|
p := memo.BuildPattern(memo.OperandSelection, memo.EngineTiDBOnly, tg)
|
|
|
|
rule := &PushSelDownTiKVSingleGather{}
|
|
rule.pattern = p
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
//
|
|
// It transforms `oldSel -> oldTg -> any` to one of the following new exprs:
|
|
// 1. `newTg -> pushedSel -> any`
|
|
// 2. `remainedSel -> newTg -> pushedSel -> any`
|
|
func (r *PushSelDownTiKVSingleGather) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
sel := old.GetExpr().ExprNode.(*plannercore.LogicalSelection)
|
|
sg := old.Children[0].GetExpr().ExprNode.(*plannercore.TiKVSingleGather)
|
|
childGroup := old.Children[0].Children[0].Group
|
|
var pushed, remained []expression.Expression
|
|
sctx := sg.SCtx()
|
|
pushed, remained = expression.PushDownExprs(sctx.GetSessionVars().StmtCtx, sel.Conditions, sctx.GetClient(), kv.TiKV)
|
|
if len(pushed) == 0 {
|
|
return nil, false, false, nil
|
|
}
|
|
pushedSel := plannercore.LogicalSelection{Conditions: pushed}.Init(sctx, sel.SelectBlockOffset())
|
|
pushedSelExpr := memo.NewGroupExpr(pushedSel)
|
|
pushedSelExpr.Children = append(pushedSelExpr.Children, childGroup)
|
|
pushedSelGroup := memo.NewGroupWithSchema(pushedSelExpr, childGroup.Prop.Schema).SetEngineType(childGroup.EngineType)
|
|
// The field content of TiKVSingleGather would not be modified currently, so we
|
|
// just reference the same tg instead of making a copy of it.
|
|
//
|
|
// TODO: if we save pushed filters later in TiKVSingleGather, in order to do partition
|
|
// pruning or skyline pruning, we need to make a copy of the TiKVSingleGather here.
|
|
tblGatherExpr := memo.NewGroupExpr(sg)
|
|
tblGatherExpr.Children = append(tblGatherExpr.Children, pushedSelGroup)
|
|
if len(remained) == 0 {
|
|
// `oldSel -> oldTg -> any` is transformed to `newTg -> pushedSel -> any`.
|
|
return []*memo.GroupExpr{tblGatherExpr}, true, false, nil
|
|
}
|
|
tblGatherGroup := memo.NewGroupWithSchema(tblGatherExpr, pushedSelGroup.Prop.Schema)
|
|
remainedSel := plannercore.LogicalSelection{Conditions: remained}.Init(sel.SCtx(), sel.SelectBlockOffset())
|
|
remainedSelExpr := memo.NewGroupExpr(remainedSel)
|
|
remainedSelExpr.Children = append(remainedSelExpr.Children, tblGatherGroup)
|
|
// `oldSel -> oldTg -> any` is transformed to `remainedSel -> newTg -> pushedSel -> any`.
|
|
return []*memo.GroupExpr{remainedSelExpr}, true, false, nil
|
|
}
|
|
|
|
// EnumeratePaths converts DataSource to table scan and index scans.
|
|
type EnumeratePaths struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRuleEnumeratePaths creates a new Transformation EnumeratePaths.
|
|
// The pattern of this rule is: `DataSource`.
|
|
func NewRuleEnumeratePaths() Transformation {
|
|
rule := &EnumeratePaths{}
|
|
rule.pattern = memo.NewPattern(memo.OperandDataSource, memo.EngineTiDBOnly)
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
func (r *EnumeratePaths) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
ds := old.GetExpr().ExprNode.(*plannercore.DataSource)
|
|
gathers := ds.Convert2Gathers()
|
|
for _, gather := range gathers {
|
|
expr := memo.Convert2GroupExpr(gather)
|
|
expr.Children[0].SetEngineType(memo.EngineTiKV)
|
|
newExprs = append(newExprs, expr)
|
|
}
|
|
return newExprs, true, false, nil
|
|
}
|
|
|
|
// PushAggDownGather splits Aggregation to two stages, final and partial1,
|
|
// and pushed the partial Aggregation down to the child of TiKVSingleGather.
|
|
type PushAggDownGather struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushAggDownGather creates a new Transformation PushAggDownGather.
|
|
// The pattern of this rule is: `Aggregation -> TiKVSingleGather`.
|
|
func NewRulePushAggDownGather() Transformation {
|
|
rule := &PushAggDownGather{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandAggregation,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandTiKVSingleGather, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
func (r *PushAggDownGather) Match(expr *memo.ExprIter) bool {
|
|
if expr.GetExpr().HasAppliedRule(r) {
|
|
return false
|
|
}
|
|
agg := expr.GetExpr().ExprNode.(*plannercore.LogicalAggregation)
|
|
for _, aggFunc := range agg.AggFuncs {
|
|
if aggFunc.Mode != aggregation.CompleteMode {
|
|
return false
|
|
}
|
|
}
|
|
if agg.HasDistinct() {
|
|
// TODO: remove this logic after the cost estimation of distinct pushdown is implemented.
|
|
// If AllowDistinctAggPushDown is set to true, we should not consider RootTask.
|
|
if !agg.SCtx().GetSessionVars().AllowDistinctAggPushDown {
|
|
return false
|
|
}
|
|
}
|
|
childEngine := expr.Children[0].GetExpr().Children[0].EngineType
|
|
if childEngine != memo.EngineTiKV {
|
|
// TODO: Remove this check when we have implemented TiFlashAggregation.
|
|
return false
|
|
}
|
|
return plannercore.CheckAggCanPushCop(agg.SCtx(), agg.AggFuncs, agg.GroupByItems, kv.TiKV)
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// It will transform `Agg->Gather` to `Agg(Final) -> Gather -> Agg(Partial1)`.
|
|
func (r *PushAggDownGather) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
agg := old.GetExpr().ExprNode.(*plannercore.LogicalAggregation)
|
|
aggSchema := old.GetExpr().Group.Prop.Schema
|
|
gather := old.Children[0].GetExpr().ExprNode.(*plannercore.TiKVSingleGather)
|
|
childGroup := old.Children[0].GetExpr().Children[0]
|
|
// The old Aggregation should stay unchanged for other transformation.
|
|
// So we build a new LogicalAggregation for the partialAgg.
|
|
aggFuncs := make([]*aggregation.AggFuncDesc, len(agg.AggFuncs))
|
|
for i := range agg.AggFuncs {
|
|
aggFuncs[i] = agg.AggFuncs[i].Clone()
|
|
}
|
|
gbyItems := make([]expression.Expression, len(agg.GroupByItems))
|
|
copy(gbyItems, agg.GroupByItems)
|
|
|
|
partialPref, finalPref, funcMap := plannercore.BuildFinalModeAggregation(agg.SCtx(),
|
|
&plannercore.AggInfo{
|
|
AggFuncs: aggFuncs,
|
|
GroupByItems: gbyItems,
|
|
Schema: aggSchema,
|
|
}, true)
|
|
// Remove unnecessary FirstRow.
|
|
partialPref.AggFuncs =
|
|
plannercore.RemoveUnnecessaryFirstRow(agg.SCtx(), finalPref.AggFuncs, finalPref.GroupByItems, partialPref.AggFuncs, partialPref.GroupByItems, partialPref.Schema, funcMap)
|
|
|
|
partialAgg := plannercore.LogicalAggregation{
|
|
AggFuncs: partialPref.AggFuncs,
|
|
GroupByItems: partialPref.GroupByItems,
|
|
}.Init(agg.SCtx(), agg.SelectBlockOffset())
|
|
partialAgg.CopyAggHints(agg)
|
|
|
|
finalAgg := plannercore.LogicalAggregation{
|
|
AggFuncs: finalPref.AggFuncs,
|
|
GroupByItems: finalPref.GroupByItems,
|
|
}.Init(agg.SCtx(), agg.SelectBlockOffset())
|
|
finalAgg.CopyAggHints(agg)
|
|
|
|
partialAggExpr := memo.NewGroupExpr(partialAgg)
|
|
partialAggExpr.SetChildren(childGroup)
|
|
partialAggGroup := memo.NewGroupWithSchema(partialAggExpr, partialPref.Schema).SetEngineType(childGroup.EngineType)
|
|
gatherExpr := memo.NewGroupExpr(gather)
|
|
gatherExpr.SetChildren(partialAggGroup)
|
|
gatherGroup := memo.NewGroupWithSchema(gatherExpr, partialPref.Schema)
|
|
finalAggExpr := memo.NewGroupExpr(finalAgg)
|
|
finalAggExpr.SetChildren(gatherGroup)
|
|
finalAggExpr.AddAppliedRule(r)
|
|
// We don't erase the old complete mode Aggregation because
|
|
// this transformation would not always be better.
|
|
return []*memo.GroupExpr{finalAggExpr}, false, false, nil
|
|
}
|
|
|
|
// PushSelDownSort pushes the Selection down to the child of Sort.
|
|
type PushSelDownSort struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushSelDownSort creates a new Transformation PushSelDownSort.
|
|
// The pattern of this rule is: `Selection -> Sort`.
|
|
func NewRulePushSelDownSort() Transformation {
|
|
rule := &PushSelDownSort{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandSelection,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandSort, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// It will transform `sel->sort->x` to `sort->sel->x`.
|
|
func (r *PushSelDownSort) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
sel := old.GetExpr().ExprNode.(*plannercore.LogicalSelection)
|
|
sort := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalSort)
|
|
childGroup := old.Children[0].GetExpr().Children[0]
|
|
|
|
newSelExpr := memo.NewGroupExpr(sel)
|
|
newSelExpr.Children = append(newSelExpr.Children, childGroup)
|
|
newSelGroup := memo.NewGroupWithSchema(newSelExpr, childGroup.Prop.Schema)
|
|
|
|
newSortExpr := memo.NewGroupExpr(sort)
|
|
newSortExpr.Children = append(newSortExpr.Children, newSelGroup)
|
|
return []*memo.GroupExpr{newSortExpr}, true, false, nil
|
|
}
|
|
|
|
// PushSelDownProjection pushes the Selection down to the child of Projection.
|
|
type PushSelDownProjection struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushSelDownProjection creates a new Transformation PushSelDownProjection.
|
|
// The pattern of this rule is: `Selection -> Projection`.
|
|
func NewRulePushSelDownProjection() Transformation {
|
|
rule := &PushSelDownProjection{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandSelection,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandProjection, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// It will transform `selection -> projection -> x` to
|
|
// 1. `projection -> selection -> x` or
|
|
// 2. `selection -> projection -> selection -> x` or
|
|
// 3. just keep unchanged.
|
|
func (r *PushSelDownProjection) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
sel := old.GetExpr().ExprNode.(*plannercore.LogicalSelection)
|
|
proj := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalProjection)
|
|
projSchema := old.Children[0].Prop.Schema
|
|
childGroup := old.Children[0].GetExpr().Children[0]
|
|
for _, expr := range proj.Exprs {
|
|
if expression.HasAssignSetVarFunc(expr) {
|
|
return nil, false, false, nil
|
|
}
|
|
}
|
|
canBePushed := make([]expression.Expression, 0, len(sel.Conditions))
|
|
canNotBePushed := make([]expression.Expression, 0, len(sel.Conditions))
|
|
for _, cond := range sel.Conditions {
|
|
if !expression.HasGetSetVarFunc(cond) {
|
|
canBePushed = append(canBePushed, expression.ColumnSubstitute(cond, projSchema, proj.Exprs))
|
|
} else {
|
|
canNotBePushed = append(canNotBePushed, cond)
|
|
}
|
|
}
|
|
if len(canBePushed) == 0 {
|
|
return nil, false, false, nil
|
|
}
|
|
newBottomSel := plannercore.LogicalSelection{Conditions: canBePushed}.Init(sel.SCtx(), sel.SelectBlockOffset())
|
|
newBottomSelExpr := memo.NewGroupExpr(newBottomSel)
|
|
newBottomSelExpr.SetChildren(childGroup)
|
|
newBottomSelGroup := memo.NewGroupWithSchema(newBottomSelExpr, childGroup.Prop.Schema)
|
|
newProjExpr := memo.NewGroupExpr(proj)
|
|
newProjExpr.SetChildren(newBottomSelGroup)
|
|
if len(canNotBePushed) == 0 {
|
|
return []*memo.GroupExpr{newProjExpr}, true, false, nil
|
|
}
|
|
newProjGroup := memo.NewGroupWithSchema(newProjExpr, projSchema)
|
|
newTopSel := plannercore.LogicalSelection{Conditions: canNotBePushed}.Init(sel.SCtx(), sel.SelectBlockOffset())
|
|
newTopSelExpr := memo.NewGroupExpr(newTopSel)
|
|
newTopSelExpr.SetChildren(newProjGroup)
|
|
return []*memo.GroupExpr{newTopSelExpr}, true, false, nil
|
|
}
|
|
|
|
// PushSelDownAggregation pushes Selection down to the child of Aggregation.
|
|
type PushSelDownAggregation struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushSelDownAggregation creates a new Transformation PushSelDownAggregation.
|
|
// The pattern of this rule is `Selection -> Aggregation`.
|
|
func NewRulePushSelDownAggregation() Transformation {
|
|
rule := &PushSelDownAggregation{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandSelection,
|
|
memo.EngineAll,
|
|
memo.NewPattern(memo.OperandAggregation, memo.EngineAll),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// It will transform `sel->agg->x` to `agg->sel->x` or `sel->agg->sel->x`
|
|
// or just keep the selection unchanged.
|
|
func (r *PushSelDownAggregation) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
sel := old.GetExpr().ExprNode.(*plannercore.LogicalSelection)
|
|
agg := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalAggregation)
|
|
aggSchema := old.Children[0].Prop.Schema
|
|
var pushedExprs []expression.Expression
|
|
var remainedExprs []expression.Expression
|
|
exprsOriginal := make([]expression.Expression, 0, len(agg.AggFuncs))
|
|
for _, aggFunc := range agg.AggFuncs {
|
|
exprsOriginal = append(exprsOriginal, aggFunc.Args[0])
|
|
}
|
|
groupByColumns := expression.NewSchema(agg.GetGroupByCols()...)
|
|
for _, cond := range sel.Conditions {
|
|
switch cond.(type) {
|
|
case *expression.Constant:
|
|
// Consider SQL list "select sum(b) from t group by a having 1=0". "1=0" is a constant predicate which should be
|
|
// retained and pushed down at the same time. Because we will get a wrong query result that contains one column
|
|
// with value 0 rather than an empty query result.
|
|
pushedExprs = append(pushedExprs, cond)
|
|
remainedExprs = append(remainedExprs, cond)
|
|
case *expression.ScalarFunction:
|
|
extractedCols := expression.ExtractColumns(cond)
|
|
canPush := true
|
|
for _, col := range extractedCols {
|
|
if !groupByColumns.Contains(col) {
|
|
canPush = false
|
|
break
|
|
}
|
|
}
|
|
if canPush {
|
|
pushedExprs = append(pushedExprs, cond)
|
|
} else {
|
|
remainedExprs = append(remainedExprs, cond)
|
|
}
|
|
default:
|
|
remainedExprs = append(remainedExprs, cond)
|
|
}
|
|
}
|
|
// If no condition can be pushed, keep the selection unchanged.
|
|
if len(pushedExprs) == 0 {
|
|
return nil, false, false, nil
|
|
}
|
|
sctx := sel.SCtx()
|
|
childGroup := old.Children[0].GetExpr().Children[0]
|
|
pushedSel := plannercore.LogicalSelection{Conditions: pushedExprs}.Init(sctx, sel.SelectBlockOffset())
|
|
pushedGroupExpr := memo.NewGroupExpr(pushedSel)
|
|
pushedGroupExpr.SetChildren(childGroup)
|
|
pushedGroup := memo.NewGroupWithSchema(pushedGroupExpr, childGroup.Prop.Schema)
|
|
|
|
aggGroupExpr := memo.NewGroupExpr(agg)
|
|
aggGroupExpr.SetChildren(pushedGroup)
|
|
|
|
if len(remainedExprs) == 0 {
|
|
return []*memo.GroupExpr{aggGroupExpr}, true, false, nil
|
|
}
|
|
|
|
aggGroup := memo.NewGroupWithSchema(aggGroupExpr, aggSchema)
|
|
remainedSel := plannercore.LogicalSelection{Conditions: remainedExprs}.Init(sctx, sel.SelectBlockOffset())
|
|
remainedGroupExpr := memo.NewGroupExpr(remainedSel)
|
|
remainedGroupExpr.SetChildren(aggGroup)
|
|
return []*memo.GroupExpr{remainedGroupExpr}, true, false, nil
|
|
}
|
|
|
|
// PushSelDownWindow pushes Selection down to the child of Window.
|
|
type PushSelDownWindow struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushSelDownWindow creates a new Transformation PushSelDownWindow.
|
|
// The pattern of this rule is `Selection -> Window`.
|
|
func NewRulePushSelDownWindow() Transformation {
|
|
rule := &PushSelDownWindow{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandSelection,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandWindow, memo.EngineAll),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule will transform `sel -> window -> x` to
|
|
// 1. `window -> sel -> x` or
|
|
// 2. `sel -> window -> sel -> x` or
|
|
// 3. just keep unchanged.
|
|
func (r *PushSelDownWindow) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
sel := old.GetExpr().ExprNode.(*plannercore.LogicalSelection)
|
|
window := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalWindow)
|
|
windowSchema := old.Children[0].Prop.Schema
|
|
childGroup := old.Children[0].GetExpr().Children[0]
|
|
canBePushed := make([]expression.Expression, 0, len(sel.Conditions))
|
|
canNotBePushed := make([]expression.Expression, 0, len(sel.Conditions))
|
|
|
|
// get partition Columns' Schema
|
|
partitionColsSchema := expression.NewSchema(window.GetPartitionByCols()...)
|
|
|
|
for _, cond := range sel.Conditions {
|
|
if expression.ExprFromSchema(cond, partitionColsSchema) {
|
|
canBePushed = append(canBePushed, cond)
|
|
} else {
|
|
canNotBePushed = append(canNotBePushed, cond)
|
|
}
|
|
}
|
|
// Nothing can be pushed!
|
|
if len(canBePushed) == 0 {
|
|
return nil, false, false, nil
|
|
}
|
|
|
|
// construct return GroupExpr
|
|
newBottomSel := plannercore.LogicalSelection{Conditions: canBePushed}.Init(sel.SCtx(), sel.SelectBlockOffset())
|
|
newBottomSelExpr := memo.NewGroupExpr(newBottomSel)
|
|
newBottomSelExpr.SetChildren(childGroup)
|
|
newBottomSelGroup := memo.NewGroupWithSchema(newBottomSelExpr, childGroup.Prop.Schema)
|
|
newWindowExpr := memo.NewGroupExpr(window)
|
|
newWindowExpr.SetChildren(newBottomSelGroup)
|
|
if len(canNotBePushed) == 0 {
|
|
return []*memo.GroupExpr{newWindowExpr}, true, false, nil
|
|
}
|
|
|
|
newWindowGroup := memo.NewGroupWithSchema(newWindowExpr, windowSchema)
|
|
newTopSel := plannercore.LogicalSelection{Conditions: canNotBePushed}.Init(sel.SCtx(), sel.SelectBlockOffset())
|
|
newTopSelExpr := memo.NewGroupExpr(newTopSel)
|
|
newTopSelExpr.SetChildren(newWindowGroup)
|
|
return []*memo.GroupExpr{newTopSelExpr}, true, false, nil
|
|
}
|
|
|
|
// TransformLimitToTopN transforms Limit+Sort to TopN.
|
|
type TransformLimitToTopN struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRuleTransformLimitToTopN creates a new Transformation TransformLimitToTopN.
|
|
// The pattern of this rule is `Limit -> Sort`.
|
|
func NewRuleTransformLimitToTopN() Transformation {
|
|
rule := &TransformLimitToTopN{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandLimit,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandSort, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule will transform `Limit -> Sort -> x` to `TopN -> x`.
|
|
func (r *TransformLimitToTopN) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
limit := old.GetExpr().ExprNode.(*plannercore.LogicalLimit)
|
|
sort := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalSort)
|
|
childGroup := old.Children[0].GetExpr().Children[0]
|
|
topN := plannercore.LogicalTopN{
|
|
ByItems: sort.ByItems,
|
|
Offset: limit.Offset,
|
|
Count: limit.Count,
|
|
}.Init(limit.SCtx(), limit.SelectBlockOffset())
|
|
topNExpr := memo.NewGroupExpr(topN)
|
|
topNExpr.SetChildren(childGroup)
|
|
return []*memo.GroupExpr{topNExpr}, true, false, nil
|
|
}
|
|
|
|
// PushLimitDownProjection pushes Limit to Projection.
|
|
type PushLimitDownProjection struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushLimitDownProjection creates a new Transformation.
|
|
// The pattern of this rule is `Limit->Projection->X` to `Projection->Limit->X`.
|
|
func NewRulePushLimitDownProjection() Transformation {
|
|
rule := &PushLimitDownProjection{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandLimit,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandProjection, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
func (r *PushLimitDownProjection) Match(expr *memo.ExprIter) bool {
|
|
proj := expr.Children[0].GetExpr().ExprNode.(*plannercore.LogicalProjection)
|
|
for _, expr := range proj.Exprs {
|
|
if expression.HasAssignSetVarFunc(expr) {
|
|
return false
|
|
}
|
|
}
|
|
return true
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule tries to pushes the Limit through Projection.
|
|
func (r *PushLimitDownProjection) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
limit := old.GetExpr().ExprNode.(*plannercore.LogicalLimit)
|
|
proj := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalProjection)
|
|
childGroup := old.Children[0].GetExpr().Children[0]
|
|
|
|
projExpr := memo.NewGroupExpr(proj)
|
|
limitExpr := memo.NewGroupExpr(limit)
|
|
limitExpr.SetChildren(childGroup)
|
|
limitGroup := memo.NewGroupWithSchema(limitExpr, childGroup.Prop.Schema)
|
|
projExpr.SetChildren(limitGroup)
|
|
return []*memo.GroupExpr{projExpr}, true, false, nil
|
|
}
|
|
|
|
// PushLimitDownUnionAll pushes limit to union all.
|
|
type PushLimitDownUnionAll struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushLimitDownUnionAll creates a new Transformation PushLimitDownUnionAll.
|
|
// The pattern of this rule is `Limit->UnionAll->X`.
|
|
func NewRulePushLimitDownUnionAll() Transformation {
|
|
rule := &PushLimitDownUnionAll{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandLimit,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandUnionAll, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
// Use appliedRuleSet in GroupExpr to avoid re-apply rules.
|
|
func (r *PushLimitDownUnionAll) Match(expr *memo.ExprIter) bool {
|
|
return !expr.GetExpr().HasAppliedRule(r)
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// It will transform `Limit->UnionAll->X` to `Limit->UnionAll->Limit->X`.
|
|
func (r *PushLimitDownUnionAll) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
limit := old.GetExpr().ExprNode.(*plannercore.LogicalLimit)
|
|
unionAll := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalUnionAll)
|
|
unionAllSchema := old.Children[0].Group.Prop.Schema
|
|
|
|
newLimit := plannercore.LogicalLimit{
|
|
Count: limit.Count + limit.Offset,
|
|
}.Init(limit.SCtx(), limit.SelectBlockOffset())
|
|
|
|
newUnionAllExpr := memo.NewGroupExpr(unionAll)
|
|
for _, childGroup := range old.Children[0].GetExpr().Children {
|
|
newLimitExpr := memo.NewGroupExpr(newLimit)
|
|
newLimitExpr.Children = append(newLimitExpr.Children, childGroup)
|
|
newLimitGroup := memo.NewGroupWithSchema(newLimitExpr, childGroup.Prop.Schema)
|
|
|
|
newUnionAllExpr.Children = append(newUnionAllExpr.Children, newLimitGroup)
|
|
}
|
|
|
|
newLimitExpr := memo.NewGroupExpr(limit)
|
|
newUnionAllGroup := memo.NewGroupWithSchema(newUnionAllExpr, unionAllSchema)
|
|
newLimitExpr.SetChildren(newUnionAllGroup)
|
|
newLimitExpr.AddAppliedRule(r)
|
|
return []*memo.GroupExpr{newLimitExpr}, true, false, nil
|
|
}
|
|
|
|
// PushSelDownJoin pushes Selection through Join.
|
|
type PushSelDownJoin struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushSelDownJoin creates a new Transformation PushSelDownJoin.
|
|
// The pattern of this rule is `Selection -> Join`.
|
|
func NewRulePushSelDownJoin() Transformation {
|
|
rule := &PushSelDownJoin{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandSelection,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandJoin, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
func (r *PushSelDownJoin) Match(expr *memo.ExprIter) bool {
|
|
return !expr.GetExpr().HasAppliedRule(r)
|
|
}
|
|
|
|
// buildChildSelectionGroup builds a new childGroup if the pushed down condition is not empty.
|
|
func buildChildSelectionGroup(
|
|
oldSel *plannercore.LogicalSelection,
|
|
conditions []expression.Expression,
|
|
childGroup *memo.Group) *memo.Group {
|
|
if len(conditions) == 0 {
|
|
return childGroup
|
|
}
|
|
newSel := plannercore.LogicalSelection{Conditions: conditions}.Init(oldSel.SCtx(), oldSel.SelectBlockOffset())
|
|
groupExpr := memo.NewGroupExpr(newSel)
|
|
groupExpr.SetChildren(childGroup)
|
|
newChild := memo.NewGroupWithSchema(groupExpr, childGroup.Prop.Schema)
|
|
return newChild
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule tries to pushes the Selection through Join. Besides, this rule fulfills the `XXXConditions` field of Join.
|
|
func (r *PushSelDownJoin) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
sel := old.GetExpr().ExprNode.(*plannercore.LogicalSelection)
|
|
joinExpr := old.Children[0].GetExpr()
|
|
// TODO: we need to create a new LogicalJoin here.
|
|
join := joinExpr.ExprNode.(*plannercore.LogicalJoin)
|
|
sctx := sel.SCtx()
|
|
leftGroup := old.Children[0].GetExpr().Children[0]
|
|
rightGroup := old.Children[0].GetExpr().Children[1]
|
|
var equalCond []*expression.ScalarFunction
|
|
var leftPushCond, rightPushCond, otherCond, leftCond, rightCond, remainCond []expression.Expression
|
|
switch join.JoinType {
|
|
case plannercore.SemiJoin, plannercore.InnerJoin:
|
|
tempCond := make([]expression.Expression, 0,
|
|
len(join.LeftConditions)+len(join.RightConditions)+len(join.EqualConditions)+len(join.OtherConditions)+len(sel.Conditions))
|
|
tempCond = append(tempCond, join.LeftConditions...)
|
|
tempCond = append(tempCond, join.RightConditions...)
|
|
tempCond = append(tempCond, expression.ScalarFuncs2Exprs(join.EqualConditions)...)
|
|
tempCond = append(tempCond, join.OtherConditions...)
|
|
tempCond = append(tempCond, sel.Conditions...)
|
|
tempCond = expression.ExtractFiltersFromDNFs(sctx, tempCond)
|
|
tempCond = expression.PropagateConstant(sctx, tempCond)
|
|
// Return table dual when filter is constant false or null.
|
|
dual := plannercore.Conds2TableDual(join, tempCond)
|
|
if dual != nil {
|
|
return []*memo.GroupExpr{memo.NewGroupExpr(dual)}, false, true, nil
|
|
}
|
|
equalCond, leftPushCond, rightPushCond, otherCond = join.ExtractOnCondition(tempCond, leftGroup.Prop.Schema, rightGroup.Prop.Schema, true, true)
|
|
join.LeftConditions = nil
|
|
join.RightConditions = nil
|
|
join.EqualConditions = equalCond
|
|
join.OtherConditions = otherCond
|
|
leftCond = leftPushCond
|
|
rightCond = rightPushCond
|
|
case plannercore.LeftOuterJoin, plannercore.LeftOuterSemiJoin, plannercore.AntiLeftOuterSemiJoin,
|
|
plannercore.RightOuterJoin:
|
|
lenJoinConds := len(join.EqualConditions) + len(join.LeftConditions) + len(join.RightConditions) + len(join.OtherConditions)
|
|
joinConds := make([]expression.Expression, 0, lenJoinConds)
|
|
for _, equalCond := range join.EqualConditions {
|
|
joinConds = append(joinConds, equalCond)
|
|
}
|
|
joinConds = append(joinConds, join.LeftConditions...)
|
|
joinConds = append(joinConds, join.RightConditions...)
|
|
joinConds = append(joinConds, join.OtherConditions...)
|
|
join.EqualConditions = nil
|
|
join.LeftConditions = nil
|
|
join.RightConditions = nil
|
|
join.OtherConditions = nil
|
|
remainCond = make([]expression.Expression, len(sel.Conditions))
|
|
copy(remainCond, sel.Conditions)
|
|
nullSensitive := join.JoinType == plannercore.AntiLeftOuterSemiJoin || join.JoinType == plannercore.LeftOuterSemiJoin
|
|
if join.JoinType == plannercore.RightOuterJoin {
|
|
joinConds, remainCond = expression.PropConstOverOuterJoin(join.SCtx(), joinConds, remainCond, rightGroup.Prop.Schema, leftGroup.Prop.Schema, nullSensitive)
|
|
} else {
|
|
joinConds, remainCond = expression.PropConstOverOuterJoin(join.SCtx(), joinConds, remainCond, leftGroup.Prop.Schema, rightGroup.Prop.Schema, nullSensitive)
|
|
}
|
|
eq, left, right, other := join.ExtractOnCondition(joinConds, leftGroup.Prop.Schema, rightGroup.Prop.Schema, false, false)
|
|
join.AppendJoinConds(eq, left, right, other)
|
|
// Return table dual when filter is constant false or null.
|
|
dual := plannercore.Conds2TableDual(join, remainCond)
|
|
if dual != nil {
|
|
return []*memo.GroupExpr{memo.NewGroupExpr(dual)}, false, true, nil
|
|
}
|
|
if join.JoinType == plannercore.RightOuterJoin {
|
|
remainCond = expression.ExtractFiltersFromDNFs(join.SCtx(), remainCond)
|
|
// Only derive right where condition, because left where condition cannot be pushed down
|
|
equalCond, leftPushCond, rightPushCond, otherCond = join.ExtractOnCondition(remainCond, leftGroup.Prop.Schema, rightGroup.Prop.Schema, false, true)
|
|
rightCond = rightPushCond
|
|
// Handle join conditions, only derive left join condition, because right join condition cannot be pushed down
|
|
derivedLeftJoinCond, _ := plannercore.DeriveOtherConditions(join, true, false)
|
|
leftCond = append(join.LeftConditions, derivedLeftJoinCond...)
|
|
join.LeftConditions = nil
|
|
remainCond = append(expression.ScalarFuncs2Exprs(equalCond), otherCond...)
|
|
remainCond = append(remainCond, leftPushCond...)
|
|
} else {
|
|
remainCond = expression.ExtractFiltersFromDNFs(join.SCtx(), remainCond)
|
|
// Only derive left where condition, because right where condition cannot be pushed down
|
|
equalCond, leftPushCond, rightPushCond, otherCond = join.ExtractOnCondition(remainCond, leftGroup.Prop.Schema, rightGroup.Prop.Schema, true, false)
|
|
leftCond = leftPushCond
|
|
// Handle join conditions, only derive left join condition, because right join condition cannot be pushed down
|
|
_, derivedRightJoinCond := plannercore.DeriveOtherConditions(join, false, true)
|
|
rightCond = append(join.RightConditions, derivedRightJoinCond...)
|
|
join.RightConditions = nil
|
|
remainCond = append(expression.ScalarFuncs2Exprs(equalCond), otherCond...)
|
|
remainCond = append(remainCond, rightPushCond...)
|
|
}
|
|
default:
|
|
// TODO: Enhance this rule to deal with Semi/SmiAnti Joins.
|
|
}
|
|
leftCond = expression.RemoveDupExprs(sctx, leftCond)
|
|
rightCond = expression.RemoveDupExprs(sctx, rightCond)
|
|
// TODO: Update EqualConditions like what we have done in the method join.updateEQCond() before.
|
|
leftGroup = buildChildSelectionGroup(sel, leftCond, leftGroup)
|
|
rightGroup = buildChildSelectionGroup(sel, rightCond, rightGroup)
|
|
newJoinExpr := memo.NewGroupExpr(join)
|
|
newJoinExpr.SetChildren(leftGroup, rightGroup)
|
|
if len(remainCond) > 0 {
|
|
newSel := plannercore.LogicalSelection{Conditions: remainCond}.Init(sctx, sel.SelectBlockOffset())
|
|
newSel.Conditions = remainCond
|
|
newSelExpr := memo.NewGroupExpr(newSel)
|
|
newSelExpr.SetChildren(memo.NewGroupWithSchema(newJoinExpr, old.Children[0].Prop.Schema))
|
|
newSelExpr.AddAppliedRule(r)
|
|
return []*memo.GroupExpr{newSelExpr}, true, false, nil
|
|
}
|
|
return []*memo.GroupExpr{newJoinExpr}, true, false, nil
|
|
}
|
|
|
|
// PushSelDownUnionAll pushes selection through union all.
|
|
type PushSelDownUnionAll struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushSelDownUnionAll creates a new Transformation PushSelDownUnionAll.
|
|
// The pattern of this rule is `Selection -> UnionAll`.
|
|
func NewRulePushSelDownUnionAll() Transformation {
|
|
rule := &PushSelDownUnionAll{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandSelection,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandUnionAll, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// It will transform `Selection->UnionAll->x` to `UnionAll->Selection->x`.
|
|
func (r *PushSelDownUnionAll) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
sel := old.GetExpr().ExprNode.(*plannercore.LogicalSelection)
|
|
unionAll := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalUnionAll)
|
|
childGroups := old.Children[0].GetExpr().Children
|
|
|
|
newUnionAllExpr := memo.NewGroupExpr(unionAll)
|
|
for _, group := range childGroups {
|
|
newSelExpr := memo.NewGroupExpr(sel)
|
|
newSelExpr.Children = append(newSelExpr.Children, group)
|
|
newSelGroup := memo.NewGroupWithSchema(newSelExpr, group.Prop.Schema)
|
|
|
|
newUnionAllExpr.Children = append(newUnionAllExpr.Children, newSelGroup)
|
|
}
|
|
return []*memo.GroupExpr{newUnionAllExpr}, true, false, nil
|
|
}
|
|
|
|
// EliminateProjection eliminates the projection.
|
|
type EliminateProjection struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRuleEliminateProjection creates a new Transformation EliminateProjection.
|
|
// The pattern of this rule is `Projection -> Any`.
|
|
func NewRuleEliminateProjection() Transformation {
|
|
rule := &EliminateProjection{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandProjection,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandAny, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule tries to eliminate the projection whose output columns are the same with its child.
|
|
func (r *EliminateProjection) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
child := old.Children[0]
|
|
if child.Group.Prop.Schema.Len() != old.GetExpr().Group.Prop.Schema.Len() {
|
|
return nil, false, false, nil
|
|
}
|
|
|
|
oldCols := old.GetExpr().Group.Prop.Schema.Columns
|
|
for i, col := range child.Group.Prop.Schema.Columns {
|
|
if !col.Equal(nil, oldCols[i]) {
|
|
return nil, false, false, nil
|
|
}
|
|
}
|
|
|
|
// Promote the children group's expression.
|
|
finalGroupExprs := make([]*memo.GroupExpr, 0, child.Group.Equivalents.Len())
|
|
for elem := child.Group.Equivalents.Front(); elem != nil; elem = elem.Next() {
|
|
childExpr := elem.Value.(*memo.GroupExpr)
|
|
copyChildExpr := memo.NewGroupExpr(childExpr.ExprNode)
|
|
copyChildExpr.SetChildren(childExpr.Children...)
|
|
finalGroupExprs = append(finalGroupExprs, copyChildExpr)
|
|
}
|
|
return finalGroupExprs, true, false, nil
|
|
}
|
|
|
|
// MergeAdjacentProjection merge the adjacent projection.
|
|
type MergeAdjacentProjection struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRuleMergeAdjacentProjection creates a new Transformation MergeAdjacentProjection.
|
|
// The pattern of this rule is `Projection -> Projection`.
|
|
func NewRuleMergeAdjacentProjection() Transformation {
|
|
rule := &MergeAdjacentProjection{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandProjection,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandProjection, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// It will transform `proj->proj->x` to `proj->x`
|
|
// or just keep the adjacent projections unchanged.
|
|
func (r *MergeAdjacentProjection) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
proj := old.GetExpr().ExprNode.(*plannercore.LogicalProjection)
|
|
childGroup := old.Children[0].Group
|
|
child := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalProjection)
|
|
if plannercore.ExprsHasSideEffects(child.Exprs) {
|
|
return nil, false, false, nil
|
|
}
|
|
|
|
replace := make(map[string]*expression.Column)
|
|
for i, col := range childGroup.Prop.Schema.Columns {
|
|
if colOrigin, ok := child.Exprs[i].(*expression.Column); ok {
|
|
replace[string(col.HashCode(nil))] = colOrigin
|
|
}
|
|
}
|
|
|
|
newProj := plannercore.LogicalProjection{Exprs: make([]expression.Expression, len(proj.Exprs))}.Init(proj.SCtx(), proj.SelectBlockOffset())
|
|
newProj.SetSchema(old.GetExpr().Group.Prop.Schema)
|
|
for i, expr := range proj.Exprs {
|
|
newExpr := expr.Clone()
|
|
plannercore.ResolveExprAndReplace(newExpr, replace)
|
|
newProj.Exprs[i] = plannercore.ReplaceColumnOfExpr(newExpr, child, childGroup.Prop.Schema)
|
|
}
|
|
|
|
newProjExpr := memo.NewGroupExpr(newProj)
|
|
newProjExpr.SetChildren(old.Children[0].GetExpr().Children[0])
|
|
return []*memo.GroupExpr{newProjExpr}, true, false, nil
|
|
}
|
|
|
|
// PushTopNDownOuterJoin pushes topN to outer join.
|
|
type PushTopNDownOuterJoin struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushTopNDownOuterJoin creates a new Transformation PushTopNDownOuterJoin.
|
|
// The pattern of this rule is: `TopN -> Join`.
|
|
func NewRulePushTopNDownOuterJoin() Transformation {
|
|
rule := &PushTopNDownOuterJoin{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandTopN,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandJoin, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
// Use appliedRuleSet in GroupExpr to avoid re-apply rules.
|
|
func (r *PushTopNDownOuterJoin) Match(expr *memo.ExprIter) bool {
|
|
if expr.GetExpr().HasAppliedRule(r) {
|
|
return false
|
|
}
|
|
join := expr.Children[0].GetExpr().ExprNode.(*plannercore.LogicalJoin)
|
|
switch join.JoinType {
|
|
case plannercore.LeftOuterJoin, plannercore.LeftOuterSemiJoin, plannercore.AntiLeftOuterSemiJoin, plannercore.RightOuterJoin:
|
|
return true
|
|
default:
|
|
return false
|
|
}
|
|
}
|
|
|
|
func pushTopNDownOuterJoinToChild(topN *plannercore.LogicalTopN, outerGroup *memo.Group) *memo.Group {
|
|
for _, by := range topN.ByItems {
|
|
cols := expression.ExtractColumns(by.Expr)
|
|
for _, col := range cols {
|
|
if !outerGroup.Prop.Schema.Contains(col) {
|
|
return outerGroup
|
|
}
|
|
}
|
|
}
|
|
|
|
newTopN := plannercore.LogicalTopN{
|
|
Count: topN.Count + topN.Offset,
|
|
ByItems: make([]*util.ByItems, len(topN.ByItems)),
|
|
}.Init(topN.SCtx(), topN.SelectBlockOffset())
|
|
|
|
for i := range topN.ByItems {
|
|
newTopN.ByItems[i] = topN.ByItems[i].Clone()
|
|
}
|
|
newTopNGroup := memo.NewGroupExpr(newTopN)
|
|
newTopNGroup.SetChildren(outerGroup)
|
|
newChild := memo.NewGroupWithSchema(newTopNGroup, outerGroup.Prop.Schema)
|
|
return newChild
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule will transform `TopN->OuterJoin->(OuterChild, InnerChild)` to `TopN->OuterJoin->(TopN->OuterChild, InnerChild)`
|
|
func (r *PushTopNDownOuterJoin) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
topN := old.GetExpr().ExprNode.(*plannercore.LogicalTopN)
|
|
joinExpr := old.Children[0].GetExpr()
|
|
join := joinExpr.ExprNode.(*plannercore.LogicalJoin)
|
|
joinSchema := old.Children[0].Group.Prop.Schema
|
|
leftGroup := joinExpr.Children[0]
|
|
rightGroup := joinExpr.Children[1]
|
|
|
|
switch join.JoinType {
|
|
case plannercore.LeftOuterJoin, plannercore.LeftOuterSemiJoin, plannercore.AntiLeftOuterSemiJoin:
|
|
leftGroup = pushTopNDownOuterJoinToChild(topN, leftGroup)
|
|
case plannercore.RightOuterJoin:
|
|
rightGroup = pushTopNDownOuterJoinToChild(topN, rightGroup)
|
|
default:
|
|
return nil, false, false, nil
|
|
}
|
|
|
|
newJoinExpr := memo.NewGroupExpr(join)
|
|
newJoinExpr.SetChildren(leftGroup, rightGroup)
|
|
newTopNExpr := memo.NewGroupExpr(topN)
|
|
newTopNExpr.SetChildren(memo.NewGroupWithSchema(newJoinExpr, joinSchema))
|
|
newTopNExpr.AddAppliedRule(r)
|
|
return []*memo.GroupExpr{newTopNExpr}, true, false, nil
|
|
}
|
|
|
|
// PushTopNDownProjection pushes TopN to Projection.
|
|
type PushTopNDownProjection struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushTopNDownProjection creates a new Transformation PushTopNDownProjection.
|
|
// The pattern of this rule is `TopN->Projection->X` to `Projection->TopN->X`.
|
|
func NewRulePushTopNDownProjection() Transformation {
|
|
rule := &PushTopNDownProjection{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandTopN,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandProjection, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
func (r *PushTopNDownProjection) Match(expr *memo.ExprIter) bool {
|
|
proj := expr.Children[0].GetExpr().ExprNode.(*plannercore.LogicalProjection)
|
|
for _, expr := range proj.Exprs {
|
|
if expression.HasAssignSetVarFunc(expr) {
|
|
return false
|
|
}
|
|
}
|
|
return true
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule tries to pushes the TopN through Projection.
|
|
func (r *PushTopNDownProjection) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
topN := old.GetExpr().ExprNode.(*plannercore.LogicalTopN)
|
|
proj := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalProjection)
|
|
childGroup := old.Children[0].GetExpr().Children[0]
|
|
|
|
newTopN := plannercore.LogicalTopN{
|
|
Offset: topN.Offset,
|
|
Count: topN.Count,
|
|
}.Init(topN.SCtx(), topN.SelectBlockOffset())
|
|
|
|
newTopN.ByItems = make([]*util.ByItems, 0, len(topN.ByItems))
|
|
for _, by := range topN.ByItems {
|
|
newTopN.ByItems = append(newTopN.ByItems, &util.ByItems{
|
|
Expr: expression.ColumnSubstitute(by.Expr, old.Children[0].Group.Prop.Schema, proj.Exprs),
|
|
Desc: by.Desc,
|
|
})
|
|
}
|
|
|
|
// remove meaningless constant sort items.
|
|
for i := len(newTopN.ByItems) - 1; i >= 0; i-- {
|
|
switch newTopN.ByItems[i].Expr.(type) {
|
|
case *expression.Constant, *expression.CorrelatedColumn:
|
|
topN.ByItems = append(newTopN.ByItems[:i], newTopN.ByItems[i+1:]...)
|
|
}
|
|
}
|
|
projExpr := memo.NewGroupExpr(proj)
|
|
topNExpr := memo.NewGroupExpr(newTopN)
|
|
topNExpr.SetChildren(childGroup)
|
|
topNGroup := memo.NewGroupWithSchema(topNExpr, childGroup.Prop.Schema)
|
|
projExpr.SetChildren(topNGroup)
|
|
return []*memo.GroupExpr{projExpr}, true, false, nil
|
|
}
|
|
|
|
// PushTopNDownUnionAll pushes topN to union all.
|
|
type PushTopNDownUnionAll struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushTopNDownUnionAll creates a new Transformation PushTopNDownUnionAll.
|
|
// The pattern of this rule is `TopN->UnionAll->X`.
|
|
func NewRulePushTopNDownUnionAll() Transformation {
|
|
rule := &PushTopNDownUnionAll{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandTopN,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandUnionAll, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
// Use appliedRuleSet in GroupExpr to avoid re-apply rules.
|
|
func (r *PushTopNDownUnionAll) Match(expr *memo.ExprIter) bool {
|
|
return !expr.GetExpr().HasAppliedRule(r)
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// It will transform `TopN->UnionAll->X` to `TopN->UnionAll->TopN->X`.
|
|
func (r *PushTopNDownUnionAll) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
topN := old.GetExpr().ExprNode.(*plannercore.LogicalTopN)
|
|
unionAll := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalUnionAll)
|
|
|
|
newTopN := plannercore.LogicalTopN{
|
|
Count: topN.Count + topN.Offset,
|
|
ByItems: topN.ByItems,
|
|
}.Init(topN.SCtx(), topN.SelectBlockOffset())
|
|
|
|
newUnionAllExpr := memo.NewGroupExpr(unionAll)
|
|
for _, childGroup := range old.Children[0].GetExpr().Children {
|
|
newTopNExpr := memo.NewGroupExpr(newTopN)
|
|
newTopNExpr.Children = append(newTopNExpr.Children, childGroup)
|
|
newTopNGroup := memo.NewGroupWithSchema(newTopNExpr, childGroup.Prop.Schema)
|
|
|
|
newUnionAllExpr.Children = append(newUnionAllExpr.Children, newTopNGroup)
|
|
}
|
|
|
|
newTopNExpr := memo.NewGroupExpr(topN)
|
|
newUnionAllGroup := memo.NewGroupWithSchema(newUnionAllExpr, unionAll.Schema())
|
|
newTopNExpr.SetChildren(newUnionAllGroup)
|
|
newTopNExpr.AddAppliedRule(r)
|
|
return []*memo.GroupExpr{newTopNExpr}, true, false, nil
|
|
}
|
|
|
|
// PushTopNDownTiKVSingleGather pushes the top-n down to child of TiKVSingleGather.
|
|
type PushTopNDownTiKVSingleGather struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushTopNDownTiKVSingleGather creates a new Transformation PushTopNDownTiKVSingleGather.
|
|
// The pattern of this rule is `TopN -> TiKVSingleGather`.
|
|
func NewRulePushTopNDownTiKVSingleGather() Transformation {
|
|
rule := &PushTopNDownTiKVSingleGather{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandTopN,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandTiKVSingleGather, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
// Use appliedRuleSet in GroupExpr to avoid re-apply rules.
|
|
func (r *PushTopNDownTiKVSingleGather) Match(expr *memo.ExprIter) bool {
|
|
return !expr.GetExpr().HasAppliedRule(r)
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// It transforms `TopN -> TiKVSingleGather` to `TopN(Final) -> TiKVSingleGather -> TopN(Partial)`.
|
|
func (r *PushTopNDownTiKVSingleGather) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
topN := old.GetExpr().ExprNode.(*plannercore.LogicalTopN)
|
|
topNSchema := old.Children[0].Group.Prop.Schema
|
|
gather := old.Children[0].GetExpr().ExprNode.(*plannercore.TiKVSingleGather)
|
|
childGroup := old.Children[0].GetExpr().Children[0]
|
|
|
|
particalTopN := plannercore.LogicalTopN{
|
|
ByItems: topN.ByItems,
|
|
Count: topN.Count + topN.Offset,
|
|
}.Init(topN.SCtx(), topN.SelectBlockOffset())
|
|
partialTopNExpr := memo.NewGroupExpr(particalTopN)
|
|
partialTopNExpr.SetChildren(childGroup)
|
|
partialTopNGroup := memo.NewGroupWithSchema(partialTopNExpr, topNSchema).SetEngineType(childGroup.EngineType)
|
|
|
|
gatherExpr := memo.NewGroupExpr(gather)
|
|
gatherExpr.SetChildren(partialTopNGroup)
|
|
gatherGroup := memo.NewGroupWithSchema(gatherExpr, topNSchema)
|
|
|
|
finalTopNExpr := memo.NewGroupExpr(topN)
|
|
finalTopNExpr.SetChildren(gatherGroup)
|
|
finalTopNExpr.AddAppliedRule(r)
|
|
return []*memo.GroupExpr{finalTopNExpr}, true, false, nil
|
|
}
|
|
|
|
// MergeAdjacentTopN merge adjacent TopN.
|
|
type MergeAdjacentTopN struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRuleMergeAdjacentTopN creates a new Transformation MergeAdjacentTopN.
|
|
// The pattern of this rule is `TopN->TopN->X`.
|
|
func NewRuleMergeAdjacentTopN() Transformation {
|
|
rule := &MergeAdjacentTopN{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandTopN,
|
|
memo.EngineAll,
|
|
memo.NewPattern(memo.OperandTopN, memo.EngineAll),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
func (r *MergeAdjacentTopN) Match(expr *memo.ExprIter) bool {
|
|
topN := expr.GetExpr().ExprNode.(*plannercore.LogicalTopN)
|
|
child := expr.Children[0].GetExpr().ExprNode.(*plannercore.LogicalTopN)
|
|
|
|
// We can use this rule when the sort columns of parent TopN is a prefix of child TopN.
|
|
if len(child.ByItems) < len(topN.ByItems) {
|
|
return false
|
|
}
|
|
for i := 0; i < len(topN.ByItems); i++ {
|
|
if !topN.ByItems[i].Equal(topN.SCtx(), child.ByItems[i]) {
|
|
return false
|
|
}
|
|
}
|
|
return true
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule tries to merge adjacent TopN.
|
|
func (r *MergeAdjacentTopN) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
topN := old.GetExpr().ExprNode.(*plannercore.LogicalTopN)
|
|
child := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalTopN)
|
|
childGroups := old.Children[0].GetExpr().Children
|
|
|
|
if child.Count <= topN.Offset {
|
|
tableDual := plannercore.LogicalTableDual{RowCount: 0}.Init(child.SCtx(), child.SelectBlockOffset())
|
|
tableDual.SetSchema(old.GetExpr().Schema())
|
|
tableDualExpr := memo.NewGroupExpr(tableDual)
|
|
return []*memo.GroupExpr{tableDualExpr}, true, true, nil
|
|
}
|
|
|
|
offset := child.Offset + topN.Offset
|
|
count := uint64(math.Min(float64(child.Count-topN.Offset), float64(topN.Count)))
|
|
newTopN := plannercore.LogicalTopN{
|
|
Count: count,
|
|
Offset: offset,
|
|
ByItems: child.ByItems,
|
|
}.Init(child.SCtx(), child.SelectBlockOffset())
|
|
newTopNExpr := memo.NewGroupExpr(newTopN)
|
|
newTopNExpr.SetChildren(childGroups...)
|
|
return []*memo.GroupExpr{newTopNExpr}, true, false, nil
|
|
}
|
|
|
|
// MergeAggregationProjection merges the Projection below an Aggregation as a new Aggregation.
|
|
// The Projection may be regenerated in the ImplementationPhase. But this rule allows the
|
|
// Aggregation to match other rules, such as MergeAdjacentAggregation.
|
|
type MergeAggregationProjection struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRuleMergeAggregationProjection creates a new Transformation MergeAggregationProjection.
|
|
// The pattern of this rule is: `Aggregation -> Projection`.
|
|
func NewRuleMergeAggregationProjection() Transformation {
|
|
rule := &MergeAggregationProjection{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandAggregation,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandProjection, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
func (r *MergeAggregationProjection) Match(old *memo.ExprIter) bool {
|
|
proj := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalProjection)
|
|
if plannercore.ExprsHasSideEffects(proj.Exprs) {
|
|
return false
|
|
}
|
|
return true
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// It will transform `Aggregation->Projection->X` to `Aggregation->X`.
|
|
func (r *MergeAggregationProjection) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
oldAgg := old.GetExpr().ExprNode.(*plannercore.LogicalAggregation)
|
|
proj := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalProjection)
|
|
projSchema := old.Children[0].GetExpr().Schema()
|
|
|
|
groupByItems := make([]expression.Expression, len(oldAgg.GroupByItems))
|
|
for i, item := range oldAgg.GroupByItems {
|
|
groupByItems[i] = expression.ColumnSubstitute(item, projSchema, proj.Exprs)
|
|
}
|
|
|
|
aggFuncs := make([]*aggregation.AggFuncDesc, len(oldAgg.AggFuncs))
|
|
for i, aggFunc := range oldAgg.AggFuncs {
|
|
aggFuncs[i] = aggFunc.Clone()
|
|
newArgs := make([]expression.Expression, len(aggFunc.Args))
|
|
for j, arg := range aggFunc.Args {
|
|
newArgs[j] = expression.ColumnSubstitute(arg, projSchema, proj.Exprs)
|
|
}
|
|
aggFuncs[i].Args = newArgs
|
|
}
|
|
|
|
newAgg := plannercore.LogicalAggregation{
|
|
GroupByItems: groupByItems,
|
|
AggFuncs: aggFuncs,
|
|
}.Init(oldAgg.SCtx(), oldAgg.SelectBlockOffset())
|
|
|
|
newAggExpr := memo.NewGroupExpr(newAgg)
|
|
newAggExpr.SetChildren(old.Children[0].GetExpr().Children...)
|
|
return []*memo.GroupExpr{newAggExpr}, false, false, nil
|
|
}
|
|
|
|
// EliminateSingleMaxMin tries to convert a single max/min to Limit+Sort operators.
|
|
type EliminateSingleMaxMin struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRuleEliminateSingleMaxMin creates a new Transformation EliminateSingleMaxMin.
|
|
// The pattern of this rule is `max/min->X`.
|
|
func NewRuleEliminateSingleMaxMin() Transformation {
|
|
rule := &EliminateSingleMaxMin{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandAggregation,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandAny, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
func (r *EliminateSingleMaxMin) Match(expr *memo.ExprIter) bool {
|
|
// Use appliedRuleSet in GroupExpr to avoid re-apply rules.
|
|
if expr.GetExpr().HasAppliedRule(r) {
|
|
return false
|
|
}
|
|
|
|
agg := expr.GetExpr().ExprNode.(*plannercore.LogicalAggregation)
|
|
// EliminateSingleMaxMin only works on the complete mode.
|
|
if !agg.IsCompleteModeAgg() {
|
|
return false
|
|
}
|
|
if len(agg.GroupByItems) != 0 {
|
|
return false
|
|
}
|
|
|
|
// If there is only one aggFunc, we don't need to guarantee that the child of it is a data
|
|
// source, or whether the sort can be eliminated. This transformation won't be worse than previous.
|
|
// Make sure that the aggFunc are Max or Min.
|
|
// TODO: If there have only one Max or Min aggFunc and the other aggFuncs are FirstRow() can also use this rule. Waiting for the not null prop is maintained.
|
|
if len(agg.AggFuncs) != 1 {
|
|
return false
|
|
}
|
|
if agg.AggFuncs[0].Name != ast.AggFuncMax && agg.AggFuncs[0].Name != ast.AggFuncMin {
|
|
return false
|
|
}
|
|
return true
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// It will transform `max/min->X` to `max/min->top1->sel->X`.
|
|
func (r *EliminateSingleMaxMin) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
agg := old.GetExpr().ExprNode.(*plannercore.LogicalAggregation)
|
|
childGroup := old.GetExpr().Children[0]
|
|
ctx := agg.SCtx()
|
|
f := agg.AggFuncs[0]
|
|
|
|
// If there's no column in f.GetArgs()[0], we still need limit and read data from real table because the result should be NULL if the input is empty.
|
|
if len(expression.ExtractColumns(f.Args[0])) > 0 {
|
|
// If it can be NULL, we need to filter NULL out first.
|
|
if !mysql.HasNotNullFlag(f.Args[0].GetType().Flag) {
|
|
sel := plannercore.LogicalSelection{}.Init(ctx, agg.SelectBlockOffset())
|
|
isNullFunc := expression.NewFunctionInternal(ctx, ast.IsNull, types.NewFieldType(mysql.TypeTiny), f.Args[0])
|
|
notNullFunc := expression.NewFunctionInternal(ctx, ast.UnaryNot, types.NewFieldType(mysql.TypeTiny), isNullFunc)
|
|
sel.Conditions = []expression.Expression{notNullFunc}
|
|
selExpr := memo.NewGroupExpr(sel)
|
|
selExpr.SetChildren(childGroup)
|
|
selGroup := memo.NewGroupWithSchema(selExpr, childGroup.Prop.Schema)
|
|
childGroup = selGroup
|
|
}
|
|
|
|
// Add top(1) operators.
|
|
// For max function, the sort order should be desc.
|
|
desc := f.Name == ast.AggFuncMax
|
|
var byItems []*util.ByItems
|
|
byItems = append(byItems, &util.ByItems{
|
|
Expr: f.Args[0],
|
|
Desc: desc,
|
|
})
|
|
top1 := plannercore.LogicalTopN{
|
|
ByItems: byItems,
|
|
Count: 1,
|
|
}.Init(ctx, agg.SelectBlockOffset())
|
|
top1Expr := memo.NewGroupExpr(top1)
|
|
top1Expr.SetChildren(childGroup)
|
|
top1Group := memo.NewGroupWithSchema(top1Expr, childGroup.Prop.Schema)
|
|
childGroup = top1Group
|
|
} else {
|
|
li := plannercore.LogicalLimit{Count: 1}.Init(ctx, agg.SelectBlockOffset())
|
|
liExpr := memo.NewGroupExpr(li)
|
|
liExpr.SetChildren(childGroup)
|
|
liGroup := memo.NewGroupWithSchema(liExpr, childGroup.Prop.Schema)
|
|
childGroup = liGroup
|
|
}
|
|
|
|
newAgg := agg
|
|
newAggExpr := memo.NewGroupExpr(newAgg)
|
|
// If no data in the child, we need to return NULL instead of empty. This cannot be done by sort and limit themselves.
|
|
// Since now there would be at most one row returned, the remained agg operator is not expensive anymore.
|
|
newAggExpr.SetChildren(childGroup)
|
|
newAggExpr.AddAppliedRule(r)
|
|
return []*memo.GroupExpr{newAggExpr}, false, false, nil
|
|
}
|
|
|
|
// MergeAdjacentSelection merge adjacent selection.
|
|
type MergeAdjacentSelection struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRuleMergeAdjacentSelection creates a new Transformation MergeAdjacentSelection.
|
|
// The pattern of this rule is `Selection->Selection->X`.
|
|
func NewRuleMergeAdjacentSelection() Transformation {
|
|
rule := &MergeAdjacentSelection{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandSelection,
|
|
memo.EngineAll,
|
|
memo.NewPattern(memo.OperandSelection, memo.EngineAll),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule tries to merge adjacent selection, with no simplification.
|
|
func (r *MergeAdjacentSelection) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
sel := old.GetExpr().ExprNode.(*plannercore.LogicalSelection)
|
|
child := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalSelection)
|
|
childGroups := old.Children[0].GetExpr().Children
|
|
|
|
conditions := make([]expression.Expression, 0, len(sel.Conditions)+len(child.Conditions))
|
|
conditions = append(conditions, sel.Conditions...)
|
|
conditions = append(conditions, child.Conditions...)
|
|
newSel := plannercore.LogicalSelection{Conditions: conditions}.Init(sel.SCtx(), sel.SelectBlockOffset())
|
|
newSelExpr := memo.NewGroupExpr(newSel)
|
|
newSelExpr.SetChildren(childGroups...)
|
|
return []*memo.GroupExpr{newSelExpr}, true, false, nil
|
|
}
|
|
|
|
// MergeAdjacentLimit merge the adjacent limit.
|
|
type MergeAdjacentLimit struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRuleMergeAdjacentLimit creates a new Transformation MergeAdjacentLimit.
|
|
// The pattern of this rule is `Limit->Limit->X`.
|
|
func NewRuleMergeAdjacentLimit() Transformation {
|
|
rule := &MergeAdjacentLimit{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandLimit,
|
|
memo.EngineAll,
|
|
memo.NewPattern(memo.OperandLimit, memo.EngineAll),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule tries to merge adjacent limit.
|
|
func (r *MergeAdjacentLimit) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
limit := old.GetExpr().ExprNode.(*plannercore.LogicalLimit)
|
|
child := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalLimit)
|
|
childGroups := old.Children[0].GetExpr().Children
|
|
|
|
if child.Count <= limit.Offset {
|
|
tableDual := plannercore.LogicalTableDual{RowCount: 0}.Init(child.SCtx(), child.SelectBlockOffset())
|
|
tableDual.SetSchema(old.GetExpr().Schema())
|
|
tableDualExpr := memo.NewGroupExpr(tableDual)
|
|
return []*memo.GroupExpr{tableDualExpr}, true, true, nil
|
|
}
|
|
|
|
offset := child.Offset + limit.Offset
|
|
count := uint64(math.Min(float64(child.Count-limit.Offset), float64(limit.Count)))
|
|
newLimit := plannercore.LogicalLimit{
|
|
Offset: offset,
|
|
Count: count,
|
|
}.Init(limit.SCtx(), limit.SelectBlockOffset())
|
|
newLimitExpr := memo.NewGroupExpr(newLimit)
|
|
newLimitExpr.SetChildren(childGroups...)
|
|
return []*memo.GroupExpr{newLimitExpr}, true, false, nil
|
|
}
|
|
|
|
// TransformLimitToTableDual convert limit to TableDual.
|
|
type TransformLimitToTableDual struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRuleTransformLimitToTableDual creates a new Transformation TransformLimitToTableDual.
|
|
// The pattern of this rule is `Limit->X`.
|
|
func NewRuleTransformLimitToTableDual() Transformation {
|
|
rule := &TransformLimitToTableDual{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandLimit,
|
|
memo.EngineAll,
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
func (r *TransformLimitToTableDual) Match(expr *memo.ExprIter) bool {
|
|
limit := expr.GetExpr().ExprNode.(*plannercore.LogicalLimit)
|
|
return 0 == limit.Count
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule tries to convert limit to tableDual.
|
|
func (r *TransformLimitToTableDual) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
limit := old.GetExpr().ExprNode.(*plannercore.LogicalLimit)
|
|
tableDual := plannercore.LogicalTableDual{RowCount: 0}.Init(limit.SCtx(), limit.SelectBlockOffset())
|
|
tableDual.SetSchema(old.GetExpr().Schema())
|
|
tableDualExpr := memo.NewGroupExpr(tableDual)
|
|
return []*memo.GroupExpr{tableDualExpr}, true, true, nil
|
|
}
|
|
|
|
// PushLimitDownOuterJoin pushes Limit through Join.
|
|
type PushLimitDownOuterJoin struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushLimitDownOuterJoin creates a new Transformation PushLimitDownOuterJoin.
|
|
// The pattern of this rule is `Limit -> Join`.
|
|
func NewRulePushLimitDownOuterJoin() Transformation {
|
|
rule := &PushLimitDownOuterJoin{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandLimit,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandJoin, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
func (r *PushLimitDownOuterJoin) Match(expr *memo.ExprIter) bool {
|
|
if expr.GetExpr().HasAppliedRule(r) {
|
|
return false
|
|
}
|
|
join := expr.Children[0].GetExpr().ExprNode.(*plannercore.LogicalJoin)
|
|
return join.JoinType.IsOuterJoin()
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule tries to pushes the Limit through outer Join.
|
|
func (r *PushLimitDownOuterJoin) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
limit := old.GetExpr().ExprNode.(*plannercore.LogicalLimit)
|
|
join := old.Children[0].GetExpr().ExprNode.(*plannercore.LogicalJoin)
|
|
joinSchema := old.Children[0].Group.Prop.Schema
|
|
leftGroup := old.Children[0].GetExpr().Children[0]
|
|
rightGroup := old.Children[0].GetExpr().Children[1]
|
|
|
|
switch join.JoinType {
|
|
case plannercore.LeftOuterJoin, plannercore.LeftOuterSemiJoin, plannercore.AntiLeftOuterSemiJoin:
|
|
leftGroup = r.pushLimitDownOuterJoinToChild(limit, leftGroup)
|
|
case plannercore.RightOuterJoin:
|
|
rightGroup = r.pushLimitDownOuterJoinToChild(limit, rightGroup)
|
|
default:
|
|
return nil, false, false, nil
|
|
}
|
|
|
|
newJoinExpr := memo.NewGroupExpr(join)
|
|
newJoinExpr.SetChildren(leftGroup, rightGroup)
|
|
newLimitExpr := memo.NewGroupExpr(limit)
|
|
newLimitExpr.SetChildren(memo.NewGroupWithSchema(newJoinExpr, joinSchema))
|
|
newLimitExpr.AddAppliedRule(r)
|
|
return []*memo.GroupExpr{newLimitExpr}, true, false, nil
|
|
}
|
|
|
|
func (r *PushLimitDownOuterJoin) pushLimitDownOuterJoinToChild(limit *plannercore.LogicalLimit, outerGroup *memo.Group) *memo.Group {
|
|
newLimit := plannercore.LogicalLimit{
|
|
Count: limit.Count + limit.Offset,
|
|
}.Init(limit.SCtx(), limit.SelectBlockOffset())
|
|
newLimitGroup := memo.NewGroupExpr(newLimit)
|
|
newLimitGroup.SetChildren(outerGroup)
|
|
return memo.NewGroupWithSchema(newLimitGroup, outerGroup.Prop.Schema)
|
|
}
|
|
|
|
// PushLimitDownTiKVSingleGather pushes the limit down to child of TiKVSingleGather.
|
|
type PushLimitDownTiKVSingleGather struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePushLimitDownTiKVSingleGather creates a new Transformation PushLimitDownTiKVSingleGather.
|
|
// The pattern of this rule is `Limit -> TiKVSingleGather`.
|
|
func NewRulePushLimitDownTiKVSingleGather() Transformation {
|
|
rule := &PushLimitDownTiKVSingleGather{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandLimit,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandTiKVSingleGather, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
// Use appliedRuleSet in GroupExpr to avoid re-apply rules.
|
|
func (r *PushLimitDownTiKVSingleGather) Match(expr *memo.ExprIter) bool {
|
|
return !expr.GetExpr().HasAppliedRule(r)
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// It transforms `Limit -> TiKVSingleGather` to `Limit(Final) -> TiKVSingleGather -> Limit(Partial)`.
|
|
func (r *PushLimitDownTiKVSingleGather) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
limit := old.GetExpr().ExprNode.(*plannercore.LogicalLimit)
|
|
limitSchema := old.Children[0].Group.Prop.Schema
|
|
gather := old.Children[0].GetExpr().ExprNode.(*plannercore.TiKVSingleGather)
|
|
childGroup := old.Children[0].GetExpr().Children[0]
|
|
|
|
particalLimit := plannercore.LogicalLimit{
|
|
Count: limit.Count + limit.Offset,
|
|
}.Init(limit.SCtx(), limit.SelectBlockOffset())
|
|
partialLimitExpr := memo.NewGroupExpr(particalLimit)
|
|
partialLimitExpr.SetChildren(childGroup)
|
|
partialLimitGroup := memo.NewGroupWithSchema(partialLimitExpr, limitSchema).SetEngineType(childGroup.EngineType)
|
|
|
|
gatherExpr := memo.NewGroupExpr(gather)
|
|
gatherExpr.SetChildren(partialLimitGroup)
|
|
gatherGroup := memo.NewGroupWithSchema(gatherExpr, limitSchema)
|
|
|
|
finalLimitExpr := memo.NewGroupExpr(limit)
|
|
finalLimitExpr.SetChildren(gatherGroup)
|
|
finalLimitExpr.AddAppliedRule(r)
|
|
return []*memo.GroupExpr{finalLimitExpr}, true, false, nil
|
|
}
|
|
|
|
type outerJoinEliminator struct {
|
|
}
|
|
|
|
func (*outerJoinEliminator) prepareForEliminateOuterJoin(joinExpr *memo.GroupExpr) (ok bool, innerChildIdx int, outerGroup *memo.Group, innerGroup *memo.Group, outerUniqueIDs set.Int64Set) {
|
|
join := joinExpr.ExprNode.(*plannercore.LogicalJoin)
|
|
|
|
switch join.JoinType {
|
|
case plannercore.LeftOuterJoin:
|
|
innerChildIdx = 1
|
|
case plannercore.RightOuterJoin:
|
|
innerChildIdx = 0
|
|
default:
|
|
ok = false
|
|
return
|
|
}
|
|
outerGroup = joinExpr.Children[1^innerChildIdx]
|
|
innerGroup = joinExpr.Children[innerChildIdx]
|
|
|
|
outerUniqueIDs = set.NewInt64Set()
|
|
for _, outerCol := range outerGroup.Prop.Schema.Columns {
|
|
outerUniqueIDs.Insert(outerCol.UniqueID)
|
|
}
|
|
|
|
ok = true
|
|
return
|
|
}
|
|
|
|
// check whether one of unique keys sets is contained by inner join keys.
|
|
func (*outerJoinEliminator) isInnerJoinKeysContainUniqueKey(innerGroup *memo.Group, joinKeys *expression.Schema) (bool, error) {
|
|
// builds UniqueKey info of innerGroup.
|
|
innerGroup.BuildKeyInfo()
|
|
for _, keyInfo := range innerGroup.Prop.Schema.Keys {
|
|
joinKeysContainKeyInfo := true
|
|
for _, col := range keyInfo {
|
|
if !joinKeys.Contains(col) {
|
|
joinKeysContainKeyInfo = false
|
|
break
|
|
}
|
|
}
|
|
if joinKeysContainKeyInfo {
|
|
return true, nil
|
|
}
|
|
}
|
|
return false, nil
|
|
}
|
|
|
|
// EliminateOuterJoinBelowAggregation eliminate the outer join which below aggregation.
|
|
type EliminateOuterJoinBelowAggregation struct {
|
|
baseRule
|
|
outerJoinEliminator
|
|
}
|
|
|
|
// NewRuleEliminateOuterJoinBelowAggregation creates a new Transformation EliminateOuterJoinBelowAggregation.
|
|
// The pattern of this rule is `Aggregation->Join->X`.
|
|
func NewRuleEliminateOuterJoinBelowAggregation() Transformation {
|
|
rule := &EliminateOuterJoinBelowAggregation{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandAggregation,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandJoin, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
func (r *EliminateOuterJoinBelowAggregation) Match(expr *memo.ExprIter) bool {
|
|
joinType := expr.Children[0].GetExpr().ExprNode.(*plannercore.LogicalJoin).JoinType
|
|
return joinType == plannercore.LeftOuterJoin || joinType == plannercore.RightOuterJoin
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule tries to eliminate outer join which below aggregation.
|
|
func (r *EliminateOuterJoinBelowAggregation) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
agg := old.GetExpr().ExprNode.(*plannercore.LogicalAggregation)
|
|
joinExpr := old.Children[0].GetExpr()
|
|
join := joinExpr.ExprNode.(*plannercore.LogicalJoin)
|
|
|
|
ok, innerChildIdx, outerGroup, innerGroup, outerUniqueIDs := r.prepareForEliminateOuterJoin(joinExpr)
|
|
if !ok {
|
|
return nil, false, false, nil
|
|
}
|
|
|
|
// only when agg only use the columns from outer table can eliminate outer join.
|
|
if !plannercore.IsColsAllFromOuterTable(agg.GetUsedCols(), outerUniqueIDs) {
|
|
return nil, false, false, nil
|
|
}
|
|
// outer join elimination with duplicate agnostic aggregate functions.
|
|
_, aggCols := plannercore.GetDupAgnosticAggCols(agg, nil)
|
|
if len(aggCols) > 0 {
|
|
newAggExpr := memo.NewGroupExpr(agg)
|
|
newAggExpr.SetChildren(outerGroup)
|
|
return []*memo.GroupExpr{newAggExpr}, true, false, nil
|
|
}
|
|
// outer join elimination without duplicate agnostic aggregate functions.
|
|
innerJoinKeys := join.ExtractJoinKeys(innerChildIdx)
|
|
contain, err := r.isInnerJoinKeysContainUniqueKey(innerGroup, innerJoinKeys)
|
|
if err != nil {
|
|
return nil, false, false, err
|
|
}
|
|
if contain {
|
|
newAggExpr := memo.NewGroupExpr(agg)
|
|
newAggExpr.SetChildren(outerGroup)
|
|
return []*memo.GroupExpr{newAggExpr}, true, false, nil
|
|
}
|
|
|
|
return nil, false, false, nil
|
|
}
|
|
|
|
// EliminateOuterJoinBelowProjection eliminate the outer join which below projection.
|
|
type EliminateOuterJoinBelowProjection struct {
|
|
baseRule
|
|
outerJoinEliminator
|
|
}
|
|
|
|
// NewRuleEliminateOuterJoinBelowProjection creates a new Transformation EliminateOuterJoinBelowProjection.
|
|
// The pattern of this rule is `Projection->Join->X`.
|
|
func NewRuleEliminateOuterJoinBelowProjection() Transformation {
|
|
rule := &EliminateOuterJoinBelowProjection{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandProjection,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandJoin, memo.EngineTiDBOnly),
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
func (r *EliminateOuterJoinBelowProjection) Match(expr *memo.ExprIter) bool {
|
|
joinType := expr.Children[0].GetExpr().ExprNode.(*plannercore.LogicalJoin).JoinType
|
|
return joinType == plannercore.LeftOuterJoin || joinType == plannercore.RightOuterJoin
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule tries to eliminate outer join which below projection.
|
|
func (r *EliminateOuterJoinBelowProjection) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
proj := old.GetExpr().ExprNode.(*plannercore.LogicalProjection)
|
|
joinExpr := old.Children[0].GetExpr()
|
|
join := joinExpr.ExprNode.(*plannercore.LogicalJoin)
|
|
|
|
ok, innerChildIdx, outerGroup, innerGroup, outerUniqueIDs := r.prepareForEliminateOuterJoin(joinExpr)
|
|
if !ok {
|
|
return nil, false, false, nil
|
|
}
|
|
|
|
// only when proj only use the columns from outer table can eliminate outer join.
|
|
if !plannercore.IsColsAllFromOuterTable(proj.GetUsedCols(), outerUniqueIDs) {
|
|
return nil, false, false, nil
|
|
}
|
|
|
|
innerJoinKeys := join.ExtractJoinKeys(innerChildIdx)
|
|
contain, err := r.isInnerJoinKeysContainUniqueKey(innerGroup, innerJoinKeys)
|
|
if err != nil {
|
|
return nil, false, false, err
|
|
}
|
|
if contain {
|
|
newProjExpr := memo.NewGroupExpr(proj)
|
|
newProjExpr.SetChildren(outerGroup)
|
|
return []*memo.GroupExpr{newProjExpr}, true, false, nil
|
|
}
|
|
|
|
return nil, false, false, nil
|
|
}
|
|
|
|
// TransformAggregateCaseToSelection convert Agg(case when) to Agg->Selection.
|
|
type TransformAggregateCaseToSelection struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRuleTransformAggregateCaseToSelection creates a new Transformation TransformAggregateCaseToSelection.
|
|
// The pattern of this rule is `Agg->X`.
|
|
func NewRuleTransformAggregateCaseToSelection() Transformation {
|
|
rule := &TransformAggregateCaseToSelection{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandAggregation,
|
|
memo.EngineTiDBOnly,
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
func (r *TransformAggregateCaseToSelection) Match(expr *memo.ExprIter) bool {
|
|
agg := expr.GetExpr().ExprNode.(*plannercore.LogicalAggregation)
|
|
return agg.IsCompleteModeAgg() && len(agg.GroupByItems) == 0 && len(agg.AggFuncs) == 1 && len(agg.AggFuncs[0].Args) == 1 && r.isTwoOrThreeArgCase(agg.AggFuncs[0].Args[0])
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule tries to convert Agg(case when) to Agg->Selection.
|
|
func (r *TransformAggregateCaseToSelection) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
agg := old.GetExpr().ExprNode.(*plannercore.LogicalAggregation)
|
|
|
|
ok, newConditions, newAggFuncs := r.transform(agg)
|
|
if !ok {
|
|
return nil, false, false, nil
|
|
}
|
|
|
|
newSel := plannercore.LogicalSelection{Conditions: newConditions}.Init(agg.SCtx(), agg.SelectBlockOffset())
|
|
newSelExpr := memo.NewGroupExpr(newSel)
|
|
newSelExpr.SetChildren(old.GetExpr().Children...)
|
|
newSelGroup := memo.NewGroupWithSchema(newSelExpr, old.GetExpr().Children[0].Prop.Schema)
|
|
|
|
newAgg := plannercore.LogicalAggregation{
|
|
AggFuncs: newAggFuncs,
|
|
GroupByItems: agg.GroupByItems,
|
|
}.Init(agg.SCtx(), agg.SelectBlockOffset())
|
|
newAgg.CopyAggHints(agg)
|
|
newAggExpr := memo.NewGroupExpr(newAgg)
|
|
newAggExpr.SetChildren(newSelGroup)
|
|
return []*memo.GroupExpr{newAggExpr}, true, false, nil
|
|
}
|
|
|
|
func (r *TransformAggregateCaseToSelection) transform(agg *plannercore.LogicalAggregation) (ok bool, newConditions []expression.Expression, newAggFuncs []*aggregation.AggFuncDesc) {
|
|
aggFuncDesc := agg.AggFuncs[0]
|
|
aggFuncName := aggFuncDesc.Name
|
|
ctx := agg.SCtx()
|
|
|
|
caseFunc := aggFuncDesc.Args[0].(*expression.ScalarFunction)
|
|
conditionFromCase := caseFunc.GetArgs()[0]
|
|
caseArgs := caseFunc.GetArgs()
|
|
caseArgsNum := len(caseArgs)
|
|
|
|
// `case when a>0 then null else a end` should be converted to `case when !(a>0) then a else null end`.
|
|
var nullFlip = caseArgsNum == 3 && caseArgs[1].Equal(ctx, expression.NewNull()) && !caseArgs[2].Equal(ctx, expression.NewNull())
|
|
// `case when a>0 then 0 else a end` should be converted to `case when !(a>0) then a else 0 end`.
|
|
var zeroFlip = !nullFlip && caseArgsNum == 3 && caseArgs[1].Equal(ctx, expression.NewZero())
|
|
|
|
var outputIdx int
|
|
if nullFlip || zeroFlip {
|
|
outputIdx = 2
|
|
newConditions = []expression.Expression{expression.NewFunctionInternal(ctx, ast.UnaryNot, types.NewFieldType(mysql.TypeTiny), conditionFromCase)}
|
|
} else {
|
|
outputIdx = 1
|
|
newConditions = expression.SplitCNFItems(conditionFromCase)
|
|
}
|
|
|
|
if aggFuncDesc.HasDistinct {
|
|
// Just one style supported:
|
|
// COUNT(DISTINCT CASE WHEN x = 'foo' THEN y END)
|
|
// =>
|
|
// newAggFuncDesc: COUNT(DISTINCT y), newCondition: x = 'foo'
|
|
|
|
if aggFuncName == ast.AggFuncCount && r.isOnlyOneNotNull(ctx, caseArgs, caseArgsNum, outputIdx) {
|
|
newAggFuncDesc := aggFuncDesc.Clone()
|
|
newAggFuncDesc.Args = []expression.Expression{caseArgs[outputIdx]}
|
|
return true, newConditions, []*aggregation.AggFuncDesc{newAggFuncDesc}
|
|
}
|
|
return false, nil, nil
|
|
}
|
|
|
|
// Two styles supported:
|
|
//
|
|
// A1: AGG(CASE WHEN x = 'foo' THEN cnt END)
|
|
// => newAggFuncDesc: AGG(cnt), newCondition: x = 'foo'
|
|
// A2: SUM(CASE WHEN x = 'foo' THEN cnt ELSE 0 END)
|
|
// => newAggFuncDesc: SUM(cnt), newCondition: x = 'foo'
|
|
|
|
switch {
|
|
case r.allowsSelection(aggFuncName) && (caseArgsNum == 2 || caseArgs[3-outputIdx].Equal(ctx, expression.NewNull())), // Case A1
|
|
aggFuncName == ast.AggFuncSum && caseArgsNum == 3 && caseArgs[3-outputIdx].Equal(ctx, expression.NewZero()): // Case A2
|
|
newAggFuncDesc := aggFuncDesc.Clone()
|
|
newAggFuncDesc.Args = []expression.Expression{caseArgs[outputIdx]}
|
|
return true, newConditions, []*aggregation.AggFuncDesc{newAggFuncDesc}
|
|
default:
|
|
return false, nil, nil
|
|
}
|
|
}
|
|
|
|
func (r *TransformAggregateCaseToSelection) allowsSelection(aggFuncName string) bool {
|
|
return aggFuncName != ast.AggFuncFirstRow
|
|
}
|
|
|
|
func (r *TransformAggregateCaseToSelection) isOnlyOneNotNull(ctx sessionctx.Context, args []expression.Expression, argsNum int, outputIdx int) bool {
|
|
return !args[outputIdx].Equal(ctx, expression.NewNull()) && (argsNum == 2 || args[3-outputIdx].Equal(ctx, expression.NewNull()))
|
|
}
|
|
|
|
// TransformAggregateCaseToSelection only support `case when cond then var end` and `case when cond then var1 else var2 end`.
|
|
func (r *TransformAggregateCaseToSelection) isTwoOrThreeArgCase(expr expression.Expression) bool {
|
|
scalarFunc, ok := expr.(*expression.ScalarFunction)
|
|
if !ok {
|
|
return false
|
|
}
|
|
return scalarFunc.FuncName.L == ast.Case && (len(scalarFunc.GetArgs()) == 2 || len(scalarFunc.GetArgs()) == 3)
|
|
}
|
|
|
|
// TransformAggToProj convert Agg to Proj.
|
|
type TransformAggToProj struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRuleTransformAggToProj creates a new Transformation TransformAggToProj.
|
|
// The pattern of this rule is `Agg`.
|
|
func NewRuleTransformAggToProj() Transformation {
|
|
rule := &TransformAggToProj{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandAggregation,
|
|
memo.EngineTiDBOnly,
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
func (r *TransformAggToProj) Match(expr *memo.ExprIter) bool {
|
|
agg := expr.GetExpr().ExprNode.(*plannercore.LogicalAggregation)
|
|
|
|
if !agg.IsCompleteModeAgg() {
|
|
return false
|
|
}
|
|
|
|
for _, af := range agg.AggFuncs {
|
|
// TODO(issue #9968): same as rule_aggregation_elimination.go -> tryToEliminateAggregation.
|
|
// waiting for (issue #14616): `nullable` information.
|
|
if af.Name == ast.AggFuncGroupConcat {
|
|
return false
|
|
}
|
|
}
|
|
|
|
childGroup := expr.GetExpr().Children[0]
|
|
childGroup.BuildKeyInfo()
|
|
schemaByGroupby := expression.NewSchema(agg.GetGroupByCols()...)
|
|
for _, key := range childGroup.Prop.Schema.Keys {
|
|
if schemaByGroupby.ColumnsIndices(key) != nil {
|
|
return true
|
|
}
|
|
}
|
|
|
|
return false
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule tries to convert agg to proj.
|
|
func (r *TransformAggToProj) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
agg := old.GetExpr().ExprNode.(*plannercore.LogicalAggregation)
|
|
if ok, proj := plannercore.ConvertAggToProj(agg, old.GetExpr().Schema()); ok {
|
|
newProjExpr := memo.NewGroupExpr(proj)
|
|
newProjExpr.SetChildren(old.GetExpr().Children...)
|
|
return []*memo.GroupExpr{newProjExpr}, true, false, nil
|
|
}
|
|
|
|
return nil, false, false, nil
|
|
}
|
|
|
|
// InjectProjectionBelowTopN injects two Projections below and upon TopN if TopN's ByItems
|
|
// contain ScalarFunctions.
|
|
type InjectProjectionBelowTopN struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRuleInjectProjectionBelowTopN creates a new Transformation InjectProjectionBelowTopN.
|
|
// It will extract the ScalarFunctions of `ByItems` into a Projection and injects it below TopN.
|
|
// When a Projection is injected as the child of TopN, we need to add another Projection upon
|
|
// TopN to prune the extra Columns.
|
|
// The reason why we need this rule is that, TopNExecutor in TiDB does not support ScalarFunction
|
|
// as `ByItem`. So we have to use a Projection to calculate the ScalarFunctions in advance.
|
|
// The pattern of this rule is: a single TopN
|
|
func NewRuleInjectProjectionBelowTopN() Transformation {
|
|
rule := &InjectProjectionBelowTopN{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandTopN,
|
|
memo.EngineTiDBOnly,
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// Match implements Transformation interface.
|
|
func (r *InjectProjectionBelowTopN) Match(expr *memo.ExprIter) bool {
|
|
topN := expr.GetExpr().ExprNode.(*plannercore.LogicalTopN)
|
|
for _, item := range topN.ByItems {
|
|
if _, ok := item.Expr.(*expression.ScalarFunction); ok {
|
|
return true
|
|
}
|
|
}
|
|
return false
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// It will convert `TopN -> X` to `Projection -> TopN -> Projection -> X`.
|
|
func (r *InjectProjectionBelowTopN) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
topN := old.GetExpr().ExprNode.(*plannercore.LogicalTopN)
|
|
oldTopNSchema := old.GetExpr().Schema()
|
|
|
|
// Construct top Projection.
|
|
topProjExprs := make([]expression.Expression, oldTopNSchema.Len())
|
|
for i := range oldTopNSchema.Columns {
|
|
topProjExprs[i] = oldTopNSchema.Columns[i]
|
|
}
|
|
topProj := plannercore.LogicalProjection{
|
|
Exprs: topProjExprs,
|
|
}.Init(topN.SCtx(), topN.SelectBlockOffset())
|
|
topProj.SetSchema(oldTopNSchema)
|
|
|
|
// Construct bottom Projection.
|
|
bottomProjExprs := make([]expression.Expression, 0, oldTopNSchema.Len()+len(topN.ByItems))
|
|
bottomProjSchema := make([]*expression.Column, 0, oldTopNSchema.Len()+len(topN.ByItems))
|
|
for _, col := range oldTopNSchema.Columns {
|
|
bottomProjExprs = append(bottomProjExprs, col)
|
|
bottomProjSchema = append(bottomProjSchema, col)
|
|
}
|
|
newByItems := make([]*util.ByItems, 0, len(topN.ByItems))
|
|
for _, item := range topN.ByItems {
|
|
itemExpr := item.Expr
|
|
if _, isScalarFunc := itemExpr.(*expression.ScalarFunction); !isScalarFunc {
|
|
newByItems = append(newByItems, item)
|
|
continue
|
|
}
|
|
bottomProjExprs = append(bottomProjExprs, itemExpr)
|
|
newCol := &expression.Column{
|
|
UniqueID: topN.SCtx().GetSessionVars().AllocPlanColumnID(),
|
|
RetType: itemExpr.GetType(),
|
|
}
|
|
bottomProjSchema = append(bottomProjSchema, newCol)
|
|
newByItems = append(newByItems, &util.ByItems{Expr: newCol, Desc: item.Desc})
|
|
}
|
|
bottomProj := plannercore.LogicalProjection{
|
|
Exprs: bottomProjExprs,
|
|
}.Init(topN.SCtx(), topN.SelectBlockOffset())
|
|
newSchema := expression.NewSchema(bottomProjSchema...)
|
|
bottomProj.SetSchema(newSchema)
|
|
|
|
newTopN := plannercore.LogicalTopN{
|
|
ByItems: newByItems,
|
|
Offset: topN.Offset,
|
|
Count: topN.Count,
|
|
}.Init(topN.SCtx(), topN.SelectBlockOffset())
|
|
|
|
// Construct GroupExpr, Group (TopProj -> TopN -> BottomProj -> Child)
|
|
bottomProjGroupExpr := memo.NewGroupExpr(bottomProj)
|
|
bottomProjGroupExpr.SetChildren(old.GetExpr().Children[0])
|
|
bottomProjGroup := memo.NewGroupWithSchema(bottomProjGroupExpr, newSchema)
|
|
|
|
topNGroupExpr := memo.NewGroupExpr(newTopN)
|
|
topNGroupExpr.SetChildren(bottomProjGroup)
|
|
topNGroup := memo.NewGroupWithSchema(topNGroupExpr, newSchema)
|
|
|
|
topProjGroupExpr := memo.NewGroupExpr(topProj)
|
|
topProjGroupExpr.SetChildren(topNGroup)
|
|
return []*memo.GroupExpr{topProjGroupExpr}, true, false, nil
|
|
}
|
|
|
|
// TransformApplyToJoin transforms a LogicalApply to LogicalJoin if it's
|
|
// inner children has no correlated columns from it's outer schema.
|
|
type TransformApplyToJoin struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRuleTransformApplyToJoin creates a new Transformation TransformApplyToJoin.
|
|
// The pattern of this rule is: `Apply -> (X, Y)`.
|
|
func NewRuleTransformApplyToJoin() Transformation {
|
|
rule := &TransformApplyToJoin{}
|
|
rule.pattern = memo.NewPattern(memo.OperandApply, memo.EngineTiDBOnly)
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
func (r *TransformApplyToJoin) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
apply := old.GetExpr().ExprNode.(*plannercore.LogicalApply)
|
|
groupExpr := old.GetExpr()
|
|
// It's safe to use the old apply instead of creating a new LogicalApply here,
|
|
// Because apply.CorCols will only be used and updated by this rule during Transformation.
|
|
apply.CorCols = r.extractCorColumnsBySchema(groupExpr.Children[1], groupExpr.Children[0].Prop.Schema)
|
|
if len(apply.CorCols) != 0 {
|
|
return nil, false, false, nil
|
|
}
|
|
|
|
join := apply.LogicalJoin.Shallow()
|
|
joinGroupExpr := memo.NewGroupExpr(join)
|
|
joinGroupExpr.SetChildren(groupExpr.Children...)
|
|
return []*memo.GroupExpr{joinGroupExpr}, true, false, nil
|
|
}
|
|
|
|
func (r *TransformApplyToJoin) extractCorColumnsBySchema(innerGroup *memo.Group, outerSchema *expression.Schema) []*expression.CorrelatedColumn {
|
|
corCols := r.extractCorColumnsFromGroup(innerGroup)
|
|
return plannercore.ExtractCorColumnsBySchema(corCols, outerSchema)
|
|
}
|
|
|
|
func (r *TransformApplyToJoin) extractCorColumnsFromGroup(g *memo.Group) []*expression.CorrelatedColumn {
|
|
corCols := make([]*expression.CorrelatedColumn, 0)
|
|
for elem := g.Equivalents.Front(); elem != nil; elem = elem.Next() {
|
|
expr := elem.Value.(*memo.GroupExpr)
|
|
corCols = append(corCols, expr.ExprNode.ExtractCorrelatedCols()...)
|
|
for _, child := range expr.Children {
|
|
corCols = append(corCols, r.extractCorColumnsFromGroup(child)...)
|
|
}
|
|
}
|
|
// We may have duplicate CorrelatedColumns here, but it won't influence
|
|
// the logic of the transformation. Apply.CorCols will be deduplicated in
|
|
// `ResolveIndices`.
|
|
return corCols
|
|
}
|
|
|
|
// PullSelectionUpApply pulls up the inner-side Selection into Apply as
|
|
// its join condition.
|
|
type PullSelectionUpApply struct {
|
|
baseRule
|
|
}
|
|
|
|
// NewRulePullSelectionUpApply creates a new Transformation PullSelectionUpApply.
|
|
// The pattern of this rule is: `Apply -> (Any<outer>, Selection<inner>)`.
|
|
func NewRulePullSelectionUpApply() Transformation {
|
|
rule := &PullSelectionUpApply{}
|
|
rule.pattern = memo.BuildPattern(
|
|
memo.OperandApply,
|
|
memo.EngineTiDBOnly,
|
|
memo.NewPattern(memo.OperandAny, memo.EngineTiDBOnly), // outer child
|
|
memo.NewPattern(memo.OperandSelection, memo.EngineTiDBOnly), // inner child
|
|
)
|
|
return rule
|
|
}
|
|
|
|
// OnTransform implements Transformation interface.
|
|
// This rule tries to pull up the inner side Selection, and add these conditions
|
|
// to Join condition inside the Apply.
|
|
func (r *PullSelectionUpApply) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error) {
|
|
apply := old.GetExpr().ExprNode.(*plannercore.LogicalApply)
|
|
outerChildGroup := old.Children[0].Group
|
|
innerChildGroup := old.Children[1].Group
|
|
sel := old.Children[1].GetExpr().ExprNode.(*plannercore.LogicalSelection)
|
|
newConds := make([]expression.Expression, 0, len(sel.Conditions))
|
|
for _, cond := range sel.Conditions {
|
|
newConds = append(newConds, cond.Clone().Decorrelate(outerChildGroup.Prop.Schema))
|
|
}
|
|
newApply := plannercore.LogicalApply{
|
|
LogicalJoin: *(apply.LogicalJoin.Shallow()),
|
|
CorCols: apply.CorCols,
|
|
}.Init(apply.SCtx(), apply.SelectBlockOffset())
|
|
// Update Join conditions.
|
|
eq, left, right, other := newApply.LogicalJoin.ExtractOnCondition(newConds, outerChildGroup.Prop.Schema, innerChildGroup.Prop.Schema, false, false)
|
|
newApply.LogicalJoin.AppendJoinConds(eq, left, right, other)
|
|
|
|
newApplyGroupExpr := memo.NewGroupExpr(newApply)
|
|
newApplyGroupExpr.SetChildren(outerChildGroup, old.Children[1].GetExpr().Children[0])
|
|
return []*memo.GroupExpr{newApplyGroupExpr}, false, false, nil
|
|
}
|
|
|