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

package xform

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

Index

Package Files

coster.go custom_funcs.go explorer.go index_scan_builder.go interesting_orderings.go memo_format.go optimizer.go physical_props.go scan_index_iter.go

func BuildChildPhysicalProps Uses

func BuildChildPhysicalProps(
    mem *memo.Memo, parent memo.RelExpr, nth int, parentProps *physical.Required,
) *physical.Required

BuildChildPhysicalProps returns the set of physical properties required of the nth child, based upon the properties required of the parent. For example, the Project operator passes through any ordering requirement to its child, but provides any presentation requirement.

The childProps argument is allocated once by the caller and can be reused repeatedly as physical properties are derived for each child. On each call, buildChildPhysicalProps updates the childProps argument.

func BuildChildPhysicalPropsScalar Uses

func BuildChildPhysicalPropsScalar(mem *memo.Memo, parent opt.Expr, nth int) *physical.Required

BuildChildPhysicalPropsScalar is like BuildChildPhysicalProps, but for when the parent is a scalar expression.

func CanProvidePhysicalProps Uses

func CanProvidePhysicalProps(e memo.RelExpr, required *physical.Required) bool

CanProvidePhysicalProps returns true if the given expression can provide the required physical properties. The optimizer uses this to determine whether an expression provides a required physical property. If it does not, then the optimizer inserts an enforcer operator that is able to provide it.

Some operators, like Select and Project, may not directly provide a required physical property, but do "pass through" the requirement to their input. Operators that do this should return true from the appropriate canProvide method and then pass through that property in the buildChildPhysicalProps method.

func DeriveInterestingOrderings Uses

func DeriveInterestingOrderings(e memo.RelExpr) opt.OrderingSet

DeriveInterestingOrderings calculates and returns the Relational.Rule.InterestingOrderings property of a relational operator.

type AppliedRuleFunc Uses

type AppliedRuleFunc = norm.AppliedRuleFunc

AppliedRuleFunc defines the callback function for the NotifyOnAppliedRule event supported by the optimizer. See the comment in factory.go for more details.

type Coster Uses

type Coster interface {
    // ComputeCost returns the estimated cost of executing the candidate
    // expression. The optimizer does not expect the cost to correspond to any
    // real-world metric, but does expect costs to be comparable to one another,
    // as well as summable.
    ComputeCost(candidate memo.RelExpr, required *physical.Required) memo.Cost
}

Coster is used by the optimizer to assign a cost to a candidate expression that can provide a set of required physical properties. If a candidate expression has a lower cost than any other expression in the memo group, then it becomes the new best expression for the group.

The set of costing formulas maintained by the coster for the set of all operators constitute the "cost model". A given cost model can be designed to maximize any optimization goal, such as:

1. Max aggregate cluster throughput (txns/sec across cluster)
2. Min transaction latency (time to commit txns)
3. Min latency to first row (time to get first row of txns)
4. Min memory usage
5. Some weighted combination of #1 - #4

The cost model in this file targets #1 as the optimization goal. However, note that #2 is implicitly important to that goal, since overall cluster throughput will suffer if there are lots of pending transactions waiting on I/O.

Coster is an interface so that different costing algorithms can be used by the optimizer. For example, the OptSteps command uses a custom coster that assigns infinite costs to some expressions in order to prevent them from being part of the lowest cost tree (for debugging purposes).

func MakeDefaultCoster Uses

func MakeDefaultCoster(mem *memo.Memo) Coster

MakeDefaultCoster creates an instance of the default coster.

type CustomFuncs Uses

type CustomFuncs struct {
    norm.CustomFuncs
    // contains filtered or unexported fields
}

CustomFuncs contains all the custom match and replace functions used by the exploration rules. The unnamed xfunc.CustomFuncs allows CustomFuncs to provide a clean interface for calling functions from both the xform and xfunc packages using the same struct.

func (*CustomFuncs) AddPrimaryKeyColsToScanPrivate Uses

