JackieTien97 commented on code in PR #14148:
URL: https://github.com/apache/iotdb/pull/14148#discussion_r1861806159
##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ExpressionExtractor.java:
##########
@@ -73,13 +75,12 @@ public Void visitPlan(PlanNode node, Void context) {
return null;
}
- /*@Override
- public Void visitGroupReference(GroupReference node, Void context)
- {
- return lookup.resolve(node).accept(this, context);
+ @Override
+ public Void visitGroupReference(GroupReference node, Void context) {
+ return lookup.resolve(node).accept(this, context);
}
- @Override
+ /*@Override
Review Comment:
why need to delete the `visitAggregation`?
##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/distribute/TableDistributedPlanGenerator.java:
##########
@@ -652,6 +633,18 @@ public List<PlanNode> visitAggregationTableScan(
return resultTableScanNodeList;
}
+ @Override
+ public List<PlanNode> visitEnforceSingleRow(EnforceSingleRowNode node,
PlanContext context) {
+ List<PlanNode> childrenNodes = node.getChild().accept(this, context);
+ OrderingScheme childOrdering =
nodeOrderingMap.get(childrenNodes.get(0).getPlanNodeId());
+ if (childOrdering != null) {
+ nodeOrderingMap.put(node.getPlanNodeId(), childOrdering);
+ }
+
+ node.setChild(mergeChildrenViaCollectOrMergeSort(childOrdering,
childrenNodes));
+ return Collections.singletonList(node);
+ }
Review Comment:
add `EnforceSingleRowNode` for each children and then call
mergeChildrenViaCollectOrMergeSort, and then followed by a
`EnforceSingleRowNode` may be better.
##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/node/CorrelatedJoinNode.java:
##########
@@ -0,0 +1,170 @@
+/*
+ * 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.iotdb.db.queryengine.plan.relational.planner.node;
+
+import org.apache.iotdb.db.queryengine.plan.planner.plan.node.PlanNode;
+import org.apache.iotdb.db.queryengine.plan.planner.plan.node.PlanNodeId;
+import org.apache.iotdb.db.queryengine.plan.planner.plan.node.PlanVisitor;
+import
org.apache.iotdb.db.queryengine.plan.planner.plan.node.process.TwoChildProcessNode;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.Symbol;
+import org.apache.iotdb.db.queryengine.plan.relational.sql.ast.Expression;
+import org.apache.iotdb.db.queryengine.plan.relational.sql.ast.Node;
+import org.apache.iotdb.db.queryengine.plan.relational.sql.ast.NullLiteral;
+
+import com.google.common.collect.ImmutableList;
+
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.util.List;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static java.util.Objects.requireNonNull;
+
+/**
+ * For every row from {@link #leftChild}(input) a {@link
#rightChild}(subquery) relation is
+ * calculated. Then input row is cross joined with subquery relation and
returned as a result.
+ *
+ * <p>INNER - does not return any row for input row when subquery relation is
empty LEFT - does
+ * return input completed with NULL values when subquery relation is empty
+ */
+public class CorrelatedJoinNode extends TwoChildProcessNode {
Review Comment:
may need to explain what's the difference between `CorrelatedJoinNode` and
`ApplyNode`, and how an unCorrelated Join be transformed from
`CorrelatedJoinNode` or `ApplyNode` to a `JoinNode`
##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/QueryCardinalityUtil.java:
##########
@@ -0,0 +1,208 @@
+/*
+ * 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.iotdb.db.queryengine.plan.relational.planner.optimizations;
+
+import org.apache.iotdb.db.queryengine.plan.planner.plan.node.PlanNode;
+import org.apache.iotdb.db.queryengine.plan.planner.plan.node.PlanVisitor;
+import
org.apache.iotdb.db.queryengine.plan.planner.plan.node.process.ExchangeNode;
+import
org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.GroupReference;
+import
org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.Lookup;
+import
org.apache.iotdb.db.queryengine.plan.relational.planner.node.AggregationNode;
+import
org.apache.iotdb.db.queryengine.plan.relational.planner.node.EnforceSingleRowNode;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.FilterNode;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.LimitNode;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.OffsetNode;
+import
org.apache.iotdb.db.queryengine.plan.relational.planner.node.ProjectNode;
+
+import com.google.common.collect.Range;
+
+import static com.google.common.collect.Iterables.getOnlyElement;
+import static java.lang.Math.max;
+import static java.lang.Math.min;
+import static java.util.Objects.requireNonNull;
+import static
org.apache.iotdb.db.queryengine.plan.relational.planner.iterative.Lookup.noLookup;
+
+public final class QueryCardinalityUtil {
+ private QueryCardinalityUtil() {}
+
+ public static boolean isScalar(PlanNode node) {
+ return isScalar(node, noLookup());
+ }
+
+ public static boolean isScalar(PlanNode node, Lookup lookup) {
+ return extractCardinality(node, lookup).isScalar();
+ }
+
+ public static boolean isAtMostScalar(PlanNode node) {
+ return isAtMostScalar(node, noLookup());
+ }
+
+ public static boolean isAtMostScalar(PlanNode node, Lookup lookup) {
+ return isAtMost(node, lookup, 1L);
+ }
+
+ public static boolean isAtMost(PlanNode node, Lookup lookup, long
maxCardinality) {
+ return extractCardinality(node, lookup).isAtMost(maxCardinality);
+ }
+
+ public static boolean isAtLeastScalar(PlanNode node, Lookup lookup) {
+ return isAtLeast(node, lookup, 1L);
+ }
+
+ public static boolean isAtLeast(PlanNode node, Lookup lookup, long
minCardinality) {
+ return extractCardinality(node, lookup).isAtLeast(minCardinality);
+ }
+
+ public static boolean isEmpty(PlanNode node, Lookup lookup) {
+ return isAtMost(node, lookup, 0);
+ }
+
+ public static Cardinality extractCardinality(PlanNode node) {
+ return extractCardinality(node, noLookup());
+ }
+
+ public static Cardinality extractCardinality(PlanNode node, Lookup lookup) {
+ return new Cardinality(node.accept(new
CardinalityExtractorPlanVisitor(lookup), null));
+ }
+
+ private static final class CardinalityExtractorPlanVisitor
+ extends PlanVisitor<Range<Long>, Void> {
+ private final Lookup lookup;
+
+ public CardinalityExtractorPlanVisitor(Lookup lookup) {
+ this.lookup = requireNonNull(lookup, "lookup is null");
+ }
+
+ @Override
+ public Range<Long> visitPlan(PlanNode node, Void context) {
+ return Range.atLeast(0L);
+ }
+
+ @Override
+ public Range<Long> visitGroupReference(GroupReference node, Void context) {
+ return lookup.resolve(node).accept(this, context);
+ }
+
+ @Override
+ public Range<Long> visitEnforceSingleRow(EnforceSingleRowNode node, Void
context) {
+ return Range.singleton(1L);
+ }
+
+ @Override
+ public Range<Long> visitAggregation(AggregationNode node, Void context) {
+ if (node.hasSingleGlobalAggregation()) {
+ // only single default aggregation which will produce exactly single
row
+ return Range.singleton(1L);
+ }
+
+ Range<Long> sourceCardinalityRange = node.getChild().accept(this, null);
+
+ long lower;
+ if (node.hasDefaultOutput() || sourceCardinalityRange.lowerEndpoint() >
0) {
+ lower = 1;
+ } else {
+ lower = 0;
+ }
+
+ if (sourceCardinalityRange.hasUpperBound()) {
+ long upper = Math.max(lower, sourceCardinalityRange.upperEndpoint());
+ return Range.closed(lower, upper);
+ }
+
+ return Range.atLeast(lower);
+ }
+
+ @Override
+ public Range<Long> visitExchange(ExchangeNode node, Void context) {
+ if (node.getChildren().size() == 1) {
+ return getOnlyElement(node.getChildren()).accept(this, null);
+ }
+ return Range.atLeast(0L);
+ }
+
+ @Override
+ public Range<Long> visitProject(ProjectNode node, Void context) {
+ return node.getChild().accept(this, null);
+ }
+
+ @Override
+ public Range<Long> visitFilter(FilterNode node, Void context) {
+ Range<Long> sourceCardinalityRange = node.getChild().accept(this, null);
+ if (sourceCardinalityRange.hasUpperBound()) {
+ return Range.closed(0L, sourceCardinalityRange.upperEndpoint());
+ }
+ return Range.atLeast(0L);
+ }
+
+ // @Override
+ // public Range<Long> visitValues(ValuesNode node, Void context)
+ // {
+ // return Range.singleton((long) node.getRowCount());
+ // }
+
+ @Override
+ public Range<Long> visitOffset(OffsetNode node, Void context) {
+ Range<Long> sourceCardinalityRange = node.getChild().accept(this, null);
+
+ long lower = max(sourceCardinalityRange.lowerEndpoint() -
node.getCount(), 0L);
+
+ if (sourceCardinalityRange.hasUpperBound()) {
+ return Range.closed(
+ lower, max(sourceCardinalityRange.upperEndpoint() -
node.getCount(), 0L));
+ }
+ return Range.atLeast(lower);
+ }
+
+ @Override
+ public Range<Long> visitLimit(LimitNode node, Void context) {
+ if (node.isWithTies()) {
+ Range<Long> sourceCardinalityRange = node.getChild().accept(this,
null);
+ long lower = min(node.getCount(),
sourceCardinalityRange.lowerEndpoint());
+ if (sourceCardinalityRange.hasUpperBound()) {
+ return Range.closed(lower, sourceCardinalityRange.upperEndpoint());
+ }
+ return Range.atLeast(lower);
+ }
+
+ return applyLimit(node.getChild(), node.getCount());
+ }
+
+ // @Override
+ // public Range<Long> visitTopN(TopNNode node, Void context)
+ // {
+ // return applyLimit(node.getSource(), node.getCount());
+ // }
Review Comment:
we also have `TopKNode`
##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/ExpressionExtractor.java:
##########
@@ -73,13 +75,12 @@ public Void visitPlan(PlanNode node, Void context) {
return null;
}
- /*@Override
- public Void visitGroupReference(GroupReference node, Void context)
- {
- return lookup.resolve(node).accept(this, context);
+ @Override
+ public Void visitGroupReference(GroupReference node, Void context) {
+ return lookup.resolve(node).accept(this, context);
}
- @Override
+ /*@Override
Review Comment:
And what exactly the `ExpressionExtractor` used for?
##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/CheckSubqueryNodesAreRewritten.java:
##########
@@ -0,0 +1,65 @@
+/*
+ * 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.iotdb.db.queryengine.plan.relational.planner.optimizations;
+
+import org.apache.iotdb.db.exception.sql.SemanticException;
+import org.apache.iotdb.db.queryengine.plan.planner.plan.node.PlanNode;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.Symbol;
+import org.apache.iotdb.db.queryengine.plan.relational.planner.node.ApplyNode;
+import
org.apache.iotdb.db.queryengine.plan.relational.planner.node.CorrelatedJoinNode;
+
+import java.util.List;
+
+import static com.google.common.base.Preconditions.checkState;
+import static
org.apache.iotdb.db.queryengine.plan.relational.planner.PlanNodeSearcher.searchFrom;
+import static org.apache.iotdb.rpc.TSStatusCode.SEMANTIC_ERROR;
+
+public class CheckSubqueryNodesAreRewritten implements PlanOptimizer {
Review Comment:
a little bit confused here, what plan nodes will correlated subqueries use?
not ApplyNode and CorrelatedJoinNode?
##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/LogicalOptimizeFactory.java:
##########
@@ -190,6 +198,13 @@ public LogicalOptimizeFactory(PlannerContext
plannerContext) {
new UnaliasSymbolReferences(plannerContext.getMetadata()),
columnPruningOptimizer,
inlineProjectionLimitFiltersOptimizer,
+ new IterativeOptimizer(
+ plannerContext,
+ ruleStats,
+ ImmutableSet.of(
+ new RemoveRedundantEnforceSingleRowNode(),
Review Comment:
may need to add it previous `IterativeOptimizer` redundantly
##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/LogicalOptimizeFactory.java:
##########
@@ -190,6 +198,13 @@ public LogicalOptimizeFactory(PlannerContext
plannerContext) {
new UnaliasSymbolReferences(plannerContext.getMetadata()),
columnPruningOptimizer,
inlineProjectionLimitFiltersOptimizer,
+ new IterativeOptimizer(
+ plannerContext,
+ ruleStats,
+ ImmutableSet.of(
+ new RemoveRedundantEnforceSingleRowNode(),
+ new TransformUncorrelatedSubqueryToJoin())),
+ new CheckSubqueryNodesAreRewritten(),
Review Comment:
In trino, it seems that we also need to add another `simplifyOptimizer`
after it.
##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/process/join/merge/comparator/AscJoinKeyComparator.java:
##########
@@ -0,0 +1,110 @@
+/*
+ * 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.iotdb.db.queryengine.execution.operator.process.join.merge.comparator;
+
+import org.apache.tsfile.utils.Binary;
+
+public class AscJoinKeyComparator implements JoinKeyComparator {
Review Comment:
The Comparator shouldn't be this way, we should only have
1. `lessThan(TsBlock left, int leftRowIndex, TsBlock right, int
rightRowIndex)`
2. `equalsTo(TsBlock left, int leftRowIndex, TsBlock right, int
rightRowIndex)`
3. `lessThanOrEqual(TsBlock left, int leftRowIndex, TsBlock right, int
rightRowIndex)`
in interface, and asc/desc implementation class for each type.
##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/distribute/TableDistributedPlanGenerator.java:
##########
@@ -442,18 +418,23 @@ public List<PlanNode> visitFilter(FilterNode node,
PlanContext context) {
@Override
public List<PlanNode> visitJoin(JoinNode node, PlanContext context) {
- // child of JoinNode must be SortNode, so after rewritten, the child must
be MergeSortNode or
- // SortNode
- List<PlanNode> leftChildrenNodes = node.getLeftChild().accept(this,
context);
- checkArgument(
- leftChildrenNodes.size() == 1, "The size of left children node of
JoinNode should be 1");
- node.setLeftChild(leftChildrenNodes.get(0));
+ List<PlanNode> leftChildrenNodes = node.getLeftChild().accept(this,
context);
List<PlanNode> rightChildrenNodes = node.getRightChild().accept(this,
context);
- checkArgument(
- rightChildrenNodes.size() == 1, "The size of right children node of
JoinNode should be 1");
- node.setRightChild(rightChildrenNodes.get(0));
-
+ if (!node.isCrossJoin()) {
+ // child of JoinNode(excluding CrossJoin) must be SortNode, so after
rewritten, the child must
+ // be MergeSortNode or
+ // SortNode
+ checkArgument(
+ leftChildrenNodes.size() == 1, "The size of left children node of
JoinNode should be 1");
+ checkArgument(
+ rightChildrenNodes.size() == 1,
+ "The size of right children node of JoinNode should be 1");
+ }
+ // For CrossJoinNode, we need to merge children nodes(It's safe for other
JoinNodes here since
+ // the size of their children is always 1.)
+ node.setLeftChild(mergeChildrenViaCollectOrMergeSort(null,
leftChildrenNodes));
+ node.setRightChild(mergeChildrenViaCollectOrMergeSort(null,
rightChildrenNodes));
Review Comment:
directly passing null as `OrderingScheme`? should use the left and right
child's orderingschema
--
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.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
