pir

package
v0.0.0-...-86e9f11 Latest Latest
Warning

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

Go to latest
Published: Jan 7, 2024 License: Apache-2.0 Imports: 11 Imported by: 0

Documentation

Overview

Package pir manages the low-level query plan intermediate representation. This is where most of the query plan construction and optimization happens.

Index

Constants

View Source
const LargeSize = 10000

LargeSize is the point at which an exact cardinality is considered to be "large" rather than "small"

Variables

This section is empty.

Functions

This section is empty.

Types

type Aggregate

type Aggregate struct {
	Agg vm.Aggregation
	// GroupBy is nil for normal
	// aggregations, or non-nil
	// when the aggregation is formed
	// on multiple columns
	//
	// note that the groups form part
	// of the binding set
	GroupBy []expr.Binding

	// NonEmpty, if true, indicates that no results
	// should be produced when zero rows reach this op
	NonEmpty bool
	// contains filtered or unexported fields
}

Aggregate is an aggregation operation that produces a new set of bindings

type Bind

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

Bind is a collection of transformations that produce a set of output bindings from the current binding environment

func (*Bind) Bindings

func (b *Bind) Bindings() []expr.Binding

type CompileError

type CompileError struct {
	In  expr.Node
	Err string
}

CompileError is an error associated with compiling a particular expression.

func (*CompileError) Error

func (c *CompileError) Error() string

Error implements error

func (*CompileError) WriteTo

func (c *CompileError) WriteTo(dst io.Writer) (int64, error)

WriteTo implements io.WriterTo

WriteTo writes a plaintext representation of the error to dst, including the expression associated with the error.

type Distinct

type Distinct struct {
	Columns []expr.Node
	// contains filtered or unexported fields
}

type DummyOutput

type DummyOutput struct{}

DummyOutput is a dummy input of one record, {}

type Env

type Env interface {
	// Schema returns type hints associated
	// with a particular table expression.
	// In the event that there is no available
	// type information, Schema may return nil.
	Schema(expr.Node) expr.Hint
	// Index returns the index for the given table
	// expression. This may return (nil, nil) if
	// the index for the table is not available.
	Index(expr.Node) (Index, error)
}

Env can be provided in calls to Build to provide additional context for plan optimization purposes.

type EquiJoin

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

type Filter

type Filter struct {
	Where expr.Node
	// contains filtered or unexported fields
}

type Index

type Index interface {
	// TimeRange returns the inclusive time range
	// for the given path expression across the
	// given table.
	TimeRange(path []string) (min, max date.Time, ok bool)
	// HasPartition returns true if the index
	// can be partitioned on the provided field,
	// or false otherwise.
	HasPartition(field string) bool
}

type IterTable

type IterTable struct {
	Table       *expr.Table
	Schema      expr.Hint
	Index       Index
	Partitioned bool

	// OnEqual, if present, indicates that this table
	// is only iterated for partitions that match
	//
	//   OnEqual[i] = PARTITION_VALUE(i)
	//
	OnEqual []string
	// contains filtered or unexported fields
}

func (*IterTable) Fields

func (i *IterTable) Fields() []string

Fields returns the fields belonging to the table that are actually referenced. Note that zero fields are returned if *either* the table is referenced with * or if no fields are actually referenced. Use IterTable.Wildcard to determine if the table is referenced with *

func (*IterTable) Wildcard

func (i *IterTable) Wildcard() bool

Wildcard returns true if the table is referenced by the '*' operator (in other words, if all column bindings in the table are live at some point in the program)

type IterValue

type IterValue struct {
	Value  expr.Node // the expression to be iterated
	Result string    // the binding produced by iteration
	// contains filtered or unexported fields
}

type Limit

type Limit struct {
	Count  int64
	Offset int64
	// contains filtered or unexported fields
}

type NoOutput

type NoOutput struct{}

NoOutput is a dummy input of 0 rows.

type Order

type Order struct {
	Columns []expr.Order
	// contains filtered or unexported fields
}

type OutputIndex

type OutputIndex struct {
	Table    expr.Node
	Basename string
	// contains filtered or unexported fields
}

OutputIndex is a step that takes the "part" field of incoming rows and constructs an index out of them, returning a single row like

{"table": "db.table-XXXXXX"}

type OutputPart

type OutputPart struct {
	Basename string
	// contains filtered or unexported fields
}

OutputPart writes output rows into a single part and returns a row like

{"part": "path/to/packed-XXXXX.ion.zst"}

type SizeClass

type SizeClass int

SizeClass is one of the output size classifications. See SizeZero, SizeOne, etc.

const (
	// SizeZero is the SizeClass
	// for queries that produce
	// zero rows of output.
	SizeZero SizeClass = iota
	// SizeOne is the SizeClass
	// for queries that produce
	// exactly one row of output.
	SizeOne
	// SizeExactSmall is the SizeClass
	// for queries that have an exact
	// cardinality (due to the presence
	// of LIMIT, etc.) and the cardinality
	// is known to be "small" for some
	// definition of "small" ...
	SizeExactSmall
	// SizeColumnCardinality is the SizeClass
	// for queries that have inexact cardinality
	// but produce a small-ish number of output
	// rows due to the presence of a grouping operation.
	// (Our optimistic assumption is that the cardinality
	// of most columns in most datasets is lower than LargeSize.)
	SizeColumnCardinality
	// SizeExactLarge is the SizeClass
	// for queries that have an exact
	// cardinality that is "large."
	SizeExactLarge
	// SizeUnknown is the SizeClass
	// for queries that have unknown output size.
	SizeUnknown
)

func (SizeClass) Exact

func (s SizeClass) Exact() bool

Exact returns whether the SizeClass has exact (known) cardinality.

func (SizeClass) Small

func (s SizeClass) Small() bool

