Skip to content

Commit 899c86a

Browse files
authored
Reorder the physical plan optimizer rules, extract GlobalSortSelection, make Repartition optional (#4714)
* Extract the global sort algorithm selection from the BasicEnforcement to be a separate rule, GlobalSortSelection * Make the optimizer rule of Repartition optional * Fix EmptyExec data() method * Reorder the physical plan optimizer rules * Refine the UT for the repartition rule by adding the essential BasicEnforcement rule * Fix UT failure for window function * Fix example testing Co-authored-by: yangzhong <[email protected]>
1 parent 981a9bb commit 899c86a

16 files changed

Lines changed: 344 additions & 177 deletions

File tree

‎datafusion-examples/examples/custom_datasource.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -264,6 +264,6 @@ impl ExecutionPlan for CustomExec {
264264
}
265265

266266
fn statistics(&self) -> Statistics {
267-
todo!()
267+
Statistics::default()
268268
}
269269
}

‎datafusion/core/src/config.rs‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -131,6 +131,10 @@ pub const OPT_PREFER_HASH_JOIN: &str = "datafusion.optimizer.prefer_hash_join";
131131
pub const OPT_HASH_JOIN_SINGLE_PARTITION_THRESHOLD: &str =
132132
"datafusion.optimizer.hash_join_single_partition_threshold";
133133

134+
/// Configuration option "datafusion.execution.round_robin_repartition"
135+
pub const OPT_ENABLE_ROUND_ROBIN_REPARTITION: &str =
136+
"datafusion.optimizer.enable_round_robin_repartition";
137+
134138
/// Definition of a configuration option
135139
pub struct ConfigDefinition {
136140
/// key used to identifier this configuration option
@@ -409,6 +413,11 @@ impl BuiltInConfigs {
409413
"The maximum estimated size in bytes for one input side of a HashJoin will be collected into a single partition",
410414
1024 * 1024,
411415
),
416+
ConfigDefinition::new_bool(
417+
OPT_ENABLE_ROUND_ROBIN_REPARTITION,
418+
"When set to true, the physical plan optimizer will try to add round robin repartition to increase parallelism to leverage more CPU cores",
419+
true,
420+
),
412421
]
413422
}
414423
}

‎datafusion/core/src/execution/context.rs‎

Lines changed: 43 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -73,7 +73,8 @@ use crate::physical_optimizer::repartition::Repartition;
7373

7474
use crate::config::{
7575
ConfigOptions, OPT_BATCH_SIZE, OPT_COALESCE_BATCHES, OPT_COALESCE_TARGET_BATCH_SIZE,
76-
OPT_FILTER_NULL_JOIN_KEYS, OPT_OPTIMIZER_MAX_PASSES, OPT_OPTIMIZER_SKIP_FAILED_RULES,
76+
OPT_ENABLE_ROUND_ROBIN_REPARTITION, OPT_FILTER_NULL_JOIN_KEYS,
77+
OPT_OPTIMIZER_MAX_PASSES, OPT_OPTIMIZER_SKIP_FAILED_RULES,
7778
};
7879
use crate::execution::{runtime_env::RuntimeEnv, FunctionRegistry};
7980
use crate::physical_optimizer::enforcement::BasicEnforcement;
@@ -98,6 +99,7 @@ use crate::catalog::information_schema::{InformationSchemaProvider, INFORMATION_
9899
use crate::catalog::listing_schema::ListingSchemaProvider;
99100
use crate::datasource::object_store::ObjectStoreUrl;
100101
use crate::execution::memory_pool::MemoryPool;
102+
use crate::physical_optimizer::global_sort_selection::GlobalSortSelection;
101103
use crate::physical_optimizer::optimize_sorts::OptimizeSorts;
102104
use uuid::Uuid;
103105

@@ -1530,11 +1532,47 @@ impl SessionState {
15301532
);
15311533
}
15321534

