Skip to content

Commit 1d1ec1e

Browse files
author
Gene Bordegaray
committed
Support co-partitioned range inner equi joins (apache#23184)
- Closes apache#23183. - Part of apache#22395. DataFusion can represent source-declared range partitioning, but partitioned hash joins still required hash partitioned inputs. So an inner join on compatible range-partitioned keys would insert unnecessary hash repartitions, even when each left/right partition already covered the same key domain. This PR adds a partitioning requirement that means "equal key values are co-located" . I was calling this "compatibility" but found we can satisfy the requirement with looser conditions. Other systems call this "co-location" or "co-partitioning" ([trino](https://trino.io/docs/current/admin/properties-optimizer.html#optimizer-colocated-joins-enabled), [spark](https://spark.apache.org/docs/latest/sql-performance-tuning.html#storage-partition-join)). Which they (and now I am proposing) define as when both sides of a join are already partitioned so matching key values appear in corresponding partitions, so we can join partition pairs directly without repartitioning the sides. This lets "co-partitioned" range inputs satisfy inner partitioned hash joins. This will also be applicable to other join types and operators but kept the first PR thin to keep scope more reviewable. - Adds `Distribution::KeyPartitioned(Vec<Arc<dyn PhysicalExpr>>)` as a public distribution requirement. - `HashPartitioned([a])` means rows must be partitioned by hash on `a`. - `KeyPartitioned([a])` means rows with equal `a` values must be co-located, but the partitioning algorithm may be hash, range, or another compatible scheme. - Example: ```text Hash([left.a], 3) satisfies KeyPartitioned([left.a]) Range([right.b ASC], [(10), (20)], 3) satisfies KeyPartitioned([right.b]) ``` - Adds `Partitioning::co_partitioned_with(...)` to validate that two independently satisfying partitionings also can be paired by partition index. - Examples: - Accepted: both sides satisfy their own key requirement and have matching range boundaries. ```text left: Range([a ASC], [(10), (20)], 3), required KeyPartitioned([a]) right: Range([b ASC], [(10), (20)], 3), required KeyPartitioned([b]) ``` - Accepted: both sides satisfy their own key requirement and have matching hash partition counts. ```text left: Hash([a], 3), required KeyPartitioned([a]) right: Hash([b], 3), required KeyPartitioned([b]) ``` - Rejected: both sides satisfy their own key requirement, but range boundaries differ. ```text left: Range([a ASC], [(10), (20)], 3), required KeyPartitioned([a]) right: Range([b ASC], [(15), (20)], 3), required KeyPartitioned([b]) ``` - Rejected: both sides satisfy their own key requirement, but partition counts differ. ```text left: Hash([a], 3), required KeyPartitioned([a]) right: Hash([b], 4), required KeyPartitioned([b]) ``` - Changes inner partitioned `HashJoinExec` requirements from `HashPartitioned` to `KeyPartitioned`. - All other hash joins still require `HashPartitioned` for now. - Updates `EnforceDistribution` so co-partitioned range inner joins avoid repartitioning. - Examples: - Compatible range partitioning: no repartition is inserted because partitions can be joined by index. ```text HashJoinExec: mode=Partitioned, join_type=Inner, on=[(a, b)] DataSourceExec: output_partitioning=Range([a ASC], [(10), (20)], 3) DataSourceExec: output_partitioning=Range([b ASC], [(10), (20)], 3) ``` - Incompatible range boundaries: both sides are repartitioned by hash because partition `i` does not represent the same key domain on both sides. ```text HashJoinExec: mode=Partitioned, join_type=Inner, on=[(a, b)] RepartitionExec: partitioning=Hash([a], target_partitions) DataSourceExec: output_partitioning=Range([a ASC], [(10), (20)], 3) RepartitionExec: partitioning=Hash([b], target_partitions) DataSourceExec: output_partitioning=Range([b ASC], [(15), (20)], 3) ``` - Mismatched hash partition counts: both sides are forced to the target hash partition count so partition indexes line up. ```text HashJoinExec: mode=Partitioned, join_type=Inner, on=[(a, b)] RepartitionExec: partitioning=Hash([a], target_partitions) DataSourceExec: output_partitioning=Hash([a], 11) RepartitionExec: partitioning=Hash([b], target_partitions) DataSourceExec: output_partitioning=Hash([b], 12) ``` - Non-inner joins: range inputs still get hash repartitioning because only inner partitioned hash joins use `KeyPartitioned` in this PR. ```text HashJoinExec: mode=Partitioned, join_type=Left, on=[(a, b)] RepartitionExec: partitioning=Hash([a], target_partitions) DataSourceExec: output_partitioning=Range([a ASC], [(10), (20)], 3) RepartitionExec: partitioning=Hash([b], target_partitions) DataSourceExec: output_partitioning=Range([b ASC], [(10), (20)], 3) ``` - Keeps partitioned dynamic filter pushdown restricted to hash-compatible routing. - Compatible range partitioning can satisfy the join, but dynamic filters still route by hash, so range/range partitioned joins disable dynamic filters. - Degrades range join output partitioning to `UnknownPartitioning(n)` rather than erroring. Adding this behavior would need more tests and careful thought about, I think its safert o just degrade for first PR. Yes. - `KeyPartitioned` satisfaction for hash and range partitioning. - `co_partitioned_with` for compatible and incompatible range/hash partitioning. - `EnforceDistribution` behavior for: - compatible range joins avoiding hash repartitioning - incompatible range bounds rehashing - mismatched hash partition counts rehashing - non-inner range joins rehashing - sanity checking for invalid partitioned hash joins. - dynamic filter rejection for range partitioning, preserved file partitions, and mismatched hash counts. - sqllogictest coverage for range-partitioned joins avoiding hash repartitioning and non-range joins still repartitioning. Yes. This PR changes public physical planning APIs: - Adds `Distribution::KeyPartitioned`. - Adds `Partitioning::co_partitioned_with`. - **NOTE**: This replaces the previous partition compatibility API with the new co-partitioning API. Since the compatibility API was never in a release I believe this is ok to do (lesson learned to not make API change until ew have definitive consumer). - Affects users matching exhaustively on `Distribution`.
1 parent d3a9271 commit 1d1ec1e

38 files changed

Lines changed: 1762 additions & 892 deletions

File tree

‎datafusion/catalog-listing/src/table.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -802,7 +802,7 @@ impl ListingTable {
802802
.map(|part_file| async {
803803
let part_file = part_file?;
804804
let (statistics, ordering) = if self.options.collect_stat {
805-
self.do_collect_statistics_and_ordering(ctx, &store, &part_file)
805+
self.do_collect_statistics_and_ordering(ctx, store, &part_file)
806806
.await?
807807
} else {
808808
(Arc::new(Statistics::new_unknown(&self.file_schema)), None)

‎datafusion/core/src/datasource/listing/table.rs‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -147,7 +147,6 @@ mod tests {
147147
use datafusion_physical_expr::expressions::{Column, binary};
148148
use datafusion_physical_expr_common::sort_expr::LexOrdering;
149149
use datafusion_physical_plan::empty::EmptyExec;
150-
use datafusion_physical_plan::statistics::StatisticsArgs;
151150
use datafusion_physical_plan::{
152151
ExecutionPlanProperties, Partitioning, RangePartitioning, SplitPoint, collect,
153152
};

‎datafusion/core/tests/physical_optimizer/enforce_distribution.rs‎

Lines changed: 52 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -268,8 +268,12 @@ impl ExecutionPlan for SinglePartitionMaintainsOrderExec {
268268
vec![&self.input]
269269
}
270270

271-
fn required_input_distribution(&self) -> Vec<Distribution> {
272-
vec![Distribution::SinglePartition]
271+
fn input_distribution_requirements(
272+
&self,
273+
) -> datafusion_physical_plan::InputDistributionRequirements {
274+
datafusion_physical_plan::InputDistributionRequirements::new(vec![
275+
Distribution::SinglePartition,
276+
])
273277
}
274278

275279
fn maintains_input_order(&self) -> Vec<bool> {
@@ -826,7 +830,9 @@ fn inner_range_join_keeps_range_partitioning() -> Result<()> {
826830
JoinType::Inner,
827831
);
828832

829-
let plan = TestConfig::default().to_plan(join, &DISTRIB_DISTRIB_SORT);
833+
let plan = TestConfig::default()
834+
.with_query_execution_partitions(3)
835+
.to_plan(join, &DISTRIB_DISTRIB_SORT);
830836

831837
assert_plan!(
832838
plan,
@@ -1013,6 +1019,49 @@ fn range_grouping_set_aggregate_rehashes_with_grouping_id() -> Result<()> {
10131019
Ok(())
10141020
}
10151021

1022+
#[test]
1023+
fn range_inner_hash_join_rehashes_incompatible_range_partitioning() -> Result<()> {
1024+
let left = parquet_exec_with_output_partitioning(range_partitioning(
1025+
"a",
1026+
[10, 20, 30],
1027+
SortOptions::default(),
1028+
)?);
1029+
let right = projection_exec_with_alias(
1030+
parquet_exec_with_output_partitioning(range_partitioning(
1031+
"a",
1032+
[10, 30, 40],
1033+
SortOptions::default(),
1034+
)?),
1035+
vec![
1036+
("a".to_string(), "a1".to_string()),
1037+
("b".to_string(), "b1".to_string()),
1038+
],
1039+
);
1040+
let join_on = vec![(
1041+
Arc::new(Column::new_with_schema("a", &left.schema())?) as _,
1042+
Arc::new(Column::new_with_schema("a1", &right.schema())?) as _,
1043+
)];
1044+
let join = hash_join_exec(left, right, &join_on, &JoinType::Inner);
1045+
1046+
let plan = TestConfig::default()
1047+
.with_query_execution_partitions(4)
1048+
.to_plan(join, &DISTRIB_DISTRIB_SORT);
1049+
1050+
assert_plan!(
1051+
plan,
1052+
@r"
1053+
HashJoinExec: mode=Partitioned, join_type=Inner, on=[(a@0, a1@0)]
1054+
RepartitionExec: partitioning=Hash([a@0], 4), input_partitions=4
1055+
PartitionedTestExec: output_partitioning=Range([a@0 ASC], [(10), (20), (30)], 4)
1056+
RepartitionExec: partitioning=Hash([a1@0], 4), input_partitions=4
1057+
ProjectionExec: expr=[a@0 as a1, b@1 as b1]
1058+
PartitionedTestExec: output_partitioning=Range([a@0 ASC], [(10), (30), (40)], 4)
1059+
"
1060+
);
1061+
1062+
Ok(())
1063+
}
1064+
10161065
#[test]
10171066
fn multi_hash_joins() -> Result<()> {
10181067
let left = parquet_exec();

‎datafusion/core/tests/physical_optimizer/projection_pushdown.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -800,7 +800,9 @@ fn test_output_req_after_projection() -> Result<()> {
800800
if let Distribution::KeyPartitioned(vec) = after_optimize
801801
.downcast_ref::<OutputRequirementExec>()
802802
.unwrap()
803-
.required_input_distribution()[0]
803+
.input_distribution_requirements()
804+
.child_distribution(0)
805+
.unwrap()
804806
.clone()
805807
{
806808
assert!(

‎datafusion/core/tests/physical_optimizer/sanity_checker.rs‎

Lines changed: 8 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -413,35 +413,32 @@ fn range_partitioned_exec(
413413
[sort_expr(key, schema)].into(),
414414
split_points,
415415
)?);
416-
let input = memory_exec(schema);
417-
418-
RepartitionExec::try_new(input, partitioning)
416+
RepartitionExec::try_new(memory_exec(schema), partitioning)
419417
.map(|exec| Arc::new(exec) as Arc<dyn ExecutionPlan>)
420418
}
421419

422420
#[test]
423421
fn test_partitioned_hash_join_requires_co_partitioned_children() -> Result<()> {
424422
let schema = create_test_schema2();
425-
let join_on = vec![(col("a", &schema)?, col("b", &schema)?)];
426-
let right = range_partitioned_exec(&schema, "b", [10])?;
423+
let join_on = vec![(col("a", &schema)?, col("a", &schema)?)];
427424

428-
let valid_join = hash_join_exec(
425+
let compatible_join = hash_join_exec(
426+
range_partitioned_exec(&schema, "a", [10])?,
429427
range_partitioned_exec(&schema, "a", [10])?,
430-
Arc::clone(&right),
431428
join_on.clone(),
432429
None,
433430
&JoinType::Inner,
434431
)?;
435-
assert_sanity_check(&valid_join, true);
432+
assert_sanity_check(&compatible_join, true);
436433

437-
let invalid_join = hash_join_exec(
434+
let incompatible_join = hash_join_exec(
435+
range_partitioned_exec(&schema, "a", [10])?,
438436
range_partitioned_exec(&schema, "a", [20])?,
439-
right,
440437
join_on,
441438
None,
442439
&JoinType::Inner,
443440
)?;
444-
assert_sanity_check(&invalid_join, false);
441+
assert_sanity_check(&incompatible_join, false);
445442

446443
Ok(())
447444
}

‎datafusion/core/tests/user_defined/user_defined_plan.rs‎

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -708,8 +708,12 @@ impl ExecutionPlan for TopKExec {
708708
&self.cache
709709
}
710710

711-
fn required_input_distribution(&self) -> Vec<Distribution> {
712-
vec![Distribution::SinglePartition]
711+
fn input_distribution_requirements(
712+
&self,
713+
) -> datafusion_physical_plan::InputDistributionRequirements {
714+
datafusion_physical_plan::InputDistributionRequirements::new(vec![
715+
Distribution::SinglePartition,
716+
])
713717
}
714718

715719
fn children(&self) -> Vec<&Arc<dyn ExecutionPlan>> {

‎datafusion/datasource/src/sink.rs‎

Lines changed: 11 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -31,8 +31,9 @@ use datafusion_physical_expr_common::sort_expr::{LexRequirement, OrderingRequire
3131
use datafusion_physical_plan::metrics::MetricsSet;
3232
use datafusion_physical_plan::stream::RecordBatchStreamAdapter;
3333
use datafusion_physical_plan::{
34-
DisplayAs, DisplayFormatType, ExecutionPlan, ExecutionPlanProperties, Partitioning,
35-
PlanProperties, SendableRecordBatchStream, execute_input_stream,
34+
DisplayAs, DisplayFormatType, ExecutionPlan, ExecutionPlanProperties,
35+
InputDistributionRequirements, Partitioning, PlanProperties,
36+
SendableRecordBatchStream, execute_input_stream,
3637
};
3738

3839
use async_trait::async_trait;
@@ -189,9 +190,16 @@ impl ExecutionPlan for DataSinkExec {
189190
}
190191

191192
fn required_input_distribution(&self) -> Vec<Distribution> {
193+
self.input_distribution_requirements().into_per_child()
194+
}
195+
196+
fn input_distribution_requirements(&self) -> InputDistributionRequirements {
192197
// DataSink is responsible for dynamically partitioning its
193198
// own input at execution time, and so requires a single input partition.
194-
vec![Distribution::SinglePartition; self.children().len()]
199+
InputDistributionRequirements::new(vec![
200+
Distribution::SinglePartition;
201+
self.children().len()
202+
])
195203
}
196204

197205
fn required_input_ordering(&self) -> Vec<Option<OrderingRequirements>> {

‎datafusion/physical-expr/src/lib.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,9 @@ pub use datafusion_common::SplitPoint;
5959
pub use equivalence::{
6060
AcrossPartitions, ConstExpr, EquivalenceProperties, calculate_union,
6161
};
62-
pub use partitioning::{Distribution, Partitioning, RangePartitioning};
62+
pub use partitioning::{
63+
Distribution, Partitioning, PartitioningSatisfaction, RangePartitioning,
64+
};
6365
pub use physical_expr::{
6466
add_offset_to_expr, add_offset_to_physical_sort_exprs, create_lex_ordering,
6567
create_ordering, create_physical_partitioning, create_physical_sort_expr,

0 commit comments

Comments
 (0)