2010YOUY01 commented on code in PR #22050: URL: https://github.com/apache/datafusion/pull/22050#discussion_r3217545330
########## datafusion/optimizer/src/reorder_join/join_graph.rs: ########## @@ -0,0 +1,710 @@ +// 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. + +use std::sync::Arc; + +use datafusion_common::{DataFusionError, NullEquality, Result, plan_err}; +use datafusion_expr::{ + Expr, JoinType, LogicalPlan, + utils::{check_all_columns_from_schema, split_conjunction_owned}, +}; + +pub type NodeId = usize; + +pub struct Node { + pub plan: Arc<LogicalPlan>, + pub(crate) connections: Vec<EdgeId>, +} + +impl Node { + pub fn connections(&self) -> &[EdgeId] { + &self.connections + } + + pub(crate) fn connection_with<'graph>( + &self, + node_id: NodeId, + join_graph: &'graph JoinGraph, + ) -> Option<&'graph Edge> { + self.connections + .iter() + .filter_map(|edge_id| join_graph.get_edge(*edge_id)) + .find(move |x| x.nodes.contains(&node_id)) + } + + pub fn neighbours(&self, node_id: NodeId, join_graph: &JoinGraph) -> Vec<NodeId> { + self.connections + .iter() + .filter_map(|edge_id| join_graph.get_edge(*edge_id)) + .flat_map(|edge| edge.nodes) + .filter(|&id| id != node_id) + .collect() + } +} + +pub type EdgeId = usize; + +pub struct Edge { + pub nodes: [NodeId; 2], + pub on: Vec<(Expr, Expr)>, + pub join_type: JoinType, + pub null_equality: NullEquality, +} + +pub struct JoinGraph { + pub(crate) nodes: VecMap<Node>, + edges: VecMap<Edge>, + /// Non-equi predicates hoisted out of decomposed `Join.filter` clauses + /// and out of `LogicalPlan::Filter` nodes that sit between joins. + /// The enumerator must reapply these on top of the reordered plan. + filters: Vec<Expr>, Review Comment: I think these filters would be better kept inside the `Edge`. These filters should represent expressions that reference both sides of the join, for example `t1.v1 > t2.v1`. Filters that reference only one table, such as `t1.v1 > 0`, should ideally have already been pushed down. I am not 100% sure that is always guaranteed, so we may need to decide how to handle those cases... Some advanced optimizers can include non-equi join predicates in the search space and optimize them holistically using specialized join operators. Our initial implementation is likely simpler and may only consider equi-joins. However, keeping the non-equi join conditions inside the `Edge` can still make RBO easier. For example, we have a specialized join operator that handles inequality conditions efficiently, we could use override configurations to force that specialized join when an inequality condition is present. ########## datafusion/optimizer/src/reorder_join/join_graph.rs: ########## @@ -0,0 +1,710 @@ +// 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. + +use std::sync::Arc; + +use datafusion_common::{DataFusionError, NullEquality, Result, plan_err}; +use datafusion_expr::{ + Expr, JoinType, LogicalPlan, + utils::{check_all_columns_from_schema, split_conjunction_owned}, +}; + +pub type NodeId = usize; + +pub struct Node { + pub plan: Arc<LogicalPlan>, Review Comment: Now the statistics API is implemented on the `ExecutionPlan`, its needed for join reordering 🤔 I'm wondering how can we solve this issue. -- 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] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
