cockroach: github.com/cockroachdb/cockroach/pkg/sql/opt/memo Index | Files

package memo

import "github.com/cockroachdb/cockroach/pkg/sql/opt/memo"

Index

Package Files

check_expr.go constraint_builder.go cost.go expr.go expr_format.go expr_name_gen.go extract.go group.go interner.go logical_props_builder.go memo.go statistics_builder.go typing.go

Variables

var CountRowsSingleton = &CountRowsExpr{}

CountRowsSingleton maintains a global instance of CountRowsExpr, to avoid allocations.

var CumeDistSingleton = &CumeDistExpr{}

CumeDistSingleton is the global instance of CumeDistExpr.

var DenseRankSingleton = &DenseRankExpr{}

DenseRankSingleton is the global instance of DenseRankExpr.

var EmptyGroupingPrivate = &GroupingPrivate{}

EmptyGroupingPrivate is a global instance of a GroupingPrivate that has no grouping columns and no ordering.

var EmptyJoinPrivate = &JoinPrivate{}

EmptyJoinPrivate is a global instance of a JoinPrivate that has no fields set.

var EmptyTuple = &TupleExpr{Typ: types.EmptyTuple}

EmptyTuple is a global instance of a TupleExpr that contains no elements. While this cannot be created in SQL, it can be the created by normalizations.

var ExprFmtInterceptor func(f *ExprFmtCtx, tp treeprinter.Node, nd opt.Expr) bool

ExprFmtInterceptor is a callback that can be set to a custom formatting function. If the function returns true, the normal formatting code is bypassed.

var FalseFilter = FiltersExpr{{Condition: FalseSingleton}}

FalseFilter is a global instance of a FiltersExpr that contains a single False expression, used in contradiction situations:

SELECT * FROM a WHERE 1=0
var FalseSingleton = &FalseExpr{}

FalseSingleton is a global instance of FalseExpr, to avoid allocations.

var MaxCost = Cost(math.Inf(+1))

MaxCost is the maximum possible estimated cost. It's used to suppress memo group members during testing, by setting their cost so high that any other member will have a lower cost.

var NullSingleton = &NullExpr{Typ: types.Unknown}

NullSingleton is a global instance of NullExpr having the Unknown type (most common case), to avoid allocations.

var PercentRankSingleton = &PercentRankExpr{}

PercentRankSingleton is the global instance of PercentRankExpr.

var RankSingleton = &RankExpr{}

RankSingleton is the global instance of RankExpr.

var RowNumberSingleton = &RowNumberExpr{}

RowNumberSingleton is the global instance of RowNumber.

var ScalarListWithEmptyTuple = ScalarListExpr{EmptyTuple}

ScalarListWithEmptyTuple is a global instance of a ScalarListExpr containing a TupleExpr that contains no elements. It's used when constructing an empty ValuesExpr:

SELECT 1
var ScanIsReverseFn func(md *opt.Metadata, s *ScanPrivate, required *physical.OrderingChoice) bool

ScanIsReverseFn is a callback that is used to figure out if a scan needs to happen in reverse (the code lives in the ordering package, and depending on that directly would be a dependency loop).

var TrueFilter = FiltersExpr{}

TrueFilter is a global instance of the empty FiltersExpr, used in situations where the filter should always evaluate to true:

SELECT * FROM a INNER JOIN b ON True
var TrueSingleton = &TrueExpr{}

TrueSingleton is a global instance of TrueExpr, to avoid allocations.

func AggregateOverloadExists Uses

func AggregateOverloadExists(agg opt.Operator, typ *types.T) bool

AggregateOverloadExists returns whether or not the given operator has a unary overload which takes the given type as input.

func BinaryAllowsNullArgs Uses

func BinaryAllowsNullArgs(op opt.Operator, leftType, rightType *types.T) bool

BinaryAllowsNullArgs returns true if the given binary operator allows null arguments, and cannot therefore be folded away to null.

func BinaryOverloadExists Uses

func BinaryOverloadExists(op opt.Operator, leftType, rightType *types.T) bool

BinaryOverloadExists returns true if the given binary operator exists with the given arguments.

func BuildSharedProps Uses

func BuildSharedProps(mem *Memo, e opt.Expr, shared *props.Shared)

BuildSharedProps fills in the shared properties derived from the given expression's subtree.

func CanExtractConstDatum Uses

func CanExtractConstDatum(e opt.Expr) bool