func (c *CustomFuncs) AddPrimaryKeyColsToScanPrivate(sp *memo.ScanPrivate) *memo.ScanPrivate

AddPrimaryKeyColsToScanPrivate creates a new ScanPrivate that is the same as the input ScanPrivate, but has primary keys added to the ColSet.

func (*CustomFuncs) CanLimitConstrainedScan Uses

func (c *CustomFuncs) CanLimitConstrainedScan(
    scanPrivate *memo.ScanPrivate, required physical.OrderingChoice,
) bool

CanLimitConstrainedScan returns true if the given scan has already been constrained and can have a row count limit installed as well. This is only possible when the required ordering of the rows to be limited can be satisfied by the Scan operator.

NOTE: Limiting unconstrained scans is done by the GenerateLimitedScans rule,

since that can require IndexJoin operators to be generated.

func (*CustomFuncs) CommuteJoinFlags Uses

func (c *CustomFuncs) CommuteJoinFlags(p *memo.JoinPrivate) *memo.JoinPrivate

CommuteJoinFlags returns a join private for the commuted join (where the left and right sides are swapped). It adjusts any join flags that are specific to one side.

func (*CustomFuncs) ConvertIndexToLookupJoinPrivate Uses

func (c *CustomFuncs) ConvertIndexToLookupJoinPrivate(
    indexPrivate *memo.IndexJoinPrivate, outCols opt.ColSet,
) *memo.LookupJoinPrivate

ConvertIndexToLookupJoinPrivate constructs a new LookupJoinPrivate using the given IndexJoinPrivate with the given output columns.

func (*CustomFuncs) DuplicateScanPrivate Uses

func (c *CustomFuncs) DuplicateScanPrivate(sp *memo.ScanPrivate) *memo.ScanPrivate

DuplicateScanPrivate constructs a new ScanPrivate with new table and column IDs. Only the Index, Flags and Locking fields are copied from the old ScanPrivate, so the new ScanPrivate will not have constraints even if the old one did.

func (*CustomFuncs) ExprPairFiltersItemToReplace Uses

func (c *CustomFuncs) ExprPairFiltersItemToReplace(ep ExprPair) *memo.FiltersItem

ExprPairFiltersItemToReplace returns the original FiltersItem that the ExprPair was generated from. This FiltersItem should be replaced by ExprPairLeft and ExprPairRight in the newly generated filters in SplitDisjunction(AddKey).

func (*CustomFuncs) ExprPairForSplitDisjunction Uses

func (c *CustomFuncs) ExprPairForSplitDisjunction(
    sp *memo.ScanPrivate, filters memo.FiltersExpr,
) ExprPair

ExprPairForSplitDisjunction finds the first "interesting" ExprPair in the filters and returns it. If an "interesting" ExprPair is not found, an empty ExprPair is returned.

For details on what makes an ExprPair "interesting", see buildExprPairForSplitDisjunction.

func (*CustomFuncs) ExprPairLeft Uses

func (c *CustomFuncs) ExprPairLeft(ep ExprPair) opt.ScalarExpr

ExprPairLeft returns the left ScalarExpr in an ExprPair.

func (*CustomFuncs) ExprPairRight Uses

func (c *CustomFuncs) ExprPairRight(ep ExprPair) opt.ScalarExpr

ExprPairRight returns the right ScalarExpr in an ExprPair.

func (*CustomFuncs) ExprPairSucceeded Uses

func (c *CustomFuncs) ExprPairSucceeded(ep ExprPair) bool

ExprPairSucceeded returns true if the ExprPair is not nil.

func (*CustomFuncs) FirstArgIsVariable Uses

func (c *CustomFuncs) FirstArgIsVariable(fn opt.ScalarExpr) bool

FirstArgIsVariable returns true if the first argument to the given function is a variable.

func (*CustomFuncs) GenerateConstrainedScans Uses

