[jira] [Commented] (CALCITE-2624) Add a rule to copy a sort below a binary operator over the left or right input
[ https://issues.apache.org/jira/browse/CALCITE-2624?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16649089#comment-16649089 ] Julian Hyde commented on CALCITE-2624: -- Yeah, I agree it's well worth seeing how far we can generalize existing rules to new use cases. BiRel is unfortunately rather useless, except for a place to put common code, because the only useful sub-classes are members of the Join family. > Add a rule to copy a sort below a binary operator over the left or right input > -- > > Key: CALCITE-2624 > URL: https://issues.apache.org/jira/browse/CALCITE-2624 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.17.0 >Reporter: Stamatis Zampetakis >Assignee: Julian Hyde >Priority: Major > Fix For: 1.18.0 > > > Currently, the only rule that allows a sort to traverse a binary operator is > the SortJoinTransposeRule. The rule was introduced mainly to push limits in > the case of left and right outer joins (see CALCITE-831). > I assume that the main reason that we don't have more rules is that sorts > with limits and offsets cannot be pushed safely below many binary operators. > However, in many cases, it is possible and beneficial for optimization > purposes to just push the sort (without the limit and offset) below the > binary operator. Since we do not know in advance if the binary operator > preserves the sort we cannot remove (that is why I am saying copy and not > transpose) the sort operator on top of the binary operator. The latter is not > really a problem since the SortRemoveRule can detect such cases and remove > the sort if it is redundant. > A few concrete examples where this optimization makes sense are outlined > below: > * allow the sort to be later absorbed by an index scan and disappear from > the plan (Sort + Tablescan => IndexScan with RelCollation); > * allow operators that require sorted inputs to be exploited more easily > (e.g., merge join); > * allow the sort to be performed on a possibly smaller result (assuming that > the physical binary operator that is going to be used preserves the order of > left/right input and the top sort operator can be removed entirely). > I propose to add a new rule (e.g., SortCopyBelowBiRelRule, > SortBiRelCopyBelowRule, SortBiRelTransposeRule) which allows a sort to be > copied to the left or right of a BiRel operator (excluding the limit and > offset attributes) if the respective input is not already sorted. For my use > case, it would suffice to apply the rule only on joins and correlates but I > don't see why not making it a bit more general from the beginning. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2624) Add a rule to copy a sort below a binary operator over the left or right input
[ https://issues.apache.org/jira/browse/CALCITE-2624?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16648979#comment-16648979 ] Stamatis Zampetakis commented on CALCITE-2624: -- I suppose the end user feature for our use case would be something like the following. "Allow ORDER BY clause to be answered by an index". But I am not sure if that makes a better summary for the JIRA. We already need it for all types of Correlate, and Join, so thats why I thought to go directly for BiRel. Minus and Union are not extending BiRel but SetOp. > Add a rule to copy a sort below a binary operator over the left or right input > -- > > Key: CALCITE-2624 > URL: https://issues.apache.org/jira/browse/CALCITE-2624 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.17.0 >Reporter: Stamatis Zampetakis >Assignee: Julian Hyde >Priority: Major > Fix For: 1.18.0 > > > Currently, the only rule that allows a sort to traverse a binary operator is > the SortJoinTransposeRule. The rule was introduced mainly to push limits in > the case of left and right outer joins (see CALCITE-831). > I assume that the main reason that we don't have more rules is that sorts > with limits and offsets cannot be pushed safely below many binary operators. > However, in many cases, it is possible and beneficial for optimization > purposes to just push the sort (without the limit and offset) below the > binary operator. Since we do not know in advance if the binary operator > preserves the sort we cannot remove (that is why I am saying copy and not > transpose) the sort operator on top of the binary operator. The latter is not > really a problem since the SortRemoveRule can detect such cases and remove > the sort if it is redundant. > A few concrete examples where this optimization makes sense are outlined > below: > * allow the sort to be later absorbed by an index scan and disappear from > the plan (Sort + Tablescan => IndexScan with RelCollation); > * allow operators that require sorted inputs to be exploited more easily > (e.g., merge join); > * allow the sort to be performed on a possibly smaller result (assuming that > the physical binary operator that is going to be used preserves the order of > left/right input and the top sort operator can be removed entirely). > I propose to add a new rule (e.g., SortCopyBelowBiRelRule, > SortBiRelCopyBelowRule, SortBiRelTransposeRule) which allows a sort to be > copied to the left or right of a BiRel operator (excluding the limit and > offset attributes) if the respective input is not already sorted. For my use > case, it would suffice to apply the rule only on joins and correlates but I > don't see why not making it a bit more general from the beginning. -- This message was sent by Atlassian JIRA (v7.6.3#76005)
[jira] [Commented] (CALCITE-2624) Add a rule to copy a sort below a binary operator over the left or right input
[ https://issues.apache.org/jira/browse/CALCITE-2624?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16648066#comment-16648066 ] Julian Hyde commented on CALCITE-2624: -- Slight difference in tactics: I’d focus on the concrete rules, then perhaps abstract the code into a base class if applicable. It’s better to write JIRA cases in terms of features that are useful to end users. It might apply to MInus, probably wouldn’t apply to Union > Add a rule to copy a sort below a binary operator over the left or right input > -- > > Key: CALCITE-2624 > URL: https://issues.apache.org/jira/browse/CALCITE-2624 > Project: Calcite > Issue Type: Improvement > Components: core >Affects Versions: 1.17.0 >Reporter: Stamatis Zampetakis >Assignee: Julian Hyde >Priority: Major > Fix For: 1.18.0 > > > Currently, the only rule that allows a sort to traverse a binary operator is > the SortJoinTransposeRule. The rule was introduced mainly to push limits in > the case of left and right outer joins (see CALCITE-831). > I assume that the main reason that we don't have more rules is that sorts > with limits and offsets cannot be pushed safely below many binary operators. > However, in many cases, it is possible and beneficial for optimization > purposes to just push the sort (without the limit and offset) below the > binary operator. Since we do not know in advance if the binary operator > preserves the sort we cannot remove (that is why I am saying copy and not > transpose) the sort operator on top of the binary operator. The latter is not > really a problem since the SortRemoveRule can detect such cases and remove > the sort if it is redundant. > A few concrete examples where this optimization makes sense are outlined > below: > * allow the sort to be later absorbed by an index scan and disappear from > the plan (Sort + Tablescan => IndexScan with RelCollation); > * allow operators that require sorted inputs to be exploited more easily > (e.g., merge join); > * allow the sort to be performed on a possibly smaller result (assuming that > the physical binary operator that is going to be used preserves the order of > left/right input and the top sort operator can be removed entirely). > I propose to add a new rule (e.g., SortCopyBelowBiRelRule, > SortBiRelCopyBelowRule, SortBiRelTransposeRule) which allows a sort to be > copied to the left or right of a BiRel operator (excluding the limit and > offset attributes) if the respective input is not already sorted. For my use > case, it would suffice to apply the rule only on joins and correlates but I > don't see why not making it a bit more general from the beginning. -- This message was sent by Atlassian JIRA (v7.6.3#76005)