CanExtractConstDatum returns true if a constant datum can be created from the given expression (tuples and arrays of constant values are considered constant values). If CanExtractConstDatum returns true, then ExtractConstDatum is guaranteed to work as well.

func CanExtractConstTuple Uses

func CanExtractConstTuple(e opt.Expr) bool

CanExtractConstTuple returns true if the expression is a TupleOp with constant values (a nested tuple of constant values is considered constant).

func ExprIsNeverNull Uses

func ExprIsNeverNull(e opt.ScalarExpr, notNullCols opt.ColSet) bool

ExprIsNeverNull makes a best-effort attempt to prove that the provided scalar is always non-NULL, given the set of outer columns that are known to be not null. This is particularly useful with check constraints. Check constraints are satisfied when the condition evaluates to NULL, whereas filters are not. For example consider the following check constraint:

CHECK (col IN (1, 2, NULL))

Any row evaluating this check constraint with any value for the column will satisfy this check constraint, as they would evaluate to true (in the case of 1 or 2) or NULL (in the case of everything else).

func ExtractAggInputColumns Uses

func ExtractAggInputColumns(e opt.ScalarExpr) opt.ColSet

ExtractAggInputColumns returns the set of columns the aggregate depends on.

func ExtractAggSingleInputColumn Uses

func ExtractAggSingleInputColumn(e opt.ScalarExpr) opt.ColumnID

ExtractAggSingleInputColumn returns the input ColumnID of an aggregate operator that has a single input.

func ExtractConstColumns Uses

func ExtractConstColumns(
    on FiltersExpr, mem *Memo, evalCtx *tree.EvalContext,
) (fixedCols opt.ColSet)

ExtractConstColumns returns columns in the filters expression that have been constrained to fixed values.

func ExtractConstDatum Uses

func ExtractConstDatum(e opt.Expr) tree.Datum

ExtractConstDatum returns the Datum that represents the value of an expression with a constant value. An expression with a constant value is:

- one that has a ConstValue tag, or
- a tuple or array where all children are constant values.

func ExtractConstantFilter Uses

func ExtractConstantFilter(on FiltersExpr, cols opt.ColSet) map[opt.ColumnID]FiltersItem

ExtractConstantFilter returns a map of columns to the filters that constrain value to a constant.

func ExtractJoinEqualityColumns Uses

func ExtractJoinEqualityColumns(
    leftCols, rightCols opt.ColSet, on FiltersExpr,
) (leftEq opt.ColList, rightEq opt.ColList)

ExtractJoinEqualityColumns returns pairs of columns (one from the left side, one from the right side) which are constrained to be equal in a join (and have equivalent types).

func ExtractValuesFromFilter Uses

func ExtractValuesFromFilter(on FiltersExpr, cols opt.ColSet) map[opt.ColumnID]tree.Datum

ExtractValuesFromFilter returns a map of constant columns, to the values they're constrained to.

func FindAggregateOverload Uses

func FindAggregateOverload(e opt.ScalarExpr) (name string, overload *tree.Overload)

FindAggregateOverload finds an aggregate function overload that matches the given aggregate function expression. It panics if no match can be found.

func FindBinaryOverload Uses

func FindBinaryOverload(op opt.Operator, leftType, rightType *types.T) (_ *tree.BinOp, ok bool)

FindBinaryOverload finds the correct type signature overload for the specified binary operator, given the types of its inputs. If an overload is found, FindBinaryOverload returns true, plus a pointer to the overload. If an overload is not found, FindBinaryOverload returns false.

func FindComparisonOverload Uses

func FindComparisonOverload(
    op opt.Operator, leftType, rightType *types.T,
) (_ *tree.CmpOp, flipped, not, ok bool)

FindComparisonOverload finds the correct type signature overload for the specified comparison operator, given the types of its inputs. If an overload is found, FindComparisonOverload returns a pointer to the overload and ok=true. It also returns "flipped" and "not" flags. The "flipped" flag indicates whether the original left and right operands should be flipped with the returned overload. The "not" flag indicates whether the result of the comparison operation should be negated. If an overload is not found, FindComparisonOverload returns ok=false.

func FindUnaryOverload Uses

func FindUnaryOverload(op opt.Operator, typ *types.T) (_ *tree.UnaryOp, ok bool)

FindUnaryOverload finds the correct type signature overload for the specified unary operator, given the type of its input. If an overload is found, FindUnaryOverload returns true, plus a pointer to the overload. If an overload is not found, FindUnaryOverload returns false.