func (c *CustomFuncs) GenerateConstrainedScans(
    grp memo.RelExpr, scanPrivate *memo.ScanPrivate, explicitFilters memo.FiltersExpr,
)

GenerateConstrainedScans enumerates all non-inverted secondary indexes on the Scan operator's table and tries to push the given Select filter into new constrained Scan operators using those indexes. Since this only needs to be done once per table, GenerateConstrainedScans should only be called on the original unaltered primary index Scan operator (i.e. not constrained or limited).

For each secondary index that "covers" the columns needed by the scan, there are three cases:

- a filter that can be completely converted to a constraint over that index
  generates a single constrained Scan operator (to be added to the same
  group as the original Select operator):

    (Scan $scanDef)

- a filter that can be partially converted to a constraint over that index
  generates a constrained Scan operator in a new memo group, wrapped in a
  Select operator having the remaining filter (to be added to the same group
  as the original Select operator):

    (Select (Scan $scanDef) $filter)

- a filter that cannot be converted to a constraint generates nothing

And for a secondary index that does not cover the needed columns:

- a filter that can be completely converted to a constraint over that index
  generates a single constrained Scan operator in a new memo group, wrapped
  in an IndexJoin operator that looks up the remaining needed columns (and
  is added to the same group as the original Select operator)

    (IndexJoin (Scan $scanDef) $indexJoinDef)

- a filter that can be partially converted to a constraint over that index
  generates a constrained Scan operator in a new memo group, wrapped in an
  IndexJoin operator that looks up the remaining needed columns; the
  remaining filter is distributed above and/or below the IndexJoin,
  depending on which columns it references:

    (IndexJoin
      (Select (Scan $scanDef) $filter)
      $indexJoinDef
    )

    (Select
      (IndexJoin (Scan $scanDef) $indexJoinDef)
      $filter
    )

    (Select
      (IndexJoin
        (Select (Scan $scanDef) $innerFilter)
        $indexJoinDef
      )
      $outerFilter
    )

GenerateConstrainedScans will further constrain the enumerated index scans by trying to use the check constraints and computed columns that apply to the table being scanned, as well as the partitioning defined for the index. See comments above checkColumnFilters, computedColFilters, and partitionValuesFilters for more detail.

func (*CustomFuncs) GenerateGeoLookupJoins Uses

func (c *CustomFuncs) GenerateGeoLookupJoins(
    grp memo.RelExpr,
    joinType opt.Operator,
    input memo.RelExpr,
    scanPrivate *memo.ScanPrivate,
    on memo.FiltersExpr,
    joinPrivate *memo.JoinPrivate,
    fn opt.ScalarExpr,
)

GenerateGeoLookupJoins is similar to GenerateLookupJoins, but instead of generating lookup joins with regular indexes, it generates geospatial lookup joins with inverted geospatial indexes. Since these indexes are not covering, all geospatial lookup joins must be wrapped in an index join with the primary index of the table. See the description of Case 2 in the comment above GenerateLookupJoins for details about how this works. TODO(rytaft): generalize this function to be GenerateInvertedJoins and add

support for JSON and array inverted indexes.

TODO(rytaft): handle more complicated geo-spatial expressions

e.g. ST_Intersects(x, y) AND ST_Covers(x, y) where y is the indexed value.

func (*CustomFuncs) GenerateIndexScans Uses

func (c *CustomFuncs) GenerateIndexScans(grp memo.RelExpr, scanPrivate *memo.ScanPrivate)

GenerateIndexScans enumerates all non-inverted and non-partial secondary indexes on the given Scan operator's table and generates an alternate Scan operator for each index that includes the set of needed columns specified in the ScanOpDef.

Partial indexes do not index every row in the table and they can only be used in cases where a query filter implies the partial index predicate. GenerateIndexScans does not deal with filters. Therefore, partial indexes cannot be considered for non-constrained index scans.