1533-
let mut physical_optimizers: Vec<Arc<dyn PhysicalOptimizerRule + Sync + Send>> = vec![
1534-
Arc::new(AggregateStatistics::new()),
1535-
Arc::new(JoinSelection::new()),
1536-
];
1535+
// We need to take care of the rule ordering. They may influence each other.
1536+
let mut physical_optimizers: Vec<Arc<dyn PhysicalOptimizerRule + Sync + Send>> =
1537+
vec![Arc::new(AggregateStatistics::new())];
1538+
// - In order to increase the parallelism, it will change the output partitioning
1539+
// of some operators in the plan tree, which will influence other rules.
1540+
// Therefore, it should be run as soon as possible.
1541+
// - The reason to make it optional is
1542+
// - it's not used for the distributed engine, Ballista.
1543+
// - it's conflicted with some parts of the BasicEnforcement, since it will
1544+
// introduce additional repartitioning while the BasicEnforcement aims at
1545+
// reducing unnecessary repartitioning.
1546+
if config
1547+
.config_options
1548+
.get_bool(OPT_ENABLE_ROUND_ROBIN_REPARTITION)
1549+
.unwrap_or_default()
1550+
{
1551+
physical_optimizers.push(Arc::new(Repartition::new()));
1552+
}
1553+
//- Currently it will depend on the partition number to decide whether to change the
1554+
// single node sort to parallel local sort and merge. Therefore, it should be run
1555+
// after the Repartition.
1556+
// - Since it will change the output ordering of some operators, it should be run
1557+
// before JoinSelection and BasicEnforcement, which may depend on that.
1558+
physical_optimizers.push(Arc::new(GlobalSortSelection::new()));
1559+
// Statistics-base join selection will change the Auto mode to real join implementation,
1560+
// like collect left, or hash join, or future sort merge join, which will
1561+
// influence the BasicEnforcement to decide whether to add additional repartition
1562+
// and local sort to meet the distribution and ordering requirements.
1563+
// Therefore, it should be run before BasicEnforcement
1564+
physical_optimizers.push(Arc::new(JoinSelection::new()));
1565+
// It's for adding essential repartition and local sorting operator to satisfy the
1566+
// required distribution and local sort.
1567+
// Please make sure that the whole plan tree is determined.
15371568
physical_optimizers.push(Arc::new(BasicEnforcement::new()));
1569+
// `BasicEnforcement` stage conservatively inserts `SortExec`s to satisfy ordering requirements.
1570+
// However, a deeper analysis may sometimes reveal that such a `SortExec` is actually unnecessary.
1571+
// These cases typically arise when we have reversible `WindowAggExec`s or deep subqueries. The
1572+
// rule below performs this analysis and removes unnecessary `SortExec`s.
1573+
physical_optimizers.push(Arc::new(OptimizeSorts::new()));
1574+
// It will not influence the distribution and ordering of the whole plan tree.
1575+
// Therefore, to avoid influencing other rules, it should be run at last.
15381576
if config
15391577
.config_options
15401578
.get_bool(OPT_COALESCE_BATCHES)
@@ -1549,16 +1587,6 @@ impl SessionState {
15491587
.unwrap(),
15501588
)));
15511589
}
1552-
physical_optimizers.push(Arc::new(Repartition::new()));
1553-
// Repartition rule could introduce additional RepartitionExec with RoundRobin partitioning.
1554-
// To make sure the SinglePartition is satisfied, run the BasicEnforcement again, originally it was the AddCoalescePartitionsExec here.
1555-
physical_optimizers.push(Arc::new(BasicEnforcement::new()));
1556-
1557-
// `BasicEnforcement` stage conservatively inserts `SortExec`s to satisfy ordering requirements.
1558-
// However, a deeper analysis may sometimes reveal that such a `SortExec` is actually unnecessary.
1559-
// These cases typically arise when we have reversible `WindowAggExec`s or deep subqueries. The
1560-
// rule below performs this analysis and removes unnecessary `SortExec`s.
1561-
physical_optimizers.push(Arc::new(OptimizeSorts::new()));
15621590