func FindWindowOverload Uses

func FindWindowOverload(e opt.ScalarExpr) (name string, overload *tree.Overload)

FindWindowOverload finds a window function overload that matches the given window function expression. It panics if no match can be found.

func FormatExpr Uses

func FormatExpr(e opt.Expr, flags ExprFmtFlags, catalog cat.Catalog) string

FormatExpr returns a string representation of the given expression, formatted according to the specified flags.

func FormatPrivate Uses

func FormatPrivate(f *ExprFmtCtx, private interface{}, physProps *physical.Required)

FormatPrivate outputs a description of the private to f.Buffer.

func InferBinaryType Uses

func InferBinaryType(op opt.Operator, leftType, rightType *types.T) *types.T

InferBinaryType infers the return type of a binary expression, given the type of its inputs.

func InferType Uses

func InferType(mem *Memo, e opt.ScalarExpr) *types.T

InferType derives the type of the given scalar expression and stores it in the expression's Type field. Depending upon the operator, the type may be fixed, or it may be dependent upon the expression children.

func InferUnaryType Uses

func InferUnaryType(op opt.Operator, inputType *types.T) *types.T

InferUnaryType infers the return type of a unary operator, given the type of its input.

func InferWhensType Uses

func InferWhensType(whens ScalarListExpr, orElse opt.ScalarExpr) *types.T

InferWhensType returns the type of a CASE expression, which is of the form:

CASE [ <cond> ]
    WHEN <condval1> THEN <expr1>
  [ WHEN <condval2> THEN <expr2> ] ...
  [ ELSE <expr> ]
END

The type is equal to the type of the WHEN <condval> THEN <expr> clauses, or the type of the ELSE <expr> value if all the previous types are unknown.

func MakeTableFuncDep Uses

func MakeTableFuncDep(md *opt.Metadata, tabID opt.TableID) *props.FuncDepSet

MakeTableFuncDep returns the set of functional dependencies derived from the given base table. The set is derived lazily and is cached in the metadata, since it may be accessed multiple times during query optimization. For more details, see Relational.FuncDepSet.

func NormalizeComparison Uses

func NormalizeComparison(op opt.Operator) (newOp opt.Operator, flipped, not bool)

NormalizeComparison maps a given comparison operator into an equivalent operator that exists in the tree.CmpOps map, returning this new operator, along with "flipped" and "not" flags. The "flipped" flag indicates whether the left and right operands should be flipped with the new operator. The "not" flag indicates whether the result of the comparison operation should be negated.

func RequestColStat Uses

func RequestColStat(evalCtx *tree.EvalContext, e RelExpr, cols opt.ColSet)

RequestColStat causes a column statistic to be calculated on the relational expression. This is used for testing.

type ColumnNameGenerator Uses

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

ColumnNameGenerator is used to generate a unique name for each column of a relational expression. See GenerateName for details.

func NewColumnNameGenerator Uses

func NewColumnNameGenerator(e RelExpr) *ColumnNameGenerator

NewColumnNameGenerator creates a new instance of ColumnNameGenerator, initialized with the given relational expression.

func (*ColumnNameGenerator) GenerateName Uses

func (g *ColumnNameGenerator) GenerateName(col opt.ColumnID) string

GenerateName generates a unique name for each column in a relational expression. This function is used to generate consistent, unique names for the columns in the table that will be created if the session variable `save_tables_prefix` is non-empty.

type Cost Uses

type Cost float64

Cost is the best-effort approximation of the actual cost of executing a particular operator tree. TODO: Need more details about what one "unit" of cost means.

func (Cost) Less Uses

func (c Cost) Less(other Cost) bool

Less returns true if this cost is lower than the given cost.

func (Cost) Sub Uses

func (c Cost) Sub(other Cost) Cost

Sub subtracts the other cost from this cost and returns the result.

type ExprFmtCtx Uses

type ExprFmtCtx struct {
    Buffer *bytes.Buffer

    // Flags controls how the expression is formatted.
    Flags ExprFmtFlags

    // Memo must contain any expression that is formatted.
    Memo *Memo

    // Catalog must be set unless the ExprFmtHideQualifications flag is set.
    Catalog cat.Catalog
    // contains filtered or unexported fields
}

ExprFmtCtx is passed as context to expression formatting functions, which need to know the formatting flags and memo in order to format. In addition, a reusable bytes buffer avoids unnecessary allocations.

func MakeExprFmtCtx Uses

func MakeExprFmtCtx(flags ExprFmtFlags, mem *Memo, catalog cat.Catalog) ExprFmtCtx

MakeExprFmtCtx creates an expression formatting context from a new buffer.

func MakeExprFmtCtxBuffer Uses

func MakeExprFmtCtxBuffer(
    buf *bytes.Buffer, flags ExprFmtFlags, mem *Memo, catalog cat.Catalog,
) ExprFmtCtx

MakeExprFmtCtxBuffer creates an expression formatting context from an existing buffer.

func (*ExprFmtCtx) FormatExpr Uses

func (f *ExprFmtCtx) FormatExpr(e opt.Expr)

FormatExpr constructs a treeprinter view of the given expression for testing and debugging, according to the flags in this context.

func (*ExprFmtCtx) FormatScalarProps Uses

func (f *ExprFmtCtx) FormatScalarProps(scalar opt.ScalarExpr)

FormatScalarProps writes out a string representation of the scalar properties (with a preceding space); for example:

" [type=bool, outer=(1), constraints=(/1: [/1 - /1]; tight)]"

func (*ExprFmtCtx) HasFlags Uses

func (f *ExprFmtCtx) HasFlags(subset ExprFmtFlags) bool

HasFlags tests whether the given flags are all set.

type ExprFmtFlags Uses

type ExprFmtFlags int

ExprFmtFlags controls which properties of the expression are shown in formatted output.

const (
    // ExprFmtShowAll shows all properties of the expression.
    ExprFmtShowAll ExprFmtFlags = 0

    // ExprFmtHideMiscProps does not show outer columns, row cardinality, provided
    // orderings, or side effects in the output.
    ExprFmtHideMiscProps ExprFmtFlags = 1 << (iota - 1)

    // ExprFmtHideConstraints does not show inferred constraints in the output.
    ExprFmtHideConstraints

    // ExprFmtHideFuncDeps does not show functional dependencies in the output.
    ExprFmtHideFuncDeps

    // ExprFmtHideRuleProps does not show rule-specific properties in the output.
    ExprFmtHideRuleProps

    // ExprFmtHideStats does not show statistics in the output.
    ExprFmtHideStats

    // ExprFmtHideCost does not show expression cost in the output.
    ExprFmtHideCost

    // ExprFmtHideQualifications removes the qualification from column labels
    // (except when a shortened name would be ambiguous).
    ExprFmtHideQualifications

    // ExprFmtHideScalars removes subtrees that contain only scalars and replaces
    // them with the SQL expression (if possible).
    ExprFmtHideScalars

    // ExprFmtHideOrderings hides all orderings.
    ExprFmtHideOrderings

    // ExprFmtHideTypes hides type information from columns and scalar
    // expressions.
    ExprFmtHideTypes

    // ExprFmtHideColumns removes column information.
    ExprFmtHideColumns

    // ExprFmtHideAll shows only the basic structure of the expression.
    // Note: this flag should be used judiciously, as its meaning changes whenever
    // we add more flags.
    ExprFmtHideAll ExprFmtFlags = (1 << iota) - 1
)

func (ExprFmtFlags) HasFlags Uses

func (f ExprFmtFlags) HasFlags(subset ExprFmtFlags) bool

HasFlags tests whether the given flags are all set.

type ExprNameGenerator Uses

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

ExprNameGenerator is used to generate a unique name for each relational expression in a query tree. See GenerateName for details.

func NewExprNameGenerator Uses

func NewExprNameGenerator(prefix string) *ExprNameGenerator

NewExprNameGenerator creates a new instance of ExprNameGenerator, initialized with the given prefix.

func (*ExprNameGenerator) GenerateName Uses

func (g *ExprNameGenerator) GenerateName(op opt.Operator) string

GenerateName generates a name for a relational expression with the given operator. It is used to generate names for each relational expression in a query tree, corresponding to the tables that will be created if the session variable `save_tables_prefix` is non-empty.

Each invocation of GenerateName is guaranteed to produce a unique name for a given instance of ExprNameGenerator. This works because each name is appended with a unique, auto-incrementing number. For readability, the generated names also contain a common prefix and the name of the relational operator separated with underscores. For example: my_query_scan_2.

