You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "Lordworms (via GitHub)" <gi...@apache.org> on 2024/10/22 02:17:20 UTC
[PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Lordworms opened a new pull request, #13054:
URL: https://github.com/apache/datafusion/pull/13054
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
Closes #7955
## Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
## What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
## Are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
-->
## Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please add the `api change` label.
-->
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1810153790
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
+ .into_iter()
+ .try_fold::<_, _, Result<_, DataFusionError>>(
+ (Vec::new(), Vec::new()),
+ |(mut max_acc, mut min_acc), data_type| {
+ max_acc.push(MaxAccumulator::try_new(data_type)?);
+ min_acc.push(MinAccumulator::try_new(data_type)?);
+ Ok((max_acc, min_acc))
+ },
+ )?;
+
+ Ok(Self {
+ columns,
+ build_side_names,
+ inner: Mutex::new(DynamicFilterInfoInner {
+ max_accumulators,
+ min_accumulators,
+ final_expr: None,
+ batch_count: total_batches,
+ processed_partitions: HashSet::with_capacity(total_batches),
+ }),
+ })
+ }
+
+ // Set the final expression for the filter
+ pub fn with_final_expr(self, expr: Arc<dyn PhysicalExpr>) -> Self {
+ self.inner.lock().final_expr = Some(expr);
+ self
+ }
+
+ // Merge a new batch of data and update the max and min accumulators
+ pub fn merge_batch_and_check_finalized(
+ &self,
+ records: &RecordBatch,
+ partition: usize,
+ ) -> Result<bool, DataFusionError> {
+ let mut inner = self.inner.lock();
+
+ if inner.final_expr.is_some() {
+ return Ok(true);
+ }
+
+ if !inner.processed_partitions.insert(partition) {
+ return Ok(false);
+ }
+
+ inner.batch_count = inner.batch_count.saturating_sub(1);
+ if records.num_rows() == 0 {
+ return Ok(false);
+ }
+
+ let finalize = inner.batch_count == 0;
+
+ let schema = records.schema();
+ let columns = records.columns();
+ for (i, _) in self.columns.iter().enumerate() {
+ let index = schema.index_of(&self.build_side_names[i])?;
+ let column_data = &columns[index];
+ inner.max_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ inner.min_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ }
+
+ if finalize {
+ drop(inner);
+ self.finalize_filter()?;
+ return Ok(true);
+ }
+
+ Ok(false)
+ }
+
+ // Finalize the filter by creating the final expression
+ fn finalize_filter(&self) -> Result<(), DataFusionError> {
+ let mut inner = self.inner.lock();
+ let filter_expr =
+ self.columns.iter().enumerate().try_fold::<_, _, Result<
+ Option<Arc<dyn PhysicalExpr>>,
+ DataFusionError,
+ >>(None, |acc, (i, column)| {
+ let max_value = inner.max_accumulators[i].evaluate()?;
+ let min_value = inner.min_accumulators[i].evaluate()?;
+
+ let max_scalar = max_value.clone();
+ let min_scalar = min_value.clone();
+
+ let max_expr: Arc<dyn PhysicalExpr> = Arc::new(Literal::new(max_scalar));
+ let min_expr: Arc<dyn PhysicalExpr> = Arc::new(Literal::new(min_scalar));
+
+ let range_condition: Arc<dyn PhysicalExpr> = Arc::new(BinaryExpr::new(
Review Comment:
Maybe it makes sense to not create a dynamic filter in certain conditions, eg min is minimum value of data type, max is maximum of datatype (will not filter out any rows)?
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
+ .into_iter()
+ .try_fold::<_, _, Result<_, DataFusionError>>(
+ (Vec::new(), Vec::new()),
+ |(mut max_acc, mut min_acc), data_type| {
+ max_acc.push(MaxAccumulator::try_new(data_type)?);
+ min_acc.push(MinAccumulator::try_new(data_type)?);
+ Ok((max_acc, min_acc))
+ },
+ )?;
+
+ Ok(Self {
+ columns,
+ build_side_names,
+ inner: Mutex::new(DynamicFilterInfoInner {
+ max_accumulators,
+ min_accumulators,
+ final_expr: None,
+ batch_count: total_batches,
+ processed_partitions: HashSet::with_capacity(total_batches),
+ }),
+ })
+ }
+
+ // Set the final expression for the filter
+ pub fn with_final_expr(self, expr: Arc<dyn PhysicalExpr>) -> Self {
+ self.inner.lock().final_expr = Some(expr);
+ self
+ }
+
+ // Merge a new batch of data and update the max and min accumulators
+ pub fn merge_batch_and_check_finalized(
+ &self,
+ records: &RecordBatch,
+ partition: usize,
+ ) -> Result<bool, DataFusionError> {
+ let mut inner = self.inner.lock();
+
+ if inner.final_expr.is_some() {
+ return Ok(true);
+ }
+
+ if !inner.processed_partitions.insert(partition) {
+ return Ok(false);
+ }
+
+ inner.batch_count = inner.batch_count.saturating_sub(1);
+ if records.num_rows() == 0 {
+ return Ok(false);
+ }
+
+ let finalize = inner.batch_count == 0;
+
+ let schema = records.schema();
+ let columns = records.columns();
+ for (i, _) in self.columns.iter().enumerate() {
+ let index = schema.index_of(&self.build_side_names[i])?;
+ let column_data = &columns[index];
+ inner.max_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ inner.min_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ }
+
+ if finalize {
+ drop(inner);
+ self.finalize_filter()?;
+ return Ok(true);
+ }
+
+ Ok(false)
+ }
+
+ // Finalize the filter by creating the final expression
+ fn finalize_filter(&self) -> Result<(), DataFusionError> {
+ let mut inner = self.inner.lock();
+ let filter_expr =
+ self.columns.iter().enumerate().try_fold::<_, _, Result<
+ Option<Arc<dyn PhysicalExpr>>,
+ DataFusionError,
+ >>(None, |acc, (i, column)| {
+ let max_value = inner.max_accumulators[i].evaluate()?;
+ let min_value = inner.min_accumulators[i].evaluate()?;
+
+ let max_scalar = max_value.clone();
+ let min_scalar = min_value.clone();
+
+ let max_expr: Arc<dyn PhysicalExpr> = Arc::new(Literal::new(max_scalar));
+ let min_expr: Arc<dyn PhysicalExpr> = Arc::new(Literal::new(min_scalar));
+
+ let range_condition: Arc<dyn PhysicalExpr> = Arc::new(BinaryExpr::new(
Review Comment:
Maybe it makes sense to not create a dynamic filter in certain conditions, eg min is minimum value of data type, max is maximum of datatype (expression will not filter out any rows)?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1810705503
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
Review Comment:
I wonder if we can just use `batches: Vec<Vec<Arc<dyn Array>>>` here and compute any filters from that?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] closed pull request #13054: JoinOptimization: Add build side pushdown to probe side
URL: https://github.com/apache/datafusion/pull/13054
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#issuecomment-2436724056
> > How would you display them in sources? The dynamic filter will only be added during execution, so it will only be available through e.g. ParquetExec after loading the build side.
>
> Doesn’t `JoinFilterPushdown: PhysicalOptimizerRule` modify the `dynamic_filters` in `ParquetExec` during optimizations? My intention was to ensure the rule is functioning correctly and to prevent this feature from being silently broken in the future. Perhaps we could add some unit tests to verify this.
Maybe I can show them in 'explain analyze'
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "simonvandel (via GitHub)" <gi...@apache.org>.
simonvandel commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1810049282
##########
datafusion/core/src/physical_optimizer/join_filter_pushdown.rs:
##########
@@ -0,0 +1,112 @@
+// 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.
+
+//! Pushdown the dynamic join filters down to scan execution if there is any
+
+use std::sync::Arc;
+
+#[cfg(feature = "parquet")]
+use crate::datasource::physical_plan::ParquetExec;
+use crate::physical_plan::ExecutionPlan;
+use crate::{config::ConfigOptions, error::Result, physical_plan::joins::HashJoinExec};
+use datafusion_common::tree_node::{Transformed, TransformedResult};
+use datafusion_physical_optimizer::PhysicalOptimizerRule;
+use datafusion_physical_plan::joins::DynamicFilterInfo;
+
+/// this rule used for pushing the build side statistic down to probe phase
+#[derive(Default, Debug)]
+pub struct JoinFilterPushdown {}
+
+impl JoinFilterPushdown {
+ #[allow(missing_docs)]
+ pub fn new() -> Self {
+ Self {}
+ }
+}
+
+impl PhysicalOptimizerRule for JoinFilterPushdown {
+ fn optimize(
+ &self,
+ plan: Arc<dyn ExecutionPlan>,
+ config: &ConfigOptions,
+ ) -> Result<Arc<dyn ExecutionPlan>> {
+ if !config.optimizer.dynamic_join_pushdown {
+ return Ok(plan);
+ }
+ optimize_impl(plan, &mut None).data()
+ }
+
+ fn name(&self) -> &str {
+ "JoinFilterPushdown"
+ }
+
+ fn schema_check(&self) -> bool {
+ true
+ }
+}
+
+fn optimize_impl(
+ plan: Arc<dyn ExecutionPlan>,
+ join_filters: &mut Option<Arc<DynamicFilterInfo>>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ if let Some(hashjoin_exec) = plan.as_any().downcast_ref::<HashJoinExec>() {
+ join_filters.clone_from(&hashjoin_exec.dynamic_filters_pushdown);
+ let new_right = optimize_impl(hashjoin_exec.right.clone(), join_filters)?;
+ if new_right.transformed {
+ let new_hash_join = HashJoinExec::try_new(
+ hashjoin_exec.left().clone(),
+ new_right.data,
+ hashjoin_exec.on.clone(),
+ hashjoin_exec.filter().cloned(),
+ hashjoin_exec.join_type(),
+ hashjoin_exec.projection.clone(),
+ *hashjoin_exec.partition_mode(),
+ hashjoin_exec.null_equals_null(),
+ )?
+ .with_dynamic_filter_info(hashjoin_exec.dynamic_filters_pushdown.clone());
+ return Ok(Transformed::yes(Arc::new(new_hash_join)));
+ }
+ Ok(Transformed::no(plan))
+ } else if let Some(parquet_exec) = plan.as_any().downcast_ref::<ParquetExec>() {
Review Comment:
I wonder if we could allow this cool optimization on any ExecutionPlan by adding the "with_dynamic_filter" to the ExecutionPlan?
Maybe also a "supports_dynamic_filter" to know when to call "with_dynamic_filter".
So same principle as the existing static filter pushdown setup.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1811366669
##########
datafusion/core/src/physical_optimizer/join_filter_pushdown.rs:
##########
@@ -0,0 +1,112 @@
+// 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.
+
+//! Pushdown the dynamic join filters down to scan execution if there is any
+
+use std::sync::Arc;
+
+#[cfg(feature = "parquet")]
+use crate::datasource::physical_plan::ParquetExec;
+use crate::physical_plan::ExecutionPlan;
+use crate::{config::ConfigOptions, error::Result, physical_plan::joins::HashJoinExec};
+use datafusion_common::tree_node::{Transformed, TransformedResult};
+use datafusion_physical_optimizer::PhysicalOptimizerRule;
+use datafusion_physical_plan::joins::DynamicFilterInfo;
+
+/// this rule used for pushing the build side statistic down to probe phase
+#[derive(Default, Debug)]
+pub struct JoinFilterPushdown {}
+
+impl JoinFilterPushdown {
+ #[allow(missing_docs)]
+ pub fn new() -> Self {
+ Self {}
+ }
+}
+
+impl PhysicalOptimizerRule for JoinFilterPushdown {
+ fn optimize(
+ &self,
+ plan: Arc<dyn ExecutionPlan>,
+ config: &ConfigOptions,
+ ) -> Result<Arc<dyn ExecutionPlan>> {
+ if !config.optimizer.dynamic_join_pushdown {
+ return Ok(plan);
+ }
+ optimize_impl(plan, &mut None).data()
+ }
+
+ fn name(&self) -> &str {
+ "JoinFilterPushdown"
+ }
+
+ fn schema_check(&self) -> bool {
+ true
+ }
+}
+
+fn optimize_impl(
+ plan: Arc<dyn ExecutionPlan>,
+ join_filters: &mut Option<Arc<DynamicFilterInfo>>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ if let Some(hashjoin_exec) = plan.as_any().downcast_ref::<HashJoinExec>() {
+ join_filters.clone_from(&hashjoin_exec.dynamic_filters_pushdown);
+ let new_right = optimize_impl(hashjoin_exec.right.clone(), join_filters)?;
+ if new_right.transformed {
+ let new_hash_join = HashJoinExec::try_new(
+ hashjoin_exec.left().clone(),
+ new_right.data,
+ hashjoin_exec.on.clone(),
+ hashjoin_exec.filter().cloned(),
+ hashjoin_exec.join_type(),
+ hashjoin_exec.projection.clone(),
+ *hashjoin_exec.partition_mode(),
+ hashjoin_exec.null_equals_null(),
+ )?
+ .with_dynamic_filter_info(hashjoin_exec.dynamic_filters_pushdown.clone());
+ return Ok(Transformed::yes(Arc::new(new_hash_join)));
+ }
+ Ok(Transformed::no(plan))
+ } else if let Some(parquet_exec) = plan.as_any().downcast_ref::<ParquetExec>() {
Review Comment:
Sure, I'll. refactor this, but currently support ParquetExec first? Since I think for other PhysicalScanExec, the way to add dynamic filter is to add a FilterExec above, but in parquet, we could utilize the predicate to add filters dynamically?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1810141838
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
Review Comment:
I wonder if we can use a logical plan instead of manually invoking min/max accumulators? Not sure if that makes sense :)
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
Review Comment:
I wonder if we can use a logical plan / physical plan instead of manually invoking min/max accumulators? Not sure if that makes sense :)
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1810178550
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
+ .into_iter()
+ .try_fold::<_, _, Result<_, DataFusionError>>(
+ (Vec::new(), Vec::new()),
+ |(mut max_acc, mut min_acc), data_type| {
+ max_acc.push(MaxAccumulator::try_new(data_type)?);
+ min_acc.push(MinAccumulator::try_new(data_type)?);
+ Ok((max_acc, min_acc))
+ },
+ )?;
+
+ Ok(Self {
+ columns,
+ build_side_names,
+ inner: Mutex::new(DynamicFilterInfoInner {
+ max_accumulators,
+ min_accumulators,
+ final_expr: None,
+ batch_count: total_batches,
+ processed_partitions: HashSet::with_capacity(total_batches),
+ }),
+ })
+ }
+
+ // Set the final expression for the filter
+ pub fn with_final_expr(self, expr: Arc<dyn PhysicalExpr>) -> Self {
+ self.inner.lock().final_expr = Some(expr);
+ self
+ }
+
+ // Merge a new batch of data and update the max and min accumulators
+ pub fn merge_batch_and_check_finalized(
+ &self,
+ records: &RecordBatch,
+ partition: usize,
+ ) -> Result<bool, DataFusionError> {
+ let mut inner = self.inner.lock();
+
+ if inner.final_expr.is_some() {
+ return Ok(true);
+ }
+
+ if !inner.processed_partitions.insert(partition) {
+ return Ok(false);
+ }
+
+ inner.batch_count = inner.batch_count.saturating_sub(1);
+ if records.num_rows() == 0 {
+ return Ok(false);
+ }
+
+ let finalize = inner.batch_count == 0;
+
+ let schema = records.schema();
+ let columns = records.columns();
+ for (i, _) in self.columns.iter().enumerate() {
+ let index = schema.index_of(&self.build_side_names[i])?;
+ let column_data = &columns[index];
+ inner.max_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ inner.min_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ }
+
+ if finalize {
+ drop(inner);
+ self.finalize_filter()?;
+ return Ok(true);
+ }
+
+ Ok(false)
+ }
+
+ // Finalize the filter by creating the final expression
+ fn finalize_filter(&self) -> Result<(), DataFusionError> {
+ let mut inner = self.inner.lock();
+ let filter_expr =
+ self.columns.iter().enumerate().try_fold::<_, _, Result<
+ Option<Arc<dyn PhysicalExpr>>,
+ DataFusionError,
+ >>(None, |acc, (i, column)| {
+ let max_value = inner.max_accumulators[i].evaluate()?;
+ let min_value = inner.min_accumulators[i].evaluate()?;
+
+ let max_scalar = max_value.clone();
+ let min_scalar = min_value.clone();
+
+ let max_expr: Arc<dyn PhysicalExpr> = Arc::new(Literal::new(max_scalar));
Review Comment:
For readability, it's better to use `LogicalPlan` here and convert to physical? This might also support some optimizations for free...
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1811141278
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
Review Comment:
This makes it pretty easy to support additional filters. It's pretty easy to add `InListExpr` filter based on this (I have some code locally).
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1811912253
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
+ .into_iter()
+ .try_fold::<_, _, Result<_, DataFusionError>>(
+ (Vec::new(), Vec::new()),
+ |(mut max_acc, mut min_acc), data_type| {
+ max_acc.push(MaxAccumulator::try_new(data_type)?);
+ min_acc.push(MinAccumulator::try_new(data_type)?);
+ Ok((max_acc, min_acc))
+ },
+ )?;
+
+ Ok(Self {
+ columns,
+ build_side_names,
+ inner: Mutex::new(DynamicFilterInfoInner {
+ max_accumulators,
+ min_accumulators,
+ final_expr: None,
+ batch_count: total_batches,
+ processed_partitions: HashSet::with_capacity(total_batches),
+ }),
+ })
+ }
+
+ // Set the final expression for the filter
+ pub fn with_final_expr(self, expr: Arc<dyn PhysicalExpr>) -> Self {
+ self.inner.lock().final_expr = Some(expr);
+ self
+ }
+
+ // Merge a new batch of data and update the max and min accumulators
+ pub fn merge_batch_and_check_finalized(
+ &self,
+ records: &RecordBatch,
+ partition: usize,
+ ) -> Result<bool, DataFusionError> {
+ let mut inner = self.inner.lock();
+
+ if inner.final_expr.is_some() {
+ return Ok(true);
+ }
+
+ if !inner.processed_partitions.insert(partition) {
+ return Ok(false);
+ }
+
+ inner.batch_count = inner.batch_count.saturating_sub(1);
+ if records.num_rows() == 0 {
Review Comment:
yes, it happens sometime, haven't check the reason
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1811370182
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
Review Comment:
I don't know either, First I want to try using min/max ScalarFunction, but the ScalaFunction translation from logical_expr to physical_expr is not implemented yet... I guess using accumulator would be more Intuitive?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1825101656
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
Review Comment:
I can do that
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#issuecomment-2477812838
<img width="568" alt="image" src="https://github.com/user-attachments/assets/0d4015d8-435f-4f57-bb1f-fb17a574dd48">
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#issuecomment-2428074119
For query like
```
select count(*) from part join lineitem on l_partkey=p_partkey where p_partkey > 10;
```
and with data scale like

The execution time is 5 times faster
before:

after:

--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1811372047
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
Review Comment:
I agree, I'll refactor it, after that maybe I can combine your commit.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1813994423
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -243,6 +231,65 @@ impl DynamicFilterInfo {
}
}
+macro_rules! process_min_max {
+ ($ARRAYS:expr, $ARRAY_TYPE:ty, $SCALAR_TY:ident, $NATIVE_TYPE:ty) => {{
+ let mut min_val: Option<$NATIVE_TYPE> = None;
+ let mut max_val: Option<$NATIVE_TYPE> = None;
+
+ for array in $ARRAYS {
+ if let Some(primitive_array) = array.as_any().downcast_ref::<$ARRAY_TYPE>() {
+ let batch_min = min(primitive_array);
+ let batch_max = max(primitive_array);
+
+ min_val = match (min_val, batch_min) {
+ (Some(a), Some(b)) => Some(if a.is_lt(b) { a } else { b }),
+ (None, Some(b)) => Some(b),
+ (Some(a), None) => Some(a),
+ (None, None) => None,
+ };
+
+ max_val = match (max_val, batch_max) {
+ (Some(a), Some(b)) => Some(if a.is_gt(b) { a } else { b }),
+ (None, Some(b)) => Some(b),
+ (Some(a), None) => Some(a),
+ (None, None) => None,
+ };
+ }
+ }
+ Ok((
+ ScalarValue::$SCALAR_TY(min_val),
+ ScalarValue::$SCALAR_TY(max_val),
+ ))
+ }};
+}
+
+/// Currently only support numeric data types so generate a range filter
+fn compute_min_max_from_batches(
+ arrays: &[Arc<dyn Array>],
+) -> Result<(ScalarValue, ScalarValue), DataFusionError> {
+ if arrays.is_empty() {
+ return exec_err!("should not be an empty array");
+ }
+
+ let data_type = arrays[0].data_type();
+ match data_type {
+ DataType::Int8 => process_min_max!(arrays, Int8Array, Int8, i8),
Review Comment:
I'll add it.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1811979076
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
Review Comment:
Cool, after changes have cooled down a bit I can update and share my branch.
Adding something like that on top is actually quite easy after making the `make_set` helper public:
```
+ let col =
+ Arc::<datafusion_physical_expr::expressions::Column>::clone(column);
+ let batches: Vec<&dyn Array> = inner.batches[i]
+ .iter()
+ .map(|x| x as &dyn Array)
+ .collect();
+
+ // use inlist rather than min/max, use some threshold to avoid big inputs
+ // TODO: big inputs could be using bloom filter
+ if batches.iter().map(|x|x.len()).sum::<usize>() < 100 {
+ let batches = concat(batches.as_slice())?;
+ let set = make_set(&batches)?;
+
+ let unique_condition = InListExpr::new(col, vec![], false, Some(set));
+ condition = Arc::new(BinaryExpr::new(
+ Arc::new(unique_condition),
Operator::And,
- range_condition,
- ))
- as Arc<dyn PhysicalExpr>)),
- None => Ok(Some(range_condition)),
+ condition,
+ ));
}
+ Ok(Some(condition))
```
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#issuecomment-2434455783
Could you update the display of sources to include these pushed-down filters? I believe it would be more clear if we could see them clearly in the output (I'm also curious to see how this impacts the test plans). Additionally, are there any benchmark results you could share with us?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#issuecomment-2434908233
> > How would you display them in sources? The dynamic filter will only be added during execution, so it will only be available through e.g. ParquetExec after loading the build side.
>
> Doesn’t `JoinFilterPushdown: PhysicalOptimizerRule` modify the `dynamic_filters` in `ParquetExec` during optimizations? My intention was to ensure the rule is functioning correctly and to prevent this feature from being silently broken in the future. Perhaps we could add some unit tests to verify this.
Yes that's correct, just wanted to stress the actual filter isn't added during the optimization phase, only a "placeholder" that might be filled with some filter expressions during execution. So it only shows `ParquetExec` might be filtered dynamically from the join values.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1810178550
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
+ .into_iter()
+ .try_fold::<_, _, Result<_, DataFusionError>>(
+ (Vec::new(), Vec::new()),
+ |(mut max_acc, mut min_acc), data_type| {
+ max_acc.push(MaxAccumulator::try_new(data_type)?);
+ min_acc.push(MinAccumulator::try_new(data_type)?);
+ Ok((max_acc, min_acc))
+ },
+ )?;
+
+ Ok(Self {
+ columns,
+ build_side_names,
+ inner: Mutex::new(DynamicFilterInfoInner {
+ max_accumulators,
+ min_accumulators,
+ final_expr: None,
+ batch_count: total_batches,
+ processed_partitions: HashSet::with_capacity(total_batches),
+ }),
+ })
+ }
+
+ // Set the final expression for the filter
+ pub fn with_final_expr(self, expr: Arc<dyn PhysicalExpr>) -> Self {
+ self.inner.lock().final_expr = Some(expr);
+ self
+ }
+
+ // Merge a new batch of data and update the max and min accumulators
+ pub fn merge_batch_and_check_finalized(
+ &self,
+ records: &RecordBatch,
+ partition: usize,
+ ) -> Result<bool, DataFusionError> {
+ let mut inner = self.inner.lock();
+
+ if inner.final_expr.is_some() {
+ return Ok(true);
+ }
+
+ if !inner.processed_partitions.insert(partition) {
+ return Ok(false);
+ }
+
+ inner.batch_count = inner.batch_count.saturating_sub(1);
+ if records.num_rows() == 0 {
+ return Ok(false);
+ }
+
+ let finalize = inner.batch_count == 0;
+
+ let schema = records.schema();
+ let columns = records.columns();
+ for (i, _) in self.columns.iter().enumerate() {
+ let index = schema.index_of(&self.build_side_names[i])?;
+ let column_data = &columns[index];
+ inner.max_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ inner.min_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ }
+
+ if finalize {
+ drop(inner);
+ self.finalize_filter()?;
+ return Ok(true);
+ }
+
+ Ok(false)
+ }
+
+ // Finalize the filter by creating the final expression
+ fn finalize_filter(&self) -> Result<(), DataFusionError> {
+ let mut inner = self.inner.lock();
+ let filter_expr =
+ self.columns.iter().enumerate().try_fold::<_, _, Result<
+ Option<Arc<dyn PhysicalExpr>>,
+ DataFusionError,
+ >>(None, |acc, (i, column)| {
+ let max_value = inner.max_accumulators[i].evaluate()?;
+ let min_value = inner.min_accumulators[i].evaluate()?;
+
+ let max_scalar = max_value.clone();
+ let min_scalar = min_value.clone();
+
+ let max_expr: Arc<dyn PhysicalExpr> = Arc::new(Literal::new(max_scalar));
Review Comment:
For readability, it's better to use `LogicalPlan` here and convert to physical? This might also do some optimizations for free...
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1833251081
##########
datafusion/physical-plan/src/joins/hash_join.rs:
##########
@@ -1406,12 +1403,24 @@ impl HashJoinStream {
self.hashes_buffer.resize(batch.num_rows(), 0);
create_hashes(&keys_values, &self.random_state, &mut self.hashes_buffer)?;
+ let (filtered_batch, filtered_hashes) =
+ if let Some(dynamic_filter) = &self.dynamic_filter_info {
+ dynamic_filter.filter_probe_batch(
Review Comment:
> Hmm, `filter_probe_batch` shouldn't be added as filter on the `hash_join` but rather as `PhysicalExpr` (returning boolean) to filter the `ParquetExec`
Sure, I'll refactor that, other than that I found a problem with ParquetExec here https://github.com/apache/datafusion/issues/13298
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#issuecomment-2475214828
I repushed with an adaptive way to generate dynamic filter(when unique value exceed a threshold, generate range filter, otherwise inlist filter), and due to https://github.com/apache/datafusion/issues/13298 I didn't pushdown the filter down to parquet scan, I pushed the filter down to file stream, also tried with random data like
```python
import pandas as pd
import numpy as np
part = pd.DataFrame({
'p_partkey': np.random.randint(10, 21, size=1000),
'p_brand': np.random.choice(['Brand#1', 'Brand#2', 'Brand#3'], 1000),
'p_container': np.random.choice(['SM BOX', 'LG BOX', 'MED BOX'], 1000)
})
lineitem = pd.DataFrame({
'l_partkey': np.random.randint(1, 1000001, size=100000000),
'l_quantity': np.random.uniform(1, 50, size=100000000),
'l_extendedprice': np.random.uniform(100, 10000, size=100000000)
})
```
and the result is

which only get like 40% of increase, I think we could try to pushdown filter down to parquet scan if the filter for reading parquet is optimized.
Also perhaps we need to improve performance of Inlist since when I tried 20 elements, the performance is 5 times slower than using range filter.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1810149645
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
+ .into_iter()
+ .try_fold::<_, _, Result<_, DataFusionError>>(
+ (Vec::new(), Vec::new()),
+ |(mut max_acc, mut min_acc), data_type| {
+ max_acc.push(MaxAccumulator::try_new(data_type)?);
+ min_acc.push(MinAccumulator::try_new(data_type)?);
+ Ok((max_acc, min_acc))
+ },
+ )?;
+
+ Ok(Self {
+ columns,
+ build_side_names,
+ inner: Mutex::new(DynamicFilterInfoInner {
+ max_accumulators,
+ min_accumulators,
+ final_expr: None,
+ batch_count: total_batches,
+ processed_partitions: HashSet::with_capacity(total_batches),
+ }),
+ })
+ }
+
+ // Set the final expression for the filter
+ pub fn with_final_expr(self, expr: Arc<dyn PhysicalExpr>) -> Self {
+ self.inner.lock().final_expr = Some(expr);
+ self
+ }
+
+ // Merge a new batch of data and update the max and min accumulators
+ pub fn merge_batch_and_check_finalized(
+ &self,
+ records: &RecordBatch,
+ partition: usize,
+ ) -> Result<bool, DataFusionError> {
+ let mut inner = self.inner.lock();
+
+ if inner.final_expr.is_some() {
+ return Ok(true);
+ }
+
+ if !inner.processed_partitions.insert(partition) {
+ return Ok(false);
+ }
+
+ inner.batch_count = inner.batch_count.saturating_sub(1);
+ if records.num_rows() == 0 {
Review Comment:
Couldn't the input of a join partition be empty, in which case it will never be finalized?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1810153790
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
+ .into_iter()
+ .try_fold::<_, _, Result<_, DataFusionError>>(
+ (Vec::new(), Vec::new()),
+ |(mut max_acc, mut min_acc), data_type| {
+ max_acc.push(MaxAccumulator::try_new(data_type)?);
+ min_acc.push(MinAccumulator::try_new(data_type)?);
+ Ok((max_acc, min_acc))
+ },
+ )?;
+
+ Ok(Self {
+ columns,
+ build_side_names,
+ inner: Mutex::new(DynamicFilterInfoInner {
+ max_accumulators,
+ min_accumulators,
+ final_expr: None,
+ batch_count: total_batches,
+ processed_partitions: HashSet::with_capacity(total_batches),
+ }),
+ })
+ }
+
+ // Set the final expression for the filter
+ pub fn with_final_expr(self, expr: Arc<dyn PhysicalExpr>) -> Self {
+ self.inner.lock().final_expr = Some(expr);
+ self
+ }
+
+ // Merge a new batch of data and update the max and min accumulators
+ pub fn merge_batch_and_check_finalized(
+ &self,
+ records: &RecordBatch,
+ partition: usize,
+ ) -> Result<bool, DataFusionError> {
+ let mut inner = self.inner.lock();
+
+ if inner.final_expr.is_some() {
+ return Ok(true);
+ }
+
+ if !inner.processed_partitions.insert(partition) {
+ return Ok(false);
+ }
+
+ inner.batch_count = inner.batch_count.saturating_sub(1);
+ if records.num_rows() == 0 {
+ return Ok(false);
+ }
+
+ let finalize = inner.batch_count == 0;
+
+ let schema = records.schema();
+ let columns = records.columns();
+ for (i, _) in self.columns.iter().enumerate() {
+ let index = schema.index_of(&self.build_side_names[i])?;
+ let column_data = &columns[index];
+ inner.max_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ inner.min_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ }
+
+ if finalize {
+ drop(inner);
+ self.finalize_filter()?;
+ return Ok(true);
+ }
+
+ Ok(false)
+ }
+
+ // Finalize the filter by creating the final expression
+ fn finalize_filter(&self) -> Result<(), DataFusionError> {
+ let mut inner = self.inner.lock();
+ let filter_expr =
+ self.columns.iter().enumerate().try_fold::<_, _, Result<
+ Option<Arc<dyn PhysicalExpr>>,
+ DataFusionError,
+ >>(None, |acc, (i, column)| {
+ let max_value = inner.max_accumulators[i].evaluate()?;
+ let min_value = inner.min_accumulators[i].evaluate()?;
+
+ let max_scalar = max_value.clone();
+ let min_scalar = min_value.clone();
+
+ let max_expr: Arc<dyn PhysicalExpr> = Arc::new(Literal::new(max_scalar));
+ let min_expr: Arc<dyn PhysicalExpr> = Arc::new(Literal::new(min_scalar));
+
+ let range_condition: Arc<dyn PhysicalExpr> = Arc::new(BinaryExpr::new(
Review Comment:
Maybe it makes sense to not create a dynamic filter in certain conditions, eg `min==max` (will not filter out any rows)?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1833251081
##########
datafusion/physical-plan/src/joins/hash_join.rs:
##########
@@ -1406,12 +1403,24 @@ impl HashJoinStream {
self.hashes_buffer.resize(batch.num_rows(), 0);
create_hashes(&keys_values, &self.random_state, &mut self.hashes_buffer)?;
+ let (filtered_batch, filtered_hashes) =
+ if let Some(dynamic_filter) = &self.dynamic_filter_info {
+ dynamic_filter.filter_probe_batch(
Review Comment:
> Hmm, `filter_probe_batch` shouldn't be added as filter on the `hash_join` but rather as `PhysicalExpr` (returning boolean) to filter the `ParquetExec`
Sure, I'll refactor that, other than that I found a problem with ParquetExec here https://github.com/apache/datafusion/issues/13298. If the pushdown cost is much more than do it directly. I am not sure whether it is a 'optimization' or not....
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1824670958
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
Review Comment:
Something that would be fun to try is creating a `PhysicalExpr` from the `JoinHashMap` - that way we can build a good filter without any overhead.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1811912253
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
+ .into_iter()
+ .try_fold::<_, _, Result<_, DataFusionError>>(
+ (Vec::new(), Vec::new()),
+ |(mut max_acc, mut min_acc), data_type| {
+ max_acc.push(MaxAccumulator::try_new(data_type)?);
+ min_acc.push(MinAccumulator::try_new(data_type)?);
+ Ok((max_acc, min_acc))
+ },
+ )?;
+
+ Ok(Self {
+ columns,
+ build_side_names,
+ inner: Mutex::new(DynamicFilterInfoInner {
+ max_accumulators,
+ min_accumulators,
+ final_expr: None,
+ batch_count: total_batches,
+ processed_partitions: HashSet::with_capacity(total_batches),
+ }),
+ })
+ }
+
+ // Set the final expression for the filter
+ pub fn with_final_expr(self, expr: Arc<dyn PhysicalExpr>) -> Self {
+ self.inner.lock().final_expr = Some(expr);
+ self
+ }
+
+ // Merge a new batch of data and update the max and min accumulators
+ pub fn merge_batch_and_check_finalized(
+ &self,
+ records: &RecordBatch,
+ partition: usize,
+ ) -> Result<bool, DataFusionError> {
+ let mut inner = self.inner.lock();
+
+ if inner.final_expr.is_some() {
+ return Ok(true);
+ }
+
+ if !inner.processed_partitions.insert(partition) {
+ return Ok(false);
+ }
+
+ inner.batch_count = inner.batch_count.saturating_sub(1);
+ if records.num_rows() == 0 {
Review Comment:
yes, it happens sometime, haven't got a way to solve it yet
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1810116130
##########
datafusion/core/src/datasource/physical_plan/parquet/mod.rs:
##########
@@ -711,10 +724,15 @@ impl DisplayAs for ParquetExec {
)
})
.unwrap_or_default();
-
+ let dynamic_filter =
+ format!("dynamic_filter: {:?}", self.dynamic_filters);
Review Comment:
I think it's best to only write this if available. + Would be good to implement `Display` for `DynamicFilterInfo` as well
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1810178550
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
+ .into_iter()
+ .try_fold::<_, _, Result<_, DataFusionError>>(
+ (Vec::new(), Vec::new()),
+ |(mut max_acc, mut min_acc), data_type| {
+ max_acc.push(MaxAccumulator::try_new(data_type)?);
+ min_acc.push(MinAccumulator::try_new(data_type)?);
+ Ok((max_acc, min_acc))
+ },
+ )?;
+
+ Ok(Self {
+ columns,
+ build_side_names,
+ inner: Mutex::new(DynamicFilterInfoInner {
+ max_accumulators,
+ min_accumulators,
+ final_expr: None,
+ batch_count: total_batches,
+ processed_partitions: HashSet::with_capacity(total_batches),
+ }),
+ })
+ }
+
+ // Set the final expression for the filter
+ pub fn with_final_expr(self, expr: Arc<dyn PhysicalExpr>) -> Self {
+ self.inner.lock().final_expr = Some(expr);
+ self
+ }
+
+ // Merge a new batch of data and update the max and min accumulators
+ pub fn merge_batch_and_check_finalized(
+ &self,
+ records: &RecordBatch,
+ partition: usize,
+ ) -> Result<bool, DataFusionError> {
+ let mut inner = self.inner.lock();
+
+ if inner.final_expr.is_some() {
+ return Ok(true);
+ }
+
+ if !inner.processed_partitions.insert(partition) {
+ return Ok(false);
+ }
+
+ inner.batch_count = inner.batch_count.saturating_sub(1);
+ if records.num_rows() == 0 {
+ return Ok(false);
+ }
+
+ let finalize = inner.batch_count == 0;
+
+ let schema = records.schema();
+ let columns = records.columns();
+ for (i, _) in self.columns.iter().enumerate() {
+ let index = schema.index_of(&self.build_side_names[i])?;
+ let column_data = &columns[index];
+ inner.max_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ inner.min_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ }
+
+ if finalize {
+ drop(inner);
+ self.finalize_filter()?;
+ return Ok(true);
+ }
+
+ Ok(false)
+ }
+
+ // Finalize the filter by creating the final expression
+ fn finalize_filter(&self) -> Result<(), DataFusionError> {
+ let mut inner = self.inner.lock();
+ let filter_expr =
+ self.columns.iter().enumerate().try_fold::<_, _, Result<
+ Option<Arc<dyn PhysicalExpr>>,
+ DataFusionError,
+ >>(None, |acc, (i, column)| {
+ let max_value = inner.max_accumulators[i].evaluate()?;
+ let min_value = inner.min_accumulators[i].evaluate()?;
+
+ let max_scalar = max_value.clone();
+ let min_scalar = min_value.clone();
+
+ let max_expr: Arc<dyn PhysicalExpr> = Arc::new(Literal::new(max_scalar));
Review Comment:
For readability, it's better to use `LogicalPlan` here and convert to physical? This might also support some optimizations for free (e.g. expression simplification)...
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#issuecomment-2463427276
I decided not to create PhysicalExpr for it since the only benefit of creating extra PhysicalExpr is try to pushdown it to ParquetScan, but currently the adaptive feature of pushdown predicate is not done yet. I'll just try to push build side hash down to FileStream which could make this PR much much simpler
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1831783035
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
Review Comment:
So the idea is just to filter out values where the hash isn't present in the hashmap, that way we can filter out most values.
It's fine to focus on min/max first, the positive side is that evaluation is fast, but it won't filter out a lot of values if the min/max range from the left side is as big as the right side (regardless of number of values being much smaller).
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
Review Comment:
So the idea is just to filter out values where the hash isn't present in the hashmap, that way we can filter out most values.
It's fine to focus on min/max first, the positive side is that evaluation is fast, but it won't filter out a lot of values if the min/max range from the left side is as big as the right side (regardless of number of values being much smaller on left side).
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1832226325
##########
datafusion/physical-plan/src/joins/hash_join.rs:
##########
@@ -1406,12 +1403,24 @@ impl HashJoinStream {
self.hashes_buffer.resize(batch.num_rows(), 0);
create_hashes(&keys_values, &self.random_state, &mut self.hashes_buffer)?;
+ let (filtered_batch, filtered_hashes) =
+ if let Some(dynamic_filter) = &self.dynamic_filter_info {
+ dynamic_filter.filter_probe_batch(
Review Comment:
Hmm, `filter_probe_batch` shouldn't be added as filter on the `hash_join` but rather as `PhysicalExpr` (returning boolean) to filter the `ParquetExec`
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1811372356
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
+ .into_iter()
+ .try_fold::<_, _, Result<_, DataFusionError>>(
+ (Vec::new(), Vec::new()),
+ |(mut max_acc, mut min_acc), data_type| {
+ max_acc.push(MaxAccumulator::try_new(data_type)?);
+ min_acc.push(MinAccumulator::try_new(data_type)?);
+ Ok((max_acc, min_acc))
+ },
+ )?;
+
+ Ok(Self {
+ columns,
+ build_side_names,
+ inner: Mutex::new(DynamicFilterInfoInner {
+ max_accumulators,
+ min_accumulators,
+ final_expr: None,
+ batch_count: total_batches,
+ processed_partitions: HashSet::with_capacity(total_batches),
+ }),
+ })
+ }
+
+ // Set the final expression for the filter
+ pub fn with_final_expr(self, expr: Arc<dyn PhysicalExpr>) -> Self {
+ self.inner.lock().final_expr = Some(expr);
+ self
+ }
+
+ // Merge a new batch of data and update the max and min accumulators
+ pub fn merge_batch_and_check_finalized(
+ &self,
+ records: &RecordBatch,
+ partition: usize,
+ ) -> Result<bool, DataFusionError> {
+ let mut inner = self.inner.lock();
+
+ if inner.final_expr.is_some() {
+ return Ok(true);
+ }
+
+ if !inner.processed_partitions.insert(partition) {
+ return Ok(false);
+ }
+
+ inner.batch_count = inner.batch_count.saturating_sub(1);
+ if records.num_rows() == 0 {
+ return Ok(false);
+ }
+
+ let finalize = inner.batch_count == 0;
+
+ let schema = records.schema();
+ let columns = records.columns();
+ for (i, _) in self.columns.iter().enumerate() {
+ let index = schema.index_of(&self.build_side_names[i])?;
+ let column_data = &columns[index];
+ inner.max_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ inner.min_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ }
+
+ if finalize {
+ drop(inner);
+ self.finalize_filter()?;
+ return Ok(true);
+ }
+
+ Ok(false)
+ }
+
+ // Finalize the filter by creating the final expression
+ fn finalize_filter(&self) -> Result<(), DataFusionError> {
+ let mut inner = self.inner.lock();
+ let filter_expr =
+ self.columns.iter().enumerate().try_fold::<_, _, Result<
+ Option<Arc<dyn PhysicalExpr>>,
+ DataFusionError,
+ >>(None, |acc, (i, column)| {
+ let max_value = inner.max_accumulators[i].evaluate()?;
+ let min_value = inner.min_accumulators[i].evaluate()?;
+
+ let max_scalar = max_value.clone();
+ let min_scalar = min_value.clone();
+
+ let max_expr: Arc<dyn PhysicalExpr> = Arc::new(Literal::new(max_scalar));
Review Comment:
got it.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1811370714
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
+ .into_iter()
+ .try_fold::<_, _, Result<_, DataFusionError>>(
+ (Vec::new(), Vec::new()),
+ |(mut max_acc, mut min_acc), data_type| {
+ max_acc.push(MaxAccumulator::try_new(data_type)?);
+ min_acc.push(MinAccumulator::try_new(data_type)?);
+ Ok((max_acc, min_acc))
+ },
+ )?;
+
+ Ok(Self {
+ columns,
+ build_side_names,
+ inner: Mutex::new(DynamicFilterInfoInner {
+ max_accumulators,
+ min_accumulators,
+ final_expr: None,
+ batch_count: total_batches,
+ processed_partitions: HashSet::with_capacity(total_batches),
+ }),
+ })
+ }
+
+ // Set the final expression for the filter
+ pub fn with_final_expr(self, expr: Arc<dyn PhysicalExpr>) -> Self {
+ self.inner.lock().final_expr = Some(expr);
+ self
+ }
+
+ // Merge a new batch of data and update the max and min accumulators
+ pub fn merge_batch_and_check_finalized(
+ &self,
+ records: &RecordBatch,
+ partition: usize,
+ ) -> Result<bool, DataFusionError> {
+ let mut inner = self.inner.lock();
+
+ if inner.final_expr.is_some() {
+ return Ok(true);
+ }
+
+ if !inner.processed_partitions.insert(partition) {
+ return Ok(false);
+ }
+
+ inner.batch_count = inner.batch_count.saturating_sub(1);
+ if records.num_rows() == 0 {
Review Comment:
Haven't try that, I'll add a test for that
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#issuecomment-2428075067
@Dandandan Sorry for the late response, I have reinvested it and format the code. Really appreciate your suggestion. Thanks a lot.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#issuecomment-2428351362
Really nice @Lordworms , will have a good look later today.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1810119820
##########
datafusion/core/src/physical_optimizer/join_filter_pushdown.rs:
##########
@@ -0,0 +1,112 @@
+// 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.
+
+//! Pushdown the dynamic join filters down to scan execution if there is any
+
+use std::sync::Arc;
+
+#[cfg(feature = "parquet")]
+use crate::datasource::physical_plan::ParquetExec;
+use crate::physical_plan::ExecutionPlan;
+use crate::{config::ConfigOptions, error::Result, physical_plan::joins::HashJoinExec};
+use datafusion_common::tree_node::{Transformed, TransformedResult};
+use datafusion_physical_optimizer::PhysicalOptimizerRule;
+use datafusion_physical_plan::joins::DynamicFilterInfo;
+
+/// this rule used for pushing the build side statistic down to probe phase
+#[derive(Default, Debug)]
+pub struct JoinFilterPushdown {}
+
+impl JoinFilterPushdown {
+ #[allow(missing_docs)]
+ pub fn new() -> Self {
+ Self {}
+ }
+}
+
+impl PhysicalOptimizerRule for JoinFilterPushdown {
+ fn optimize(
+ &self,
+ plan: Arc<dyn ExecutionPlan>,
+ config: &ConfigOptions,
+ ) -> Result<Arc<dyn ExecutionPlan>> {
+ if !config.optimizer.dynamic_join_pushdown {
+ return Ok(plan);
+ }
+ optimize_impl(plan, &mut None).data()
+ }
+
+ fn name(&self) -> &str {
+ "JoinFilterPushdown"
+ }
+
+ fn schema_check(&self) -> bool {
+ true
+ }
+}
+
+fn optimize_impl(
+ plan: Arc<dyn ExecutionPlan>,
+ join_filters: &mut Option<Arc<DynamicFilterInfo>>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ if let Some(hashjoin_exec) = plan.as_any().downcast_ref::<HashJoinExec>() {
+ join_filters.clone_from(&hashjoin_exec.dynamic_filters_pushdown);
+ let new_right = optimize_impl(hashjoin_exec.right.clone(), join_filters)?;
+ if new_right.transformed {
+ let new_hash_join = HashJoinExec::try_new(
+ hashjoin_exec.left().clone(),
+ new_right.data,
+ hashjoin_exec.on.clone(),
+ hashjoin_exec.filter().cloned(),
+ hashjoin_exec.join_type(),
+ hashjoin_exec.projection.clone(),
+ *hashjoin_exec.partition_mode(),
+ hashjoin_exec.null_equals_null(),
+ )?
+ .with_dynamic_filter_info(hashjoin_exec.dynamic_filters_pushdown.clone());
+ return Ok(Transformed::yes(Arc::new(new_hash_join)));
+ }
+ Ok(Transformed::no(plan))
+ } else if let Some(parquet_exec) = plan.as_any().downcast_ref::<ParquetExec>() {
Review Comment:
That makes a lot of sense
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1810118665
##########
datafusion/core/src/physical_optimizer/join_filter_pushdown.rs:
##########
@@ -0,0 +1,112 @@
+// 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.
+
+//! Pushdown the dynamic join filters down to scan execution if there is any
+
+use std::sync::Arc;
+
+#[cfg(feature = "parquet")]
+use crate::datasource::physical_plan::ParquetExec;
+use crate::physical_plan::ExecutionPlan;
+use crate::{config::ConfigOptions, error::Result, physical_plan::joins::HashJoinExec};
+use datafusion_common::tree_node::{Transformed, TransformedResult};
+use datafusion_physical_optimizer::PhysicalOptimizerRule;
+use datafusion_physical_plan::joins::DynamicFilterInfo;
+
+/// this rule used for pushing the build side statistic down to probe phase
+#[derive(Default, Debug)]
+pub struct JoinFilterPushdown {}
+
+impl JoinFilterPushdown {
+ #[allow(missing_docs)]
+ pub fn new() -> Self {
+ Self {}
+ }
+}
+
+impl PhysicalOptimizerRule for JoinFilterPushdown {
Review Comment:
This is executed during plan time, won't it be reasonable to execute this during execution of `HashJoin` after build side is loaded?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1810153790
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
+ .into_iter()
+ .try_fold::<_, _, Result<_, DataFusionError>>(
+ (Vec::new(), Vec::new()),
+ |(mut max_acc, mut min_acc), data_type| {
+ max_acc.push(MaxAccumulator::try_new(data_type)?);
+ min_acc.push(MinAccumulator::try_new(data_type)?);
+ Ok((max_acc, min_acc))
+ },
+ )?;
+
+ Ok(Self {
+ columns,
+ build_side_names,
+ inner: Mutex::new(DynamicFilterInfoInner {
+ max_accumulators,
+ min_accumulators,
+ final_expr: None,
+ batch_count: total_batches,
+ processed_partitions: HashSet::with_capacity(total_batches),
+ }),
+ })
+ }
+
+ // Set the final expression for the filter
+ pub fn with_final_expr(self, expr: Arc<dyn PhysicalExpr>) -> Self {
+ self.inner.lock().final_expr = Some(expr);
+ self
+ }
+
+ // Merge a new batch of data and update the max and min accumulators
+ pub fn merge_batch_and_check_finalized(
+ &self,
+ records: &RecordBatch,
+ partition: usize,
+ ) -> Result<bool, DataFusionError> {
+ let mut inner = self.inner.lock();
+
+ if inner.final_expr.is_some() {
+ return Ok(true);
+ }
+
+ if !inner.processed_partitions.insert(partition) {
+ return Ok(false);
+ }
+
+ inner.batch_count = inner.batch_count.saturating_sub(1);
+ if records.num_rows() == 0 {
+ return Ok(false);
+ }
+
+ let finalize = inner.batch_count == 0;
+
+ let schema = records.schema();
+ let columns = records.columns();
+ for (i, _) in self.columns.iter().enumerate() {
+ let index = schema.index_of(&self.build_side_names[i])?;
+ let column_data = &columns[index];
+ inner.max_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ inner.min_accumulators[i]
+ .update_batch(&[Arc::<dyn arrow_array::Array>::clone(column_data)])?;
+ }
+
+ if finalize {
+ drop(inner);
+ self.finalize_filter()?;
+ return Ok(true);
+ }
+
+ Ok(false)
+ }
+
+ // Finalize the filter by creating the final expression
+ fn finalize_filter(&self) -> Result<(), DataFusionError> {
+ let mut inner = self.inner.lock();
+ let filter_expr =
+ self.columns.iter().enumerate().try_fold::<_, _, Result<
+ Option<Arc<dyn PhysicalExpr>>,
+ DataFusionError,
+ >>(None, |acc, (i, column)| {
+ let max_value = inner.max_accumulators[i].evaluate()?;
+ let min_value = inner.min_accumulators[i].evaluate()?;
+
+ let max_scalar = max_value.clone();
+ let min_scalar = min_value.clone();
+
+ let max_expr: Arc<dyn PhysicalExpr> = Arc::new(Literal::new(max_scalar));
+ let min_expr: Arc<dyn PhysicalExpr> = Arc::new(Literal::new(min_scalar));
+
+ let range_condition: Arc<dyn PhysicalExpr> = Arc::new(BinaryExpr::new(
Review Comment:
Maybe it makes sense to not create a dynamic filter in certain conditions, eg min==Datatype::MIN / max==Datatype::Max (will not filter out any rows)?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1811367135
##########
datafusion/core/src/datasource/physical_plan/parquet/mod.rs:
##########
@@ -711,10 +724,15 @@ impl DisplayAs for ParquetExec {
)
})
.unwrap_or_default();
-
+ let dynamic_filter =
+ format!("dynamic_filter: {:?}", self.dynamic_filters);
Review Comment:
Sorry for that, this is for debug use, I'll refactor it
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#issuecomment-2436827458
I think it is ready now
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1831785310
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
Review Comment:
> So the idea is just to filter out values where the hash isn't present in the hashmap, that way we can filter out most values.
I got it, I was think about rebuild original array using hashmap and records 😅...... I'll add the logic
> It's fine to focus on min/max first, the positive side is that evaluation is fast, but it won't filter out a lot of values if the min/max range from the left side is as big as the right side (regardless of number of values being much smaller on left side).
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
Review Comment:
> So the idea is just to filter out values where the hash isn't present in the hashmap, that way we can filter out most values.
I got it, I was think about rebuild original array using hashmap and records 😅...... I'll add the logic
> It's fine to focus on min/max first, the positive side is that evaluation is fast, but it won't filter out a lot of values if the min/max range from the left side is as big as the right side (regardless of number of values being much smaller on left side).
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#issuecomment-2461159231
Another weird thing I found after rebasing main is that the ParquetExec time seems to be wrong
without optimization
<img width="1413" alt="Screenshot 2024-11-06 at 5 50 47 PM" src="https://github.com/user-attachments/assets/6207c16e-69e2-4565-898b-70a9e0e3e806">
with optimization
<img width="1418" alt="Screenshot 2024-11-06 at 5 51 02 PM" src="https://github.com/user-attachments/assets/64b87eb4-3a2c-4df7-9e64-b5627c7984f7">
The total time with optimzation is 30s, while it is 19s without processing, which means adding the dynamic filter added 10s on ParquetExec. Seems like there's something wrong with parquet filter pushdown
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1831707315
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
Review Comment:
I was trying to do this , but since hash function is one-way function, I can only combine the record batches to get original value... I didn't see the benefits here, I think one way to reduce overhead is just supporting max/min filter here(as what duckdb does)... If there is a better way, please tell me. I am getting a little confused here. Thanks
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1833251081
##########
datafusion/physical-plan/src/joins/hash_join.rs:
##########
@@ -1406,12 +1403,24 @@ impl HashJoinStream {
self.hashes_buffer.resize(batch.num_rows(), 0);
create_hashes(&keys_values, &self.random_state, &mut self.hashes_buffer)?;
+ let (filtered_batch, filtered_hashes) =
+ if let Some(dynamic_filter) = &self.dynamic_filter_info {
+ dynamic_filter.filter_probe_batch(
Review Comment:
> Hmm, `filter_probe_batch` shouldn't be added as filter on the `hash_join` but rather as `PhysicalExpr` (returning boolean) to filter the `ParquetExec`
Sure, I'll refactor that, other than that I found a problem with ParquetExec after rebase the main https://github.com/apache/datafusion/issues/13298. If the pushdown cost is much more than do it directly. I am not sure whether it is a 'optimization' or not....
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#issuecomment-2434605384
> Could you update the display of sources to include these pushed-down filters? I believe it would be more clear if we could see them clearly in the output (I'm also curious to see how this impacts the test plans). Additionally, are there any benchmark results you could share with us?
How would you display them in sources? The dynamic filter will only be added during execution, so it will only be available through e.g. ParquetExec after loading the build side.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1811366669
##########
datafusion/core/src/physical_optimizer/join_filter_pushdown.rs:
##########
@@ -0,0 +1,112 @@
+// 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.
+
+//! Pushdown the dynamic join filters down to scan execution if there is any
+
+use std::sync::Arc;
+
+#[cfg(feature = "parquet")]
+use crate::datasource::physical_plan::ParquetExec;
+use crate::physical_plan::ExecutionPlan;
+use crate::{config::ConfigOptions, error::Result, physical_plan::joins::HashJoinExec};
+use datafusion_common::tree_node::{Transformed, TransformedResult};
+use datafusion_physical_optimizer::PhysicalOptimizerRule;
+use datafusion_physical_plan::joins::DynamicFilterInfo;
+
+/// this rule used for pushing the build side statistic down to probe phase
+#[derive(Default, Debug)]
+pub struct JoinFilterPushdown {}
+
+impl JoinFilterPushdown {
+ #[allow(missing_docs)]
+ pub fn new() -> Self {
+ Self {}
+ }
+}
+
+impl PhysicalOptimizerRule for JoinFilterPushdown {
+ fn optimize(
+ &self,
+ plan: Arc<dyn ExecutionPlan>,
+ config: &ConfigOptions,
+ ) -> Result<Arc<dyn ExecutionPlan>> {
+ if !config.optimizer.dynamic_join_pushdown {
+ return Ok(plan);
+ }
+ optimize_impl(plan, &mut None).data()
+ }
+
+ fn name(&self) -> &str {
+ "JoinFilterPushdown"
+ }
+
+ fn schema_check(&self) -> bool {
+ true
+ }
+}
+
+fn optimize_impl(
+ plan: Arc<dyn ExecutionPlan>,
+ join_filters: &mut Option<Arc<DynamicFilterInfo>>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ if let Some(hashjoin_exec) = plan.as_any().downcast_ref::<HashJoinExec>() {
+ join_filters.clone_from(&hashjoin_exec.dynamic_filters_pushdown);
+ let new_right = optimize_impl(hashjoin_exec.right.clone(), join_filters)?;
+ if new_right.transformed {
+ let new_hash_join = HashJoinExec::try_new(
+ hashjoin_exec.left().clone(),
+ new_right.data,
+ hashjoin_exec.on.clone(),
+ hashjoin_exec.filter().cloned(),
+ hashjoin_exec.join_type(),
+ hashjoin_exec.projection.clone(),
+ *hashjoin_exec.partition_mode(),
+ hashjoin_exec.null_equals_null(),
+ )?
+ .with_dynamic_filter_info(hashjoin_exec.dynamic_filters_pushdown.clone());
+ return Ok(Transformed::yes(Arc::new(new_hash_join)));
+ }
+ Ok(Transformed::no(plan))
+ } else if let Some(parquet_exec) = plan.as_any().downcast_ref::<ParquetExec>() {
Review Comment:
Sure, I'll. refactor this, but currently support ParquetExec first?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1811568285
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -243,6 +231,65 @@ impl DynamicFilterInfo {
}
}
+macro_rules! process_min_max {
+ ($ARRAYS:expr, $ARRAY_TYPE:ty, $SCALAR_TY:ident, $NATIVE_TYPE:ty) => {{
+ let mut min_val: Option<$NATIVE_TYPE> = None;
+ let mut max_val: Option<$NATIVE_TYPE> = None;
+
+ for array in $ARRAYS {
+ if let Some(primitive_array) = array.as_any().downcast_ref::<$ARRAY_TYPE>() {
+ let batch_min = min(primitive_array);
+ let batch_max = max(primitive_array);
+
+ min_val = match (min_val, batch_min) {
+ (Some(a), Some(b)) => Some(if a.is_lt(b) { a } else { b }),
+ (None, Some(b)) => Some(b),
+ (Some(a), None) => Some(a),
+ (None, None) => None,
+ };
+
+ max_val = match (max_val, batch_max) {
+ (Some(a), Some(b)) => Some(if a.is_gt(b) { a } else { b }),
+ (None, Some(b)) => Some(b),
+ (Some(a), None) => Some(a),
+ (None, None) => None,
+ };
+ }
+ }
+ Ok((
+ ScalarValue::$SCALAR_TY(min_val),
+ ScalarValue::$SCALAR_TY(max_val),
+ ))
+ }};
+}
+
+/// Currently only support numeric data types so generate a range filter
+fn compute_min_max_from_batches(
+ arrays: &[Arc<dyn Array>],
+) -> Result<(ScalarValue, ScalarValue), DataFusionError> {
+ if arrays.is_empty() {
+ return exec_err!("should not be an empty array");
+ }
+
+ let data_type = arrays[0].data_type();
+ match data_type {
+ DataType::Int8 => process_min_max!(arrays, Int8Array, Int8, i8),
Review Comment:
Currently support numeric types columns(which adds a range filter), would support string types in next PR(add IN (xx, xx) filter)
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Lordworms (via GitHub)" <gi...@apache.org>.
Lordworms commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1813300852
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -0,0 +1,267 @@
+// 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 arrow::array::AsArray;
+use arrow::compute::filter_record_batch;
+use arrow::datatypes::DataType;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{exec_err, DataFusionError};
+use datafusion_expr::Accumulator;
+use datafusion_expr::Operator;
+use datafusion_functions_aggregate::min_max::{MaxAccumulator, MinAccumulator};
+use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
+use datafusion_physical_expr::PhysicalExpr;
+use hashbrown::HashSet;
+use parking_lot::Mutex;
+use std::fmt;
+use std::sync::Arc;
+
+pub struct DynamicFilterInfo {
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ inner: Mutex<DynamicFilterInfoInner>,
+}
+
+struct DynamicFilterInfoInner {
+ max_accumulators: Vec<MaxAccumulator>,
+ min_accumulators: Vec<MinAccumulator>,
+ final_expr: Option<Arc<dyn PhysicalExpr>>,
+ batch_count: usize,
+ processed_partitions: HashSet<usize>,
+}
+
+impl fmt::Debug for DynamicFilterInfo {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("DynamicFilterInfo")
+ .field("columns", &self.columns)
+ .field("inner", &"<locked>")
+ .finish()
+ }
+}
+
+impl DynamicFilterInfo {
+ // Create a new DynamicFilterInfo instance
+ pub fn try_new(
+ columns: Vec<Arc<Column>>,
+ build_side_names: Vec<String>,
+ data_types: Vec<&DataType>,
+ total_batches: usize,
+ ) -> Result<Self, DataFusionError> {
+ let (max_accumulators, min_accumulators) = data_types
+ .into_iter()
+ .try_fold::<_, _, Result<_, DataFusionError>>(
+ (Vec::new(), Vec::new()),
+ |(mut max_acc, mut min_acc), data_type| {
+ max_acc.push(MaxAccumulator::try_new(data_type)?);
+ min_acc.push(MinAccumulator::try_new(data_type)?);
+ Ok((max_acc, min_acc))
+ },
+ )?;
+
+ Ok(Self {
+ columns,
+ build_side_names,
+ inner: Mutex::new(DynamicFilterInfoInner {
+ max_accumulators,
+ min_accumulators,
+ final_expr: None,
+ batch_count: total_batches,
+ processed_partitions: HashSet::with_capacity(total_batches),
+ }),
+ })
+ }
+
+ // Set the final expression for the filter
+ pub fn with_final_expr(self, expr: Arc<dyn PhysicalExpr>) -> Self {
+ self.inner.lock().final_expr = Some(expr);
+ self
+ }
+
+ // Merge a new batch of data and update the max and min accumulators
+ pub fn merge_batch_and_check_finalized(
+ &self,
+ records: &RecordBatch,
+ partition: usize,
+ ) -> Result<bool, DataFusionError> {
+ let mut inner = self.inner.lock();
+
+ if inner.final_expr.is_some() {
+ return Ok(true);
+ }
+
+ if !inner.processed_partitions.insert(partition) {
+ return Ok(false);
+ }
+
+ inner.batch_count = inner.batch_count.saturating_sub(1);
+ if records.num_rows() == 0 {
Review Comment:
I added a new judge "if a partition id has been recorded and it return empty batch again, we treat it as an empty partition and return true"
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#issuecomment-2434890005
> How would you display them in sources? The dynamic filter will only be added during execution, so it will only be available through e.g. ParquetExec after loading the build side.
Doesn’t `JoinFilterPushdown: PhysicalOptimizerRule` modify the `dynamic_filters` in `ParquetExec` during optimizations? My intention was to ensure the rule is functioning correctly and to prevent this feature from being silently broken in the future. Perhaps we could add some unit tests to verify 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.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#discussion_r1811959953
##########
datafusion/physical-plan/src/joins/dynamic_filters.rs:
##########
@@ -243,6 +231,65 @@ impl DynamicFilterInfo {
}
}
+macro_rules! process_min_max {
+ ($ARRAYS:expr, $ARRAY_TYPE:ty, $SCALAR_TY:ident, $NATIVE_TYPE:ty) => {{
+ let mut min_val: Option<$NATIVE_TYPE> = None;
+ let mut max_val: Option<$NATIVE_TYPE> = None;
+
+ for array in $ARRAYS {
+ if let Some(primitive_array) = array.as_any().downcast_ref::<$ARRAY_TYPE>() {
+ let batch_min = min(primitive_array);
+ let batch_max = max(primitive_array);
+
+ min_val = match (min_val, batch_min) {
+ (Some(a), Some(b)) => Some(if a.is_lt(b) { a } else { b }),
+ (None, Some(b)) => Some(b),
+ (Some(a), None) => Some(a),
+ (None, None) => None,
+ };
+
+ max_val = match (max_val, batch_max) {
+ (Some(a), Some(b)) => Some(if a.is_gt(b) { a } else { b }),
+ (None, Some(b)) => Some(b),
+ (Some(a), None) => Some(a),
+ (None, None) => None,
+ };
+ }
+ }
+ Ok((
+ ScalarValue::$SCALAR_TY(min_val),
+ ScalarValue::$SCALAR_TY(max_val),
+ ))
+ }};
+}
+
+/// Currently only support numeric data types so generate a range filter
+fn compute_min_max_from_batches(
+ arrays: &[Arc<dyn Array>],
+) -> Result<(ScalarValue, ScalarValue), DataFusionError> {
+ if arrays.is_empty() {
+ return exec_err!("should not be an empty array");
+ }
+
+ let data_type = arrays[0].data_type();
+ match data_type {
+ DataType::Int8 => process_min_max!(arrays, Int8Array, Int8, i8),
Review Comment:
String types could perform range as well, no?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] JoinOptimization: Add build side pushdown to probe side [datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #13054:
URL: https://github.com/apache/datafusion/pull/13054#issuecomment-2591473073
Thank you for your contribution. Unfortunately, this pull request is stale because it has been open 60 days with no activity. Please remove the stale label or comment or this will be closed in 7 days.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org