gortiz commented on code in PR #14296: URL: https://github.com/apache/pinot/pull/14296#discussion_r1818689731
########## pinot-query-planner/src/main/java/org/apache/pinot/query/planner/logical/EquivalentStagesFinder.java: ########## @@ -0,0 +1,339 @@ +/** + * 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.pinot.query.planner.logical; + +import com.google.common.base.Preconditions; +import java.util.List; +import java.util.Objects; +import org.apache.pinot.query.planner.plannode.AggregateNode; +import org.apache.pinot.query.planner.plannode.ExchangeNode; +import org.apache.pinot.query.planner.plannode.ExplainedNode; +import org.apache.pinot.query.planner.plannode.FilterNode; +import org.apache.pinot.query.planner.plannode.JoinNode; +import org.apache.pinot.query.planner.plannode.MailboxReceiveNode; +import org.apache.pinot.query.planner.plannode.MailboxSendNode; +import org.apache.pinot.query.planner.plannode.PlanNode; +import org.apache.pinot.query.planner.plannode.PlanNodeVisitor; +import org.apache.pinot.query.planner.plannode.ProjectNode; +import org.apache.pinot.query.planner.plannode.SetOpNode; +import org.apache.pinot.query.planner.plannode.SortNode; +import org.apache.pinot.query.planner.plannode.TableScanNode; +import org.apache.pinot.query.planner.plannode.ValueNode; +import org.apache.pinot.query.planner.plannode.WindowNode; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + + +/** + * This utility class can be used to find equivalent stages in the query plan. + * + * Equivalent stages are stages that represent the same job to be done. These stages can be potentially optimized to + * execute that job only once in a special stage that broadcast the results to all the equivalent stages. + */ +public class EquivalentStagesFinder { + public static final Logger LOGGER = LoggerFactory.getLogger(EquivalentStagesFinder.class); + + private EquivalentStagesFinder() { + } + + public static GroupedStages findEquivalentStages(MailboxSendNode root) { Review Comment: I think there are several questions in this paragraph. > Will this be called with the mailbox that sends data to the broker's receiving mailbox in stage 0? I don't think this matter. That stage will be, by definition, different to all other stages, so the only difference if that stage is being send is whether the stage 0 is included in GroupedStages or not. The reason why the root stage will always be different than the others is that in a tree a node cannot be equivalent to any of its (recursive) children. > every time we visit a mailbox send node in the depth first visitor here, we'll check whether it is equivalent to every other known mailbox send node Yes, where: - mailbox send is equivalent to stage. We can use one term or the other. - each _known_ mailbox is know because it has been already visited. > in the equivalence check we visit all the inputs and even traverse mailbox / stage boundaries right? Yes. > And since this is a depth first visitor, the lower (in the tree, but with a higher stage ID) mailbox send nodes will already have been visited so we should directly be able to check whether those children mailbox send nodes belong to the same equivalence group or not - is this understanding correct? Yes, that property reduce the cost of the algorithm sensibely. In fact even we traverse stage boundaries, whenever we do that the next comparison will not be recursive because it will touch a send mailbox and therefore it must be in the list of visited stages. We can use this property to simplify NodeEquivalence by adding the logic to compare not visted nodes in `areEquivalent` and keep `visitMailboxSend` as the trivial comparison. -- 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: commits-unsubscr...@pinot.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@pinot.apache.org For additional commands, e-mail: commits-h...@pinot.apache.org
