tidb: github.com/pingcap/tidb/planner/cascades Index | Files

package cascades

import "github.com/pingcap/tidb/planner/cascades"

Index

Package Files

enforcer_rules.go implementation_rules.go optimize.go transformation_rules.go

func FindBestPlan Uses

func FindBestPlan(sctx sessionctx.Context, logical plannercore.LogicalPlan) (p plannercore.PhysicalPlan, err error)

FindBestPlan is the optimization entrance of the cascades planner. The optimization is composed of 2 phases: exploration and implementation.

------------------------------------------------------------------------------ Phase 1: Exploration ------------------------------------------------------------------------------

The target of this phase is to explore all the logically equivalent expressions by exploring all the equivalent group expressions of each group.

At the very beginning, there is only one group expression in a Group. After applying some transformation rules on certain expressions of the Group, all the equivalent expressions are found and stored in the Group. This procedure can be regarded as searching for a weak connected component in a directed graph, where nodes are expressions and directed edges are the transformation rules.

------------------------------------------------------------------------------ Phase 2: Implementation ------------------------------------------------------------------------------

The target of this phase is to search the best physical plan for a Group which satisfies a certain required physical property.

In this phase, we need to enumerate all the applicable implementation rules for each expression in each group under the required physical property. A memo structure is used for a group to reduce the repeated search on the same required physical property.

type Enforcer Uses

type Enforcer interface {
    // NewProperty generates relaxed property with the help of enforcer.
    NewProperty(prop *property.PhysicalProperty) (newProp *property.PhysicalProperty)
    // OnEnforce adds physical operators on top of child implementation to satisfy
    // required physical property.
    OnEnforce(reqProp *property.PhysicalProperty, child memo.Implementation) (impl memo.Implementation)
    // GetEnforceCost calculates cost of enforcing required physical property.
    GetEnforceCost(inputCount float64) float64
}

Enforcer defines the interface for enforcer rules.

func GetEnforcerRules Uses

func GetEnforcerRules(prop *property.PhysicalProperty) (enforcers []Enforcer)

GetEnforcerRules gets all candidate enforcer rules based on required physical property.

type EnumeratePaths Uses

type EnumeratePaths struct {
}

EnumeratePaths converts DataSource to table scan and index scans.

func (*EnumeratePaths) GetPattern Uses

func (r *EnumeratePaths) GetPattern() *memo.Pattern

GetPattern implements Transformation interface. The pattern of this rule is `DataSource`.

func (*EnumeratePaths) Match Uses

func (r *EnumeratePaths) Match(expr *memo.ExprIter) bool

Match implements Transformation interface.

func (*EnumeratePaths) OnTransform Uses

func (r *EnumeratePaths) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error)

OnTransform implements Transformation interface.

type ImplProjection Uses

type ImplProjection struct {
}

ImplProjection implements LogicalProjection as PhysicalProjection.

func (*ImplProjection) Match Uses

func (r *ImplProjection) Match(expr *memo.GroupExpr, prop *property.PhysicalProperty) (matched bool)

Match implements ImplementationRule Match interface.

func (*ImplProjection) OnImplement Uses

func (r *ImplProjection) OnImplement(expr *memo.GroupExpr, reqProp *property.PhysicalProperty) (memo.Implementation, error)

OnImplement implements ImplementationRule OnImplement interface.

type ImplShow Uses

type ImplShow struct {
}

ImplShow is the implementation rule which implements LogicalShow to PhysicalShow.

func (*ImplShow) Match Uses

func (r *ImplShow) Match(expr *memo.GroupExpr, prop *property.PhysicalProperty) (matched bool)

Match implements ImplementationRule Match interface.

func (*ImplShow) OnImplement Uses

func (r *ImplShow) OnImplement(expr *memo.GroupExpr, reqProp *property.PhysicalProperty) (memo.Implementation, error)

OnImplement implements ImplementationRule OnImplement interface.

type ImplTableDual Uses

type ImplTableDual struct {
}

ImplTableDual implements LogicalTableDual as PhysicalTableDual.

func (*ImplTableDual) Match Uses

func (r *ImplTableDual) Match(expr *memo.GroupExpr, prop *property.PhysicalProperty) (matched bool)

Match implements ImplementationRule Match interface.

func (*ImplTableDual) OnImplement Uses

func (r *ImplTableDual) OnImplement(expr *memo.GroupExpr, reqProp *property.PhysicalProperty) (memo.Implementation, error)

OnImplement implements ImplementationRule OnImplement interface.

type ImplTableGather Uses

