FarragoSortOrder
From Eigenpedia
Contents |
Farrago Sort Order
Overview
Sorting is useful for certain tasks (such as merge join) and is required for other tasks (such as aggregating sorted data and order by). At the same time, sorting large data sets can be expensive, so it should be avoided if possible.
The initial policy for sorting was to request a sort whenever one was needed. For example, one Fennel implementation of aggregation requires group by keys to appear in the first columns of its input. It wants data to be sorted for easy aggregation, so it always sorts the input. (see FennelAggRule.java) This example highlights two problems. First, if data is already sorted, then there would be no need to sort it again. A smart sort could alleviate this problem by optimizing trivial sorts, but it should not be there at all. Second, recognizing the desired sort order could help the optimizer search for efficient data access paths.
Addressing the first problem is somewhat straightforward. It mainly involves recognizing the sort order of any given relation. In general, sort order propagates from bottom up, from child to parent. For example, if a filter's input is sorted, then the filter is likely to preserve the input's sorting. We can calculate a relation's sort order when it is constructed, based on its input's sort order. Whenever a sort is redundant, it can be removed.
Choosing between access paths can be a bit trickier. Suppose we want to implement an aggregate and have two options (1) hash aggregate and (2) sorted aggregate. In general, hash aggregate wins over the combination of sorting and sorted aggregate. However, if there is no need for sorting, then sorted aggregate wins. To choose between the two aggregation schemes, we can passively detect the input sort order.
On the other hand, sort requirements generally flow from top down. A relation may require a sort order of its child. But the child's sort order may result from it's own child, which may eventually result from a decision made far beneath. A more general solution to sorting would allow a relation to identify its desired sort order and the cost of doing without it (for example the cost of hash aggregate vs sorted aggregate).
In perspective, various implementations of input streams may rarely differ in the sort order they produce. One situation in which this arises is in index selection. Since indexes are sorted, we may want to take advantage of their sorting. But due to later joins and transformations, we are often not able to. So smart sorting decisions are a nice to have but are perhaps not so urgent (as far as this author knows).
Current state of sort order
This section discusses work to identify the sort order of relations. (This would help with the first problem discussed in the overview.)
Physical Rels
Initially JVS put sort order in physical (Fennel) Rels (since logical Rels might result in multiple sort orders). The following method was introduced to the FennelRel interface.
public interface FennelRel
{
/**
* @return the sort order produced by this FennelRel, or an empty array if
* the output is not guaranteed to be in any particular order.
*/
public RelFieldCollation [] getCollations();
}
A corresponding rule, FennelRemoveRedundantSortRule, was written in order to cleanup extra sorts.
Logical Rels
Julian broadened sorts to logical (org.eigenbase.rel) Rels. He also extended the notion of sort order to include direction and multiple collations. (For example, a dataset might satisfy three separate sort orders. For its first sort order, the dataset could be descending on c2, then ascending on c3. Other sort orders would be on different columns. Note that for a standard RDBMS, it is usually sufficient to have one collation.)
public interface RelNode
{
/**
* Returns a description of the physical ordering (or orderings) of this
* relational expression.
*
* @post return != null
*/
public List<RelCollation> getCollationList();
}
Table columns could also be described as monotonic (presumably making them a potential collation).
/**
* Supplies a {@link SqlValidator} with the metadata for a table.
*/
public interface SqlValidatorTable
{
/**
* Returns whether a given column is monotonic.
*/
boolean isMonotonic(String columnName);
}
Integration
Each approach (physical and logical) was pursued to an extent, though neither was implemented for all relations. Given that all relations now describe collations, Fennel relations will be moved over to the generalized interface. The following is a catalog of Fennel Rels and their sort behaviors.
- CalcRel:
- output sorting is deduced from inputs (for simple projections)
- FennelAggRel:
- input must be sorted by group count prefix
- todo: output is sorted by group count prefix (perhaps trivially sorted)
- FennelCartesianProduct
- todo: output is sorted by left input, if join remains row-wise
- FennelMergeRel: none (alternates between two input buffers)
- FennelRenameRel:
- todo: output sort order is same as input
- FennelSortRel:
- output is sorted by sort keys
- FennelValuesRel:
- todo: identify trivial sorting
- FtrsIndexScanRel (or FtrsIndexSearchRel)
- output is sorted by projected keys
- FlatFileFennelRel: none
- LcsIndexRel(Intersect | Minus | Merge | Rowscan):
- todo: output is sorted by RID
- LcsIndexSearchRel (or LcsIndexOnlyScanRel or LcsNormalizer)
- sorted by index keys
- LcsSortedAggRel: same as FennelAggRel
- LhxJoinRel: none
- FennelPullCorrelatorRel
- FennelPullCollectRel
- FennelPullUncollectRel
- FennelWindowRel
Better sort optimization
This section discusses the second problem from the overview. In general, sorting presents a challenge for the optimizer.
The Heuristic planner would find it hard to handle sorting perfectly, because it only considers one part of one plan at any time. It might be possible for the top part of a plan (result) to prefer a sorting of the bottom part (inputs). This would help, though different overall strategies might want different sort orders to a different degree.
The Volcano planner does consider multiple plans, though sorting could add a new dimension of complexity. Volcano considers different "equivalence classes" for relations. Within an equivalence class, relations are more or less interchangable. This helps to narrow down the complexity of it's search space. It would be nice to use sort order as a factor to differentiate two equivalence classes. But that would slow down the already burdened volcano.
JVS Notes
John Pham wrote up the summary above; here's my take.
My position has always been that for SQL conformance, sortedness has to be treated as a physical property rather than a logical property. This means
- for a physical expression, we can ask for sortedness metadata (like we do for stats), and the interpretation is clear
- for an arbitrary RelNode, we can ask for sortedness metadata (similar to asking for stats), but there's no guarantee that it's not going to change as the planner continues to apply rules
Julian's position has been that as an extension (particularly relevant to streaming), sortedness could be treated as a logical property, implying that rules would be constrained to preserve it (like datatype).
I have never understood how that is supposed to work with a Volcano-based planner. If you start out with a logical table access (no sortedness), and then recognize that you could replace it with an index-ordered access, how do you expose the potential sortedness without changing the overall sortedness of the equivalence class (going from no sortedness to some)? However, treating sortedness as a physical trait should theoretically work fine with Volcano, although it would make plan space explosion even worse.
With a Hep-based planner, the situation is a little more tractable. There are no parallel worlds, and rules can be written which are allowed to assume that they will only be fired at a point where the planner will be making no more changes to anything underneath them. These rules then become very much planner-dependent (leading to a more brittle optimizer), but that may be acceptable for some use cases. However, as noted by John Pham above, it is difficult to come up with optimal global sort order using Hep, so attempts to take advantage of interesting orderings will be opportunistic at best.
The RelNode.getCollationsList method is currently ambiguous as to interpretation, and we do not have any general law in place to require rules to preserve its result. So it is up to developers of specific optimizer implementations to decide whether a particular combination of planner, ruleset, and rel definitions safely accomplishes their purposes, per HowToWriteAnOptimizer.
Regardless of those issues, there would be no harm in unifying FennelRel.getCollations with RelNode.getCollationList (or eventually phasing out both in favor of a RelMetadataQuery to make it possible to factor out some of the optimizer-specifics to plugins, noted in FarragoRelCleanup and similar to what was halfway done for RelNode.getRows).
--Rchen 14:30, 10 March 2009 (EDT) Two questions:
- How will the sortedness be maintained by the parallel executor?
- --Jvs 23:52, 12 March 2009 (EDT): For horizontal parallelism, the merge ExecStream would need to perform a heap-based ordered merge. For vertical parallelism, there shouldn't be any issues, except in cases where a UNION ALL is being used to concatenate in a particular order (I think this is an issue already for when we construct ordered sets of index search keys).
- Can additional property/requirement be incorporated in the solution, such as one to indicate the "clustering" of data(weaker than sort) for hash aggregation?
- --Jvs 23:52, 12 March 2009 (EDT): At Broadbase we used to call this "clumping" to differentiate it from clustering and GROUP BY. (It was in the BB codebase for a while but we never exposed/maintained it properly.) Yes, certainly anything written about sortedness above applies to optimizing/preserving clumping as well.