NOTE: This does not generate index joins for non-covering indexes (except in

case of ForceIndex). Index joins are usually only introduced "one level
up", when the Scan operator is wrapped by an operator that constrains
or limits scan output in some way (e.g. Select, Limit, InnerJoin).
Index joins are only lower cost when their input does not include all
rows from the table. See ConstrainScans and LimitScans for cases where
index joins are introduced into the memo.

func (*CustomFuncs) GenerateInvertedIndexScans Uses

func (c *CustomFuncs) GenerateInvertedIndexScans(
    grp memo.RelExpr, scanPrivate *memo.ScanPrivate, filters memo.FiltersExpr,
)

GenerateInvertedIndexScans enumerates all inverted indexes on the Scan operator's table and generates an alternate Scan operator for each inverted index that can service the query.

The resulting Scan operator is pre-constrained and requires an IndexJoin to project columns other than the primary key columns. The reason it's pre- constrained is that we cannot treat an inverted index in the same way as a regular index, since it does not actually contain the indexed column.

func (*CustomFuncs) GenerateInvertedIndexZigzagJoins Uses

func (c *CustomFuncs) GenerateInvertedIndexZigzagJoins(
    grp memo.RelExpr, scanPrivate *memo.ScanPrivate, filters memo.FiltersExpr,
)

GenerateInvertedIndexZigzagJoins generates zigzag joins for constraints on inverted index. It looks for cases where one inverted index can satisfy two constraints, and it produces zigzag joins with the same index on both sides of the zigzag join for those cases, fixed on different constant values.

func (*CustomFuncs) GenerateLimitedScans Uses

func (c *CustomFuncs) GenerateLimitedScans(
    grp memo.RelExpr,
    scanPrivate *memo.ScanPrivate,
    limit tree.Datum,
    required physical.OrderingChoice,
)

GenerateLimitedScans enumerates all non-inverted and non-partial secondary indexes on the Scan operator's table and tries to create new limited Scan operators from them. Since this only needs to be done once per table, GenerateLimitedScans should only be called on the original unaltered primary index Scan operator (i.e. not constrained or limited).

For a secondary index that "covers" the columns needed by the scan, a single limited Scan operator is created. For a non-covering index, an IndexJoin is constructed to add missing columns to the limited Scan.

Inverted index scans are not guaranteed to produce a specific number of result rows because they contain multiple entries for a single row indexed. Therefore, they cannot be considered for limited scans.

Partial indexes do not index every row in the table and they can only be used in cases where a query filter implies the partial index predicate. GenerateLimitedScans deals with limits, but no filters. Therefore, partial indexes cannot be considered for limited scans.

func (*CustomFuncs) GenerateLookupJoins Uses

func (c *CustomFuncs) GenerateLookupJoins(
    grp memo.RelExpr,
    joinType opt.Operator,
    input memo.RelExpr,
    scanPrivate *memo.ScanPrivate,
    on memo.FiltersExpr,
    joinPrivate *memo.JoinPrivate,
)

GenerateLookupJoins looks at the possible indexes and creates lookup join expressions in the current group. A lookup join can be created when the ON condition has equality constraints on a prefix of the index columns.

There are two cases:

1. The index has all the columns we need; this is the simple case, where we
   generate a LookupJoin expression in the current group:

       Join                       LookupJoin(t@idx))
       /   \                           |
      /     \            ->            |
    Input  Scan(t)                   Input

2. The index is not covering. We have to generate an index join above the
   lookup join. Note that this index join is also implemented as a
   LookupJoin, because an IndexJoin can only output columns from one table,
   whereas we also need to output columns from Input.

       Join                       LookupJoin(t@primary)
       /   \                           |
      /     \            ->            |
    Input  Scan(t)                LookupJoin(t@idx)
                                       |
                                       |
                                     Input

   For example:
    CREATE TABLE abc (a PRIMARY KEY, b INT, c INT)
    CREATE TABLE xyz (x PRIMARY KEY, y INT, z INT, INDEX (y))
    SELECT * FROM abc JOIN xyz ON a=y

   We want to first join abc with the index on y (which provides columns y, x)
   and then use a lookup join to retrieve column z. The "index join" (top
   LookupJoin) will produce columns a,b,c,x,y; the lookup columns are just z
   (the original index join produced x,y,z).

   Note that the top LookupJoin "sees" column IDs from the table on both
   "sides" (in this example x,y on the left and z on the right) but there is
   no overlap.

