OmniSciDB  5ade3759e0
DynamicFilterJoinRule.java
Go to the documentation of this file.
1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one or more
3  * contributor license agreements. See the NOTICE file distributed with
4  * this work for additional information regarding copyright ownership.
5  * The ASF licenses this file to you under the Apache License, Version 2.0
6  * (the "License"); you may not use this file except in compliance with
7  * the License. You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 
18 package org.apache.calcite.rel.rules;
19 
20 import static org.apache.calcite.plan.RelOptUtil.conjunctions;
21 
22 import com.google.common.collect.ImmutableList;
23 import com.google.common.collect.Sets;
25 
26 import org.apache.calcite.plan.RelOptRuleCall;
27 import org.apache.calcite.plan.RelOptUtil;
28 import org.apache.calcite.rel.RelNode;
29 import org.apache.calcite.rel.core.Filter;
30 import org.apache.calcite.rel.core.Join;
31 import org.apache.calcite.rel.core.JoinRelType;
32 import org.apache.calcite.rel.type.RelDataType;
33 import org.apache.calcite.rex.RexBuilder;
34 import org.apache.calcite.rex.RexNode;
35 import org.apache.calcite.rex.RexUtil;
36 import org.apache.calcite.tools.RelBuilder;
37 import org.apache.calcite.tools.RelBuilderFactory;
38 import org.apache.calcite.util.ImmutableBitSet;
39 
40 import java.util.ArrayList;
41 import java.util.List;
42 
43 public class DynamicFilterJoinRule extends FilterJoinRule.FilterIntoJoinRule {
44  public DynamicFilterJoinRule(boolean smart,
45  RelBuilderFactory relBuilderFactory,
46  Predicate predicate,
47  final List<MapDParserOptions.FilterPushDownInfo> filter_push_down_info) {
48  super(smart, relBuilderFactory, predicate);
49  this.filter_push_down_info = filter_push_down_info;
50  this.smart = smart;
51  }
53  private final boolean smart;
54 
55  @Override
56  public void onMatch(RelOptRuleCall call) {
57  Filter filter = call.rel(0);
58  Join join = call.rel(1);
59  performSelectivePushDown(call, filter, join);
60  }
61 
68  public void performSelectivePushDown(RelOptRuleCall call, Filter filter, Join join) {
69  // Splitting filters into two categories: those that have been previously identified
70  // to be pushed down and those that remain.
71  // It is also assumed that we would only push down filters with singular reference
72  List<RexNode> filtersToBePushedDown = new ArrayList<>();
73  List<RexNode> filtersAboveRemained =
74  filter != null ? conjunctions(filter.getCondition()) : new ArrayList<>();
75 
76  for (RexNode each_filter : conjunctions(filter.getCondition())) {
77  ImmutableBitSet filterRefs = RelOptUtil.InputFinder.bits(each_filter);
78  if (filterRefs.cardinality() == 1) {
79  Integer ref_index = filterRefs.toList().get(0);
81  if (ref_index >= cand.input_start && ref_index < cand.input_next) {
82  filtersToBePushedDown.add(each_filter);
83  filtersAboveRemained.remove(each_filter);
84  }
85  }
86  }
87  }
88 
89  final List<RexNode> joinFilters = RelOptUtil.conjunctions(join.getCondition());
90  final List<RexNode> origJoinFilters = ImmutableList.copyOf(joinFilters);
91 
92  // If there is only the joinRel,
93  // make sure it does not match a cartesian product joinRel
94  // (with "true" condition), otherwise this rule will be applied
95  // again on the new cartesian product joinRel.
96  if (filter == null && joinFilters.isEmpty()) {
97  return;
98  }
99 
100  final List<RexNode> aboveFilters = filtersAboveRemained;
101  final ImmutableList<RexNode> origAboveFilters = ImmutableList.copyOf(aboveFilters);
102 
103  // Simplify Outer Joins
104  JoinRelType joinType = join.getJoinType();
105  if (smart && !origAboveFilters.isEmpty() && join.getJoinType() != JoinRelType.INNER) {
106  joinType = RelOptUtil.simplifyJoin(join, origAboveFilters, joinType);
107  }
108 
109  final List<RexNode> leftFilters = new ArrayList<>();
110  final List<RexNode> rightFilters = new ArrayList<>();
111 
112  // TODO - add logic to derive additional filters. E.g., from
113  // (t1.a = 1 AND t2.a = 2) OR (t1.b = 3 AND t2.b = 4), you can
114  // derive table filters:
115  // (t1.a = 1 OR t1.b = 3)
116  // (t2.a = 2 OR t2.b = 4)
117 
118  // Try to push down above filters. These are typically where clause
119  // filters. They can be pushed down if they are not on the NULL
120  // generating side.
121  boolean filterPushed = false;
122  if (RelOptUtil.classifyFilters(join,
123  filtersToBePushedDown,
124  joinType,
125  !(join instanceof EquiJoin),
126  !joinType.generatesNullsOnLeft(),
127  !joinType.generatesNullsOnRight(),
128  joinFilters,
129  leftFilters,
130  rightFilters)) {
131  filterPushed = true;
132  }
133  // Move join filters up if needed
134  validateJoinFilters(aboveFilters, joinFilters, join, joinType);
135 
136  // If no filter got pushed after validate, reset filterPushed flag
137  if (leftFilters.isEmpty() && rightFilters.isEmpty()
138  && joinFilters.size() == origJoinFilters.size()) {
139  if (Sets.newHashSet(joinFilters).equals(Sets.newHashSet(origJoinFilters))) {
140  filterPushed = false;
141  }
142  }
143 
144  // Try to push down filters in ON clause. A ON clause filter can only be
145  // pushed down if it does not affect the non-matching set, i.e. it is
146  // not on the side which is preserved.
147  if (RelOptUtil.classifyFilters(join,
148  joinFilters,
149  joinType,
150  false,
151  !joinType.generatesNullsOnLeft(),
152  !joinType.generatesNullsOnRight(),
153  joinFilters,
154  leftFilters,
155  rightFilters)) {
156  filterPushed = true;
157  }
158 
159  // if nothing actually got pushed and there is nothing leftover,
160  // then this rule is a no-op
161  if ((!filterPushed && joinType == join.getJoinType())
162  || (joinFilters.isEmpty() && leftFilters.isEmpty()
163  && rightFilters.isEmpty())) {
164  return;
165  }
166 
167  // create Filters on top of the children if any filters were
168  // pushed to them
169  final RexBuilder rexBuilder = join.getCluster().getRexBuilder();
170  final RelBuilder relBuilder = call.builder();
171  final RelNode leftRel = relBuilder.push(join.getLeft()).filter(leftFilters).build();
172  final RelNode rightRel =
173  relBuilder.push(join.getRight()).filter(rightFilters).build();
174 
175  // create the new join node referencing the new children and
176  // containing its new join filters (if there are any)
177  final ImmutableList<RelDataType> fieldTypes =
178  ImmutableList.<RelDataType>builder()
179  .addAll(RelOptUtil.getFieldTypeList(leftRel.getRowType()))
180  .addAll(RelOptUtil.getFieldTypeList(rightRel.getRowType()))
181  .build();
182  final RexNode joinFilter = RexUtil.composeConjunction(
183  rexBuilder, RexUtil.fixUp(rexBuilder, joinFilters, fieldTypes), false);
184 
185  // If nothing actually got pushed and there is nothing leftover,
186  // then this rule is a no-op
187  if (joinFilter.isAlwaysTrue() && leftFilters.isEmpty() && rightFilters.isEmpty()
188  && joinType == join.getJoinType()) {
189  return;
190  }
191 
192  RelNode newJoinRel = join.copy(join.getTraitSet(),
193  joinFilter,
194  leftRel,
195  rightRel,
196  joinType,
197  join.isSemiJoinDone());
198  call.getPlanner().onCopy(join, newJoinRel);
199  if (!leftFilters.isEmpty()) {
200  call.getPlanner().onCopy(filter, leftRel);
201  }
202  if (!rightFilters.isEmpty()) {
203  call.getPlanner().onCopy(filter, rightRel);
204  }
205 
206  relBuilder.push(newJoinRel);
207 
208  // Create a project on top of the join if some of the columns have become
209  // NOT NULL due to the join-type getting stricter.
210  relBuilder.convert(join.getRowType(), false);
211 
212  // create a FilterRel on top of the join if needed
213  relBuilder.filter(RexUtil.fixUp(rexBuilder,
214  aboveFilters,
215  RelOptUtil.getFieldTypeList(relBuilder.peek().getRowType())));
216 
217  call.transformTo(relBuilder.build());
218  }
219 }
final List< MapDParserOptions.FilterPushDownInfo > filter_push_down_info
std::string join(T const &container, std::string const &delim)
DynamicFilterJoinRule(boolean smart, RelBuilderFactory relBuilderFactory, Predicate predicate, final List< MapDParserOptions.FilterPushDownInfo > filter_push_down_info)
void performSelectivePushDown(RelOptRuleCall call, Filter filter, Join join)