plan

package
v0.15.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 16, 2019 License: MIT Imports: 8 Imported by: 19

Documentation

Index

Constants

View Source 
const AnyKind = "*** any procedure kind ***"
View Source 
const DefaultYieldName = "_result"

DefaultYieldName is the name of a result that doesn't have any name assigned.

Variables

View Source 
var EmptyBounds = &Bounds{
	Start: values.Time(0),
	Stop:  values.Time(0),
}

EmptyBounds is a time range containing only a single point

Functions

func ComputeBounds 

func ComputeBounds(node PlanNode) error

ComputeBounds computes the time bounds for a plan node from the bounds of its predecessors.

func Formatted 

func Formatted(p *PlanSpec, opts ...FormatOption) fmt.Formatter

TODO(cwolff): enhance the this output to make it more useful

func HasSideEffect added in v0.8.0 

func HasSideEffect(spec ProcedureSpec) bool

func RegisterLogicalRules 

func RegisterLogicalRules(rules ...Rule)

RegisterLogicalRules registers the rule created by createFn with the logical plan.

func RegisterPhysicalRules 

func RegisterPhysicalRules(rules ...Rule)

RegisterPhysicalRules registers the rule created by createFn with the physical plan.

func RegisterProcedureSpec 

func RegisterProcedureSpec(k ProcedureKind, c CreateProcedureSpec, qks ...flux.OperationKind)

RegisterProcedureSpec registers a new procedure with the specified kind. The call panics if the kind is not unique.

func RegisterProcedureSpecWithSideEffect 

func RegisterProcedureSpecWithSideEffect(k ProcedureKind, c CreateProcedureSpec, qks ...flux.OperationKind)

RegisterProcedureSpecWithSideEffect registers a new procedure that produces side effects

func ReplaceNode added in v0.10.0 

func ReplaceNode(oldNode, newNode PlanNode)

ReplaceNode accepts two nodes and attaches all the predecessors of the old node to the new node. 

S1   S2        S1   S2
  \ /
oldNode   =>   newNode
  / \            / \
P1   P2        P1   P2

As is convention, newNode will not have any successors attached. The planner will take care of this.

func WalkPredecessors added in v0.10.0 

func WalkPredecessors(roots []PlanNode, visitFn func(node PlanNode) error) error

WalkPredecessor visits every node in the plan rooted at `roots` in topological order, following predecessor links. If a cycle is detected, no node is visited and an error is returned.

func WalkSuccessors added in v0.10.0 

func WalkSuccessors(roots []PlanNode, visitFn func(node PlanNode) error) error

WalkSuccessors visits every node in the plan rooted at `roots` in topological order, following successor links. If a cycle is detected, no node is visited and an error is returned.

Types

type Administration 

type Administration interface {
	Now() time.Time
}

type AnyPattern 

type AnyPattern struct{}

AnyPattern describes (and matches) any plan node

func (AnyPattern) Match 

func (AnyPattern) Match(node PlanNode) bool

func (AnyPattern) Root 

func (AnyPattern) Root() ProcedureKind

type Bounds 

type Bounds struct {
	Start values.Time
	Stop  values.Time
}

Bounds is a range of time

func (*Bounds) Contains 

func (b *Bounds) Contains(t values.Time) bool

Contains reports whether a given time is contained within the time range

func (*Bounds) Intersect 

func (b *Bounds) Intersect(o *Bounds) *Bounds

Intersect returns the intersection of two bounds. It returns empty bounds if one of the input bounds are empty.

func (*Bounds) IsEmpty 

func (b *Bounds) IsEmpty() bool

IsEmpty reports whether the given bounds contain at most a single point

func (*Bounds) Overlaps 

func (b *Bounds) Overlaps(o *Bounds) bool

Overlaps reports whether two given bounds have overlapping time ranges

func (*Bounds) Shift 

func (b *Bounds) Shift(d values.Duration) *Bounds

Shift moves the start and stop values of a time range by a specified duration

func (*Bounds) Union 

func (b *Bounds) Union(o *Bounds) *Bounds