func (*CustomFuncs) GenerateMergeJoins Uses

func (c *CustomFuncs) GenerateMergeJoins(
    grp memo.RelExpr,
    originalOp opt.Operator,
    left, right memo.RelExpr,
    on memo.FiltersExpr,
    joinPrivate *memo.JoinPrivate,
)

GenerateMergeJoins spawns MergeJoinOps, based on any interesting orderings.

func (*CustomFuncs) GeneratePartialIndexScans Uses

func (c *CustomFuncs) GeneratePartialIndexScans(
    grp memo.RelExpr, scanPrivate *memo.ScanPrivate, filters memo.FiltersExpr,
)

GeneratePartialIndexScans generates unconstrained index scans over all partial indexes with predicates that are implied by the filters. Partial indexes with predicates which cannot be proven to be implied by the filters are disregarded.

When a filter completely matches the predicate, the remaining filters are simplified so that they do not include the filter. A redundant filter is unnecessary to include in the remaining filters because a scan over the partial index implicitly filters the results.

For every partial index that is implied by the filters, a Scan will be generated along with a combination of an IndexJoin and Selects. There are three questions to consider which determine which operators are generated.

1. Does the index "cover" the columns needed?
2. Are there any remaining filters to apply after the Scan?
3. If there are remaining filters does the index cover the referenced
   columns?

If the index covers the columns needed, no IndexJoin is need. The two possible generated expressions are either a lone Scan or a Scan wrapped in a Select that applies any remaining filters.

(Scan $scanDef)

(Select (Scan $scanDef) $remainingFilters)

If the index is not covering, then an IndexJoin is required to retrieve the needed columns. Some or all of the remaining filters may be required to be applied after the IndexJoin, because they reference columns not covered by the index. Therefore, Selects can be constructed before, after, or both before and after the IndexJoin depending on the columns referenced in the remaining filters.

If the index is not covering, then an IndexJoin is required to retrieve the needed columns. Some of the remaining filters may be applied in a Select before the IndexJoin, if all the columns referenced in the filter are covered by the index. Some of the remaining filters may be applied in a Select after the IndexJoin, if their columns are not covered. Therefore, Selects can be constructed before, after, or both before and after the IndexJoin.

 (IndexJoin (Scan $scanDef) $indexJoinDef)

 (IndexJoin
   (Select (Scan $scanDef) $remainingFilters)
   $indexJoinDef
 )

(Select
  (IndexJoin (Scan $scanDef) $indexJoinDef)
  $outerFilter
)

(Select
  (IndexJoin
    (Select (Scan $scanDef) $innerFilter)
    $indexJoinDef
  )
  $outerFilter
)

func (*CustomFuncs) GenerateStreamingGroupBy Uses

func (c *CustomFuncs) GenerateStreamingGroupBy(
    grp memo.RelExpr,
    op opt.Operator,
    input memo.RelExpr,
    aggs memo.AggregationsExpr,
    private *memo.GroupingPrivate,
)

GenerateStreamingGroupBy generates variants of a GroupBy or DistinctOn expression with more specific orderings on the grouping columns, using the interesting orderings property. See the GenerateStreamingGroupBy rule.

func (*CustomFuncs) GenerateZigzagJoins Uses

func (c *CustomFuncs) GenerateZigzagJoins(
    grp memo.RelExpr, scanPrivate *memo.ScanPrivate, filters memo.FiltersExpr,
)

GenerateZigzagJoins generates zigzag joins for all pairs of indexes of the Scan table which contain one of the constant columns in the FiltersExpr as its prefix.

Similar to the lookup join, if the selected index pair does not contain all the columns in the output of the scan, we wrap the zigzag join in another index join (implemented as a lookup join) on the primary index. The index join is implemented with a lookup join since the index join does not support arbitrary input sources that are not plain index scans.

func (*CustomFuncs) HasInvertedIndexes Uses

func (c *CustomFuncs) HasInvertedIndexes(scanPrivate *memo.ScanPrivate) bool

HasInvertedIndexes returns true if at least one inverted index is defined on the Scan operator's table.

func (*CustomFuncs) Init Uses

func (c *CustomFuncs) Init(e *explorer)

Init initializes a new CustomFuncs with the given explorer.

func (*CustomFuncs) IsCanonicalGroupBy Uses

func (c *CustomFuncs) IsCanonicalGroupBy(private *memo.GroupingPrivate) bool

IsCanonicalGroupBy returns true if the private is for the canonical version of the grouping operator. This is the operator that is built initially (and has all grouping columns as optional in the ordering), as opposed to variants generated by the GenerateStreamingGroupBy exploration rule.

func (*CustomFuncs) IsCanonicalScan Uses

func (c *CustomFuncs) IsCanonicalScan(scan *memo.ScanPrivate) bool

IsCanonicalScan returns true if the given ScanPrivate is an original unaltered primary index Scan operator (i.e. unconstrained and not limited).

func (*CustomFuncs) IsGeoIndexFunction Uses

func (c *CustomFuncs) IsGeoIndexFunction(fn opt.ScalarExpr) bool

IsGeoIndexFunction returns true if the given function is a geospatial function that can be index-accelerated.

func (*CustomFuncs) IsLocking Uses

func (c *CustomFuncs) IsLocking(scan *memo.ScanPrivate) bool

IsLocking returns true if the ScanPrivate is configured to use a row-level locking mode. This can be the case either because the Scan is in the scope of a SELECT .. FOR [KEY] UPDATE/SHARE clause or because the Scan was configured as part of the row retrieval of a DELETE or UPDATE statement.

func (*CustomFuncs) IsSimpleEquality Uses

func (c *CustomFuncs) IsSimpleEquality(filters memo.FiltersExpr) bool

IsSimpleEquality returns true if all of the filter conditions are equalities between simple data types (constants, variables, tuples and NULL).

func (*CustomFuncs) LimitScanPrivate Uses

func (c *CustomFuncs) LimitScanPrivate(
    scanPrivate *memo.ScanPrivate, limit tree.Datum, required physical.OrderingChoice,
) *memo.ScanPrivate

LimitScanPrivate constructs a new ScanPrivate value that is based on the given ScanPrivate. The new private's HardLimit is set to the given limit, which must be a constant int datum value. The other fields are inherited from the existing private.

func (*CustomFuncs) MakeOrderingChoiceFromColumn Uses

func (c *CustomFuncs) MakeOrderingChoiceFromColumn(
    op opt.Operator, col opt.ColumnID,
) physical.OrderingChoice

MakeOrderingChoiceFromColumn constructs a new OrderingChoice with one element in the sequence: the columnID in the order defined by (MIN/MAX) operator. This function was originally created to be used with the Replace(Min|Max)WithLimit exploration rules.

WARNING: The MinOp case can return a NULL value if the column allows it. This is because NULL values sort first in CRDB.

func (*CustomFuncs) MakeProjectFromPassthroughAggs Uses

func (c *CustomFuncs) MakeProjectFromPassthroughAggs(
    grp memo.RelExpr, input memo.RelExpr, aggs memo.AggregationsExpr,
)

MakeProjectFromPassthroughAggs constructs a top-level Project operator that contains one output column per function in the given aggregrate list. The input expression is expected to return zero or one rows, and the aggregate functions are expected to always pass through their values in that case.

func (*CustomFuncs) MakeSetPrivateForSplitDisjunction Uses

func (c *CustomFuncs) MakeSetPrivateForSplitDisjunction(
    left, right *memo.ScanPrivate,
) *memo.SetPrivate

