plan_ordering.go

// Copyright 2017 The Cockroach Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
// implied. See the License for the specific language governing
// permissions and limitations under the License.

package sql

// planOrdering describes known ordering information for the rows generated by
// this node. The ordering information includes columns the output is ordered
// by and columns for which we know all rows have the same value. See
// orderingInfo for more details.
//
// Stable after optimizePlan() (or makePlan).
// Available after newPlan(), but may change on intermediate plan
// nodes during optimizePlan() due to index selection.
func planOrdering(plan planNode) orderingInfo {
	switch n := plan.(type) {
	case *explainPlanNode:
		return planOrdering(n.results)
	case *distinctNode:
		return planOrdering(n.plan)
	case *filterNode:
		return planOrdering(n.source.plan)
	case *limitNode:
		return planOrdering(n.plan)
	case *indexJoinNode:
		return planOrdering(n.index)

	case *groupNode:
		// TODO(dt,knz,radu): aggregate buckets can be ordered if the source is
		// ordered on the aggregating column already.
	case *windowNode:
		// TODO: window partitions can be ordered if the source is ordered
		// appropriately.
	case *joinNode:
		return n.ordering
	case *unionNode:
		// TODO(knz): this can be ordered if the source is ordered already.
	case *insertNode:
		// TODO(knz): RETURNING is ordered by the PK.
	case *deleteNode:
		// TODO(knz): RETURNING is ordered by the PK.
	case *updateNode:
		// TODO(knz): RETURNING is ordered by the PK.

	case *scanNode:
		return n.ordering
	case *ordinalityNode:
		return n.ordering
	case *renderNode:
		return n.ordering
	case *sortNode:
		return sortOrdering(n)
	}

	// Every other node simply has no ordering guarantees on its output
	// rows.

	return orderingInfo{}
}

func sortOrdering(n *sortNode) orderingInfo {
	underlying := planOrdering(n.plan)

	var ord orderingInfo
	if n.needSort {
		// We will sort and can guarantee the desired ordering.
		ord.ordering = make([]orderingColumnGroup, 0, len(n.ordering))
		for _, o := range n.ordering {
			// Skip any constant columns (we preserve them below).
			if !underlying.constantCols.Contains(uint32(o.ColIdx)) {
				ord.addColumn(o.ColIdx, o.Direction)
			}
		}
		// Preserve constant columns.
		ord.constantCols = underlying.constantCols.Copy()
	} else {
		// If we aren't sorting, the underlying plan's ordering can be more specific
		// than the sortNode's ordering, so we want to use that. E.g:
		//   CREATE INDEX foo ON t (a, b);
		//   SELECT a, b, c FROM t ORDER BY a;
		// We want to use (a, b) instead of just (a).
		ord = underlying.copy()
	}

	// Remove constant columns not in the output.
	for col, ok := ord.constantCols.Next(uint32(len(n.columns))); ok; col, ok = ord.constantCols.Next(col) {
		ord.constantCols.Remove(col)
	}

	// The sortNode can project away columns, for queries like:
	//   SELECT k FROM kv ORDER BY v).
	// Remove all the columns after the first one that's not present in
	// the result columns.
	for i, group := range ord.ordering {
		// Check if the group has a column that is not present.
		if missingCol, ok := group.cols.Next(uint32(len(n.columns))); ok {
			if firstCol, ok := group.cols.Next(0); ok && firstCol < uint32(len(n.columns)) {
				// The group has at least a column that is present. Remove the columns
				// that are not present.
				for ok := true; ok; missingCol, ok = group.cols.Next(missingCol + 1) {
					group.cols.Remove(missingCol)
				}
			} else {
				// None of the columns in the group are present. We need to break the
				// orderingInfo here.
				// If something is ordered by columns A, then B, then C, if I remove
				// column B I can't say it's ordered by columns A, then C.
				// Example:
				// A | B | C          A | C
				// ---------          -----
				// 1 | 1 | 2   --->   1 | 2
				// 1 | 2 | 1          1 | 1
				// 1 | 2 | 3          1 | 3
				ord.ordering = ord.ordering[:i]
				ord.isKey = false
				break
			}
		}
	}
	return ord
}