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

Source Files

View all Source files

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.