MakeSetPrivateForSplitDisjunction constructs a new SetPrivate with column sets from the left and right ScanPrivate. We use the same ColList for the LeftCols and OutCols of the SetPrivate because we've used the original ScanPrivate column IDs for the left ScanPrivate and those are safe to use as output column IDs of the Union expression.

func (*CustomFuncs) MapScanFilterCols Uses

func (c *CustomFuncs) MapScanFilterCols(
    filters memo.FiltersExpr, src *memo.ScanPrivate, dst *memo.ScanPrivate,
) memo.FiltersExpr

MapScanFilterCols returns a new FiltersExpr with all the src column IDs in the input expression replaced with column IDs in dst.

NOTE: Every ColumnID in src must map to the a ColumnID in dst with the same relative position in the ColSets. For example, if src and dst are (1, 5, 6) and (7, 12, 15), then the following mapping would be applied:

1 => 7
5 => 12
6 => 15

func (*CustomFuncs) OtherAggsAreConst Uses

func (c *CustomFuncs) OtherAggsAreConst(
    aggs memo.AggregationsExpr, except *memo.AggregationsItem,
) bool

OtherAggsAreConst returns true if all items in the given aggregate list contain ConstAgg functions, except for the "except" item. The ConstAgg functions will always return the same value, as long as there is at least one input row.

func (*CustomFuncs) ScanIsInverted Uses

func (c *CustomFuncs) ScanIsInverted(sp *memo.ScanPrivate) bool

ScanIsInverted returns true if the index of the given ScanPrivate is an inverted index.

func (*CustomFuncs) ScanIsLimited Uses

func (c *CustomFuncs) ScanIsLimited(sp *memo.ScanPrivate) bool

ScanIsLimited returns true if the scan operator with the given ScanPrivate is limited.

func (*CustomFuncs) SecondArgIsVariable Uses

func (c *CustomFuncs) SecondArgIsVariable(fn opt.ScalarExpr) bool

SecondArgIsVariable returns true if the second argument to the given function is a variable.

func (*CustomFuncs) ShouldReorderJoins Uses

func (c *CustomFuncs) ShouldReorderJoins(root memo.RelExpr) bool

ShouldReorderJoins returns whether the optimizer should attempt to find a better ordering of inner joins.

func (*CustomFuncs) SplitScanIntoUnionScans Uses

func (c *CustomFuncs) SplitScanIntoUnionScans(
    limitOrdering physical.OrderingChoice, scan memo.RelExpr, sp *memo.ScanPrivate, limit tree.Datum,
) memo.RelExpr

SplitScanIntoUnionScans returns a Union of Scan operators with hard limits that each scan over a single key from the original scan's constraints. This is beneficial in cases where the original scan had to scan over many rows but had relatively few keys to scan over. TODO(drewk): handle inverted scans.

type ExprPair Uses

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

ExprPair stores a left and right ScalarExpr. ExprPairForSplitDisjunction returns ExprPair, which can be deconstructed later, to avoid extra computation in determining the left and right expression groups.

type FmtFlags Uses

type FmtFlags int

FmtFlags controls how the memo output is formatted.

const (
    // FmtPretty performs a breadth-first topological sort on the memo groups,
    // and shows the root group at the top of the memo.
    FmtPretty FmtFlags = iota
)

type MatchedRuleFunc Uses

type MatchedRuleFunc = norm.MatchedRuleFunc

MatchedRuleFunc defines the callback function for the NotifyOnMatchedRule event supported by the optimizer. See the comment in factory.go for more details.

type Optimizer Uses

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

Optimizer transforms an input expression tree into the logically equivalent output expression tree with the lowest possible execution cost.

To use the optimizer, construct an input expression tree by invoking construction methods on the Optimizer.Factory instance. The factory transforms the input expression into its canonical form as part of construction. Pass the root of the tree constructed by the factory to the Optimize method, along with a set of required physical properties that the expression must provide. The optimizer will return an Expr over the output expression tree with the lowest cost.