type ImplTableGather struct {
}

ImplTableGather implements TableGather as PhysicalTableReader.

func (*ImplTableGather) Match Uses

func (r *ImplTableGather) Match(expr *memo.GroupExpr, prop *property.PhysicalProperty) (matched bool)

Match implements ImplementationRule Match interface.

func (*ImplTableGather) OnImplement Uses

func (r *ImplTableGather) OnImplement(expr *memo.GroupExpr, reqProp *property.PhysicalProperty) (memo.Implementation, error)

OnImplement implements ImplementationRule OnImplement interface.

type ImplTableScan Uses

type ImplTableScan struct {
}

ImplTableScan implements TableScan as PhysicalTableScan.

func (*ImplTableScan) Match Uses

func (r *ImplTableScan) Match(expr *memo.GroupExpr, prop *property.PhysicalProperty) (matched bool)

Match implements ImplementationRule Match interface.

func (*ImplTableScan) OnImplement Uses

func (r *ImplTableScan) OnImplement(expr *memo.GroupExpr, reqProp *property.PhysicalProperty) (memo.Implementation, error)

OnImplement implements ImplementationRule OnImplement interface.

type ImplementationRule Uses

type ImplementationRule interface {
    // Match checks if current GroupExpr matches this rule under required physical property.
    Match(expr *memo.GroupExpr, prop *property.PhysicalProperty) (matched bool)
    // OnImplement generates physical plan using this rule for current GroupExpr. Note that
    // childrenReqProps of generated physical plan should be set correspondingly in this function.
    OnImplement(expr *memo.GroupExpr, reqProp *property.PhysicalProperty) (memo.Implementation, error)
}

ImplementationRule defines the interface for implementation rules.

func GetImplementationRules Uses

func GetImplementationRules(node plannercore.LogicalPlan) []ImplementationRule

GetImplementationRules gets all the candidate implementation rules for the logical plan node.

type OrderEnforcer Uses

type OrderEnforcer struct {
}

OrderEnforcer enforces order property on child implementation.

func (*OrderEnforcer) GetEnforceCost Uses

func (e *OrderEnforcer) GetEnforceCost(inputCount float64) float64

GetEnforceCost calculates cost of sort operator.

func (*OrderEnforcer) NewProperty Uses

func (e *OrderEnforcer) NewProperty(prop *property.PhysicalProperty) (newProp *property.PhysicalProperty)

NewProperty removes order property from required physical property.

func (*OrderEnforcer) OnEnforce Uses

func (e *OrderEnforcer) OnEnforce(reqProp *property.PhysicalProperty, child memo.Implementation) (impl memo.Implementation)

OnEnforce adds sort operator to satisfy required order property.

type PushSelDownTableGather Uses

type PushSelDownTableGather struct {
}

PushSelDownTableGather pushes the selection down to child of TableGather.

func (*PushSelDownTableGather) GetPattern Uses

func (r *PushSelDownTableGather) GetPattern() *memo.Pattern

GetPattern implements Transformation interface. The pattern of this rule is `Selection -> TableGather -> Any`

func (*PushSelDownTableGather) Match Uses

func (r *PushSelDownTableGather) Match(expr *memo.ExprIter) bool

Match implements Transformation interface.

func (*PushSelDownTableGather) OnTransform Uses

func (r *PushSelDownTableGather) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error)

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`

type PushSelDownTableScan Uses

type PushSelDownTableScan struct {
}

PushSelDownTableScan pushes the selection down to TableScan.

func (*PushSelDownTableScan) GetPattern Uses

func (r *PushSelDownTableScan) GetPattern() *memo.Pattern

GetPattern implements Transformation interface. The pattern of this rule is `Selection -> TableScan`.

func (*PushSelDownTableScan) Match Uses

func (r *PushSelDownTableScan) Match(expr *memo.ExprIter) bool

Match implements Transformation interface.

func (*PushSelDownTableScan) OnTransform Uses

func (r *PushSelDownTableScan) OnTransform(old *memo.ExprIter) (newExprs []*memo.GroupExpr, eraseOld bool, eraseAll bool, err error)

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.

type Transformation Uses

type Transformation interface {
    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)
}

Transformation defines the interface for the transformation rules.

func GetTransformationRules Uses

func GetTransformationRules(node plannercore.LogicalPlan) []Transformation

GetTransformationRules gets the all the candidate transformation rules based on the logical plan node.

Package cascades imports 9 packages (graph) and is imported by 3 packages. Updated 2019-09-22. Refresh now. Tools for package owners.