Skip to content

Commit b7a3331

Browse files
authored
[Part2] Partition and Sort Enforcement, ExecutionPlan enhancement (#4043)
* [Part2] Partition and Sort Enforcement, ExecutionPlan enhancement * Fix hash join output_partitioning * fix * fix format * Resolve review comments * tiny fix * UT to verify hash join output_partitioning * fix comments
1 parent 238e179 commit b7a3331

36 files changed

Lines changed: 1537 additions & 234 deletions

‎datafusion/core/src/dataframe.rs‎

Lines changed: 162 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -842,6 +842,8 @@ mod tests {
842842
use super::*;
843843
use crate::execution::options::{CsvReadOptions, ParquetReadOptions};
844844
use crate::physical_plan::ColumnarValue;
845+
use crate::physical_plan::Partitioning;
846+
use crate::physical_plan::PhysicalExpr;
845847
use crate::test_util;
846848
use crate::test_util::parquet_test_data;
847849
use crate::{assert_batches_sorted_eq, execution::context::SessionContext};
@@ -851,6 +853,7 @@ mod tests {
851853
avg, cast, count, count_distinct, create_udf, lit, max, min, sum,
852854
BuiltInWindowFunction, ScalarFunctionImplementation, Volatility, WindowFunction,
853855
};
856+
use datafusion_physical_expr::expressions::Column;
854857

855858
#[tokio::test]
856859
async fn select_columns() -> Result<()> {
@@ -1515,4 +1518,163 @@ mod tests {
15151518

15161519
Ok(())
15171520
}
1521+
1522+
#[tokio::test]
1523+
async fn partition_aware_union() -> Result<()> {
1524+
let left = test_table().await?.select_columns(&["c1", "c2"])?;
1525+
let right = test_table_with_name("c2")
1526+
.await?
1527+
.select_columns(&["c1", "c3"])?
1528+
.with_column_renamed("c2.c1", "c2_c1")?;
1529+
1530+
let left_rows = left.collect().await?;
1531+
let right_rows = right.collect().await?;
1532+
let join1 =
1533+
left.join(right.clone(), JoinType::Inner, &["c1"], &["c2_c1"], None)?;
1534+
let join2 = left.join(right, JoinType::Inner, &["c1"], &["c2_c1"], None)?;
1535+
1536+
let union = join1.union(join2)?;
1537+
1538+
let union_rows = union.collect().await?;
1539+
1540+
assert_eq!(100, left_rows.iter().map(|x| x.num_rows()).sum::<usize>());
1541+
assert_eq!(100, right_rows.iter().map(|x| x.num_rows()).sum::<usize>());
1542+
assert_eq!(4016, union_rows.iter().map(|x| x.num_rows()).sum::<usize>());
1543+
1544+
let physical_plan = union.create_physical_plan().await?;
1545+
let default_partition_count =
1546+
SessionContext::new().copied_config().target_partitions;
1547+
1548+
// For partition aware union, the output partition count should not be changed.
1549+
assert_eq!(
1550+
physical_plan.output_partitioning().partition_count(),
1551+
default_partition_count
1552+
);
1553+
// For partition aware union, the output partition is the same with the union's inputs
1554+
for child in physical_plan.children() {
1555+
assert_eq!(
1556+
physical_plan.output_partitioning(),
1557+
child.output_partitioning()
1558+
);
1559+
}
1560+
1561+
Ok(())
1562+
}
1563+
1564+
#[tokio::test]
1565+
async fn non_partition_aware_union() -> Result<()> {
1566+
let left = test_table().await?.select_columns(&["c1", "c2"])?;
1567+
let right = test_table_with_name("c2")
1568+
.await?
1569+
.select_columns(&["c1", "c2"])?
1570+
.with_column_renamed("c2.c1", "c2_c1")?
1571+
.with_column_renamed("c2.c2", "c2_c2")?;
1572+
1573+
let left_rows = left.collect().await?;
1574+
let right_rows = right.collect().await?;
1575+
let join1 = left.join(
1576+
right.clone(),
1577+
JoinType::Inner,
1578+
&["c1", "c2"],
1579+
&["c2_c1", "c2_c2"],
1580+
None,
1581+
)?;
1582+
1583+
// join key ordering is different
1584+
let join2 = left.join(
1585+
right,
1586+
JoinType::Inner,
1587+
&["c2", "c1"],
1588+
&["c2_c2", "c2_c1"],
1589+
None,
1590+
)?;
1591+
1592+
let union = join1.union(join2)?;
1593+
1594+
let union_rows = union.collect().await?;
1595+
1596+
assert_eq!(100, left_rows.iter().map(|x| x.num_rows()).sum::<usize>());
1597+
assert_eq!(100, right_rows.iter().map(|x| x.num_rows()).sum::<usize>());
1598+
assert_eq!(916, union_rows.iter().map(|x| x.num_rows()).sum::<usize>());
1599+
1600+
let physical_plan = union.create_physical_plan().await?;
1601+
let default_partition_count =
1602+
SessionContext::new().copied_config().target_partitions;
1603+
1604+
// For non-partition aware union, the output partitioning count should be the combination of all output partitions count
1605+
assert!(matches!(
1606+
physical_plan.output_partitioning(),
1607+
Partitioning::UnknownPartitioning(partition_count) if partition_count == default_partition_count * 2));
1608+
Ok(())
1609+
}
1610+
1611+
#[tokio::test]
1612+
async fn verify_join_output_partitioning() -> Result<()> {
1613+
let left = test_table().await?.select_columns(&["c1", "c2"])?;
1614+
let right = test_table_with_name("c2")
1615+
.await?
1616+
.select_columns(&["c1", "c2"])?
1617+
.with_column_renamed("c2.c1", "c2_c1")?
1618+
.with_column_renamed("c2.c2", "c2_c2")?;
1619+
1620+
let all_join_types = vec![
1621+
JoinType::Inner,
1622+
JoinType::Left,
1623+
JoinType::Right,
1624+
JoinType::Full,
1625+
JoinType::LeftSemi,
1626+
JoinType::RightSemi,
1627+
JoinType::LeftAnti,
1628+
JoinType::RightAnti,
1629+
];
1630+
1631+
let default_partition_count =
1632+
SessionContext::new().copied_config().target_partitions;
1633+
1634+
for join_type in all_join_types {
1635+
let join = left.join(
1636+
right.clone(),
1637+
join_type,
1638+
&["c1", "c2"],
1639+
&["c2_c1", "c2_c2"],
1640+
None,
1641+
)?;
1642+
let physical_plan = join.create_physical_plan().await?;
1643+
let out_partitioning = physical_plan.output_partitioning();
1644+
let join_schema = physical_plan.schema();
1645+
1646+
match join_type {
1647+
JoinType::Inner
1648+
| JoinType::Left
1649+
| JoinType::LeftSemi
1650+
| JoinType::LeftAnti => {
1651+
let left_exprs: Vec<Arc<dyn PhysicalExpr>> = vec![
1652+
Arc::new(Column::new_with_schema("c1", &join_schema).unwrap()),
1653+
Arc::new(Column::new_with_schema("c2", &join_schema).unwrap()),
1654+
];
1655+
assert_eq!(
1656+
out_partitioning,
1657+
Partitioning::Hash(left_exprs, default_partition_count)
1658+
);
1659+
}
1660+
JoinType::Right | JoinType::RightSemi | JoinType::RightAnti => {
1661+
let right_exprs: Vec<Arc<dyn PhysicalExpr>> = vec![
1662+
Arc::new(Column::new_with_schema("c2_c1", &join_schema).unwrap()),
1663+
Arc::new(Column::new_with_schema("c2_c2", &join_schema).unwrap()),
1664+
];
1665+
assert_eq!(
1666+
out_partitioning,
1667+
Partitioning::Hash(right_exprs, default_partition_count)
1668+
);
1669+
}
1670+
JoinType::Full => {
1671+
assert!(matches!(
1672+
out_partitioning,
1673+
Partitioning::UnknownPartitioning(partition_count) if partition_count == default_partition_count));
1674+
}
1675+
}
1676+
}
1677+
1678+
Ok(())
1679+
}
15181680
}

‎datafusion/core/src/physical_optimizer/merge_exec.rs‎

Lines changed: 14 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -52,27 +52,20 @@ impl PhysicalOptimizerRule for AddCoalescePartitionsExec {
5252
.iter()
5353
.map(|child| self.optimize(child.clone(), _config))
5454
.collect::<Result<Vec<_>>>()?;
55-
match plan.required_child_distribution() {
56-
Distribution::UnspecifiedDistribution => {
57-
with_new_children_if_necessary(plan, children)
58-
}
59-
Distribution::HashPartitioned(_) => {
60-
with_new_children_if_necessary(plan, children)
61-
}
62-
Distribution::SinglePartition => with_new_children_if_necessary(
63-
plan,
64-
children
65-
.iter()
66-
.map(|child| {
67-
if child.output_partitioning().partition_count() == 1 {
68-
child.clone()
69-
} else {
70-
Arc::new(CoalescePartitionsExec::new(child.clone()))
71-
}
72-
})
73-
.collect(),
74-
),
75-
}
55+
assert_eq!(children.len(), plan.required_input_distribution().len());
56+
let new_children = children
57+
.into_iter()
58+
.zip(plan.required_input_distribution())
59+
.map(|(child, dist)| match dist {
60+
Distribution::SinglePartition
61+
if child.output_partitioning().partition_count() > 1 =>
62+
{
63+
Arc::new(CoalescePartitionsExec::new(child.clone()))
64+
}
65+
_ => child,
66+
})
67+
.collect::<Vec<_>>();
68+
with_new_children_if_necessary(plan, new_children)
7669
}
7770
}
7871

‎datafusion/core/src/physical_plan/aggregates/mod.rs‎

Lines changed: 54 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -37,6 +37,7 @@ use datafusion_physical_expr::{
3737
expressions, AggregateExpr, PhysicalExpr, PhysicalSortExpr,
3838
};
3939
use std::any::Any;
40+
use std::collections::HashMap;
4041

4142
use std::sync::Arc;
4243

@@ -45,9 +46,11 @@ mod no_grouping;
4546
mod row_hash;
4647

4748
use crate::physical_plan::aggregates::row_hash::GroupedHashAggregateStreamV2;
49+
use crate::physical_plan::EquivalenceProperties;
4850
pub use datafusion_expr::AggregateFunction;
4951
use datafusion_physical_expr::aggregate::row_accumulator::RowAccumulator;
5052
pub use datafusion_physical_expr::expressions::create_aggregate_expr;
53+
use datafusion_physical_expr::normalize_out_expr_with_alias_schema;
5154
use datafusion_row::{row_supported, RowType};
5255

5356
/// Hash aggregate modes
@@ -163,6 +166,9 @@ pub struct AggregateExec {
163166
/// same as input.schema() but for the final aggregate it will be the same as the input
164167
/// to the partial aggregate
165168
input_schema: SchemaRef,
169+
/// The alias map used to normalize out expressions like Partitioning and PhysicalSortExpr
170+
/// The key is the column from the input schema and the values are the columns from the output schema
171+
alias_map: HashMap<Column, Vec<Column>>,
166172
/// Execution Metrics
167173
metrics: ExecutionPlanMetricsSet,
168174
}
@@ -186,13 +192,26 @@ impl AggregateExec {
186192

187193
let schema = Arc::new(schema);
188194

195+
let mut alias_map: HashMap<Column, Vec<Column>> = HashMap::new();
196+
for (expression, name) in group_by.expr.iter() {
197+
if let Some(column) = expression.as_any().downcast_ref::<Column>() {
198+
let new_col_idx = schema.index_of(name)?;
199+
// When the column name is the same, but index does not equal, treat it as Alias
200+
if (column.name() != name) || (column.index() != new_col_idx) {
201+
let entry = alias_map.entry(column.clone()).or_insert_with(Vec::new);
202+
entry.push(Column::new(name, new_col_idx));
203+
}
204+
};
205+
}
206+
189207
Ok(AggregateExec {
190208
mode,
191209
group_by,
192210
aggr_expr,
193211
input,
194212
schema,
195213
input_schema,
214+
alias_map,
196215
metrics: ExecutionPlanMetricsSet::new(),
197216
})
198217
}
@@ -255,25 +274,51 @@ impl ExecutionPlan for AggregateExec {
255274

256275
/// Get the output partitioning of this plan
257276
fn output_partitioning(&self) -> Partitioning {
258-
self.input.output_partitioning()
277+
match &self.mode {
278+
AggregateMode::Partial => {
279+
// Partial Aggregation will not change the output partitioning but need to respect the Alias
280+
let input_partition = self.input.output_partitioning();
281+
match input_partition {
282+
Partitioning::Hash(exprs, part) => {
283+
let normalized_exprs = exprs
284+
.into_iter()
285+
.map(|expr| {
286+
normalize_out_expr_with_alias_schema(
287+
expr,
288+
&self.alias_map,
289+
&self.schema,
290+
)
291+
})
292+
.collect::<Vec<_>>();
293+
Partitioning::Hash(normalized_exprs, part)
294+
}
295+
_ => input_partition,
296+
}
297+
}
298+
// Final Aggregation's output partitioning is the same as its real input
299+
_ => self.input.output_partitioning(),
300+
}
259301
}
260302

261303
fn output_ordering(&self) -> Option<&[PhysicalSortExpr]> {
262304
None
263305
}
264306

265-
fn required_child_distribution(&self) -> Distribution {
307+
fn required_input_distribution(&self) -> Vec<Distribution> {
266308
match &self.mode {
267-
AggregateMode::Partial => Distribution::UnspecifiedDistribution,
268-
AggregateMode::FinalPartitioned => Distribution::HashPartitioned(
269-
self.group_by.expr.iter().map(|x| x.0.clone()).collect(),
270-
),
271-
AggregateMode::Final => Distribution::SinglePartition,
309+
AggregateMode::Partial => vec![Distribution::UnspecifiedDistribution],
310+
AggregateMode::FinalPartitioned => {
311+
vec![Distribution::HashPartitioned(self.output_group_expr())]
312+
}
313+
AggregateMode::Final => vec![Distribution::SinglePartition],
272314
}
273315
}
274316

275-
fn relies_on_input_order(&self) -> bool {
276-
false
317+
fn equivalence_properties(&self) -> EquivalenceProperties {
318+
let mut input_equivalence_properties = self.input.equivalence_properties();
319+
input_equivalence_properties.merge_properties_with_alias(&self.alias_map);
320+
input_equivalence_properties.truncate_properties_not_in_schema(&self.schema);
321+
input_equivalence_properties
277322
}
278323

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

‎datafusion/core/src/physical_plan/analyze.rs‎

Lines changed: 2 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -72,8 +72,8 @@ impl ExecutionPlan for AnalyzeExec {
7272
}
7373

7474
/// Specifies we want the input as a single stream
75-
fn required_child_distribution(&self) -> Distribution {
76-
Distribution::SinglePartition
75+
fn required_input_distribution(&self) -> Vec<Distribution> {
76+
vec![Distribution::SinglePartition]
7777
}
7878

7979
/// Get the output partitioning of this plan
@@ -85,10 +85,6 @@ impl ExecutionPlan for AnalyzeExec {
8585
None
8686
}
8787

88-
fn relies_on_input_order(&self) -> bool {
89-
false
90-
}
91-
9288
fn with_new_children(
9389
self: Arc<Self>,
9490
mut children: Vec<Arc<dyn ExecutionPlan>>,

‎datafusion/core/src/physical_plan/coalesce_batches.rs‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -25,8 +25,8 @@ use std::task::{Context, Poll};
2525

2626
use crate::error::Result;
2727
use crate::physical_plan::{
28-
DisplayFormatType, ExecutionPlan, Partitioning, RecordBatchStream,
29-
SendableRecordBatchStream,
28+
DisplayFormatType, EquivalenceProperties, ExecutionPlan, Partitioning,
29+
RecordBatchStream, SendableRecordBatchStream,
3030
};
3131

3232
use crate::execution::context::TaskContext;
@@ -100,8 +100,8 @@ impl ExecutionPlan for CoalesceBatchesExec {
100100
None
101101
}
102102

103-
fn relies_on_input_order(&self) -> bool {
104-
false
103+
fn equivalence_properties(&self) -> EquivalenceProperties {
104+
self.input.equivalence_properties()
105105
}
106106

107107
fn with_new_children(

0 commit comments

Comments
 (0)