func (*Optimizer) Coster Uses

func (o *Optimizer) Coster() Coster

Coster returns the coster instance that the optimizer is currently using to estimate the cost of executing portions of the expression tree. When a new optimizer is constructed, it creates a default coster that will be used unless it is overridden with a call to SetCoster.

func (*Optimizer) DetachMemo Uses

func (o *Optimizer) DetachMemo() *memo.Memo

DetachMemo extracts the memo from the optimizer, and then re-initializes the optimizer so that its reuse will not impact the detached memo. This method is used to extract a read-only memo during the PREPARE phase.

func (*Optimizer) DisableOptimizations Uses

func (o *Optimizer) DisableOptimizations()

DisableOptimizations disables all transformation rules, including normalize and explore rules. The unaltered input expression tree becomes the output expression tree (because no transforms are applied).

func (*Optimizer) Factory Uses

func (o *Optimizer) Factory() *norm.Factory

Factory returns a factory interface that the caller uses to construct an input expression tree. The root of the resulting tree can be passed to the Optimize method in order to find the lowest cost plan.

func (*Optimizer) FormatExpr Uses

func (o *Optimizer) FormatExpr(e opt.Expr, flags memo.ExprFmtFlags) string

FormatExpr is a convenience wrapper for memo.FormatExpr.

func (*Optimizer) FormatMemo Uses

func (o *Optimizer) FormatMemo(flags FmtFlags) string

FormatMemo returns a string representation of the memo for testing and debugging. The given flags control which properties are shown.

func (*Optimizer) Init Uses

func (o *Optimizer) Init(evalCtx *tree.EvalContext, catalog cat.Catalog)

Init initializes the Optimizer with a new, blank memo structure inside. This must be called before the optimizer can be used (or reused).

func (*Optimizer) Memo Uses

func (o *Optimizer) Memo() *memo.Memo

Memo returns the memo structure that the optimizer is using to optimize.

func (*Optimizer) NotifyOnAppliedRule Uses

func (o *Optimizer) NotifyOnAppliedRule(appliedRule AppliedRuleFunc)

NotifyOnAppliedRule sets a callback function which is invoked each time an optimization rule (Normalize or Explore) has been applied by the optimizer. If appliedRule is nil, then no further notifications are sent.

func (*Optimizer) NotifyOnMatchedRule Uses

func (o *Optimizer) NotifyOnMatchedRule(matchedRule MatchedRuleFunc)

NotifyOnMatchedRule sets a callback function which is invoked each time an optimization rule (Normalize or Explore) has been matched by the optimizer. If matchedRule is nil, then no notifications are sent, and all rules are applied by default. In addition, callers can invoke the DisableOptimizations convenience method to disable all rules.

func (*Optimizer) Optimize Uses

func (o *Optimizer) Optimize() (_ opt.Expr, err error)

Optimize returns the expression which satisfies the required physical properties at the lowest possible execution cost, but is still logically equivalent to the given expression. If there is a cost "tie", then any one of the qualifying lowest cost expressions may be selected by the optimizer.

func (*Optimizer) RecomputeCost Uses

func (o *Optimizer) RecomputeCost()

RecomputeCost recomputes the cost of each expression in the lowest cost tree. It should be used in combination with the perturb-cost OptTester flag in order to update the query plan tree after optimization is complete with the real computed cost, not the perturbed cost.

func (*Optimizer) SetCoster Uses

func (o *Optimizer) SetCoster(coster Coster)

SetCoster overrides the default coster. The optimizer will now use the given coster to estimate the cost of expression execution.

func (*Optimizer) String Uses

func (o *Optimizer) String() string

type RuleSet Uses

type RuleSet = util.FastIntSet

RuleSet efficiently stores an unordered set of RuleNames.

Package xform imports 27 packages (graph) and is imported by 8 packages. Updated 2020-07-11. Refresh now. Tools for package owners.