Small returns whether the SizeClass is considered "small."

Whether or not a trace produces a "small" output set determines how certain query planning optimizations are performed.

func (SizeClass) String

func (s SizeClass) String() string

type Step

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

func Input

func Input(s Step) Step

Input returns the input to a Step

type Trace

type Trace struct {
	// If this trace is not a root trace,
	// then Parent will be a trace that
	// has this trace as one of its inputs.
	Parent *Trace
	// Replacements are traces that produce
	// results that are necessary in order
	// to execute this trace.
	// The results of input traces
	// are available to this trace
	// through the SCALAR_REPLACEMENT(index)
	// and IN_REPLACEMENT(index) expressions.
	// The traces in Input may be executed
	// in any order.
	Replacements []*Trace
	// contains filtered or unexported fields
}

Trace is a linear sequence of physical plan operators. Traces are arranged in a tree, where each Trace depends on the execution of zero or more children (see Inputs).

func Build

func Build(q *expr.Query, e Env) (*Trace, error)

Build walks the provided Query and lowers it into the optimized query IR. If the provided SchemaHint is non-nil, then it will be used to provide additional type information that can be used to type-check and optimize the query.

func NoSplit

func NoSplit(t *Trace) *Trace

NoSplit optimizes a trace assuming it won't ever be passed to Split.

func Split

func Split(b *Trace) (*Trace, error)

Split splits a query plan into a mapping step and a reduction step. The argument to split is destructively edited to become the mapping step, and the returned step is the new reduction step. If the query can't be split (either because it is not profitable or not possible), the returned Builder is the same as the argument.

The mapping step of the query plan can be performed in parallel (on different machines, etc.), and the rows output by the mapping step can be unioned and then passed to the reduction step, which produces the final query results.

NOTE: Split destructively edits the Builder query provided to it, so the scope information yielded by b.Scope() will no longer be accurate. Also, Split will panic if it is called on a query that has already been split.

func (*Trace) Aggregate

func (b *Trace) Aggregate(agg vm.Aggregation, groups []expr.Binding) error

Aggregate pushes an aggregation to the stack

func (*Trace) Begin

func (b *Trace) Begin(f *expr.Table, e Env) error

func (*Trace) Bind

func (b *Trace) Bind(bindings ...[]expr.Binding) error

Bind pushes a set of variable bindings to the stack

func (*Trace) BindStar

func (b *Trace) BindStar() error

func (*Trace) Class

func (b *Trace) Class() SizeClass

Class returns the "size class" of the result of executing the trace. See SizeClass for the definition of each result size class.

func (*Trace) Describe

func (b *Trace) Describe(dst io.Writer)

Describe writes a plain-text representation of b to dst. The output of this representation is purely for diagnostic purposes; it cannot be deserialized back into a trace.

func (*Trace) Distinct

func (b *Trace) Distinct(exprs []expr.Node) error

Distinct takes a sets of bindings and produces only distinct sets of output tuples of the given variable bindings

func (*Trace) DistinctFromBindings

func (b *Trace) DistinctFromBindings(bind []expr.Binding) error

func (*Trace) Equals

func (b *Trace) Equals(x *Trace) bool

Equals returns true if b and x would produce the same rows and thus can be substituted for one another.

func (*Trace) Final

func (b *Trace) Final() Step

Final returns the final step of the query. The caller can use Input to walk the inputs to each step up to the first input step.

func (*Trace) FinalBindings

func (b *Trace) FinalBindings() []expr.Binding

FinalBindings returns the set of output bindings, or none if they could not be computed

func (*Trace) FinalTypes

func (b *Trace) FinalTypes() []expr.TypeSet

FinalTypes returns the computed ion type sets of the output bindings. Each element of the returned slice corresponds with the same index in the return value of Builder.FinalBindings

Note that the return value may be nil if the query does not produce a know (finite) result-set

func (*Trace) Into

func (b *Trace) Into(table expr.Node, basepath string)

Into handles the INTO clause by pushing the appropriate OutputIndex and OutputPart nodes.

func (*Trace) Iterate

func (b *Trace) Iterate(bind *expr.Binding) error

Iterate pushes an implicit iteration to the stack

func (*Trace) LimitOffset

func (b *Trace) LimitOffset(limit, offset int64) error

LimitOffset pushes a limit operation to the stack

func (*Trace) Order

func (b *Trace) Order(cols []expr.Order) error

Order pushes an ordering to the stack

func (*Trace) Rewrite

func (b *Trace) Rewrite(rw expr.Rewriter)

func (*Trace) String

func (b *Trace) String() string

String implements fmt.Stringer.

func (*Trace) Where

func (b *Trace) Where(e expr.Node) error

Where pushes a filter to the expression stack

type UnionMap

type UnionMap struct {
	// Inner is the table that needs
	// to be partitioned into the child
	// subquery.
	Inner *IterTable
	// Child is the sub-query that is
	// applied to the partitioned table.
	Child *Trace
	// PartitionBy is a list of fields
	// over which the unioning should be partitioned.
	// PartitionBy[i] corresponds to PARTITION_VALUE(i)
	// within each step within Child.
	PartitionBy []string
	// contains filtered or unexported fields
}

UnionMap represents a terminal query Step that unions the results of parallel invocations of the Child subquery operation.

type Unpivot

type Unpivot struct {
	Ast *expr.Unpivot // The AST node this node was constructed from
	// contains filtered or unexported fields
}

Unpivot represents the UNPIVOT expr AS as AT at statement

type UnpivotAtDistinct

type UnpivotAtDistinct struct {
	Ast *expr.Unpivot // The AST node this node was constructed from
	// contains filtered or unexported fields
}

UnpivotAtDistinct represents the UNPIVOT expr AT x GROUP BY x statement

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL