cockroach: Index | Files

package memo

import ""


Package Files

check_expr_skip.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 multiplicity_builder.go statistics_builder.go typing.go


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 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 ScalarFmtInterceptor func(f *ExprFmtCtx, expr opt.ScalarExpr) string

ScalarFmtInterceptor is a callback that can be set to a custom formatting function. If the function returns a non-empty string, the normal formatting code is bypassed.

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:

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:

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 BuildConstraints Uses

func BuildConstraints(
    e opt.ScalarExpr, md *opt.Metadata, evalCtx *tree.EvalContext,
) (_ *constraint.Set, tight bool)

BuildConstraints returns a constraint.Set that represents the given scalar expression. A "tight" boolean is also returned which is true if the constraint is exactly equivalent to the expression.

func BuildSharedProps Uses

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

BuildSharedProps fills in the shared properties derived from the given expression's subtree. It will only recurse into a child when it is not already caching properties.

Note that shared is an "input-output" argument, and should be assumed to be partially filled in already. Boolean fields such as HasPlaceholder, HasCorrelatedSubquery should never be reset to false once set to true; VolatilitySet should never be re-initialized.

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 DeriveJoinMultiplicityFromInputs Uses

func DeriveJoinMultiplicityFromInputs(
    left, right RelExpr, filters FiltersExpr,
) props.JoinMultiplicity

DeriveJoinMultiplicityFromInputs returns a JoinMultiplicity that describes how an inner join with the given inputs and filters will affect the rows of its inputs. When possible, GetJoinMultiplicity should be called instead because DeriveJoinMultiplicityFromInputs cannot take advantage of a previously calculated JoinMultiplicity. The UnfilteredCols Relational property is used in calculating the JoinMultiplicity, and is lazily derived by a call to deriveUnfilteredCols.

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 ExtractAggFunc Uses

func ExtractAggFunc(e opt.ScalarExpr) opt.ScalarExpr

ExtractAggFunc digs down into the given aggregate expression and returns the aggregate function, skipping past any AggFilter or AggDistinct operators.

func ExtractAggInputColumns Uses

func ExtractAggInputColumns(e opt.ScalarExpr) opt.ColSet

ExtractAggInputColumns returns the set of columns the aggregate depends on.

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 ExtractJoinEquality Uses

func ExtractJoinEquality(
    leftCols, rightCols opt.ColSet, condition opt.ScalarExpr,
) (ok bool, left, right opt.ColumnID)

ExtractJoinEquality returns true if the given condition is a simple equality condition with two variables (e.g. a=b), where one of the variables (returned as "left") is in the set of leftCols and the other (returned as "right") is in the set of rightCols.

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 ExtractValueForConstColumn Uses

func ExtractValueForConstColumn(
    on FiltersExpr, mem *Memo, evalCtx *tree.EvalContext, col opt.ColumnID,
) tree.Datum

ExtractValueForConstColumn returns the constant value of a column returned by ExtractConstColumns.

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 FindFunction Uses

func FindFunction(
    e opt.ScalarExpr, name string,
) (props *tree.FunctionProperties, overload *tree.Overload, ok bool)

FindFunction returns the function properties and overload of the function with the given name and argument types matching the children of the given input.

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, mem *Memo, 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 GetJoinMultiplicity Uses

func GetJoinMultiplicity(in RelExpr) props.JoinMultiplicity

GetJoinMultiplicity returns a JoinMultiplicity struct that describes how a join operator will affect the rows of its left and right inputs (e.g. duplicated and/or filtered). Panics if the method is called on an operator that does not support JoinMultiplicity (any operator other than an InnerJoin, LeftJoin, or FullJoin).

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> ]

All possible values should have the same type, and that is the type of the case.

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 OutputColumnIsAlwaysNull Uses

func OutputColumnIsAlwaysNull(e RelExpr, col opt.ColumnID) bool

OutputColumnIsAlwaysNull returns true if the expression produces only NULL values for the given column. Used to elide foreign key checks.

This could be a logical property but we only care about simple cases (NULLs in Projections and Values).

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.

func WithUses Uses

func WithUses(r opt.Expr) props.WithUsesMap

WithUses returns the WithUsesMap for the given expression.

type CascadeBuilder Uses

type CascadeBuilder interface {
    // Build constructs a cascading query that mutates the child table. The input
    // is scanned using WithScan with the given WithID; oldValues and newValues
    // columns correspond 1-to-1 to foreign key columns. For deletes, newValues is
    // empty.
    // The query does not need to be built in the same memo as the original query;
    // the only requirement is that the mutation input columns
    // (oldValues/newValues) are valid in the metadata.
    // The method does not mutate any captured state; it is ok to call Build
    // concurrently (e.g. if the plan it originates from is cached and reused).
    // Note: factory is always *norm.Factory; it is an interface{} only to avoid
    // circular package dependencies.
        ctx context.Context,
        semaCtx *tree.SemaContext,
        evalCtx *tree.EvalContext,
        catalog cat.Catalog,
        factory interface{},
        binding opt.WithID,
        bindingProps *props.Relational,
        oldValues, newValues opt.ColList,
    ) (RelExpr, error)

CascadeBuilder is an interface used to construct a cascading query for a specific FK relation. For example: if we are deleting rows from a parent table, after deleting the rows from the parent table this interface will be used to build the corresponding deletion in the child table.

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) ColumnString Uses

func (f *ExprFmtCtx) ColumnString(id opt.ColumnID) string

ColumnString returns the column in the same format as formatColSimple.

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, side effects, or error text in the output.
    ExprFmtHideMiscProps ExprFmtFlags = 1 << (iota - 1)

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

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

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

    // ExprFmtHideStats does not show statistics in the output.

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

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

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

    // ExprFmtHidePhysProps hides all required physical properties, except for
    // Presentation (see ExprFmtHideColumns).

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

    // ExprFmtHideNotNull hides the !null specifier from columns.

    // ExprFmtHideColumns removes column information.

    // 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 FKCascade Uses

type FKCascade struct {
    // FKName is the name of the FK constraint.
    FKName string

    // Builder is an object that can be used as the "optbuilder" for the cascading
    // query.
    Builder CascadeBuilder

    // WithID identifies the buffer for the mutation input in the original
    // expression tree.
    WithID opt.WithID

    // OldValues are column IDs from the mutation input that correspond to the
    // old values of the modified rows. The list maps 1-to-1 to foreign key
    // columns.
    OldValues opt.ColList

    // NewValues are column IDs from the mutation input that correspond to the
    // new values of the modified rows. The list maps 1-to-1 to foreign key columns.
    // It is empty if the mutation is a deletion.
    NewValues opt.ColList

FKCascade stores metadata necessary for building a cascading query. Cascading queries are built as needed, after the original query is executed.

type FKCascades Uses

type FKCascades []FKCascade

FKCascades stores metadata necessary for building cascading queries.

type JoinFlags Uses

type JoinFlags uint8

JoinFlags stores restrictions on the join execution method, derived from hints for a join specified in the query (see tree.JoinTableExpr). It is a bitfield where each bit indicates if a certain type of join is disallowed or preferred.

The zero value indicates that any join is allowed and there are no special preferences.

const (
    // DisallowHashJoinStoreLeft corresponds to a hash join where the left side is
    // stored into the hashtable. Note that execution can override the stored side
    // if it finds that the other side is smaller (up to a certain size).
    DisallowHashJoinStoreLeft JoinFlags = (1 << iota)

    // DisallowHashJoinStoreRight corresponds to a hash join where the right side
    // is stored into the hashtable. Note that execution can override the stored
    // side if it finds that the other side is smaller (up to a certain size).

    // DisallowMergeJoin corresponds to a merge join.

    // DisallowLookupJoinIntoLeft corresponds to a lookup join where the lookup
    // table is on the left side.

    // DisallowLookupJoinIntoRight corresponds to a lookup join where the lookup
    // table is on the right side.

    // PreferLookupJoinIntoLeft reduces the cost of a lookup join where the lookup
    // table is on the left side.

    // PreferLookupJoinIntoRight reduces the cost of a lookup join where the
    // lookup table is on the right side.

Each flag indicates if a certain type of join is disallowed.

const (

    // AllowOnlyHashJoinStoreRight has all "disallow" flags set except
    // DisallowHashJoinStoreRight.
    AllowOnlyHashJoinStoreRight JoinFlags = disallowAll ^ DisallowHashJoinStoreRight

    // AllowOnlyLookupJoinIntoRight has all "disallow" flags set except
    // DisallowLookupJoinIntoRight.
    AllowOnlyLookupJoinIntoRight JoinFlags = disallowAll ^ DisallowLookupJoinIntoRight

    // AllowOnlyMergeJoin has all "disallow" flags set except DisallowMergeJoin.
    AllowOnlyMergeJoin JoinFlags = disallowAll ^ DisallowMergeJoin

func (JoinFlags) Empty Uses

func (jf JoinFlags) Empty() bool

Empty returns true if this is the default value (where all join types are allowed).

func (JoinFlags) Has Uses

func (jf JoinFlags) Has(flag JoinFlags) bool

Has returns true if the given flag is 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) CheckExpr Uses

func (m *Memo) CheckExpr(e opt.Expr)

CheckExpr is a no-op in non-race builds.

func (*Memo) ClearColStats Uses

func (m *Memo) ClearColStats(parent opt.Expr)

ClearColStats clears all column statistics from every relational expression in the memo. This is used to free up the potentially large amount of memory used by histograms.

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
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) NotifyOnNewGroup Uses

func (m *Memo) NotifyOnNewGroup(fn func(opt.Expr))

NotifyOnNewGroup sets a callback function which is invoked each time we create a new memo group.

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. Used only for testing.

type RelExpr Uses

type RelExpr interface {

    // 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 {

    // ScalarProps returns the scalar properties associated with the expression.
    ScalarProps() *props.Scalar

ScalarPropsExpr is implemented by scalar expressions which cache scalar properties, like FiltersExpr and ProjectionsExpr. These expressions are also tagged with the ScalarProps tag.

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.

func (*WindowFrame) HasOffset Uses

func (f *WindowFrame) HasOffset() bool

HasOffset returns true if the WindowFrame contains a specific offset.

func (*WindowFrame) String Uses

func (f *WindowFrame) String() string

Package memo imports 30 packages (graph) and is imported by 23 packages. Updated 2020-09-22. Refresh now. Tools for package owners.