Package org.apache.calcite.rel.rules

Class LoptOptimizeJoinRule

  • public class LoptOptimizeJoinRule
extends RelOptRule
    Planner rule that implements the heuristic planner for determining optimal join orderings.

    It is triggered by the pattern LogicalProject (MultiJoin).

    • Method Detail

      • findRemovableOuterJoins

        private void findRemovableOuterJoins​(RelMetadataQuery mq,
                                     LoptMultiJoin multiJoin)
        Locates all null generating factors whose outer join can be removed. The outer join can be removed if the join keys corresponding to the null generating factor are unique and no columns are projected from it.
        Parameters:
        multiJoin - join factors being optimized

      • setJoinKey

        private void setJoinKey​(ImmutableBitSet.Builder joinKeys,
                        ImmutableBitSet.Builder otherJoinKeys,
                        int ref1,
                        int ref2,
                        int firstFieldNum,
                        int lastFieldNum,
                        boolean swap)
        Sets a join key if only one of the specified input references corresponds to a specified factor as determined by its field numbers. Also keeps track of the keys from the other factor.
        Parameters:
        joinKeys - join keys to be set if a key is found
        otherJoinKeys - join keys for the other join factor
        ref1 - first input reference
        ref2 - second input reference
        firstFieldNum - first field number of the factor
        lastFieldNum - last field number + 1 of the factor
        swap - if true, check for the desired input reference in the second input reference parameter if the first input reference isn't the correct one

      • findRemovableSelfJoins

        private void findRemovableSelfJoins​(RelMetadataQuery mq,
                                    LoptMultiJoin multiJoin)
        Locates pairs of joins that are self-joins where the join can be removed because the join condition between the two factors is an equality join on unique keys.
        Parameters:
        multiJoin - join factors being optimized

      • getSimpleFactors

        private java.util.Map<java.lang.Integer,​RelOptTable> getSimpleFactors​(RelMetadataQuery mq,
                                                                            LoptMultiJoin multiJoin)
        Retrieves join factors that correspond to simple table references. A simple table reference is a single table reference with no grouping or aggregation.
        Parameters:
        multiJoin - join factors being optimized
        Returns:
        map consisting of the simple factors and the tables they correspond

      • isSelfJoinFilterUnique

        private boolean isSelfJoinFilterUnique​(RelMetadataQuery mq,
                                       LoptMultiJoin multiJoin,
                                       int leftFactor,
                                       int rightFactor,
                                       java.util.List<RexNode> joinFilterList)
        Determines if the equality join filters between two factors that map to the same table consist of unique, identical keys.
        Parameters:
        multiJoin - join factors being optimized
        leftFactor - left factor in the join
        rightFactor - right factor in the join
        joinFilterList - list of join filters between the two factors
        Returns:
        true if the criteria are met

      • findBestOrderings

        private void findBestOrderings​(RelMetadataQuery mq,
                               RelBuilder relBuilder,
                               LoptMultiJoin multiJoin,
                               LoptSemiJoinOptimizer semiJoinOpt,
                               RelOptRuleCall call)
        Generates N optimal join orderings. Each ordering contains each factor as the first factor in the ordering.
        Parameters:
        multiJoin - join factors being optimized
        semiJoinOpt - optimal semijoins for each factor
        call - RelOptRuleCall associated with this rule

      • createTopProject

        private RelNode createTopProject​(RelBuilder relBuilder,
                                 LoptMultiJoin multiJoin,
                                 LoptJoinTree joinTree,
                                 java.util.List<java.lang.String> fieldNames)
        Creates the topmost projection that will sit on top of the selected join ordering. The projection needs to match the original join ordering. Also, places any post-join filters on top of the project.
        Parameters:
        multiJoin - join factors being optimized
        joinTree - selected join ordering
        fieldNames - field names corresponding to the projection expressions
        Returns:
        created projection

      • computeJoinCardinality

        private java.lang.Double computeJoinCardinality​(RelMetadataQuery mq,
                                                LoptMultiJoin multiJoin,
                                                LoptSemiJoinOptimizer semiJoinOpt,
                                                LoptJoinTree joinTree,
                                                java.util.List<RexNode> filters,
                                                int factor)
        Computes the cardinality of the join columns from a particular factor, when that factor is joined with another join tree.
        Parameters:
        multiJoin - join factors being optimized
        semiJoinOpt - optimal semijoins chosen for each factor
        joinTree - the join tree that the factor is being joined with
        filters - possible join filters to select from
        factor - the factor being added
        Returns:
        computed cardinality

      • setFactorJoinKeys

        private void setFactorJoinKeys​(LoptMultiJoin multiJoin,
                               java.util.List<RexNode> filters,
                               ImmutableBitSet joinFactors,
                               int factorStart,
                               int nFields,
                               ImmutableBitSet.Builder joinKeys)
        Locates from a list of filters those that correspond to a particular join tree. Then, for each of those filters, extracts the fields corresponding to a particular factor, setting them in a bitmap.
        Parameters:
        multiJoin - join factors being optimized
        filters - list of join filters
        joinFactors - bitmap containing the factors in a particular join tree
        factorStart - the initial offset of the factor whose join keys will be extracted
        nFields - the number of fields in the factor whose join keys will be extracted
        joinKeys - the bitmap that will be set with the join keys

      • createOrdering

        private LoptJoinTree createOrdering​(RelMetadataQuery mq,
                                    RelBuilder relBuilder,
                                    LoptMultiJoin multiJoin,
                                    LoptSemiJoinOptimizer semiJoinOpt,
                                    int firstFactor)
        Generates a join tree with a specific factor as the first factor in the join tree
        Parameters:
        multiJoin - join factors being optimized
        semiJoinOpt - optimal semijoins for each factor
        firstFactor - first factor in the tree
        Returns:
        constructed join tree or null if it is not possible for firstFactor to appear as the first factor in the join

      • getBestNextFactor

        private int getBestNextFactor​(RelMetadataQuery mq,
                              LoptMultiJoin multiJoin,
                              java.util.BitSet factorsToAdd,
                              java.util.BitSet factorsAdded,
                              LoptSemiJoinOptimizer semiJoinOpt,
                              LoptJoinTree joinTree,
                              java.util.List<RexNode> filtersToAdd)
        Determines the best factor to be added next into a join tree.
        Parameters:
        multiJoin - join factors being optimized
        factorsToAdd - factors to choose from to add next
        factorsAdded - factors that have already been added to the join tree
        semiJoinOpt - optimal semijoins for each factor
        joinTree - join tree constructed thus far
        filtersToAdd - remaining filters that need to be added
        Returns:
        index of the best factor to add next

      • isJoinTree

        private boolean isJoinTree​(RelNode rel)
        Returns whether a RelNode corresponds to a Join that wasn't one of the original MultiJoin input factors.

      • addFactorToTree

        private LoptJoinTree addFactorToTree​(RelMetadataQuery mq,
                                     RelBuilder relBuilder,
                                     LoptMultiJoin multiJoin,
                                     LoptSemiJoinOptimizer semiJoinOpt,
                                     LoptJoinTree joinTree,
                                     int factorToAdd,
                                     java.util.BitSet factorsNeeded,
                                     java.util.List<RexNode> filtersToAdd,
                                     boolean selfJoin)
        Adds a new factor into the current join tree. The factor is either pushed down into one of the subtrees of the join recursively, or it is added to the top of the current tree, whichever yields a better ordering.
        Parameters:
        multiJoin - join factors being optimized
        semiJoinOpt - optimal semijoins for each factor
        joinTree - current join tree
        factorToAdd - new factor to be added
        factorsNeeded - factors that must precede the factor to be added
        filtersToAdd - filters remaining to be added; filters added to the new join tree are removed from the list
        selfJoin - true if the join being created is a self-join that's removable
        Returns:
        optimal join tree with the new factor added if it is possible to add the factor; otherwise, null is returned

      • rowWidthCost

        private int rowWidthCost​(RelNode tree)
        Computes a cost for a join tree based on the row widths of the inputs into the join. Joins where the inputs have the fewest number of columns lower in the tree are better than equivalent joins where the inputs with the larger number of columns are lower in the tree.
        Parameters:
        tree - a tree of RelNodes
        Returns:
        the cost associated with the width of the tree

      • pushDownFactor

        private LoptJoinTree pushDownFactor​(RelMetadataQuery mq,
                                    RelBuilder relBuilder,
                                    LoptMultiJoin multiJoin,
                                    LoptSemiJoinOptimizer semiJoinOpt,
                                    LoptJoinTree joinTree,
                                    int factorToAdd,
                                    java.util.BitSet factorsNeeded,
                                    java.util.List<RexNode> filtersToAdd,
                                    boolean selfJoin)
        Creates a join tree where the new factor is pushed down one of the operands of the current join tree
        Parameters:
        multiJoin - join factors being optimized
        semiJoinOpt - optimal semijoins for each factor
        joinTree - current join tree
        factorToAdd - new factor to be added
        factorsNeeded - factors that must precede the factor to be added
        filtersToAdd - filters remaining to be added; filters that are added to the join tree are removed from the list
        selfJoin - true if the factor being added is part of a removable self-join
        Returns:
        optimal join tree with the new factor pushed down the current join tree if it is possible to do the pushdown; otherwise, null is returned

      • addToTop

        private LoptJoinTree addToTop​(RelMetadataQuery mq,
                              RelBuilder relBuilder,
                              LoptMultiJoin multiJoin,
                              LoptSemiJoinOptimizer semiJoinOpt,
                              LoptJoinTree joinTree,
                              int factorToAdd,
                              java.util.List<RexNode> filtersToAdd,
                              boolean selfJoin)
        Creates a join tree with the new factor added to the top of the tree
        Parameters:
        multiJoin - join factors being optimized
        semiJoinOpt - optimal semijoins for each factor
        joinTree - current join tree
        factorToAdd - new factor to be added
        filtersToAdd - filters remaining to be added; modifies the list to remove filters that can be added to the join tree
        selfJoin - true if the join being created is a self-join that's removable
        Returns:
        new join tree

      • addFilters

        private RexNode addFilters​(LoptMultiJoin multiJoin,
                           LoptJoinTree leftTree,
                           int leftIdx,
                           LoptJoinTree rightTree,
                           java.util.List<RexNode> filtersToAdd,
                           boolean adjust)
        Determines which join filters can be added to the current join tree. Note that the join filter still reflects the original join ordering. It will only be adjusted to reflect the new join ordering if the "adjust" parameter is set to true.
        Parameters:
        multiJoin - join factors being optimized
        leftTree - left subtree of the join tree
        leftIdx - if ≥ 0, only consider filters that reference leftIdx in leftTree; otherwise, consider all filters that reference any factor in leftTree
        rightTree - right subtree of the join tree
        filtersToAdd - remaining join filters that need to be added; those that are added are removed from the list
        adjust - if true, adjust filter to reflect new join ordering
        Returns:
        AND'd expression of the join filters that can be added to the current join tree

      • adjustFilter

        private RexNode adjustFilter​(LoptMultiJoin multiJoin,
                             LoptJoinTree left,
                             LoptJoinTree right,
                             RexNode condition,
                             int factorAdded,
                             java.util.List<java.lang.Integer> origJoinOrder,
                             java.util.List<RelDataTypeField> origFields)
        Adjusts a filter to reflect a newly added factor in the middle of an existing join tree
        Parameters:
        multiJoin - join factors being optimized
        left - left subtree of the join
        right - right subtree of the join
        condition - current join condition
        factorAdded - index corresponding to the newly added factor
        origJoinOrder - original join order, before factor was pushed into the tree
        origFields - fields from the original join before the factor was added
        Returns:
        modified join condition reflecting addition of the new factor

      • remapJoinReferences

        private boolean remapJoinReferences​(LoptMultiJoin multiJoin,
                                    int factor,
                                    java.util.List<java.lang.Integer> newJoinOrder,
                                    int newPos,
                                    int[] adjustments,
                                    int offset,
                                    int newOffset,
                                    boolean alwaysUseDefault)
        Sets an adjustment array based on where column references for a particular factor end up as a result of a new join ordering.

        If the factor is not the right factor in a removable self-join, then it needs to be adjusted as follows:

        • First subtract, based on where the factor was in the original join ordering.
        • Then add on the number of fields in the factors that now precede this factor in the new join ordering.

        If the factor is the right factor in a removable self-join and its column reference can be mapped to the left factor in the self-join, then:

        • First subtract, based on where the column reference is in the new join ordering.
        • Then, add on the number of fields up to the start of the left factor in the self-join in the new join ordering.
        • Then, finally add on the offset of the corresponding column from the left factor.

        Note that this only applies if both factors in the self-join are in the join ordering. If they are, then the left factor always precedes the right factor in the join ordering.

        Parameters:
        multiJoin - join factors being optimized
        factor - the factor whose references are being adjusted
        newJoinOrder - the new join ordering containing the factor
        newPos - the position of the factor in the new join ordering
        adjustments - the adjustments array that will be set
        offset - the starting offset within the original join ordering for the columns of the factor being adjusted
        newOffset - the new starting offset in the new join ordering for the columns of the factor being adjusted
        alwaysUseDefault - always use the default adjustment value regardless of whether the factor is the right factor in a removable self-join
        Returns:
        true if at least one column from the factor requires adjustment

      • createReplacementSemiJoin

        private LoptJoinTree createReplacementSemiJoin​(RelBuilder relBuilder,
                                               LoptMultiJoin multiJoin,
                                               LoptSemiJoinOptimizer semiJoinOpt,
                                               LoptJoinTree factTree,
                                               int dimIdx,
                                               java.util.List<RexNode> filtersToAdd)
        In the event that a dimension table does not need to be joined because of a semijoin, this method creates a join tree that consists of a projection on top of an existing join tree. The existing join tree must contain the fact table in the semijoin that allows the dimension table to be removed.

        The projection created on top of the join tree mimics a join of the fact and dimension tables. In order for the dimension table to have been removed, the only fields referenced from the dimension table are its dimension keys. Therefore, we can replace these dimension fields with the fields corresponding to the semijoin keys from the fact table in the projection.

        Parameters:
        multiJoin - join factors being optimized
        semiJoinOpt - optimal semijoins for each factor
        factTree - existing join tree containing the fact table
        dimIdx - dimension table factor id
        filtersToAdd - filters remaining to be added; filters added to the new join tree are removed from the list
        Returns:
        created join tree or null if the corresponding fact table has not been joined in yet

      • createReplacementJoin

        private LoptJoinTree createReplacementJoin​(RelBuilder relBuilder,
                                           LoptMultiJoin multiJoin,
                                           LoptSemiJoinOptimizer semiJoinOpt,
                                           LoptJoinTree currJoinTree,
                                           int leftIdx,
                                           int factorToAdd,
                                           ImmutableIntList newKeys,
                                           java.lang.Integer[] replacementKeys,
                                           java.util.List<RexNode> filtersToAdd)
        Creates a replacement join, projecting either dummy columns or replacement keys from the factor that doesn't actually need to be joined.
        Parameters:
        multiJoin - join factors being optimized
        semiJoinOpt - optimal semijoins for each factor
        currJoinTree - current join tree being added to
        leftIdx - if ≥ 0, when creating the replacement join, only consider filters that reference leftIdx in currJoinTree; otherwise, consider all filters that reference any factor in currJoinTree
        factorToAdd - new factor whose join can be removed
        newKeys - join keys that need to be replaced
        replacementKeys - the keys that replace the join keys; null if we're removing the null generating factor in an outer join
        filtersToAdd - filters remaining to be added; filters added to the new join tree are removed from the list
        Returns:
        created join tree with an appropriate projection for the factor that can be removed

      • createJoinSubtree

        private LoptJoinTree createJoinSubtree​(RelMetadataQuery mq,
                                       RelBuilder relBuilder,
                                       LoptMultiJoin multiJoin,
                                       LoptJoinTree left,
                                       LoptJoinTree right,
                                       RexNode condition,
                                       JoinRelType joinType,
                                       java.util.List<RexNode> filtersToAdd,
                                       boolean fullAdjust,
                                       boolean selfJoin)
        Creates a LogicalJoin given left and right operands and a join condition. Swaps the operands if beneficial.
        Parameters:
        multiJoin - join factors being optimized
        left - left operand
        right - right operand
        condition - join condition
        joinType - the join type
        fullAdjust - true if the join condition reflects the original join ordering and therefore has not gone through any type of adjustment yet; otherwise, the condition has already been partially adjusted and only needs to be further adjusted if swapping is done
        filtersToAdd - additional filters that may be added on top of the resulting LogicalJoin, if the join is a left or right outer join
        selfJoin - true if the join being created is a self-join that's removable
        Returns:
        created LogicalJoin

      • addAdditionalFilters

        private void addAdditionalFilters​(RelBuilder relBuilder,
                                  LoptMultiJoin multiJoin,
                                  LoptJoinTree left,
                                  LoptJoinTree right,
                                  java.util.List<RexNode> filtersToAdd)
        Determines whether any additional filters are applicable to a join tree. If there are any, creates a filter node on top of the join tree with the additional filters.
        Parameters:
        relBuilder - Builder holding current join tree
        multiJoin - join factors being optimized
        left - left side of join tree
        right - right side of join tree
        filtersToAdd - remaining filters

      • swapInputs

        private boolean swapInputs​(RelMetadataQuery mq,
                           LoptMultiJoin multiJoin,
                           LoptJoinTree left,
                           LoptJoinTree right,
                           boolean selfJoin)
        Swaps the operands to a join, so the smaller input is on the right. Or, if this is a removable self-join, swap so the factor that should be preserved when the self-join is removed is put on the left.
        Parameters:
        multiJoin - join factors being optimized
        left - left side of join tree
        right - right hand side of join tree
        selfJoin - true if the join is a removable self-join
        Returns:
        true if swapping should be done

      • swapFilter

        private RexNode swapFilter​(RexBuilder rexBuilder,
                           LoptMultiJoin multiJoin,
                           LoptJoinTree origLeft,
                           LoptJoinTree origRight,
                           RexNode condition)
        Adjusts a filter to reflect swapping of join inputs
        Parameters:
        rexBuilder - rexBuilder
        multiJoin - join factors being optimized
        origLeft - original LHS of the join tree (before swap)
        origRight - original RHS of the join tree (before swap)
        condition - original join condition
        Returns:
        join condition reflect swap of join inputs

      • needsAdjustment

        private boolean needsAdjustment​(LoptMultiJoin multiJoin,
                                int[] adjustments,
                                LoptJoinTree joinTree,
                                LoptJoinTree otherTree,
                                boolean selfJoin)
        Sets an array indicating how much each factor in a join tree needs to be adjusted to reflect the tree's join ordering
        Parameters:
        multiJoin - join factors being optimized
        adjustments - array to be filled out
        joinTree - join tree
        otherTree - null unless joinTree only represents the left side of the join tree
        selfJoin - true if no adjustments need to be made for self-joins
        Returns:
        true if some adjustment is required; false otherwise

      • isRemovableSelfJoin

        public static boolean isRemovableSelfJoin​(Join joinRel)
        Determines whether a join is a removable self-join. It is if it's an inner join between identical, simple factors and the equality portion of the join condition consists of the same set of unique keys.
        Parameters:
        joinRel - the join
        Returns:
        true if the join is removable

      • areSelfJoinKeysUnique

        private static boolean areSelfJoinKeysUnique​(RelMetadataQuery mq,
                                             RelNode leftRel,
                                             RelNode rightRel,
                                             RexNode joinFilters)
        Determines if the equality portion of a self-join condition is between identical keys that are unique.
        Parameters:
        mq - Metadata query
        leftRel - left side of the join
        rightRel - right side of the join
        joinFilters - the join condition
        Returns:
        true if the equality join keys are the same and unique