calcite-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Stamatis Zampetakis (JIRA)" <>
Subject [jira] [Created] (CALCITE-2624) Add a rule to copy a sort below a binary operator over the left or right input
Date Fri, 12 Oct 2018 08:50:00 GMT
Stamatis Zampetakis created CALCITE-2624:

             Summary: Add a rule to copy a sort below a binary operator over the left or right
                 Key: CALCITE-2624
             Project: Calcite
          Issue Type: Improvement
          Components: core
    Affects Versions: 1.17.0
            Reporter: Stamatis Zampetakis
            Assignee: Julian Hyde
             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

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

View raw message