Skip to content

Commit 54424e3

Browse files
924060929yinzhijian
authored andcommitted
[Enhancement](Nereids)refactor plan node into plan + operator (apache#9755)
Close apache#9623 Summary: This pr refactor plan node into plan + operator. In the previous version in nereids, a plan node consists of children and relational algebra, e.g. ```java class LogicalJoin extends LogicalBinary { private Plan left, right; } ``` This structure above is easy to understand, but it difficult to optimize `Memo.copyIn`: rule generate complete sub-plan, and Memo must compare the complete sub-plan to distinct GroupExpression and hurt performance. First, we need change the rule to generate partial sub-plan, and replace some children plan to a placeholder, e.g. LeafOp in Columbia optimizer. And then mark some children in sub-plan to unchanged, and bind the relate group, so don't have to compare and copy some sub-plan if relate group exists. Second, we need separate the origin `Plan` into `Plan` and `Operator`, which Plan contains children and Operator, and Operator just denote relation relational algebra(no children/ input field). This design make operator and children not affect each other. So plan-group binder can generate placeholder plan(contains relate group) for the sub-query, don't have to generate current plan node case by case because the plan is immutable(means generate a new plan with replace children). And rule implementer can reuse the placeholder to generate partial sub-plan. Operator and Plan have the similar inheritance structure like below. XxxPlan contains XxxOperator, e.g. LogicalBinary contains a LogicalBinaryOperator. ``` TreeNode │ │ ┌───────┴────────┐ Operator │ │ │ │ │ │ │ │ │ ▼ ▼ ▼ Expression Plan PlanOperator │ │ │ │ ┌───────────┴─────────┐ │ │ │ ┌───────────┴──────────────────┐ │ │ │ │ │ │ │ │ ▼ ▼ ▼ ▼ LogicalPlan PhysicalPlan LogicalPlanOperator PhysicalPlanOperator │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ├───►LogicalLeaf ├──►PhysicalLeaf ├──► LogicalLeafOperator ├───►PhysicalLeafOperator │ │ │ │ │ │ │ │ │ │ │ │ ├───►LogicalUnary ├──►PhysicalUnary ├──► LogicalUnaryOperator ├───►PhysicalUnaryOperator │ │ │ │ │ │ │ │ │ │ │ │ └───►LogicalBinary └──►PhysicalBinary └──► LogicalBinaryOperator └───►PhysicalBinaryOperator ``` The concrete operator extends the XxxNaryOperator, e.g. ```java class LogicalJoin extends LogicalBinaryOperator; class PhysicalProject extends PhysicalUnaryOperator; class LogicalRelation extends LogicalLeafOperator; ``` So the first example change to this: ```java class LogicalBinary extends AbstractLogicalPlan implements BinaryPlan { private Plan left, right; private LogicalBinaryOperator operator; } class LogicalJoin extends LogicalBinaryOperator {} ``` Under such changes, Rule must build the plan and operator as needed, not only the plan like before. for example: JoinCommutative Rule ```java public Rule<Plan> build() { // the plan override function can automatic build plan, according to the Operator's type, // so return a LogicalBinary(LogicalJoin, Plan, Plan) return innerLogicalJoin().then(join -> plan( // operator new LogicalJoin(join.op.getJoinType().swap(), join.op.getOnClause()), // children join.right(), join.left() )).toRule(RuleType.LOGICAL_JOIN_COMMUTATIVE); } ```
1 parent 272a2d4 commit 54424e3

62 files changed

Lines changed: 1112 additions & 519 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎fe/fe-core/src/main/java/org/apache/doris/nereids/analyzer/UnboundRelation.java‎

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -19,9 +19,9 @@
1919

2020
import org.apache.doris.nereids.analyzer.identifier.TableIdentifier;
2121
import org.apache.doris.nereids.exceptions.UnboundException;
22-
import org.apache.doris.nereids.trees.NodeType;
22+
import org.apache.doris.nereids.operators.OperatorType;
23+
import org.apache.doris.nereids.operators.plans.logical.LogicalLeafOperator;
2324
import org.apache.doris.nereids.trees.expressions.Slot;
24-
import org.apache.doris.nereids.trees.plans.logical.LogicalLeaf;
2525
import org.apache.doris.nereids.util.Utils;
2626

2727
import com.clearspring.analytics.util.Lists;
@@ -32,11 +32,11 @@
3232
/**
3333
* Represent a relation plan node that has not been bound.
3434
*/
35-
public class UnboundRelation extends LogicalLeaf<UnboundRelation> {
35+
public class UnboundRelation extends LogicalLeafOperator<UnboundRelation> {
3636
private final List<String> nameParts;
3737

3838
public UnboundRelation(List<String> nameParts) {
39-
super(NodeType.LOGICAL_UNBOUND_RELATION);
39+
super(OperatorType.LOGICAL_UNBOUND_RELATION);
4040
this.nameParts = nameParts;
4141
}
4242

@@ -46,7 +46,7 @@ public UnboundRelation(List<String> nameParts) {
4646
* @param identifier relation identifier
4747
*/
4848
public UnboundRelation(TableIdentifier identifier) {
49-
super(NodeType.LOGICAL_UNBOUND_RELATION);
49+
super(OperatorType.LOGICAL_UNBOUND_RELATION);
5050
this.nameParts = Lists.newArrayList();
5151
if (identifier.getDatabaseName().isPresent()) {
5252
nameParts.add(identifier.getDatabaseName().get());
@@ -64,8 +64,9 @@ public String getTableName() {
6464
}
6565

6666
@Override
67-
public List<Slot> getOutput() throws UnboundException {
68-
throw new UnboundException("output");
67+
public List<Slot> doComputeOutput() {
68+
// fixme: throw unchecked exception
69+
throw new IllegalStateException(new UnboundException("output"));
6970
}
7071

7172
@Override

‎fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/cascades/ApplyRuleJob.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,7 @@ public void execute() throws AnalysisException {
5959

6060
// TODO: need to find all plan reference tree that match this pattern
6161
PatternMatching patternMatching = new PatternMatching();
62-
for (Plan<?> plan : patternMatching) {
62+
for (Plan<?, ?> plan : patternMatching) {
6363
if (!rule.check(plan, context)) {
6464
continue;
6565
}

‎fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Group.java‎

Lines changed: 1 addition & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,6 @@
1818
package org.apache.doris.nereids.memo;
1919

2020
import org.apache.doris.common.Pair;
21-
import org.apache.doris.nereids.exceptions.UnboundException;
2221
import org.apache.doris.nereids.properties.LogicalProperties;
2322
import org.apache.doris.nereids.properties.PhysicalProperties;
2423
import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
@@ -55,12 +54,7 @@ public Group(GroupExpression groupExpression) {
5554
} else {
5655
this.physicalPlanList.add(groupExpression);
5756
}
58-
logicalProperties = new LogicalProperties();
59-
try {
60-
logicalProperties.setOutput(groupExpression.getPlan().getOutput());
61-
} catch (UnboundException e) {
62-
throw new RuntimeException(e);
63-
}
57+
logicalProperties = groupExpression.getParent().getLogicalProperties();
6458
groupExpression.setParent(this);
6559
}
6660

‎fe/fe-core/src/main/java/org/apache/doris/nereids/memo/GroupExpression.java‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -32,11 +32,11 @@
3232
public class GroupExpression {
3333
private Group parent;
3434
private List<Group> children;
35-
private final Plan<?> plan;
35+
private final Plan<?, ?> plan;
3636
private final BitSet ruleMasks;
3737
private boolean statDerived;
3838

39-
public GroupExpression(Plan<?> plan) {
39+
public GroupExpression(Plan<?, ?> plan) {
4040
this(plan, Lists.newArrayList());
4141
}
4242

@@ -46,7 +46,7 @@ public GroupExpression(Plan<?> plan) {
4646
* @param plan {@link Plan} to reference
4747
* @param children children groups in memo
4848
*/
49-
public GroupExpression(Plan<?> plan, List<Group> children) {
49+
public GroupExpression(Plan<?, ?> plan, List<Group> children) {
5050
this.plan = plan;
5151
this.children = children;
5252
this.ruleMasks = new BitSet(RuleType.SENTINEL.ordinal());
@@ -65,7 +65,7 @@ public void setParent(Group parent) {
6565
this.parent = parent;
6666
}
6767

68-
public Plan<?> getPlan() {
68+
public Plan<?, ?> getPlan() {
6969
return plan;
7070
}
7171

‎fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -50,9 +50,9 @@ public Group getRootSet() {
5050
* @return Reference of plan in Memo
5151
*/
5252
// TODO: need to merge PlanRefSet if new PlanRef is same with some one already in memo
53-
public GroupExpression newGroupExpression(Plan<?> plan, Group target) {
53+
public GroupExpression newGroupExpression(Plan<?, ?> plan, Group target) {
5454
List<GroupExpression> childGroupExpr = Lists.newArrayList();
55-
for (Plan<?> childrenPlan : plan.children()) {
55+
for (Plan<?, ?> childrenPlan : plan.children()) {
5656
childGroupExpr.add(newGroupExpression(childrenPlan, null));
5757
}
5858
GroupExpression newGroupExpression = new GroupExpression(plan);
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with 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,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
package org.apache.doris.nereids.operators;
19+
20+
import java.util.Objects;
21+
22+
/**
23+
* Abstract class for all concrete operator.
24+
*/
25+
public abstract class AbstractOperator<TYPE extends AbstractOperator<TYPE>> implements Operator<TYPE> {
26+
protected final OperatorType type;
27+
28+
public AbstractOperator(OperatorType type) {
29+
this.type = Objects.requireNonNull(type, "type can not be null");
30+
}
31+
32+
@Override
33+
public OperatorType getType() {
34+
return type;
35+
}
36+
}
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with 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,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
package org.apache.doris.nereids.operators;
19+
20+
/**
21+
* interface for all concrete operator.
22+
*/
23+
public interface Operator<TYPE extends Operator<TYPE>> {
24+
OperatorType getType();
25+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with 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,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
package org.apache.doris.nereids.operators;
19+
20+
/**
21+
* Types for all Operator in Nereids, include PlanOperator and Pattern placeholder type.
22+
*/
23+
public enum OperatorType {
24+
// logical plan
25+
LOGICAL_UNBOUND_RELATION,
26+
LOGICAL_BOUND_RELATION,
27+
LOGICAL_PROJECT,
28+
LOGICAL_FILTER,
29+
LOGICAL_JOIN,
30+
31+
// physical plan
32+
PHYSICAL_OLAP_SCAN,
33+
PHYSICAL_PROJECT,
34+
PHYSICAL_FILTER,
35+
PHYSICAL_BROADCAST_HASH_JOIN,
36+
37+
// pattern
38+
ANY,
39+
MULTI,
40+
}
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with 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,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
package org.apache.doris.nereids.operators.plans;
19+
20+
import org.apache.doris.nereids.trees.plans.Plan;
21+
22+
/**
23+
* interface for all concrete binary plan operator.
24+
*/
25+
public interface BinaryPlanOperator<
26+
TYPE extends BinaryPlanOperator<TYPE, LEFT_INPUT_TYPE, RIGHT_INPUT_TYPE>,
27+
LEFT_INPUT_TYPE extends Plan,
28+
RIGHT_INPUT_TYPE extends Plan> extends PlanOperator<TYPE> {
29+
}

fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/JoinType.java renamed to fe/fe-core/src/main/java/org/apache/doris/nereids/operators/plans/JoinType.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18-
package org.apache.doris.nereids.trees.plans;
18+
package org.apache.doris.nereids.operators.plans;
1919

2020
import org.apache.doris.analysis.JoinOperator;
2121
import org.apache.doris.common.AnalysisException;

0 commit comments

Comments
 (0)