15631591
SessionState {
15641592
session_id,

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

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,7 @@ use crate::{
2323
physical_optimizer::PhysicalOptimizerRule,
2424
physical_plan::{
2525
coalesce_batches::CoalesceBatchesExec, filter::FilterExec, joins::HashJoinExec,
26-
repartition::RepartitionExec, rewrite::TreeNodeRewritable,
26+
repartition::RepartitionExec, rewrite::TreeNodeRewritable, Partitioning,
2727
},
2828
};
2929
use std::sync::Arc;
@@ -57,7 +57,16 @@ impl PhysicalOptimizerRule for CoalesceBatches {
5757
// See https://github.com/apache/arrow-datafusion/issues/139
5858
let wrap_in_coalesce = plan_any.downcast_ref::<FilterExec>().is_some()
5959
|| plan_any.downcast_ref::<HashJoinExec>().is_some()
60-
|| plan_any.downcast_ref::<RepartitionExec>().is_some();
60+
// Don't need to add CoalesceBatchesExec after a round robin RepartitionExec
61+
|| plan_any
62+
.downcast_ref::<RepartitionExec>()
63+
.map(|repart_exec| {
64+
!matches!(
65+
repart_exec.partitioning().clone(),
66+
Partitioning::RoundRobinBatch(_)
67+
)
68+
})
69+
.unwrap_or(false);
6170
if wrap_in_coalesce {
6271
Ok(Some(Arc::new(CoalesceBatchesExec::new(
6372
plan.clone(),

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

Lines changed: 1 addition & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -30,8 +30,7 @@ use crate::physical_plan::joins::{
3030
use crate::physical_plan::projection::ProjectionExec;
3131
use crate::physical_plan::repartition::RepartitionExec;
3232
use crate::physical_plan::rewrite::TreeNodeRewritable;
33-
use crate::physical_plan::sorts::sort::{SortExec, SortOptions};
34-
use crate::physical_plan::sorts::sort_preserving_merge::SortPreservingMergeExec;
33+
use crate::physical_plan::sorts::sort::SortOptions;
3534
use crate::physical_plan::windows::WindowAggExec;
3635
use crate::physical_plan::Partitioning;
3736
use crate::physical_plan::{with_new_children_if_necessary, Distribution, ExecutionPlan};
@@ -844,36 +843,6 @@ fn ensure_distribution_and_ordering(
844843
if plan.children().is_empty() {
845844
return Ok(plan);
846845
}
847-
// It's mainly for changing the single node global SortExec to
848-
// the SortPreservingMergeExec with multiple local SortExec.
849-
// What's more, if limit exists, it can also be pushed down to the local sort
850-
let plan = plan
851-
.as_any()
852-
.downcast_ref::<SortExec>()
853-
.and_then(|sort_exec| {
854-
// There are three situations that there's no need for this optimization
855-
// - There's only one input partition;
856-
// - It's already preserving the partitioning so that it can be regarded as a local sort
857-
// - There's no limit pushed down to the local sort (It's still controversial)
858-
if sort_exec.input().output_partitioning().partition_count() > 1
859-
&& !sort_exec.preserve_partitioning()
860-
&& sort_exec.fetch().is_some()
861-
{
862-
let sort = SortExec::new_with_partitioning(
863-
sort_exec.expr().to_vec(),
864-
sort_exec.input().clone(),
865-
true,
866-
sort_exec.fetch(),
867-
);
868-
Some(Arc::new(SortPreservingMergeExec::new(
869-
sort_exec.expr().to_vec(),
870-
Arc::new(sort),
871-
)))
872-
} else {
873-
None
874-
}
875-
})
876-
.map_or(plan, |new_plan| new_plan);
877846

878847
let required_input_distributions = plan.required_input_distribution();
879848
let required_input_orderings = plan.required_input_ordering();
Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
//! Select the efficient global sort implementation based on sort details.
19+
20+
use std::sync::Arc;
21+
22+
use crate::error::Result;
23+
use crate::physical_optimizer::PhysicalOptimizerRule;
24+
use crate::physical_plan::rewrite::TreeNodeRewritable;
25+
use crate::physical_plan::sorts::sort::SortExec;
26+
use crate::physical_plan::sorts::sort_preserving_merge::SortPreservingMergeExec;
27+
use crate::physical_plan::ExecutionPlan;
28+
use crate::prelude::SessionConfig;
29+
30+
/// Currently for a sort operator, if
31+
/// - there are more than one input partitions
32+
/// - and there's some limit which can be pushed down to each of its input partitions
33+
/// then [SortPreservingMergeExec] with local sort with a limit pushed down will be preferred;
34+
/// Otherwise, the normal global sort [SortExec] will be used.
35+
/// Later more intelligent statistics-based decision can also be introduced.
36+
/// For example, for a small data set, the global sort may be efficient enough
37+
#[derive(Default)]
38+
pub struct GlobalSortSelection {}
39+
40+
impl GlobalSortSelection {
41+
#[allow(missing_docs)]
42+
pub fn new() -> Self {
43+
Self {}
44+
}
45+
}
46+
47+
impl PhysicalOptimizerRule for GlobalSortSelection {
48+
fn optimize(
49+
&self,
50+
plan: Arc<dyn ExecutionPlan>,
51+
_config: &SessionConfig,
52+
) -> Result<Arc<dyn ExecutionPlan>> {
53+
plan.transform_up(&|plan| {
54+
Ok(plan
55+
.as_any()
56+
.downcast_ref::<SortExec>()
57+
.and_then(|sort_exec| {
58+
if sort_exec.input().output_partitioning().partition_count() > 1
59+
&& sort_exec.fetch().is_some()
60+
// It's already preserving the partitioning so that it can be regarded as a local sort
61+
&& !sort_exec.preserve_partitioning()
62+
{
63+
let sort = SortExec::new_with_partitioning(
64+
sort_exec.expr().to_vec(),
65+
sort_exec.input().clone(),
66+
true,
67+
sort_exec.fetch(),
68+
);
69+
let global_sort: Arc<dyn ExecutionPlan> =
70+
Arc::new(SortPreservingMergeExec::new(
71+
sort_exec.expr().to_vec(),
72+
Arc::new(sort),
73+
));
74+
Some(global_sort)
75+
} else {
76+
None
77+
}
78+
}))
79+
})
80+
}
81+
82+
fn name(&self) -> &str {
83+
"global_sort_selection"
84+
}
85+
86+
fn schema_check(&self) -> bool {
87+
false
88+
}
89+
}

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@
2121
pub mod aggregate_statistics;
2222
pub mod coalesce_batches;
2323
pub mod enforcement;
24+
pub mod global_sort_selection;
2425
pub mod join_selection;
2526
pub mod optimize_sorts;
2627
pub mod optimizer;

0 commit comments

Comments
 (0)