Since the names are generated with an auto-incrementing number, the order of invocation is important. For a given query, the number assigned to each relational subexpression corresponds to the order in which the expression was encountered during tree traversal. Thus, in order to generate a consistent name, always call GenerateName in a pre-order traversal of the expression tree.

type JoinFlags Uses

type JoinFlags struct {
    DisallowLookupJoin bool
    DisallowMergeJoin  bool
    DisallowHashJoin   bool
}

JoinFlags stores restrictions on the join execution method, derived from hints for a join specified in the query (see tree.JoinTableExpr).

func (JoinFlags) Empty Uses

func (jf JoinFlags) Empty() bool

Empty returns true if there are no flags set.

func (JoinFlags) String Uses

func (jf JoinFlags) String() string

type Memo Uses

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

Memo is a data structure for efficiently storing a forest of query plans. Conceptually, the memo is composed of a numbered set of equivalency classes called groups where each group contains a set of logically equivalent expressions. Two expressions are considered logically equivalent if:

1. They return the same number and data type of columns. However, order and
   naming of columns doesn't matter.
2. They return the same number of rows, with the same values in each row.
   However, order of rows doesn't matter.

The different expressions in a single group are called memo expressions (memo-ized expressions). The children of a memo expression can themselves be part of memo groups. Therefore, the memo forest is composed of every possible combination of parent expression with its possible child expressions, recursively applied.

Memo expressions can be relational (e.g. join) or scalar (e.g. <). Operators are always both logical (specify results) and physical (specify results and a particular implementation). This means that even a "raw" unoptimized expression tree can be executed (naively). Both relational and scalar operators are uniformly represented as nodes in memo expression trees, which facilitates tree pattern matching and replacement. However, because scalar expression memo groups never have more than one expression, scalar expressions can use a simpler representation.

Because memo groups contain logically equivalent expressions, all the memo expressions in a group share the same logical properties. However, it's possible for two logically equivalent expression to be placed in different memo groups. This occurs because determining logical equivalency of two relational expressions is too complex to perform 100% correctly. A correctness failure (i.e. considering two expressions logically equivalent when they are not) results in invalid transformations and invalid plans. But placing two logically equivalent expressions in different groups has a much gentler failure mode: the memo and transformations are less efficient. Expressions within the memo may have different physical properties. For example, a memo group might contain both hash join and merge join expressions which produce the same set of output rows, but produce them in different orders.

Expressions are inserted into the memo by the factory, which ensure that expressions have been fully normalized before insertion (see the comment in factory.go for more details). A new group is created only when unique normalized expressions are created by the factory during construction or rewrite of the tree. Uniqueness is determined by "interning" each expression, which means that multiple equivalent expressions are mapped to a single in-memory instance. This allows interned expressions to be checked for equivalence by simple pointer comparison. For example:

SELECT * FROM a, b WHERE a.x = b.x

After insertion into the memo, the memo would contain these six groups, with numbers substituted for pointers to the normalized expression in each group:

G6: [inner-join [G1 G2 G5]]
G5: [eq [G3 G4]]
G4: [variable b.x]
G3: [variable a.x]
G2: [scan b]
G1: [scan a]

Each leaf expressions is interned by hashing its operator type and any private field values. Expressions higher in the tree can then rely on the fact that all children have been interned, and include their pointer values in its hash value. Therefore, the memo need only hash the expression's fields in order to determine whether the expression already exists in the memo. Walking the subtree is not necessary.

The normalizing factory will never add more than one expression to a memo group. But the explorer does add denormalized expressions to existing memo groups, since oftentimes one of these equivalent, but denormalized expressions will have a lower cost than the initial normalized expression added by the factory. For example, the join commutativity transformation expands the memo like this:

G6: [inner-join [G1 G2 G5]] [inner-join [G2 G1 G5]]
G5: [eq [G3 G4]]
G4: [variable b.x]
G3: [variable a.x]
G2: [scan b]
G1: [scan a]

See the comments in explorer.go for more details.

func (*Memo) HasPlaceholders Uses

func (m *Memo) HasPlaceholders() bool

HasPlaceholders returns true if the memo contains at least one placeholder operator.

func (*Memo) Init Uses

func (m *Memo) Init(evalCtx *tree.EvalContext)

Init initializes a new empty memo instance, or resets existing state so it can be reused. It must be called before use (or reuse). The memo collects information about the context in which it is compiled from the evalContext argument. If any of that changes, then the memo must be invalidated (see the IsStale method for more details).

func (*Memo) InternPhysicalProps Uses

