cockroach: Index | Files

package physical

import ""


Package Files

ordering_choice.go provided.go required.go


var MinRequired = &Required{}

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

func ParseOrdering Uses

func ParseOrdering(str string) opt.Ordering

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 Uses

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:


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


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 Uses

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|2),+3 opt(5,6)

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

func (*OrderingChoice) Any Uses

func (oc *OrderingChoice) Any() bool

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

func (*OrderingChoice) AppendCol Uses

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 (*OrderingChoice) CanProjectCols Uses

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 (*OrderingChoice) CanSimplify Uses

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 (*OrderingChoice) ColSet Uses

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 (*OrderingChoice) Copy Uses

func (oc *OrderingChoice) Copy() OrderingChoice

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

func (*OrderingChoice) Equals Uses

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 (OrderingChoice) Format Uses

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:

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

func (*OrderingChoice) FromOrdering Uses

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

FromOrdering sets this OrderingChoice to the given opt.Ordering.

func (*OrderingChoice) FromOrderingWithOptCols Uses

func (oc *OrderingChoice) FromOrderingWithOptCols(ord opt.Ordering, optCols opt.ColSet)

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 (*OrderingChoice) Implies Uses

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.


<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 (*OrderingChoice) Intersection Uses

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 (*OrderingChoice) Intersects Uses

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

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

func (*OrderingChoice) MatchesAt Uses

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 (OrderingChoice) PrefixIntersection Uses

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 (*OrderingChoice) ProjectCols Uses

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 (*OrderingChoice) Simplify Uses

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

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.

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

func (OrderingChoice) String Uses

func (oc OrderingChoice) String() string

func (*OrderingChoice) SubsetOfCols Uses

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

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

func (*OrderingChoice) ToOrdering Uses

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 (*OrderingChoice) Truncate Uses

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 Uses

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 (*OrderingColumnChoice) AnyID Uses

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

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

type Presentation Uses

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 (Presentation) Any Uses

func (p Presentation) Any() bool

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

func (Presentation) Equals Uses

func (p Presentation) Equals(rhs Presentation) bool

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

func (Presentation) String Uses

func (p Presentation) String() string

type Provided Uses

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

func (*Provided) Equals Uses

func (p *Provided) Equals(other *Provided) bool

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

func (*Provided) String Uses

func (p *Provided) String() string

type Required Uses

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.

func (*Required) ColSet Uses

func (p *Required) ColSet() opt.ColSet

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

func (*Required) Defined Uses

func (p *Required) Defined() bool

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

func (*Required) Equals Uses

func (p *Required) Equals(rhs *Required) bool

Equals returns true if the two physical properties are identical.

func (*Required) String Uses

func (p *Required) String() string

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