You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by GitBox <gi...@apache.org> on 2020/04/25 08:50:52 UTC
[GitHub] [druid] maytasm opened a new pull request #9773: [WIP] Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
maytasm opened a new pull request #9773:
URL: https://github.com/apache/druid/pull/9773
Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
### Description
This PR has:
- [ ] been self-reviewed.
- [ ] using the [concurrency checklist](https://github.com/apache/druid/blob/master/dev/code-review/concurrency.md) (Remove this item if the PR doesn't have any relation to concurrency.)
- [ ] added documentation for new or modified features or behaviors.
- [ ] added Javadocs for most classes and all non-trivial methods. Linked related entities via Javadoc links.
- [ ] added or updated version, license, or notice information in [licenses.yaml](https://github.com/apache/druid/blob/master/licenses.yaml)
- [ ] added comments explaining the "why" and the intent of the code wherever would not be obvious for an unfamiliar reader.
- [ ] added unit tests or modified existing tests to cover new code paths.
- [ ] added integration tests.
- [ ] been tested in a test Druid cluster.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r425448336
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rule/DruidJoinRule.java
##########
@@ -193,9 +193,16 @@ static boolean canHandleCondition(final RexNode condition, final RelDataType lef
final int numLeftFields = leftRowType.getFieldCount();
for (RexNode subCondition : subConditions) {
- if (subCondition.isA(SqlKind.LITERAL)) {
- // Literals are always OK.
- literalSubConditions.add((RexLiteral) subCondition);
+ if (RexUtil.isLiteral(subCondition, true)) {
+ if (subCondition instanceof RexCall) {
+ // This is CAST(literal) which is always OK.
+ // We know that this is CASE(literal) as it pass the check from RexUtil.isLiteral
Review comment:
Done
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] gianm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
gianm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r421173321
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rel/DruidJoinQueryRel.java
##########
@@ -293,23 +293,17 @@ protected RelDataType deriveRowType()
@Override
public RelOptCost computeSelfCost(final RelOptPlanner planner, final RelMetadataQuery mq)
{
- double cost;
-
- if (computeLeftRequiresSubquery(getSomeDruidChild(left))) {
- cost = CostEstimates.COST_JOIN_SUBQUERY;
- } else {
- cost = partialQuery.estimateCost();
- }
-
- if (computeRightRequiresSubquery(getSomeDruidChild(right))) {
- cost += CostEstimates.COST_JOIN_SUBQUERY;
- }
-
+ double cost = partialQuery.estimateCost();
if (joinRel.getCondition().isA(SqlKind.LITERAL) && !joinRel.getCondition().isAlwaysFalse()) {
cost += CostEstimates.COST_JOIN_CROSS;
}
-
- return planner.getCostFactory().makeCost(cost, 0, 0);
+ // This is to cancel out the MULTIPLIER_FILTER (value=0.1) from partialQuery.estimateCost() to discourage
+ // filter push down if pushing down the filter makes this DruidJoinQueryRel not a scan or mapping.
+ // This will leave the filter at the topmost DruidJoinQueryRel (due to the order of applying/popping rules).
Review comment:
After thinking about this for a while, I'm thinking that a less-sketchy method would be to remove the rules that push filters past joins. It's similar to how #9648 (temporarily) addressed issues related to bad join orderings by just nuking the rules that reordered joins. It makes sense since we don't have a good way to guide the optimizer at this point.
We'll want to reintroduce these rules when we've made improvements to the cost estimators that allow all these rules to operate at their full power.
In this case, I think the relevant rules are `FilterJoinRule.FILTER_ON_JOIN` and `FilterJoinRule.JOIN`. I'm not sure if we can actually fully disable them, though. We might need parts of them. So we might need to copy them and dumb them down a bit? I'm not sure if this will be necessary, but it's an option if necessary.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r421917947
##########
File path: sql/src/test/java/org/apache/druid/sql/calcite/CalciteQueryTest.java
##########
@@ -8346,6 +8346,166 @@ public void testLeftJoinTwoLookupsUsingJoinOperator() throws Exception
);
}
+ @Test
+ public void testInnerJoinTableLookupLookupWithFilterWithOuterLimit() throws Exception
+ {
+ testQuery(
+ "SELECT dim1\n"
+ + "FROM foo\n"
+ + "INNER JOIN lookup.lookyloo l ON foo.dim2 = l.k\n"
+ + "INNER JOIN lookup.lookyloo l2 ON foo.dim2 = l2.k\n"
+ + "WHERE l.v = 'xa'\n"
+ + "LIMIT 100\n",
+ ImmutableList.of(
+ newScanQueryBuilder()
+ .dataSource(
+ join(
+ join(
+ new TableDataSource(CalciteTests.DATASOURCE1),
+ new LookupDataSource("lookyloo"),
+ "j0.",
+ equalsCondition(DruidExpression.fromColumn("dim2"), DruidExpression.fromColumn("j0.k")),
+ JoinType.INNER
+ ),
+ new LookupDataSource("lookyloo"),
+ "_j0.",
+ equalsCondition(DruidExpression.fromColumn("dim2"), DruidExpression.fromColumn("_j0.k")),
+ JoinType.INNER
+ )
+ )
+ .intervals(querySegmentSpec(Filtration.eternity()))
+ .limit(100)
+ .filters(selector("j0.v", "xa", null))
+ .columns("dim1")
+ .context(QUERY_CONTEXT_DEFAULT)
+ .build()
+ ),
+ ImmutableList.of(
+ new Object[]{""},
+ new Object[]{"1"}
+ )
+ );
+ }
+
+ @Test
+ public void testInnerJoinTableLookupLookupWithFilterWithoutLimit() throws Exception
+ {
+ testQuery(
Review comment:
Done
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rel/DruidQueryRel.java
##########
@@ -183,6 +183,10 @@ public RelWriter explainTerms(final RelWriter pw)
@Override
public RelOptCost computeSelfCost(final RelOptPlanner planner, final RelMetadataQuery mq)
{
- return planner.getCostFactory().makeCost(partialQuery.estimateCost(), 0, 0);
+ double cost = partialQuery.estimateCost();
+ double multiplier = DruidRels.isScanOrMapping(this, true)
Review comment:
No longer need this.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on pull request #9773: [WIP] Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on pull request #9773:
URL: https://github.com/apache/druid/pull/9773#issuecomment-622535442
@gianm I found something that works for all the new test cases but I am not exactly sure how it works. If we ONLY boost the cost for rels that must always query on DruidQueryRel and NOT DruidJoinQueryRel. Then we also exclude/remove the where filter multiplier (MULTIPLIER_FILTER) for DruidJoinQueryRel. Hence, if we have DruidJoinQueryRel, then the the where filter will not affect the cost of DruidJoinQueryRel. I found that the planner will always (at least for the test cases I added) put the where filter on the topmost/outermost DruidJoinQueryRel. I am not sure how the planner decides this. the cummulative cost will be exactly the same between putting the where filter on the topmost/outermost DruidJoinQueryRel vs. on the inner DruidJoinQueryRel (since where filter does not affect the cost), how does the planner choose which to put the where filter on?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r425454252
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rule/FilterJoinExcludePushToChildRule.java
##########
@@ -0,0 +1,280 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.sql.calcite.rule;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Sets;
+import org.apache.calcite.adapter.enumerable.EnumerableConvention;
+import org.apache.calcite.plan.RelOptRule;
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelOptRuleOperand;
+import org.apache.calcite.plan.RelOptUtil;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Filter;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.core.RelFactories;
+import org.apache.calcite.rel.rules.FilterJoinRule;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexCall;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexUtil;
+import org.apache.calcite.tools.RelBuilder;
+import org.apache.calcite.tools.RelBuilderFactory;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public abstract class FilterJoinExcludePushToChildRule extends FilterJoinRule
Review comment:
Done
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on pull request #9773: [WIP] Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on pull request #9773:
URL: https://github.com/apache/druid/pull/9773#issuecomment-622523625
> 1. Figure out a way to compute costs that encourages the SQL planner to push projects and filters above joins consistently.
@gianm Thinking of different ideas....in addition to what we already have now... is it possible to add a new RelOptRule that when see two DruidJoinQueryRel, will push filter to the topmost DruidJoinQueryRel if the filter is on the inner DruidJoinQueryRel?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] gianm commented on pull request #9773: [WIP] Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
gianm commented on pull request #9773:
URL: https://github.com/apache/druid/pull/9773#issuecomment-622457445
By the way, let me discuss for a bit what this cost-estimation stuff is trying to accomplish, in case that's helpful.
In Druid native queries, in order for a Join tree (multiple stacked joins) to execute without subqueries, it must be left-heavy and the bottom-leftmost must be a table. We are trying to encourage the SQL planner to put things in that form whenever possible. "Must be left-heavy" means that the right child should be a regular datasource, not a join. The left child could potentially be a join."Bottom-leftmost must be a table" means that if you follow the chain of joins down the left-child pointers, the final, leaf regular datasource must be a table.
What if we need to apply some filters or projections to that table? In Druid native queries, we do that by adding `filter` or `virtualColumns` in the query that references the outermost join datasource.
But it is important, for performance, to push filters and projections down past a join when a query is executed. We do this at the native query level: if you have a filter or virtual column on a join that could apply to the base table, we apply it to the base table.
So we want the SQL planner to generate queries where projects and filters are completely above the join, and we'll push them down later, at the native query execution stage.
On the other hand, what if the SQL planner generates projects and filters below a join? That's bad, because the only way the SQL-to-native translation can handle that structure is by generating a subquery. This is bad because subqueries require transferring the full results of the subquery to the Broker.
So I think broadly we have to do either one of two things.
1. Figure out a way to compute costs that encourages the SQL planner to push projects and filters above joins consistently.
2. Extend the native query language so you can specify a filter or virtualColumn at the level of a join datasource, so even if the SQL planner generates a rel tree with a filter randomly in the middle, the SQL-to-native translation can attach the filter to the join datasource and does not need to generate a subquery.
IMO (1) is nice since it keeps the native language simple. But if it's not workable, we might need to go with (2).
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm edited a comment on pull request #9773: [WIP] Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm edited a comment on pull request #9773:
URL: https://github.com/apache/druid/pull/9773#issuecomment-622521552
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on pull request #9773: [WIP] Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on pull request #9773:
URL: https://github.com/apache/druid/pull/9773#issuecomment-622521552
> > A problem with this solution is that it does not guarantee to push the filter to the topmost DruidJoinQueryRel. This problem is showed in CalciteQueryTest#testInnerJoinTableLookupLookupWithFilterWithoutLimitWithAllColumns where the filter is on the inner DruidJoinQueryRel instead of the other DruidJoinQueryRel.
>
> The plan in your current patch (cafca03) looks OK to me. It's exactly what we want. Do you have a different case that illustrates the issue you're talking about?
Sorry for the confusion. CalciteQueryTest#testInnerJoinTableLookupLookupWithFilterWithoutLimitWithAllColumns has @Ignore on it because it DOES NOT generate the plan in my current patch (cafca03) and hence will fail. The plan it generates is similar to the bad plan in the description of this PR.
```
2020-05-01T09:06:01,490 INFO [main] org.apache.druid.sql.calcite.util.QueryLogHook - Issued query: {
"queryType" : "scan",
"dataSource" : {
"type" : "join",
"left" : {
"type" : "query",
"query" : {
"queryType" : "scan",
"dataSource" : {
"type" : "join",
"left" : {
"type" : "table",
"name" : "foo"
},
"right" : {
"type" : "lookup",
"lookup" : "lookyloo"
},
"rightPrefix" : "j0.",
"condition" : "(\"dim2\" == \"j0.k\")",
"joinType" : "INNER"
},
"intervals" : {
"type" : "intervals",
"intervals" : [ "-146136543-09-08T08:23:32.096Z/146140482-04-24T15:36:27.903Z" ]
},
"virtualColumns" : [ ],
"resultFormat" : "compactedList",
"batchSize" : 20480,
"limit" : 9223372036854775807,
"order" : "none",
"filter" : {
"type" : "selector",
"dimension" : "j0.v",
"value" : "xa",
"extractionFn" : null
},
"columns" : [ "__time", "cnt", "dim1", "dim2", "dim3", "j0.k", "j0.v", "m1", "m2", "unique_dim1" ],
"legacy" : false,
"context" : {
"defaultTimeout" : 300000,
"maxScatterGatherBytes" : 9223372036854775807,
"sqlCurrentTimestamp" : "2000-01-01T00:00:00Z",
"sqlQueryId" : "dummy",
"vectorize" : "false"
},
"descending" : false,
"granularity" : {
"type" : "all"
}
}
},
"right" : {
"type" : "lookup",
"lookup" : "lookyloo"
},
"rightPrefix" : "_j0.",
"condition" : "(\"dim2\" == \"_j0.k\")",
"joinType" : "INNER"
},
"intervals" : {
"type" : "intervals",
"intervals" : [ "-146136543-09-08T08:23:32.096Z/146140482-04-24T15:36:27.903Z" ]
},
"virtualColumns" : [ ],
"resultFormat" : "compactedList",
"batchSize" : 20480,
"limit" : 9223372036854775807,
"order" : "none",
"filter" : null,
"columns" : [ "__time", "cnt", "dim1", "dim2", "dim3", "m1", "m2", "unique_dim1" ],
"legacy" : false,
"context" : {
"defaultTimeout" : 300000,
"maxScatterGatherBytes" : 9223372036854775807,
"sqlCurrentTimestamp" : "2000-01-01T00:00:00Z",
"sqlQueryId" : "dummy",
"vectorize" : "false"
},
"descending" : false,
"granularity" : {
"type" : "all"
}
}
```
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] gianm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
gianm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r421051659
##########
File path: sql/src/test/java/org/apache/druid/sql/calcite/CalciteQueryTest.java
##########
@@ -8346,6 +8346,166 @@ public void testLeftJoinTwoLookupsUsingJoinOperator() throws Exception
);
}
+ @Test
+ public void testInnerJoinTableLookupLookupWithFilterWithOuterLimit() throws Exception
+ {
+ testQuery(
+ "SELECT dim1\n"
+ + "FROM foo\n"
+ + "INNER JOIN lookup.lookyloo l ON foo.dim2 = l.k\n"
+ + "INNER JOIN lookup.lookyloo l2 ON foo.dim2 = l2.k\n"
+ + "WHERE l.v = 'xa'\n"
+ + "LIMIT 100\n",
+ ImmutableList.of(
+ newScanQueryBuilder()
+ .dataSource(
+ join(
+ join(
+ new TableDataSource(CalciteTests.DATASOURCE1),
+ new LookupDataSource("lookyloo"),
+ "j0.",
+ equalsCondition(DruidExpression.fromColumn("dim2"), DruidExpression.fromColumn("j0.k")),
+ JoinType.INNER
+ ),
+ new LookupDataSource("lookyloo"),
+ "_j0.",
+ equalsCondition(DruidExpression.fromColumn("dim2"), DruidExpression.fromColumn("_j0.k")),
+ JoinType.INNER
+ )
+ )
+ .intervals(querySegmentSpec(Filtration.eternity()))
+ .limit(100)
+ .filters(selector("j0.v", "xa", null))
+ .columns("dim1")
+ .context(QUERY_CONTEXT_DEFAULT)
+ .build()
+ ),
+ ImmutableList.of(
+ new Object[]{""},
+ new Object[]{"1"}
+ )
+ );
+ }
+
+ @Test
+ public void testInnerJoinTableLookupLookupWithFilterWithoutLimit() throws Exception
+ {
+ testQuery(
Review comment:
Could you also add a super-long version of this (just in case)? Such as:
```java
"SELECT dim1\n"
+ "FROM foo\n"
+ "INNER JOIN lookup.lookyloo l ON foo.dim2 = l.k\n"
+ "INNER JOIN lookup.lookyloo l2 ON foo.dim2 = l2.k\n"
+ "INNER JOIN lookup.lookyloo l3 ON foo.dim2 = l3.k\n"
+ "INNER JOIN lookup.lookyloo l4 ON foo.dim2 = l4.k\n"
+ "INNER JOIN lookup.lookyloo l5 ON foo.dim2 = l5.k\n"
+ "INNER JOIN lookup.lookyloo l6 ON foo.dim2 = l6.k\n"
+ "INNER JOIN lookup.lookyloo l7 ON foo.dim2 = l7.k\n"
+ "INNER JOIN lookup.lookyloo l8 ON foo.dim2 = l8.k\n"
+ "INNER JOIN lookup.lookyloo l9 ON foo.dim2 = l9.k\n"
+ "INNER JOIN lookup.lookyloo l10 ON foo.dim2 = l10.k\n"
+ "INNER JOIN lookup.lookyloo l11 ON foo.dim2 = l11.k\n"
+ "INNER JOIN lookup.lookyloo l12 ON foo.dim2 = l12.k\n"
+ "INNER JOIN lookup.lookyloo l13 ON foo.dim2 = l13.k\n"
+ "INNER JOIN lookup.lookyloo l14 ON foo.dim2 = l14.k\n"
+ "INNER JOIN lookup.lookyloo l15 ON foo.dim2 = l15.k\n"
+ "INNER JOIN lookup.lookyloo l16 ON foo.dim2 = l16.k\n"
+ "INNER JOIN lookup.lookyloo l17 ON foo.dim2 = l17.k\n"
+ "INNER JOIN lookup.lookyloo l18 ON foo.dim2 = l18.k\n"
+ "INNER JOIN lookup.lookyloo l19 ON foo.dim2 = l19.k\n"
+ "WHERE l.v = 'xa'\n",
```
The reason I'm suggesting this is we want to make sure the approach we're using doesn't change behavior as the stack gets deeper.
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rel/DruidQueryRel.java
##########
@@ -183,6 +183,10 @@ public RelWriter explainTerms(final RelWriter pw)
@Override
public RelOptCost computeSelfCost(final RelOptPlanner planner, final RelMetadataQuery mq)
{
- return planner.getCostFactory().makeCost(partialQuery.estimateCost(), 0, 0);
+ double cost = partialQuery.estimateCost();
+ double multiplier = DruidRels.isScanOrMapping(this, true)
Review comment:
Could you add a comment about why this is being done here?
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rel/DruidJoinQueryRel.java
##########
@@ -293,23 +293,17 @@ protected RelDataType deriveRowType()
@Override
public RelOptCost computeSelfCost(final RelOptPlanner planner, final RelMetadataQuery mq)
{
- double cost;
-
- if (computeLeftRequiresSubquery(getSomeDruidChild(left))) {
- cost = CostEstimates.COST_JOIN_SUBQUERY;
- } else {
- cost = partialQuery.estimateCost();
- }
-
- if (computeRightRequiresSubquery(getSomeDruidChild(right))) {
- cost += CostEstimates.COST_JOIN_SUBQUERY;
- }
-
+ double cost = partialQuery.estimateCost();
if (joinRel.getCondition().isA(SqlKind.LITERAL) && !joinRel.getCondition().isAlwaysFalse()) {
cost += CostEstimates.COST_JOIN_CROSS;
}
-
- return planner.getCostFactory().makeCost(cost, 0, 0);
+ // This is to cancel out the MULTIPLIER_FILTER (value=0.1) from partialQuery.estimateCost() to discourage
+ // filter push down if pushing down the filter makes this DruidJoinQueryRel not a scan or mapping.
+ // This will leave the filter at the topmost DruidJoinQueryRel (due to the order of applying/popping rules).
Review comment:
This "due to the order of applying/popping rules" sounds a bit sketchy. Does it mean that a good plan and bad plan will have equal cost, and we'll pick the good plan due to order-based tiebreaking? If so, I'm not sure it would be safe to rely on that. Ideally the good plans should be cheaper than the bad plans, which ensures we pick them.
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rel/DruidJoinQueryRel.java
##########
@@ -293,23 +293,17 @@ protected RelDataType deriveRowType()
@Override
public RelOptCost computeSelfCost(final RelOptPlanner planner, final RelMetadataQuery mq)
{
- double cost;
-
- if (computeLeftRequiresSubquery(getSomeDruidChild(left))) {
- cost = CostEstimates.COST_JOIN_SUBQUERY;
- } else {
- cost = partialQuery.estimateCost();
- }
-
- if (computeRightRequiresSubquery(getSomeDruidChild(right))) {
- cost += CostEstimates.COST_JOIN_SUBQUERY;
- }
-
+ double cost = partialQuery.estimateCost();
if (joinRel.getCondition().isA(SqlKind.LITERAL) && !joinRel.getCondition().isAlwaysFalse()) {
cost += CostEstimates.COST_JOIN_CROSS;
}
-
- return planner.getCostFactory().makeCost(cost, 0, 0);
+ // This is to cancel out the MULTIPLIER_FILTER (value=0.1) from partialQuery.estimateCost() to discourage
+ // filter push down if pushing down the filter makes this DruidJoinQueryRel not a scan or mapping.
+ // This will leave the filter at the topmost DruidJoinQueryRel (due to the order of applying/popping rules).
+ double multiplier = DruidRels.isScanOrMapping(this, true)
+ ? 1
+ : 1 / CostEstimates.MULTIPLIER_FILTER;
Review comment:
It seems like this happens even if there is no filter. Is that right?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r425455631
##########
File path: sql/src/test/java/org/apache/druid/sql/calcite/CalciteQueryTest.java
##########
@@ -8749,6 +9097,9 @@ public void testCommaJoinLeftFunction() throws Exception
);
}
+ // This SQL currently does not result in an optimum plan.
+ // Unfortunetly, we have disabled pushing down predicates (conditions and filters) due to https://github.com/apache/druid/pull/9773
Review comment:
Done
##########
File path: sql/src/test/java/org/apache/druid/sql/calcite/CalciteQueryTest.java
##########
@@ -8749,6 +9097,9 @@ public void testCommaJoinLeftFunction() throws Exception
);
}
+ // This SQL currently does not result in an optimum plan.
+ // Unfortunetly, we have disabled pushing down predicates (conditions and filters) due to https://github.com/apache/druid/pull/9773
+ // Hence, comma join will result in a cross join with filter on outermost
Review comment:
Done
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm removed a comment on pull request #9773: [WIP] Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm removed a comment on pull request #9773:
URL: https://github.com/apache/druid/pull/9773#issuecomment-622523625
> 1. Figure out a way to compute costs that encourages the SQL planner to push projects and filters above joins consistently.
@gianm Thinking of different ideas....in addition to what we already have now... is it possible to add a new RelOptRule that when see two DruidJoinQueryRel, will push filter to the topmost DruidJoinQueryRel if the filter is on the inner DruidJoinQueryRel?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] suneet-s commented on a change in pull request #9773: [WIP] Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
suneet-s commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r416778349
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rel/DruidJoinQueryRel.java
##########
@@ -328,17 +327,27 @@ private static JoinType toDruidJoinType(JoinRelType calciteJoinType)
}
}
- private static boolean computeLeftRequiresSubquery(final DruidRel<?> left)
+ private static boolean computeLeftRequiresSubquery(final List<DruidRel<?>> leftList)
Review comment:
What do you think about keeping this interface the same and instead changing the private members left and right to `DruidRel<?>`
Whenever left and right is set - we can do something like `this.left = getCheapestDruidRel(RelNode);`
As it's written, I wonder if it's possible for us to estimate that a subquery is not required in the computeSelfCost function, but the DruidRel used to build the native query actually uses a subquery.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] gianm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
gianm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r425274781
##########
File path: docs/querying/sql.md
##########
@@ -526,15 +526,19 @@ the way you write the filter.
2. Try to avoid subqueries underneath joins: they affect both performance and scalability. This includes implicit
subqueries generated by conditions on mismatched types, and implicit subqueries generated by conditions that use
-expressions to refer to the right-hand side.
+expressions to refer to the right-hand side.
Review comment:
The stray space shouldn't be here.
##########
File path: docs/querying/datasource.md
##########
@@ -268,12 +268,16 @@ perform best if `d.field` is a string.
4. As of Druid {{DRUIDVERSION}}, the join operator must evaluate the condition for each row. In the future, we expect
to implement both early and deferred condition evaluation, which we expect to improve performance considerably for
common use cases.
+5. Currently, Druid does not support pushing down predicates (condition and filter) pass a Join (i.e. into
Review comment:
past a join (spelling)
##########
File path: sql/src/test/java/org/apache/druid/sql/calcite/CalciteQueryTest.java
##########
@@ -8749,6 +9097,9 @@ public void testCommaJoinLeftFunction() throws Exception
);
}
+ // This SQL currently does not result in an optimum plan.
+ // Unfortunetly, we have disabled pushing down predicates (conditions and filters) due to https://github.com/apache/druid/pull/9773
+ // Hence, comma join will result in a cross join with filter on outermost
Review comment:
Please update the docs to point out that people should avoid comma joins for this reason.
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rule/DruidJoinRule.java
##########
@@ -193,9 +193,16 @@ static boolean canHandleCondition(final RexNode condition, final RelDataType lef
final int numLeftFields = leftRowType.getFieldCount();
for (RexNode subCondition : subConditions) {
- if (subCondition.isA(SqlKind.LITERAL)) {
- // Literals are always OK.
- literalSubConditions.add((RexLiteral) subCondition);
+ if (RexUtil.isLiteral(subCondition, true)) {
+ if (subCondition instanceof RexCall) {
+ // This is CAST(literal) which is always OK.
+ // We know that this is CASE(literal) as it pass the check from RexUtil.isLiteral
+ RexCall call = (RexCall) subCondition;
+ literalSubConditions.add((RexLiteral) call.operands.get(0));
Review comment:
We have to verify the types of the cast here, because if the underlying literal and the cast output type are different, then skipping the cast might change the meaning of the subcondition. Try looking at the type of the RexCall and comparing it to the type of the underlying RexLiteral. I think some logic like this would work:
1. If the types are the same, unwrap the cast and use the underlying literal.
2. If the types are not the same, return `Optional.empty()` indicating the condition is not supported.
Alternatively, actually apply the cast in step (2) instead of rejecting the condition. I'm not sure how exactly you would do this or whether it is necessary. If it turns out to be necessary, perhaps check out what ReduceExpressionsRule does.
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rule/FilterJoinExcludePushToChildRule.java
##########
@@ -0,0 +1,280 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.sql.calcite.rule;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Sets;
+import org.apache.calcite.adapter.enumerable.EnumerableConvention;
+import org.apache.calcite.plan.RelOptRule;
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelOptRuleOperand;
+import org.apache.calcite.plan.RelOptUtil;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Filter;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.core.RelFactories;
+import org.apache.calcite.rel.rules.FilterJoinRule;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexCall;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexUtil;
+import org.apache.calcite.tools.RelBuilder;
+import org.apache.calcite.tools.RelBuilderFactory;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public abstract class FilterJoinExcludePushToChildRule extends FilterJoinRule
Review comment:
Please add a javadoc here explaining where the code came from, what modifications you made, and what might need to happen to make this no longer necessary (so we can use the builtin rule instead).
##########
File path: docs/querying/sql.md
##########
@@ -526,15 +526,19 @@ the way you write the filter.
2. Try to avoid subqueries underneath joins: they affect both performance and scalability. This includes implicit
subqueries generated by conditions on mismatched types, and implicit subqueries generated by conditions that use
-expressions to refer to the right-hand side.
+expressions to refer to the right-hand side.
-3. Read through the [Query execution](query-execution.md) page to understand how various types of native queries
+3. Currently, Druid does not support pushing down predicates (condition and filter) pass a Join (i.e. into
Review comment:
past a join (spelling)
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rule/DruidJoinRule.java
##########
@@ -193,9 +193,16 @@ static boolean canHandleCondition(final RexNode condition, final RelDataType lef
final int numLeftFields = leftRowType.getFieldCount();
for (RexNode subCondition : subConditions) {
- if (subCondition.isA(SqlKind.LITERAL)) {
- // Literals are always OK.
- literalSubConditions.add((RexLiteral) subCondition);
+ if (RexUtil.isLiteral(subCondition, true)) {
+ if (subCondition instanceof RexCall) {
+ // This is CAST(literal) which is always OK.
+ // We know that this is CASE(literal) as it pass the check from RexUtil.isLiteral
Review comment:
- CAST, not CASE (spelling)
- passed the check (spelling)
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rule/DruidJoinRule.java
##########
@@ -193,9 +193,16 @@ static boolean canHandleCondition(final RexNode condition, final RelDataType lef
final int numLeftFields = leftRowType.getFieldCount();
for (RexNode subCondition : subConditions) {
- if (subCondition.isA(SqlKind.LITERAL)) {
- // Literals are always OK.
- literalSubConditions.add((RexLiteral) subCondition);
+ if (RexUtil.isLiteral(subCondition, true)) {
+ if (subCondition instanceof RexCall) {
Review comment:
A bit nicer to do `if (subCondition.isA(SqlKind.CAST))`, since it's more explicit as to what we're actually looking for.
##########
File path: sql/src/test/java/org/apache/druid/sql/calcite/CalciteQueryTest.java
##########
@@ -8749,6 +9097,9 @@ public void testCommaJoinLeftFunction() throws Exception
);
}
+ // This SQL currently does not result in an optimum plan.
+ // Unfortunetly, we have disabled pushing down predicates (conditions and filters) due to https://github.com/apache/druid/pull/9773
Review comment:
Unfortunately (spelling)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] gianm merged pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
gianm merged pull request #9773:
URL: https://github.com/apache/druid/pull/9773
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r425447829
##########
File path: docs/querying/sql.md
##########
@@ -526,15 +526,19 @@ the way you write the filter.
2. Try to avoid subqueries underneath joins: they affect both performance and scalability. This includes implicit
subqueries generated by conditions on mismatched types, and implicit subqueries generated by conditions that use
-expressions to refer to the right-hand side.
+expressions to refer to the right-hand side.
-3. Read through the [Query execution](query-execution.md) page to understand how various types of native queries
+3. Currently, Druid does not support pushing down predicates (condition and filter) pass a Join (i.e. into
Review comment:
Done
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] gianm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
gianm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r421173321
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rel/DruidJoinQueryRel.java
##########
@@ -293,23 +293,17 @@ protected RelDataType deriveRowType()
@Override
public RelOptCost computeSelfCost(final RelOptPlanner planner, final RelMetadataQuery mq)
{
- double cost;
-
- if (computeLeftRequiresSubquery(getSomeDruidChild(left))) {
- cost = CostEstimates.COST_JOIN_SUBQUERY;
- } else {
- cost = partialQuery.estimateCost();
- }
-
- if (computeRightRequiresSubquery(getSomeDruidChild(right))) {
- cost += CostEstimates.COST_JOIN_SUBQUERY;
- }
-
+ double cost = partialQuery.estimateCost();
if (joinRel.getCondition().isA(SqlKind.LITERAL) && !joinRel.getCondition().isAlwaysFalse()) {
cost += CostEstimates.COST_JOIN_CROSS;
}
-
- return planner.getCostFactory().makeCost(cost, 0, 0);
+ // This is to cancel out the MULTIPLIER_FILTER (value=0.1) from partialQuery.estimateCost() to discourage
+ // filter push down if pushing down the filter makes this DruidJoinQueryRel not a scan or mapping.
+ // This will leave the filter at the topmost DruidJoinQueryRel (due to the order of applying/popping rules).
Review comment:
After thinking about this for a while, I'm thinking that a less-sketchy method would be to remove the rules that push filters past joins. It's similar to how #9648 (temporarily) addressed issues related to bad join orderings by just nuking the rules that reordered joins. It makes sense since we don't have a good way to guide the optimizer at this point.
We'll want to reintroduce these rules when we've made improvements to the cost estimators that allow all these rules to operate at their full power.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] gianm commented on pull request #9773: [WIP] Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
gianm commented on pull request #9773:
URL: https://github.com/apache/druid/pull/9773#issuecomment-622456503
> A problem with this solution is that it does not guarantee to push the filter to the topmost DruidJoinQueryRel. This problem is showed in CalciteQueryTest#testInnerJoinTableLookupLookupWithFilterWithoutLimitWithAllColumns where the filter is on the inner DruidJoinQueryRel instead of the other DruidJoinQueryRel.
The plan in your current patch (cafca03) looks OK to me. It's exactly what we want. Do you have a different case that illustrates the issue you're talking about?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r421918022
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rel/DruidJoinQueryRel.java
##########
@@ -293,23 +293,17 @@ protected RelDataType deriveRowType()
@Override
public RelOptCost computeSelfCost(final RelOptPlanner planner, final RelMetadataQuery mq)
{
- double cost;
-
- if (computeLeftRequiresSubquery(getSomeDruidChild(left))) {
- cost = CostEstimates.COST_JOIN_SUBQUERY;
- } else {
- cost = partialQuery.estimateCost();
- }
-
- if (computeRightRequiresSubquery(getSomeDruidChild(right))) {
- cost += CostEstimates.COST_JOIN_SUBQUERY;
- }
-
+ double cost = partialQuery.estimateCost();
if (joinRel.getCondition().isA(SqlKind.LITERAL) && !joinRel.getCondition().isAlwaysFalse()) {
cost += CostEstimates.COST_JOIN_CROSS;
}
-
- return planner.getCostFactory().makeCost(cost, 0, 0);
+ // This is to cancel out the MULTIPLIER_FILTER (value=0.1) from partialQuery.estimateCost() to discourage
+ // filter push down if pushing down the filter makes this DruidJoinQueryRel not a scan or mapping.
+ // This will leave the filter at the topmost DruidJoinQueryRel (due to the order of applying/popping rules).
+ double multiplier = DruidRels.isScanOrMapping(this, true)
+ ? 1
+ : 1 / CostEstimates.MULTIPLIER_FILTER;
Review comment:
No longer need this. Removed
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rel/DruidQueryRel.java
##########
@@ -183,6 +183,10 @@ public RelWriter explainTerms(final RelWriter pw)
@Override
public RelOptCost computeSelfCost(final RelOptPlanner planner, final RelMetadataQuery mq)
{
- return planner.getCostFactory().makeCost(partialQuery.estimateCost(), 0, 0);
+ double cost = partialQuery.estimateCost();
+ double multiplier = DruidRels.isScanOrMapping(this, true)
Review comment:
No longer need this. Removed
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on pull request #9773:
URL: https://github.com/apache/druid/pull/9773#issuecomment-622590345
> > A problem with this solution is that it does not guarantee to push the filter to the topmost DruidJoinQueryRel. This problem is showed in CalciteQueryTest#testInnerJoinTableLookupLookupWithFilterWithoutLimitWithAllColumns where the filter is on the inner DruidJoinQueryRel instead of the other DruidJoinQueryRel.
>
> The plan in your current patch (cafca03) looks OK to me. It's exactly what we want. Do you have a different case that illustrates the issue you're talking about?
In the patch (cafca03) I put an `@Ignore` because it does not generate the good plan that you see in the patch. It was generating the bad plan (same as the bad plan in this PR description). But now with the latest patch (7911b20) that test and other new added tests should all be good now (hence removed the `@Ignore`).
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm removed a comment on pull request #9773: [WIP] Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm removed a comment on pull request #9773:
URL: https://github.com/apache/druid/pull/9773#issuecomment-622535442
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r421920290
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rule/FilterJoinExcludePushToChildRule.java
##########
@@ -0,0 +1,277 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.sql.calcite.rule;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Sets;
+import org.apache.calcite.adapter.enumerable.EnumerableConvention;
+import org.apache.calcite.plan.RelOptRule;
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelOptRuleOperand;
+import org.apache.calcite.plan.RelOptUtil;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Filter;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.core.RelFactories;
+import org.apache.calcite.rel.rules.FilterJoinRule;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexCall;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexUtil;
+import org.apache.calcite.tools.RelBuilder;
+import org.apache.calcite.tools.RelBuilderFactory;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import static org.apache.calcite.plan.RelOptUtil.conjunctions;
+
+public abstract class FilterJoinExcludePushToChildRule extends FilterJoinRule
+{
+ /** Copied from {@link FilterJoinRule#NOT_ENUMERABLE} */
+ private static final Predicate NOT_ENUMERABLE = (join, joinType, exp) ->
+ join.getConvention() != EnumerableConvention.INSTANCE;
+
+ /**
+ * Rule that pushes predicates from a Filter into the Join below them.
+ * Similar to {@link FilterJoinRule#FILTER_ON_JOIN} but does not push predicate to the child
+ */
+ public static final FilterJoinRule FILTER_ON_JOIN_EXCLUDE_PUSH_TO_CHILD =
+ new FilterIntoJoinExcludePushToChildRule(RelFactories.LOGICAL_BUILDER, NOT_ENUMERABLE);
+
+ FilterJoinExcludePushToChildRule(RelOptRuleOperand operand,
+ String id,
+ boolean smart,
+ RelBuilderFactory relBuilderFactory,
+ Predicate predicate) {
+ super(operand, id, smart, relBuilderFactory, predicate);
+ }
+
+ /**
+ * Rule that tries to push filter expressions into a join
+ * condition. Exlucde pushing into the inputs (child) of the join.
+ */
+ public static class FilterIntoJoinExcludePushToChildRule extends FilterJoinExcludePushToChildRule
+ {
+ public FilterIntoJoinExcludePushToChildRule(RelBuilderFactory relBuilderFactory, Predicate predicate) {
+ super(
+ operand(Filter.class,
+ operand(Join.class, RelOptRule.any())),
+ "FilterJoinExcludePushToChildRule:filter", true, relBuilderFactory,
+ predicate);
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ Filter filter = call.rel(0);
+ Join join = call.rel(1);
+ perform(call, filter, join);
+ }
+ }
+
+ /**
+ * Copied from {@link FilterJoinRule#perform}
+ * The difference is that this method will not not push filters to the children in classifyFilters
+ */
+ @Override
+ protected void perform(RelOptRuleCall call, Filter filter,
+ Join join) {
+ final List<RexNode> joinFilters =
+ RelOptUtil.conjunctions(join.getCondition());
+ final List<RexNode> origJoinFilters = ImmutableList.copyOf(joinFilters);
+ // If there is only the joinRel,
+ // make sure it does not match a cartesian product joinRel
+ // (with "true" condition), otherwise this rule will be applied
+ // again on the new cartesian product joinRel.
+ if (filter == null && joinFilters.isEmpty()) {
+ return;
+ }
+
+ final List<RexNode> aboveFilters =
+ filter != null
+ ? getConjunctions(filter)
+ : new ArrayList<>();
+ final ImmutableList<RexNode> origAboveFilters =
+ ImmutableList.copyOf(aboveFilters);
+
+ // Simplify Outer Joins
+ JoinRelType joinType = join.getJoinType();
+ if (!origAboveFilters.isEmpty() && join.getJoinType() != JoinRelType.INNER) {
+ joinType = RelOptUtil.simplifyJoin(join, origAboveFilters, joinType);
+ }
+
+ final List<RexNode> leftFilters = new ArrayList<>();
Review comment:
These left right thing is not needed. But I copied this whole code from Calcite and made minimum change (which is just the classifyFilters method). Hence, keeping these variables here as I don't want to refactor Calcite stuff more than needed.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on pull request #9773: [WIP] Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on pull request #9773:
URL: https://github.com/apache/druid/pull/9773#issuecomment-622587823
> By the way, let me discuss for a bit what this cost-estimation stuff is trying to accomplish, in case that's helpful.
>
> In Druid native queries, in order for a Join tree (multiple stacked joins) to execute without subqueries, it must be left-heavy and the bottom-leftmost must be a table. We are trying to encourage the SQL planner to put things in that form whenever possible. "Must be left-heavy" means that the right child should be a regular datasource, not a join. The left child could potentially be a join."Bottom-leftmost must be a table" means that if you follow the chain of joins down the left-child pointers, the final, leaf regular datasource must be a table.
>
> What if we need to apply some filters or projections to that table? In Druid native queries, we do that by adding `filter` or `virtualColumns` in the query that references the outermost join datasource.
>
> But it is important, for performance, to push filters and projections down past a join when a query is executed. We do this at the native query level: if you have a filter or virtual column on a join that could apply to the base table, we apply it to the base table.
>
> So we want the SQL planner to generate queries where projects and filters are completely above the join, and we'll push them down later, at the native query execution stage.
>
> On the other hand, what if the SQL planner generates projects and filters below a join? That's bad, because the only way the SQL-to-native translation can handle that structure is by generating a subquery. This is bad because subqueries require transferring the full results of the subquery to the Broker.
>
> So I think broadly we have to do either one of two things.
>
> 1. Figure out a way to compute costs that encourages the SQL planner to push projects and filters above joins consistently.
> 2. Extend the native query language so you can specify a filter or virtualColumn at the level of a join datasource, so even if the SQL planner generates a rel tree with a filter randomly in the middle, the SQL-to-native translation can attach the filter to the join datasource and does not need to generate a subquery.
>
> IMO (1) is nice since it keeps the native language simple. But if it's not workable, we might need to go with (2).
I think I have found a way to work with number 1. This now pass for all the new added test cases. Thank you for the help and insights.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r425447702
##########
File path: docs/querying/sql.md
##########
@@ -526,15 +526,19 @@ the way you write the filter.
2. Try to avoid subqueries underneath joins: they affect both performance and scalability. This includes implicit
subqueries generated by conditions on mismatched types, and implicit subqueries generated by conditions that use
-expressions to refer to the right-hand side.
+expressions to refer to the right-hand side.
Review comment:
Done
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r425448518
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rule/DruidJoinRule.java
##########
@@ -193,9 +193,16 @@ static boolean canHandleCondition(final RexNode condition, final RelDataType lef
final int numLeftFields = leftRowType.getFieldCount();
for (RexNode subCondition : subConditions) {
- if (subCondition.isA(SqlKind.LITERAL)) {
- // Literals are always OK.
- literalSubConditions.add((RexLiteral) subCondition);
+ if (RexUtil.isLiteral(subCondition, true)) {
+ if (subCondition instanceof RexCall) {
Review comment:
Done
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r425465115
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rule/DruidJoinRule.java
##########
@@ -193,9 +193,16 @@ static boolean canHandleCondition(final RexNode condition, final RelDataType lef
final int numLeftFields = leftRowType.getFieldCount();
for (RexNode subCondition : subConditions) {
- if (subCondition.isA(SqlKind.LITERAL)) {
- // Literals are always OK.
- literalSubConditions.add((RexLiteral) subCondition);
+ if (RexUtil.isLiteral(subCondition, true)) {
+ if (subCondition instanceof RexCall) {
+ // This is CAST(literal) which is always OK.
+ // We know that this is CASE(literal) as it pass the check from RexUtil.isLiteral
+ RexCall call = (RexCall) subCondition;
+ literalSubConditions.add((RexLiteral) call.operands.get(0));
Review comment:
Done
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r425447494
##########
File path: docs/querying/datasource.md
##########
@@ -268,12 +268,16 @@ perform best if `d.field` is a string.
4. As of Druid {{DRUIDVERSION}}, the join operator must evaluate the condition for each row. In the future, we expect
to implement both early and deferred condition evaluation, which we expect to improve performance considerably for
common use cases.
+5. Currently, Druid does not support pushing down predicates (condition and filter) pass a Join (i.e. into
Review comment:
Done
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm edited a comment on pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm edited a comment on pull request #9773:
URL: https://github.com/apache/druid/pull/9773#issuecomment-622587823
> By the way, let me discuss for a bit what this cost-estimation stuff is trying to accomplish, in case that's helpful.
>
> In Druid native queries, in order for a Join tree (multiple stacked joins) to execute without subqueries, it must be left-heavy and the bottom-leftmost must be a table. We are trying to encourage the SQL planner to put things in that form whenever possible. "Must be left-heavy" means that the right child should be a regular datasource, not a join. The left child could potentially be a join."Bottom-leftmost must be a table" means that if you follow the chain of joins down the left-child pointers, the final, leaf regular datasource must be a table.
>
> What if we need to apply some filters or projections to that table? In Druid native queries, we do that by adding `filter` or `virtualColumns` in the query that references the outermost join datasource.
>
> But it is important, for performance, to push filters and projections down past a join when a query is executed. We do this at the native query level: if you have a filter or virtual column on a join that could apply to the base table, we apply it to the base table.
>
> So we want the SQL planner to generate queries where projects and filters are completely above the join, and we'll push them down later, at the native query execution stage.
>
> On the other hand, what if the SQL planner generates projects and filters below a join? That's bad, because the only way the SQL-to-native translation can handle that structure is by generating a subquery. This is bad because subqueries require transferring the full results of the subquery to the Broker.
>
> So I think broadly we have to do either one of two things.
>
> 1. Figure out a way to compute costs that encourages the SQL planner to push projects and filters above joins consistently.
> 2. Extend the native query language so you can specify a filter or virtualColumn at the level of a join datasource, so even if the SQL planner generates a rel tree with a filter randomly in the middle, the SQL-to-native translation can attach the filter to the join datasource and does not need to generate a subquery.
>
> IMO (1) is nice since it keeps the native language simple. But if it's not workable, we might need to go with (2).
I think I have found a way to work with number 1. This now pass for all the new added test cases. Thank you for the help and insights. See updated PR description for details
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] maytasm commented on a change in pull request #9773: Bad plan for table-lookup-lookup join with filter on first lookup and outer limit
Posted by GitBox <gi...@apache.org>.
maytasm commented on a change in pull request #9773:
URL: https://github.com/apache/druid/pull/9773#discussion_r421917928
##########
File path: sql/src/main/java/org/apache/druid/sql/calcite/rel/DruidJoinQueryRel.java
##########
@@ -293,23 +293,17 @@ protected RelDataType deriveRowType()
@Override
public RelOptCost computeSelfCost(final RelOptPlanner planner, final RelMetadataQuery mq)
{
- double cost;
-
- if (computeLeftRequiresSubquery(getSomeDruidChild(left))) {
- cost = CostEstimates.COST_JOIN_SUBQUERY;
- } else {
- cost = partialQuery.estimateCost();
- }
-
- if (computeRightRequiresSubquery(getSomeDruidChild(right))) {
- cost += CostEstimates.COST_JOIN_SUBQUERY;
- }
-
+ double cost = partialQuery.estimateCost();
if (joinRel.getCondition().isA(SqlKind.LITERAL) && !joinRel.getCondition().isAlwaysFalse()) {
cost += CostEstimates.COST_JOIN_CROSS;
}
-
- return planner.getCostFactory().makeCost(cost, 0, 0);
+ // This is to cancel out the MULTIPLIER_FILTER (value=0.1) from partialQuery.estimateCost() to discourage
+ // filter push down if pushing down the filter makes this DruidJoinQueryRel not a scan or mapping.
+ // This will leave the filter at the topmost DruidJoinQueryRel (due to the order of applying/popping rules).
Review comment:
Done. Updated PR description with details.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org