func (m *Memo) InternPhysicalProps(phys *physical.Required) *physical.Required

InternPhysicalProps adds the given physical props to the memo if they haven't yet been added. If the same props was added previously, then return a pointer to the previously added props. This allows interned physical props to be compared for equality using simple pointer comparison.

func (*Memo) IsEmpty Uses

func (m *Memo) IsEmpty() bool

IsEmpty returns true if there are no expressions in the memo.

func (*Memo) IsOptimized Uses

func (m *Memo) IsOptimized() bool

IsOptimized returns true if the memo has been fully optimized.

func (*Memo) IsStale Uses

func (m *Memo) IsStale(
    ctx context.Context, evalCtx *tree.EvalContext, catalog cat.Catalog,
) (bool, error)

IsStale returns true if the memo has been invalidated by changes to any of its dependencies. Once a memo is known to be stale, it must be ejected from any query cache or prepared statement and replaced with a recompiled memo that takes into account the changes. IsStale checks the following dependencies:

1. Current database: this can change name resolution.
2. Current search path: this can change name resolution.
3. Current location: this determines time zone, and can change how time-
   related types are constructed and compared.
4. Data source schema: this determines most aspects of how the query is
   compiled.
5. Data source privileges: current user may no longer have access to one or
   more data sources.

This function cannot swallow errors and return only a boolean, as it may perform KV operations on behalf of the transaction associated with the provided catalog, and those errors are required to be propagated.

func (*Memo) MemoryEstimate Uses

func (m *Memo) MemoryEstimate() int64

MemoryEstimate returns a rough estimate of the memo's memory usage, in bytes. It only includes memory usage that is proportional to the size and complexity of the query, rather than constant overhead bytes.

func (*Memo) Metadata Uses

func (m *Memo) Metadata() *opt.Metadata

Metadata returns the metadata instance associated with the memo.

func (*Memo) NextID Uses

func (m *Memo) NextID() opt.ScalarID

NextID returns a new unique ScalarID to number expressions with.

func (*Memo) NextWithID Uses

func (m *Memo) NextWithID() opt.WithID

NextWithID returns a not-yet-assigned identifier for a WITH expression.

func (*Memo) RequestColStat Uses

func (m *Memo) RequestColStat(
    expr RelExpr, cols opt.ColSet,
) (colStat *props.ColumnStatistic, ok bool)

RequestColStat calculates and returns the column statistic calculated on the relational expression.

func (*Memo) ResetCost Uses

func (m *Memo) ResetCost(e RelExpr, cost Cost)

ResetCost updates the cost of a relational expression's memo group. It should *only* be called by Optimizer.RecomputeCost() for testing purposes.

func (*Memo) RootExpr Uses

func (m *Memo) RootExpr() opt.Expr

RootExpr returns the root memo expression previously set via a call to SetRoot.

func (*Memo) RootProps Uses

func (m *Memo) RootProps() *physical.Required

RootProps returns the physical properties required of the root memo group, previously set via a call to SetRoot.

func (*Memo) RowsProcessed Uses

func (m *Memo) RowsProcessed(expr RelExpr) (_ float64, ok bool)

RowsProcessed calculates and returns the number of rows processed by the relational expression. It is currently only supported for joins.

func (*Memo) SetBestProps Uses

func (m *Memo) SetBestProps(
    e RelExpr, required *physical.Required, provided *physical.Provided, cost Cost,
)

SetBestProps updates the physical properties, provided ordering, and cost of a relational expression's memo group (see the relevant methods of RelExpr). It is called by the optimizer once it determines the expression in the group that is part of the lowest cost tree (for the overall query).

func (*Memo) SetRoot Uses

func (m *Memo) SetRoot(e RelExpr, phys *physical.Required)

SetRoot stores the root memo expression when it is a relational expression, and also stores the physical properties required of the root group.

func (*Memo) SetScalarRoot Uses

func (m *Memo) SetScalarRoot(scalar opt.ScalarExpr)

SetScalarRoot stores the root memo expression when it is a scalar expression.

type RelExpr Uses

