`import "github.com/cockroachdb/cockroach/pkg/sql/opt/props/physical"`

- Variables
- func ParseOrdering(str string) opt.Ordering
- type OrderingChoice
- func ParseOrderingChoice(s string) OrderingChoice
- func (oc *OrderingChoice) Any() bool
- func (oc *OrderingChoice) AppendCol(id opt.ColumnID, descending bool)
- func (oc *OrderingChoice) CanProjectCols(cs opt.ColSet) bool
- func (oc *OrderingChoice) CanSimplify(fdset *props.FuncDepSet) bool
- func (oc *OrderingChoice) ColSet() opt.ColSet
- func (oc *OrderingChoice) Copy() OrderingChoice
- func (oc *OrderingChoice) Equals(rhs *OrderingChoice) bool
- func (oc OrderingChoice) Format(buf *bytes.Buffer)
- func (oc *OrderingChoice) FromOrdering(ord opt.Ordering)
- func (oc *OrderingChoice) FromOrderingWithOptCols(ord opt.Ordering, optCols opt.ColSet)
- func (oc *OrderingChoice) Implies(other *OrderingChoice) bool
- func (oc *OrderingChoice) Intersection(other *OrderingChoice) OrderingChoice
- func (oc *OrderingChoice) Intersects(other *OrderingChoice) bool
- func (oc *OrderingChoice) MatchesAt(index int, col opt.OrderingColumn) bool
- func (oc OrderingChoice) PrefixIntersection( prefix opt.ColSet, suffix []OrderingColumnChoice, ) (_ OrderingChoice, ok bool)
- func (oc *OrderingChoice) ProjectCols(cols opt.ColSet)
- func (oc *OrderingChoice) Simplify(fdset *props.FuncDepSet)
- func (oc OrderingChoice) String() string
- func (oc *OrderingChoice) SubsetOfCols(cs opt.ColSet) bool
- func (oc *OrderingChoice) ToOrdering() opt.Ordering
- func (oc *OrderingChoice) Truncate(prefix int)
- type OrderingColumnChoice
- type Presentation
- func (p Presentation) Any() bool
- func (p Presentation) Equals(rhs Presentation) bool
- func (p Presentation) String() string
- type Provided
- type Required

ordering_choice.go provided.go required.go

MinRequired are the default physical properties that require nothing and provide nothing.

ParseOrdering parses a simple opt.Ordering; for example: "+1,-3".

The input string is expected to be valid; ParseOrdering will panic if it is not.

❖

