search

Documentation

Overview

Package search implements a generic query optimizer algorithm. It's loosely based on the Volcano/Cascades/Columbia line of optimizer frameworks. These are rule-driven top-down optimizers that use dynamic programming to avoid duplicating effort. This package takes the set of rules (and various other things) as input, and applies them to look for a low-cost implementation plan for a query.

Index

• func Prepare(ctx context.Context, expr *IntoExpr, def Definition, options Options) (*Space, PlanNode, error)
• type Cost
• type Definition
• type ExplorationRule
• type Expr
  • func (expr *Expr) Key(b *strings.Builder)
  • func (expr *Expr) String() string
• type Group
• type ImplementationRule
• type IntoExpr
  • func NewExpr(operator Operator, inputs ...intoExprInput) *IntoExpr
  • func (expr *IntoExpr) String() string
• type LogicalProperties
• type Operator
• type Options
• type PlanNode
• type Space
  • func NewSpace(expr *IntoExpr, def Definition, options Options) *Space
  • func (space *Space) BestPlan() (PlanNode, error)
  • func (space *Space) CheckInvariants() error
  • func (space *Space) Contains(pattern string) bool
  • func (space *Space) Debug(w bytes.StringWriter)
  • func (space *Space) DebugCostedBest(w bytes.StringWriter)
  • func (space *Space) Explore()
  • func (space *Space) Graphviz(w io.Writer)
  • func (space *Space) Implement()
  • func (space *Space) MustCheckInvariants()
  • func (space *Space) PredictCosts()
  • func (space *Space) String() string

Functions

func Prepare

func Prepare(ctx context.Context, expr *IntoExpr, def Definition, options Options) (*Space, PlanNode, error)

Prepare finds the best plan for the given query. The selected plan as well as the search space that generated it are returned. The search space is returned in error cases as well to allow the caller further introspection to the problem if needed.

This is a high-level interface to the query planner; for more control see Space. The supplied context is used to generate tracing spans and to allow for the planning operation to be canceled before it is completed. There is no I/O performed by this function.

Types

type Cost

type Cost interface {
	// Returns a human-readable single-line description of the cost.
	String() string
	// Returns true if the expression can't be executed in any reasonable period of
	// time, false otherwise.
	Infinite() bool
	// Returns true if this cost is strictly lower than the given cost, false otherwise.
	// This method may assume the two Costs have been produced by the same Estimator
	// (for most Estimators, this and 'other' will have the same type).
	Less(other Cost) bool
}

Cost represents an estimated cost for an Expr, used to find a low-cost plan.

type Definition

type Definition interface {
	// ExplorationRules returns the set of exploration rules that the optimizer may
	// apply in searching for a low-cost plan.
	ExplorationRules() []ExplorationRule
	// ImplementationRules returns the set of implementation rules that the
	// optimizer may apply in searching for a low-cost plan.
	ImplementationRules() []ImplementationRule
	// LocalCost returns the predicted costs of the operator itself, excluding
	// the costs of its inputs. It should return an infiniteCost for non-physical
	// operators. When invoked, each expr.Inputs group will have LogicalProperties
	// available but may not have Best set, and each of the groups Exprs may not have
	// LocalCost or CombinedCost set.
	LocalCost(expr *Expr) Cost
	// CombinedCost returns the cost of the operator combined with the costs of its inputs.
	// When invoked, each expr.Inputs group wil have Best set, and the Best expr
	// will have its LocalCost and CombinedCost set.
	// For most operators, this returns:
	//    expr.LocalCost + [group.Best.CombinedCost for group in expr.Inputs]
	CombinedCost(expr *Expr) Cost
	// LogicalProperties computes and returns the logical properties for a logical
	// expression. It should panic if invoked for a physical operators, as this is
	// only needed when creating a new logical equivalence class.
	LogicalProperties(op Operator, inputs []LogicalProperties) LogicalProperties
	// MakePlanNode creates a new PlanNode object. A simple implementation could
	// just create a struct out of the given arguments, but this function exists as
	// an opportunity for the user of this package to transform the output into a
	// more convenient format. For example, the given operator can be cast into a
	// more specific type.
	MakePlanNode(op Operator, inputs []PlanNode, lprop LogicalProperties) PlanNode
}

A Definition is the interface that users of this package need to define.

type ExplorationRule

type ExplorationRule struct {
	Name string
	// Returns logical or physical expressions that are equivalent to the input.
	Apply func(*Expr) []*IntoExpr
}

An ExplorationRule defines a logical equivalence.

type Expr

type Expr struct {
	// Logical or physical operator.
	Operator Operator
	// The operator reads from these to generate its output.
	Inputs []*Group
	// The cost of this algorithm, excluding the costs of its inputs.
	LocalCost Cost
	// A lower bound on the cost of this expression (including the costs of its
	// inputs).
	CombinedCost Cost
	// The expression's equivalence class.
	Group *Group
	// contains filtered or unexported fields
}

An Expr bundles a logical or physical operator along with its input groups.

func (*Expr) Key

func (expr *Expr) Key(b *strings.Builder)

Key implements cmp.Key. It writes the identity of the expression to the given strings.Builder: its operator's key and its input group IDs. This package uses the Key method to track expressions in a map; it's probably not useful outside this package but is public to implement util/cmp.Key.

func (*Expr) String

func (expr *Expr) String() string

Returns a single-line string describing the operator and its input group IDs.

type Group

type Group struct {
	// A unique identifier for the Group within the Plan, which is useful for
	// human-readable output.
	ID int
	// The set of logically equivalent expressions that make up this Group, in no
	// particular order. Groups reachable from the root of the DAG will have
	// a non-empty set of expressions. Unless otherwise stated, this field and
	// everything accessible through it are read-only outside this package.
	Exprs []*Expr
	// The query planner may write to this field to indicate which of the
	// expressions has the lowest cost.
	Best *Expr
	// User-defined properties that are true for every Expr in this Group.
	LogicalProp LogicalProperties
	// contains filtered or unexported fields
}

