opt: do a better job of optimizing recursive ctes #89954

DrewKimball · 2022-10-13T22:26:29Z

#85597 added support for variable-inequality lookup joins in an attempt to improve performance of recursive CTE expressions that are used to model loose-index-scans. However, the optimizer still isn't very smart about taking advantage of the execution changes. For example, the recursive CTE from this blog post executes with a cross join when it should use an ordered lookup join with a limit. This issue tracks items that should be improved in order to ensure good recursive CTE performance without the need for query rewrites.

Currently, we only plan a variable-inequality lookup join in the case when the input has one row or there is a join hint. This is because the joinreader logic does not fully de-duplicate lookup spans for variable inequalities, and so performance can be worse than performing a cross join in some cases. We should improve the de-duplication and/or update the cost model so that the 1-row input restriction can be safely removed.
opt: improve WithScan properties for recursive CTEs #90725 We do a poor job of calculating recursive CTE properties. We should be able to tell that each iteration only produces one row if both the recursive and anchor branches have a LIMIT 1.
We should be able to infer useful properties other than limits for recursive CTEs, like keys and orderings.
Our ability to predict statistics for recursive CTEs is very poor. We should be able to recognize common patterns (e.g. loose-index-scans) and make predictions based off of that.
We already have a rule that allows planning separate joins for each disjunction in a matched join's ON condition SplitDisjunctionOfJoinTerms. However, this rule does not match when one of the inputs is a WithScan. We should be able to fire this rule with a WithScan as long as one of the inputs has a canonical scan that can potentially be used for lookups.
We should review all rules that match Scan operators and consider whether they should be extended to work with WithScan operators as well.

Jira issue: CRDB-20511

The text was updated successfully, but these errors were encountered:

This commit adds an optimization rule `ApplyLimitToRecursiveCTEScan` that matches recursive CTE expressions that have bounded cardinality in both the anchor and recursive branches, then updates the properties of the recursive scan to reflect this limit. This can allow other rules to fire in the recursive branch. Informs cockroachdb#89954 Release note: None

…e cte It is common to see cases where we are unable to infer that the recursive branch of a recursive CTE returns a limited number of rows because the properties of the recursive branch depend on the properties of the recursive `WithScan`. This commit adds a new rule called `TryAddLimitToRecursiveBranch` that matches cases where the anchor branch has bounded cardinality but not the recursive branch. It then traverses the recursive branch until it finds a matching `WithScan`, and checks whether applying the limit from the anchor branch to the `WithScan` would cause the recursive branch to have the same upper cardinality bound. If this is the case, `TryAddLimitToRecursiveBranch` re-optimizes the recursive branch with a limit added on top of it. Doing so can allow other rules to fire - for example, `ApplyLimitToRecursiveCTEScan`. Informs cockroachdb#89954 Release note (performance improvement): The optimizer can now better calculate the properties of recursive CTE expressions in the presence of a `LIMIT`.