type RelExpr interface {
    opt.Expr

    // Memo is the memo which contains this relational expression.
    Memo() *Memo

    // Relational is the set of logical properties that describe the content and
    // characteristics of this expression's behavior and results.
    Relational() *props.Relational

    // RequiredPhysical is the set of required physical properties with respect to
    // which this expression was optimized. Enforcers may be added to the
    // expression tree to ensure the physical properties are provided.
    //
    // Set when optimization is complete, only for the expressions in the final
    // tree.
    RequiredPhysical() *physical.Required

    // ProvidedPhysical is the set of provided physical properties (which must be
    // compatible with the set of required physical properties).
    //
    // Set when optimization is complete, only for the expressions in the final
    // tree.
    ProvidedPhysical() *physical.Provided

    // Cost is an estimate of the cost of executing this expression tree. Set
    // when optimization is complete, only for the expressions in the final tree.
    Cost() Cost

    // FirstExpr returns the first member expression in the memo group (could be
    // this expression if it happens to be first in the group). Subsequent members
    // can be enumerated by then calling NextExpr. Note that enforcer operators
    // are not part of this list (but do maintain a link to it).
    FirstExpr() RelExpr

    // NextExpr returns the next member expression in the memo group, or nil if
    // there are no further members in the group.
    NextExpr() RelExpr
    // contains filtered or unexported methods
}

RelExpr is implemented by all operators tagged as Relational. Relational expressions have a set of logical properties that describe the content and characteristics of their behavior and results. They are stored as part of a memo group that contains other logically equivalent expressions. Expressions in the same memo group are linked together in a list that can be traversed via calls to FirstExpr and NextExpr:

  +--------------------------------------+
  |  +---------------+                   |
  |  |               |FirstExpr          |FirstExpr
  v  v               |                   |
member #1 -------> member #2 --------> member #3 -------> nil
          NextExpr           NextExpr            NextExpr

A relational expression's physical properties and cost are defined once it has been optimized.

func LastGroupMember Uses

func LastGroupMember(e RelExpr) RelExpr

LastGroupMember returns the last member in the same memo group of the given relational expression.

type ScalarPropsExpr Uses

type ScalarPropsExpr interface {
    opt.ScalarExpr

    // ScalarProps returns the scalar properties associated with the expression.
    // These can be lazily calculated using the given memo as context.
    ScalarProps(mem *Memo) *props.Scalar
}

ScalarPropsExpr is implemented by scalar expressions which cache scalar properties, like FiltersExpr and ProjectionsExpr. The scalar properties are lazily populated only when requested by walking the expression subtree.

type ScanFlags Uses

type ScanFlags struct {
    // NoIndexJoin disallows use of non-covering indexes (index-join) for scanning
    // this table.
    NoIndexJoin bool

    // ForceIndex forces the use of a specific index (specified in Index).
    // ForceIndex and NoIndexJoin cannot both be set at the same time.
    ForceIndex bool
    Direction  tree.Direction
    Index      int
}

ScanFlags stores any flags for the scan specified in the query (see tree.IndexFlags). These flags may be consulted by transformation rules or the coster.

func (*ScanFlags) Empty Uses

func (sf *ScanFlags) Empty() bool

Empty returns true if there are no flags set.

type ScanLimit Uses

type ScanLimit int64

ScanLimit is used for a limited table or index scan and stores the limit as well as the desired scan direction. A value of 0 means that there is no limit.

func MakeScanLimit Uses

func MakeScanLimit(rowCount int64, reverse bool) ScanLimit

MakeScanLimit initializes a ScanLimit with a number of rows and a direction.

func (ScanLimit) IsSet Uses

func (sl ScanLimit) IsSet() bool

IsSet returns true if there is a limit.

func (ScanLimit) Reverse Uses

func (sl ScanLimit) Reverse() bool

Reverse returns true if the limit requires a reverse scan.

func (ScanLimit) RowCount Uses

func (sl ScanLimit) RowCount() int64

RowCount returns the number of rows in the limit.

func (ScanLimit) String Uses

func (sl ScanLimit) String() string

type TupleOrdinal Uses

type TupleOrdinal uint32

TupleOrdinal is an ordinal index into an expression of type Tuple. It is used by the ColumnAccess scalar expression.

type WindowFrame Uses

type WindowFrame struct {
    Mode           tree.WindowFrameMode
    StartBoundType tree.WindowFrameBoundType
    EndBoundType   tree.WindowFrameBoundType
    FrameExclusion tree.WindowFrameExclusion
}

WindowFrame denotes the definition of a window frame for an individual window function, excluding the OFFSET expressions, if present.

Package memo imports 27 packages (graph) and is imported by 25 packages. Updated 2019-09-15. Refresh now. Tools for package owners.