cockroach: Index | Files

package xform

import ""


Package Files

coster.go custom_funcs.go explorer.go index_scan_builder.go interesting_orderings.go memo_format.go optimizer.go physical_props.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 {
    // 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) 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 PushLimitIntoScan rule,

since that can require IndexJoin operators to be generated.

func (*CustomFuncs) GenerateConstrainedScans Uses

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

GenerateConstrainedScans enumerates all 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:

      (Select (Scan $scanDef) $filter)

      (IndexJoin (Scan $scanDef) $indexJoinDef)

        (Select (Scan $scanDef) $innerFilter)

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

func (*CustomFuncs) GenerateIndexScans Uses

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

GenerateIndexScans enumerates all 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.

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

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)

   For example:
    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) 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.

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) 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.

func (*CustomFuncs) NoJoinHints Uses

func (c *CustomFuncs) NoJoinHints(p *memo.JoinPrivate) bool

NoJoinHints returns true if no hints were specified for this join.

func (*CustomFuncs) ShouldReorderJoins Uses

func (c *CustomFuncs) ShouldReorderJoins(left, right memo.RelExpr) bool

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

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

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 23 packages (graph) and is imported by 7 packages. Updated 2019-09-19. Refresh now. Tools for package owners.