Union returns the smallest bounds which contain both input bounds. It returns empty bounds if one of the input bounds are empty.

type BoundsAwareProcedureSpec 

type BoundsAwareProcedureSpec interface {
	TimeBounds(predecessorBounds *Bounds) *Bounds
}

BoundsAwareProcedureSpec is any procedure that modifies the time bounds of its data.

type Cost 

type Cost struct {
	Disk int64
	CPU  int64
	GPU  int64
	MEM  int64
	NET  int64
}

Cost stores various dimensions of the cost of a query plan

func Add 

func Add(a Cost, b Cost) Cost

Add two cost structures together

type CreateProcedureSpec 

type CreateProcedureSpec func(flux.OperationSpec, Administration) (ProcedureSpec, error)

CreateProcedureSpec creates a ProcedureSpec from an OperationSpec and Administration

type DefaultCost 

type DefaultCost struct {
}

func (DefaultCost) Cost 

func (c DefaultCost) Cost(inStats []Statistics) (Cost, Statistics)

type FormatOption 

type FormatOption func(*formatter)

type GeneratedYieldProcedureSpec 

type GeneratedYieldProcedureSpec struct {
	DefaultCost
	Name string
}

GeneratedYieldProcedureSpec provides a special planner-generated yield for queries that don't have explicit calls to yield().

func (*GeneratedYieldProcedureSpec) Copy 

func (y *GeneratedYieldProcedureSpec) Copy() ProcedureSpec

func (*GeneratedYieldProcedureSpec) Kind 

func (y *GeneratedYieldProcedureSpec) Kind() ProcedureKind

func (*GeneratedYieldProcedureSpec) YieldName 

func (y *GeneratedYieldProcedureSpec) YieldName() string

type LogicalOption 

type LogicalOption interface {
	// contains filtered or unexported methods
}

LogicalOption is an option to configure the behavior of the logical plan.

func DisableIntegrityChecks added in v0.10.0 

func DisableIntegrityChecks() LogicalOption

Disables integrity checks in the logical planner

func OnlyLogicalRules 

func OnlyLogicalRules(rules ...Rule) LogicalOption

OnlyLogicalRules produces a logical plan option that forces only a set of particular rules to be applied.

type LogicalPlanNode 

type LogicalPlanNode struct {
	Spec ProcedureSpec
	// contains filtered or unexported fields
}

LogicalPlanNode consists of the input and output edges and a procedure spec that describes what the node does.

func CreateLogicalNode 

func CreateLogicalNode(id NodeID, spec ProcedureSpec) *LogicalPlanNode

CreateLogicalNode creates a single logical plan node from a procedure spec. The newly created logical node has no incoming or outgoing edges.

func (*LogicalPlanNode) AddPredecessors 

func (e *LogicalPlanNode) AddPredecessors(nodes ...PlanNode)

func (*LogicalPlanNode) AddSuccessors 

func (e *LogicalPlanNode) AddSuccessors(nodes ...PlanNode)

func (*LogicalPlanNode) Bounds 

func (b *LogicalPlanNode) Bounds() *Bounds

func (*LogicalPlanNode) ClearPredecessors 

func (e *LogicalPlanNode) ClearPredecessors()

func (*LogicalPlanNode) ClearSuccessors 

func (e *LogicalPlanNode) ClearSuccessors()

func (*LogicalPlanNode) ID 

func (lpn *LogicalPlanNode) ID() NodeID

ID returns a human-readable identifier unique to this plan.

func (*LogicalPlanNode) Kind 

func (lpn *LogicalPlanNode) Kind() ProcedureKind

Kind returns the kind of procedure performed by this plan node.

func (*LogicalPlanNode) Predecessors 

func (e *LogicalPlanNode) Predecessors() []PlanNode

func (*LogicalPlanNode) ProcedureSpec 

func (lpn *LogicalPlanNode) ProcedureSpec() ProcedureSpec

ProcedureSpec returns the procedure spec for this plan node.

func (*LogicalPlanNode) ReplaceSpec 

func (lpn *LogicalPlanNode) ReplaceSpec(newSpec ProcedureSpec) error