type OrderingChoice struct { // Optional is the set of columns that can appear at any position in the // ordering. Columns in Optional must not appear in the Columns sequence. // In addition, if Columns is empty, then Optional must be as well. // After initial construction, Optional is immutable. To update, replace // with a different set containing the desired columns. Optional opt.ColSet // Columns is the sequence of equivalent column groups that can be used to // form each column in the sort key. Columns must not appear in the Optional // set. The array memory is owned by this struct, and should not be copied // to another OrderingChoice unless both are kept immutable. Columns []OrderingColumnChoice }

OrderingChoice defines the set of possible row orderings that are provided or required by an operator. An OrderingChoice consists of two parts: an ordered sequence of equivalent column groups and a set of optional columns. Together, these parts specify a simple pattern that can match one or more candidate orderings. Here are some examples:

+1 ORDER BY a +1,-2 ORDER BY a,b DESC +(1|2) ORDER BY a | ORDER BY b +(1|2),+3 ORDER BY a,c | ORDER BY b, c -(3|4),+5 opt(1,2) ORDER BY c DESC,e | ORDER BY a,d DESC,b DESC,e | ...

Each column in the ordering sequence forms the corresponding column of the sort key, from most significant to least significant. Each column has a sort direction, either ascending or descending. The relation is ordered by the first column; rows that have the same value are then ordered by the second column; rows that still have the same value are ordered by the third column, and so on.

Sometimes multiple columns in the relation have equivalent values. The OrderingChoiceColumn stores these columns in a group; any of the columns in the group can be used to form the corresponding column in the sort key. The equivalent group columns come from SQL expressions like:

a=b

The optional column set contains columns that can appear anywhere (or nowhere) in the ordering. Optional columns come from SQL expressions like:

a=1

Another case for optional columns is when we are grouping along a set of columns and only care about the intra-group ordering.

The optional columns can be interleaved anywhere in the sequence of ordering columns, as they have no effect on the ordering.

❖

func ParseOrderingChoice(s string) OrderingChoice

ParseOrderingChoice parses the string representation of an OrderingChoice for testing purposes. Here are some examples of the string format:

+1 -(1|2),+3 +(1|2),+3 opt(5,6)

The input string is expected to be valid; ParseOrderingChoice will panic if it is not.

❖

func (oc *OrderingChoice) Any() bool

Any is true if this instance allows any ordering (any length, any columns).

❖

func (oc *OrderingChoice) AppendCol(id opt.ColumnID, descending bool)

AppendCol adds a new column to the end of the sequence of ordering columns maintained by this instance. The new column has the given ID and direction as the only ordering choice.

❖

func (oc *OrderingChoice) CanProjectCols(cs opt.ColSet) bool

CanProjectCols is true if at least one column in each ordering column group is part of the given column set. For example, if the OrderingChoice is:

+1,-(2|3) opt(4,5)

then CanProjectCols will behave as follows for these input sets:

(1,2) => true (1,3) => true (1,2,4) => true (1) => false (3,4) => false

❖

func (oc *OrderingChoice) CanSimplify(fdset *props.FuncDepSet) bool

CanSimplify returns true if a call to Simplify would result in any changes to the OrderingChoice. Changes include additional constant columns, removed groups, and additional equivalent columns. This is used to quickly check whether Simplify needs to be called without requiring allocations in the common case. This logic should be changed in concert with the Simplify logic.

❖

func (oc *OrderingChoice) ColSet() opt.ColSet

ColSet returns the set of all non-optional columns that are part of this instance. For example, (1,2,3) will be returned if the OrderingChoice is:

+1,(2|3) opt(4,5)

❖

func (oc *OrderingChoice) Copy() OrderingChoice

Copy returns a complete copy of this instance, with a private version of the ordering column array.

❖

func (oc *OrderingChoice) Equals(rhs *OrderingChoice) bool

Equals returns true if the set of orderings matched by this instance is the same as the set matched by the given instance.

❖

func (oc OrderingChoice) Format(buf *bytes.Buffer)

Format writes the OrderingChoice to the given buffer in a human-readable string representation that can also be parsed by ParseOrderingChoice:

+1 +1,-2 +(1|2) +(1|2),+3 -(3|4),+5 opt(1,2)

❖

func (oc *OrderingChoice) FromOrdering(ord opt.Ordering)

FromOrdering sets this OrderingChoice to the given opt.Ordering.

FromOrderingWithOptCols sets this OrderingChoice to the given opt.Ordering and with the given optional columns. Any optional columns in the given ordering are ignored.

❖

func (oc *OrderingChoice) Implies(other *OrderingChoice) bool

Implies returns true if any ordering allowed by <oc> is also allowed by <other>.

In the case of no optional or equivalent columns, Implies returns true when the given ordering is a prefix of this ordering.

Examples:

<empty> implies <empty> +1 implies <empty> (given set is prefix) +1 implies +1 +1,-2 implies +1 (given set is prefix) +1,-2 implies +1,-2 +1 implies +1 opt(2) (unused optional col is ignored) -2,+1 implies +1 opt(2) (optional col is ignored) +1 implies +(1|2) (subset of choice) +(1|2) implies +(1|2|3) (subset of choice) +(1|2),-4 implies +(1|2|3),-(4|5) +(1|2) opt(4) implies +(1|2|3) opt(4) <empty> !implies +1 +1 !implies -1 (direction mismatch) +1 !implies +1,-2 (prefix matching not commutative) +1 opt(2) !implies +1 (extra optional cols not allowed) +1 opt(2) !implies +1 opt(3) +(1|2) !implies -(1|2) (direction mismatch) +(1|2) !implies +(3|4) (no intersection) +(1|2) !implies +(2|3) (intersects, but not subset) +(1|2|3) !implies +(1|2) (subset of choice not commutative) +(1|2) !implies +1 opt(2)

❖

func (oc *OrderingChoice) Intersection(other *OrderingChoice) OrderingChoice

Intersection returns an OrderingChoice that Implies both ordering choices. Can only be called if Intersects is true. Some examples:

+1 ∩ <empty> = +1 +1 ∩ +1,+2 = +1,+2 +1,+2 opt(3) ∩ +1,+3 = +1,+3,+2

In general, OrderingChoice is not expressive enough to represent the intersection. In such cases, an OrderingChoice representing a subset of the intersection is returned. For example,

+1 opt(2) ∩ +2 opt(1)

can be either +1,+2 or +2,+1; only one of these is returned. Note that the function may not be commutative in this case. In practice, such cases are unlikely.

It is guaranteed that if one OrderingChoice Implies the other, it will also be the Intersection.

❖

func (oc *OrderingChoice) Intersects(other *OrderingChoice) bool

Intersects returns true if there are orderings that satisfy both OrderingChoices. See Intersection for more information.

❖

func (oc *OrderingChoice) MatchesAt(index int, col opt.OrderingColumn) bool

MatchesAt returns true if the ordering column at the given index in this instance matches the given column. The column matches if its id is part of the equivalence group and if it has the same direction.

❖

func (oc OrderingChoice) PrefixIntersection( prefix opt.ColSet, suffix []OrderingColumnChoice, ) (_ OrderingChoice, ok bool)

PrefixIntersection computes an OrderingChoice which:

- implies <oc> (this instance), and - implies a "segmented ordering", which is any ordering which starts with a permutation of all columns in <prefix> followed by the <suffix> ordering.

Note that <prefix> and <suffix> cannot have any columns in common.

Such an ordering can be computed via the following rules:

- if <prefix> and <suffix> are empty: return this instance. - if <oc> is empty: generate an arbitrary segmented ordering. - if the first column of <oc> is either in <prefix> or is the first column of <suffix> while <prefix> is empty: this column is the first column of the result; calculate the rest recursively.

❖

func (oc *OrderingChoice) ProjectCols(cols opt.ColSet)

ProjectCols removes any references to columns that are not in the given set. This method can only be used when the OrderingChoice can be expressed with the given columns; i.e. all groups have at least one column in the set.

❖

func (oc *OrderingChoice) Simplify(fdset *props.FuncDepSet)

Simplify uses the given FD set to streamline the orderings allowed by this instance, and to potentially increase the number of allowed orderings:

1. Constant columns add additional optional column choices. 2. Equivalent columns allow additional choices within an ordering column group. 3. If the columns in a group are functionally determined by columns from previous groups, the group can be dropped. This technique is described in the "Reduce Order" section of this paper: Simmen, David & Shekita, Eugene & Malkemus, Timothy. (1996). Fundamental Techniques for Order Optimization. Sigmod Record. Volume 25 Issue 2, June 1996. Pages 57-67. https://cs.uwaterloo.ca/~gweddell/cs798/p57-simmen.pdf

This logic should be changed in concert with the CanSimplify logic.

❖

func (oc OrderingChoice) String() string

❖

func (oc *OrderingChoice) SubsetOfCols(cs opt.ColSet) bool

SubsetOfCols is true if the OrderingChoice only references columns in the given set.

❖

func (oc *OrderingChoice) ToOrdering() opt.Ordering

ToOrdering returns an opt.Ordering instance composed of the shortest possible orderings that this instance allows. If there are several, then one is chosen arbitrarily.

❖

func (oc *OrderingChoice) Truncate(prefix int)

Truncate removes all ordering columns beyond the given index. For example, +1,+(2|3),-4 opt(5,6) would be truncated to:

prefix=0 => opt(5,6) prefix=1 => +1 opt(5,6) prefix=2 => +1,+(2|3) opt(5,6) prefix=3+ => +1,+(2|3),-4 opt(5,6)

❖

type OrderingColumnChoice struct { // Group is a set of equivalent columns, any of which can be used to form a // column in the sort key. After initial construction, Group is immutable. // To update, replace with a different set containing the desired columns. Group opt.ColSet // Descending is true if the sort key column is ordered from highest to // lowest. Otherwise, it's ordered from lowest to highest. Descending bool }

OrderingColumnChoice specifies the set of columns which can form one of the columns in the sort key, as well as the direction of that column (ascending or descending).

❖

func (oc *OrderingColumnChoice) AnyID() opt.ColumnID

AnyID returns the ID of an arbitrary member of the group of equivalent columns.

❖

type Presentation []opt.AliasedColumn

Presentation specifies the naming, membership (including duplicates), and order of result columns that are required of or provided by an operator. While it cannot add unique columns, Presentation can rename, reorder, duplicate and discard columns. If Presentation is not defined, then no particular column presentation is required or provided. For example:

a.y:2 a.x:1 a.y:2 column1:3

❖

func (p Presentation) Any() bool

Any is true if any column presentation is allowed or can be provided.

❖

func (p Presentation) Equals(rhs Presentation) bool

Equals returns true iff this presentation exactly matches the given presentation.

❖

func (p Presentation) String() string

❖

type Provided struct { // Ordering is an ordering that needs to be maintained on the rows produced by // this operator in order to satisfy its required ordering. This is useful for // configuring execution in a distributed setting, where results from multiple // nodes may need to be merged. A best-effort attempt is made to have as few // columns as possible. // // The ordering, in conjunction with the functional dependencies (in the // logical properties), must intersect the required ordering. // // See the documentation for the opt/ordering package for some examples. Ordering opt.Ordering }

Provided physical properties of an operator. An operator might be able to satisfy a required property in multiple ways, and additional information is necessary for execution. For example, the required properties may allow multiple ordering choices; the provided properties would describe the specific ordering that has to be respected during execution.

Provided properties are derived bottom-up (on the lowest cost tree).

Equals returns true if the two sets of provided properties are identical.

❖

type Required struct { // Presentation specifies the naming, membership (including duplicates), // and order of result columns. If Presentation is not defined, then no // particular column presentation is required or provided. Presentation Presentation // Ordering specifies the sort order of result rows. Rows can be sorted by // one or more columns, each of which can be sorted in either ascending or // descending order. If Ordering is not defined, then no particular ordering // is required or provided. Ordering OrderingChoice // LimitHint specifies a "soft limit" to the number of result rows that may // be required of the expression. If requested, an expression will still need // to return all result rows, but it can be optimized based on the assumption // that only the hinted number of rows will be needed. // A LimitHint of 0 indicates "no limit". The LimitHint is an intermediate // float64 representation, and can be converted to an integer number of rows // using math.Ceil. LimitHint float64 }

Required properties are interesting characteristics of an expression that impact its layout, presentation, or location, but not its logical content. Examples include row order, column naming, and data distribution (physical location of data ranges). Physical properties exist outside of the relational algebra, and arise from both the SQL query itself (e.g. the non-relational ORDER BY operator) and by the selection of specific implementations during optimization (e.g. a merge join requires the inputs to be sorted in a particular order).

Required properties are derived top-to-bottom - there is a required physical property on the root, and each expression can require physical properties on one or more of its operands. When an expression is optimized, it is always with respect to a particular set of required physical properties. The goal is to find the lowest cost expression that provides those properties while still remaining logically equivalent.

ColSet returns the set of columns used by any of the physical properties.

Defined is true if any physical property is defined. If none is defined, then this is an instance of MinRequired.

Equals returns true if the two physical properties are identical.

Package physical imports 9 packages (graph) and is imported by 18 packages. Updated 2020-07-03. Refresh now. Tools for package owners.