A Group is a set of logically equivalent expressions.

type ImplementationRule

type ImplementationRule struct {
	Name string
	// Returns physical expressions that are equivalent to the non-physical input.
	Apply func(*Expr) []*IntoExpr
}

An ImplementationRule maps logical expressions to physical access plans.

type IntoExpr

type IntoExpr struct {
	// Logical or physical operator.
	Operator Operator
	// A list of *IntoExpr or *Group inputs.
	Inputs []intoExprInput
}

IntoExpr represents an expression that hasn't yet been integrated into the search space. It's used when the logical properties are already known, such as when creating an expression that's logically equivalent to another. IntoExpr is constructed with NewExpr.

func NewExpr

func NewExpr(operator Operator, inputs ...intoExprInput) *IntoExpr

NewExpr is a convenience function for building an IntoExpr tree. Permissible inputs are either *Group or *IntoExpr.

func (*IntoExpr) String

func (expr *IntoExpr) String() string

String returns a multi-line indented human-readable string describing the new expression.

type LogicalProperties

type LogicalProperties interface {
	String() string
	DetailString() string
}

LogicalProperties are properties that remain true across logically equivalent expressions. They are defined by the specific optimizer needs but are commonly used to represent the schema of the results and the expected result size.

type Operator

type Operator interface {
	// Returns a human-readable single-line string describing the operator.
	String() string
	// The identity of an Operator is given by its Key() output. Two distinct
	// operators or operators with distinct parameters must produce distinct
	// keys. Also, the returned key cannot change over the lifetime of the
	// Operator -- Operators should be immutable.
	cmp.Key
}

An Operator is a logical or physical (executable) function attached to an expression.

type Options

type Options struct {
	// Used in testing: If set, checks the integrity of the Space's internal
	// structure after changes, and panics on errors.
	CheckInternalInvariants bool
	// Used in testing: If set, called to test the validity of expressions in the
	// Space.
	Invariants func(space *Space, root *Group)
	// If set Prepare will check the invariants after each of the major steps, Explore
	// Implement, PredictCosts.
	CheckInvariantsAfterMajorSteps bool
}

Options are configuration settings for the Space.

type PlanNode

type PlanNode interface{}

A PlanNode is part of a physically executable plan. It represents one node in the plan tree that is the result of the search. A PlanNode differs from an Expr in that it takes concrete inputs, whereas an Expr takes equivalence classes as inputs.

type Space

type Space struct {
	// contains filtered or unexported fields
}

A Space represents the search space of a single query's equivalent logical expressions and physical implementation plans. In other words, it holds the explored plans for a single query.

Space provides a somewhat low-level interface to the query planner; for a simpler interface, see Prepare.

The methods on Space are also likely to change in the future. Right now, exploration, implementation, and costing are done as discrete steps. The Cascades/Columbia papers argue for running some implementation rules and predicting some costs earlier in the process.

The core methods of Space must be invoked in this exact order:

space := NewSpace(expr, rules)
space.Explore()
space.Implement()
space.PredictCosts(estimator)
return space.BestPlan()

In between these calls, however, you can invoke String() or Graphviz() to get more information.

func NewSpace

func NewSpace(expr *IntoExpr, def Definition, options Options) *Space

NewSpace creates a search space from the given logical expression tree.

func (*Space) BestPlan

func (space *Space) BestPlan() (PlanNode, error)

BestPlan returns an execution plan with the lowest cost. If multiple plans have the same cost, it returns one arbitrarily. Returns an error if no suitable execution plan has been found.

func (*Space) CheckInvariants

func (space *Space) CheckInvariants() error

CheckInvariants runs internal consistency checks on the space data structure. It was initially used for testing and debugging but may also be called less frequently during runtime.

func (*Space) Contains

func (space *Space) Contains(pattern string) bool

Contains looks for the given expression tree in the space. It returns true if it found a matching expression tree, false otherwise. Contains is intended for unit tests only. It panics if the pattern isn't indented correctly.

pattern should be a multi-line indented string like this:

Join
    Select
        Scan A
    Join
        Scan B
        Scan C

The lines must match the String() values of operators in the search space exactly.

func (*Space) Debug

func (space *Space) Debug(w bytes.StringWriter)

Debug will write detailed information about the current state of the space to the supplied StringWriter. It includes more details than what String() does.

func (*Space) DebugCostedBest

func (space *Space) DebugCostedBest(w bytes.StringWriter)

DebugCostedBest will write the details of the selected plan including the costing information to the supplied StringWriter.

func (*Space) Explore

func (space *Space) Explore()

Explore looks for equivalent logical plans that would give the same results as the original query. One of these new logical plans may turn out to yield a lower-cost execution plan.

func (*Space) Graphviz

func (space *Space) Graphviz(w io.Writer)

Graphviz writes a Graphviz dot-formatted description of the search space. Note: it ignores errors in writing to w.

func (*Space) Implement

func (space *Space) Implement()

Implement chooses physical execution operators to implement the logical operators in the plan space. Note that some logical operators may not be implementable; those will be left out of all execution plans.

func (*Space) MustCheckInvariants

func (space *Space) MustCheckInvariants()

MustCheckInvariants runs CheckInvariants and panics if there are any issues.

func (*Space) PredictCosts

func (space *Space) PredictCosts()

PredictCosts assigns estimated costs to the possible physical execution plans.

func (*Space) String

func (space *Space) String() string

Returns a multi-line human-readable description of the groups in the search space.