cockroach: Index | Files

package ordering

import ""

Package ordering contains operator-specific logic related to orderings - whether ops can provide Required orderings, what orderings do they need to require from their children, etc.

The package provides generic APIs that can be called on any RelExpr, as well as operator-specific APIs in some cases.

Required orderings

A Required ordering is part of the physical properties with respect to which an expression was optimized. It effectively describes a set of orderings, any of which are acceptable. See OrderingChoice for more information on how this set is represented.

An operator can provide a Required ordering if it can guarantee its results respect at least one ordering in the OrderingChoice set, perhaps by requiring specific orderings of its inputs and/or configuring its execution in a specific way. This package implements the logic that decides whether each operator can provide a Required ordering, as well as what Required orderings on its input(s) are necessary.

Provided orderings

In a single-node serial execution model, the Required ordering would be sufficient to configure execution. But in a distributed setting, even if an operator logically has a natural ordering, when multiple instances of that operator are running on multiple nodes we must do some extra work (row comparisons) to maintain their natural orderings when their results merge into a single node. We must know exactly what order must be maintained on the streams (i.e. along which columns we should perform the comparisons).

Consider a Scan operator that is scanning an index on a,b. In query:

SELECT a, b FROM abc ORDER BY a, b

the Scan has Required ordering "+a,+b". Now consider another case where (as part of some more complicated query) we have the same Scan operator but with Required ordering "+b opt(a)"¹, which means that any of "+b", "+b,±a", "±a,+b" are acceptable. Execution would still need to be configured with "+a,+b" because that is the ordering for the rows that are produced², but this information is not available from the Required ordering "+b opt(a)".

¹This could for example happen under a Select with filter "a=1". ²For example, imagine that node A produces rows (1,4), (2,1) and node B produces rows (1,2), (2,3). If these results need to be merged on a single node and we configure execution to "maintain" an ordering of +b, it will cause an incorrect ordering or a runtime error.

To address this issue, this package implements logic to calculate Provided orderings for each expression in the lowest-cost tree. Provided orderings are calculated bottom-up, in conjunction with the Required ordering at the level of each operator.

The Provided ordering is a specific opt.Ordering which describes the ordering produced by the operator, and which intersects the Required OrderingChoice (when the operator's FDs are taken into account). A best-effort attempt is made to keep the Provided ordering as simple as possible, to minimize the comparisons that are necessary to maintain it.


Package Files

doc.go group_by.go limit.go lookup_join.go merge_join.go mutation.go ordering.go project.go row_number.go scan.go select.go sort.go statement.go

func BuildChildRequired Uses

func BuildChildRequired(
    parent memo.RelExpr, required *physical.OrderingChoice, childIdx int,
) physical.OrderingChoice

BuildChildRequired returns the ordering that must be required of its given child in order to satisfy a required ordering. Can only be called if CanProvide is true for the required ordering.

func BuildProvided Uses

func BuildProvided(expr memo.RelExpr, required *physical.OrderingChoice) opt.Ordering

BuildProvided returns a specific ordering that the operator provides (and which must be maintained on the results during distributed execution).

The returned ordering, in conjunction with the operator's functional dependencies, must intersect the required ordering.

A best-effort attempt is made to make the provided orderings as simple as possible (while still satisfying the required ordering).

For example, if we scan an index on x,y,z with required ordering "+y opt(x)", the provided ordering is "+x,+y". If we scan the same index with constraint x=1, the provided ordering is "+y".

This function assumes that the provided orderings have already been set in the children of the expression.

func CanProvide Uses

func CanProvide(expr memo.RelExpr, required *physical.OrderingChoice) bool

CanProvide returns true if the given operator returns rows that can satisfy the given required ordering.

func ScanIsReverse Uses

func ScanIsReverse(scan *memo.ScanExpr, required *physical.OrderingChoice) bool

ScanIsReverse returns true if the scan must be performed in reverse order in order to satisfy the required ordering. If either direction is ok (e.g. no required ordering), reutrns false. The scan must be able to satisfy the required ordering, according to ScanCanProvideOrdering.

func ScanPrivateCanProvide Uses

func ScanPrivateCanProvide(
    md *opt.Metadata, s *memo.ScanPrivate, required *physical.OrderingChoice,
) (ok bool, reverse bool)

ScanPrivateCanProvide returns true if the scan operator returns rows that satisfy the given required ordering; it also returns whether the scan needs to be in reverse order to match the required ordering.

func StreamingGroupingColOrdering Uses

func StreamingGroupingColOrdering(
    g *memo.GroupingPrivate, required *physical.OrderingChoice,
) opt.Ordering

StreamingGroupingColOrdering returns an ordering on grouping columns that is guaranteed on the input of an aggregation operator. This ordering can be used perform a streaming aggregation.

Package ordering imports 8 packages (graph) and is imported by 5 packages. Updated 2019-09-18. Refresh now. Tools for package owners.