func (*LogicalPlanNode) SetBounds 

func (b *LogicalPlanNode) SetBounds(bounds *Bounds)

func (*LogicalPlanNode) ShallowCopy 

func (lpn *LogicalPlanNode) ShallowCopy() PlanNode

func (*LogicalPlanNode) Successors 

func (e *LogicalPlanNode) Successors() []PlanNode

type LogicalPlanner 

type LogicalPlanner interface {
	Plan(spec *flux.Spec) (*PlanSpec, error)
}

LogicalPlanner translates a flux.Spec into a PlanSpec and applies any registered logical rules to the plan.

Logical planning should transform the plan in ways that are independent of actual physical algorithms used to implement operations, and independent of the actual data being processed.

func NewLogicalPlanner 

func NewLogicalPlanner(options ...LogicalOption) LogicalPlanner

NewLogicalPlanner returns a new logical plan with the given options. The plan will be configured to apply any logical rules that have been registered.

type NodeID 

type NodeID string

type OneKindPattern 

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

OneKindPattern matches a specified procedure with a predecessor pattern 

           ProcedureKind
         /       |  ...  \
pattern1     pattern2  ... patternK

func (OneKindPattern) Match 

func (okp OneKindPattern) Match(node PlanNode) bool

func (OneKindPattern) Root 

func (okp OneKindPattern) Root() ProcedureKind

type Pattern 

type Pattern interface {
	Root() ProcedureKind
	Match(PlanNode) bool
}

Pattern represents an operator tree pattern It can match itself against a query plan

func Any 

func Any() Pattern

Any returns a pattern that matches anything.

func Pat 

func Pat(kind ProcedureKind, predecessors ...Pattern) Pattern

Pat returns a pattern that can match a plan node with the given ProcedureKind and whose predecessors match the given predecessor patterns.

For example, to construct a pattern that matches a join followed by a sum: 

 sum
  |
 |X|    <=>  join(A, B) |> sum()  <=>  Pat(SumKind, Pat(JoinKind, Any(), Any()))
/   \

A B

type PhysicalAttributes 

type PhysicalAttributes struct {
}

PhysicalAttributes encapsulates sny physical attributes of the result produced by a physical plan node, such as collation, etc.

type PhysicalOption 

type PhysicalOption interface {
	// contains filtered or unexported methods
}

PhysicalOption is an option to configure the behavior of the physical plan.

func DisableValidation added in v0.10.0 

func DisableValidation() PhysicalOption

Disables validation in the physical planner

func OnlyPhysicalRules 

func OnlyPhysicalRules(rules ...Rule) PhysicalOption

OnlyPhysicalRules produces a physical plan option that forces only a particular set of rules to be applied.

func WithDefaultMemoryLimit 

func WithDefaultMemoryLimit(memBytes int64) PhysicalOption

WithDefaultMemoryLimit sets the default memory limit for plans generated by the plan. If the query spec explicitly sets a memory limit, that limit is used instead of the default.

type PhysicalPlanNode 

type PhysicalPlanNode struct {
	Spec PhysicalProcedureSpec

	// The attributes required from inputs to this node
	RequiredAttrs []PhysicalAttributes

	// The attributes provided to consumers of this node's output
	OutputAttrs PhysicalAttributes
	// contains filtered or unexported fields
}

PhysicalPlanNode represents a physical operation in a plan.

func CreatePhysicalNode 

func CreatePhysicalNode(id NodeID, spec PhysicalProcedureSpec) *PhysicalPlanNode

CreatePhysicalNode creates a single physical plan node from a procedure spec. The newly created physical node has no incoming or outgoing edges.

func (*PhysicalPlanNode) AddPredecessors 

func (e *PhysicalPlanNode) AddPredecessors(nodes ...PlanNode)

func (*PhysicalPlanNode) AddSuccessors 

func (e *PhysicalPlanNode) AddSuccessors(nodes ...PlanNode)

func (*PhysicalPlanNode) Bounds 

func (b *PhysicalPlanNode) Bounds() *Bounds

func (*PhysicalPlanNode) ClearPredecessors 

func (e *PhysicalPlanNode) ClearPredecessors()

func (*PhysicalPlanNode) ClearSuccessors 

func (e *PhysicalPlanNode) ClearSuccessors()

func (*PhysicalPlanNode) Cost 

func (ppn *PhysicalPlanNode) Cost(inStats []Statistics) (cost Cost, outStats Statistics)

Cost provides the self-cost (i.e., does not include the cost of its predecessors) for this plan node. Caller must provide statistics of predecessors to this node.

func (*PhysicalPlanNode) ID 

func (ppn *PhysicalPlanNode) ID() NodeID

ID returns a human-readable id for this plan node.

func (*PhysicalPlanNode) Kind 

func (ppn *PhysicalPlanNode) Kind() ProcedureKind

Kind returns the procedure kind for this plan node.

func (*PhysicalPlanNode) Predecessors 

func (e *PhysicalPlanNode) Predecessors() []PlanNode

func (*PhysicalPlanNode) ProcedureSpec 

func (ppn *PhysicalPlanNode) ProcedureSpec() ProcedureSpec

ProcedureSpec returns the procedure spec for this plan node.

func (*PhysicalPlanNode) ReplaceSpec 

func (ppn *PhysicalPlanNode) ReplaceSpec(newSpec ProcedureSpec) error

func (*PhysicalPlanNode) SetBounds 

func (b *PhysicalPlanNode) SetBounds(bounds *Bounds)

func (*PhysicalPlanNode) ShallowCopy 

func (ppn *PhysicalPlanNode) ShallowCopy() PlanNode

func (*PhysicalPlanNode) Successors 

func (e *PhysicalPlanNode) Successors() []PlanNode

type PhysicalPlanner 

type PhysicalPlanner interface {
	Plan(lplan *PlanSpec) (*PlanSpec, error)
}

PhysicalPlanner performs transforms a logical plan to a physical plan, by applying any registered physical rules.

func NewPhysicalPlanner 

func NewPhysicalPlanner(options ...PhysicalOption) PhysicalPlanner

NewPhysicalPlanner creates a new physical plan with the specified options. The new plan will be configured to apply any physical rules that have been registered.

type PhysicalProcedureSpec 

type PhysicalProcedureSpec interface {
	Kind() ProcedureKind
	Copy() ProcedureSpec
	Cost(inStats []Statistics) (cost Cost, outStats Statistics)
}

PhysicalProcedureSpec is similar to its logical counterpart but must provide a method to determine cost.

type PlanNode 

type PlanNode interface {
	// Returns an identifier for this plan node
	ID() NodeID

	// Returns the time bounds for this plan node
	Bounds() *Bounds

	// Plan nodes executed immediately before this node
	Predecessors() []PlanNode

	// Plan nodes executed immediately after this node
	Successors() []PlanNode

	// Specification of the procedure represented by this node
	ProcedureSpec() ProcedureSpec

	// Replaces the procedure spec of this node with another
	ReplaceSpec(ProcedureSpec) error

	// Type of procedure represented by this node
	Kind() ProcedureKind

	// Helper methods for manipulating a plan
	// These methods are used during planning
	SetBounds(bounds *Bounds)
	AddSuccessors(...PlanNode)
	AddPredecessors(...PlanNode)
	ClearSuccessors()
	ClearPredecessors()

	ShallowCopy() PlanNode
}

PlanNode defines the common interface for interacting with logical and physical plan nodes.

func MergeLogicalPlanNodes 

func MergeLogicalPlanNodes(top, bottom PlanNode, procSpec ProcedureSpec) (PlanNode, error)

MergeLogicalPlanNodes merges top and bottom plan nodes into a new plan node, with the given procedure spec. 

V1     V2       V1            V2       <-- successors
  \   /
   top             mergedNode
    |      ==>         |
  bottom               W
    |
    W

The returned node will have its predecessors set to the predecessors of "bottom", however, it's successors will not be set---it will be the responsibility of the plan to attach the merged node to its successors.

func MergePhysicalPlanNodes 

func MergePhysicalPlanNodes(top, bottom PlanNode, procSpec PhysicalProcedureSpec) (PlanNode, error)

func SwapPlanNodes 

func SwapPlanNodes(top, bottom PlanNode) (PlanNode, error)

SwapPlanNodes swaps two plan nodes and returns an equivalent sub-plan with the nodes swapped. 

V1   V2        V1   V2
  \ /
   A              B
   |     ==>      |
   B          copy of A
   |              |
   W              W

Note that successors of the original top node will not be updated, and the returned plan node will have no successors. It will be the responsibility of the plan to attach the swapped nodes to successors.

type PlanSpec 

type PlanSpec struct {
	Roots     map[PlanNode]struct{}
	Resources flux.ResourceManagement
	Now       time.Time
}

PlanSpec holds the result nodes of a query plan with associated metadata

func NewPlanSpec 

func NewPlanSpec() *PlanSpec

NewPlanSpec initializes a new query plan

func (*PlanSpec) BottomUpWalk 

func (plan *PlanSpec) BottomUpWalk(f func(PlanNode) error) error

BottomUpWalk will execute f for each plan node in the PlanSpec, starting from the sources, and only visiting a node after all its predecessors have been visited.

func (*PlanSpec) CheckIntegrity added in v0.10.0 

func (plan *PlanSpec) CheckIntegrity() error

CheckIntegrity checks the integrity of the plan, i.e.:

  • node A is predecessor of B iff B is successor of A;
  • there is no cycle.

This check only detects this problem (N2 is predecessor of R, but not viceversa): 

N1 <----> R
          |
N2 <-------

And this one (R is successor of N2, but not viceversa): 

N1 <-------
|         |--> R
N2 --------

But not this one, because N2 is not reachable from R (root): 

N1 <-------
          |--> R
N2 --------

func (*PlanSpec) Replace 

func (plan *PlanSpec) Replace(root, with PlanNode)

Replace replaces one of the root nodes of the query plan

func (*PlanSpec) TopDownWalk 

func (plan *PlanSpec) TopDownWalk(f func(node PlanNode) error) error

TopDownWalk will execute f for each plan node in the PlanSpec. It always visits a node before visiting its predecessors.

func (*PlanSpec) TopologicalWalk added in v0.10.0 

func (plan *PlanSpec) TopologicalWalk(visitFn func(node PlanNode) error) error

TopologicalWalk visits every node in the plan in topological order. If a cycle is detected, no node is visited and an error is returned.

type PostPhysicalValidator 

type PostPhysicalValidator interface {
	PostPhysicalValidate(id NodeID) error
}

PostPhysicalValidator provides an interface that can be implemented by PhysicalProcedureSpecs for any validation checks to be performed post-physical planning.

type ProcedureKind 

type ProcedureKind string

ProcedureKind denotes the kind of operation

type ProcedureSpec 

type ProcedureSpec interface {
	Kind() ProcedureKind
	Copy() ProcedureSpec
}

ProcedureSpec specifies a query operation

type Rule 

type Rule interface {
	// The name of this rule (must be unique)
	Name() string

	// Pattern for this rule to match against
	Pattern() Pattern

	// Rewrite an operation into an equivalent one
	// The returned node is the new root of the sub tree.
	// The boolean return value should be true if anything changed during the rewrite.
	Rewrite(PlanNode) (PlanNode, bool, error)
}

Rule is transformation rule for a query operation

type Statistics 

type Statistics struct {
	Cardinality      int64
	GroupCardinality int64
}

type WindowSpec 

type WindowSpec struct {
	Every  flux.Duration
	Period flux.Duration
	Round  flux.Duration
	Start  flux.Time
}

type YieldProcedureSpec 

type YieldProcedureSpec interface {
	YieldName() string
}

YieldProcedureSpec is a special procedure that has the side effect of returning a result to the client.

Source Files

View all Source files

Directories

Path Synopsis
Package plantest contains utilities for testing each query planning phase
 Package plantest contains utilities for testing each query planning phase

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.