Repository navigation
Expand file tree
/
Copy pathunion.rs
More file actions
2130 lines (1924 loc) · 83.3 KB
/
Copy pathunion.rs
File metadata and controls
2130 lines (1924 loc) · 83.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
// Some of these functions reference the Postgres documentation
// or implementation to ensure compatibility and are subject to
// the Postgres license.
//! The Union operator combines multiple inputs with the same schema
use std::borrow::Borrow;
use std::pin::Pin;
use std::sync::Arc;
use std::task::{Context, Poll};
use super::{
DisplayAs, DisplayFormatType, ExecutionPlan, ExecutionPlanProperties, Partitioning,
PlanProperties, RecordBatchStream, SendableRecordBatchStream, Statistics,
metrics::{ExecutionPlanMetricsSet, MetricsSet},
};
use crate::execution_plan::LimitBehavior;
use crate::execution_plan::{
CardinalityEffect, InvariantLevel, boundedness_from_children,
check_default_invariants, emission_type_from_children,
};
use crate::filter::FilterExec;
use crate::filter_pushdown::{
ChildPushdownResult, FilterDescription, FilterPushdownPhase,
FilterPushdownPropagation, PushedDown,
};
use crate::metrics::BaselineMetrics;
use crate::projection::{ProjectionExec, ProjectionExpr, make_with_child};
use crate::statistics::{ChildStats, StatisticsArgs};
use crate::stream::ObservedStream;
use crate::{ChildrenPropertiesMode, ReplaceChildrenOptions, validate_child_count};
use arrow::datatypes::{Schema, SchemaRef};
use arrow::record_batch::RecordBatch;
use datafusion_common::config::ConfigOptions;
use datafusion_common::metadata::merge_metadata_for_union;
use datafusion_common::stats::NdvFallback;
use datafusion_common::tree_node::TreeNodeRecursion;
use datafusion_common::{
Result, assert_or_internal_err, exec_err, internal_datafusion_err, plan_err,
};
use datafusion_execution::TaskContext;
use datafusion_physical_expr::expressions::{CastExpr, Column};
use datafusion_physical_expr::{
EquivalenceProperties, PhysicalExpr, calculate_union, conjunction,
};
use futures::Stream;
use itertools::Itertools;
use log::{debug, trace, warn};
use tokio::macros::support::thread_rng_n;
/// Coerces `input`'s output schema to exactly `schema` via a `ProjectionExec`
/// that re-stamps each column with the union's merged field (same
/// `DataType`, but the union's merged nullability/name/metadata), or returns
/// `input` unchanged if its schema already matches. [`UnionExec::try_new`]
/// and [`InterleaveExec::try_new`] call this on every child, so the coercion
/// is visible in the plan tree (e.g. in `EXPLAIN`) instead of happening
/// invisibly inside the union operator's own `execute()`.
///
/// A column whose `DataType` doesn't already match the union's is a genuine
/// data type mismatch (as opposed to a nullability/name/metadata-only one),
/// and is rejected eagerly here rather than silently cast or deferred to a
/// runtime failure -- this only ever changes a column's declared schema,
/// never its values.
///
/// Casting a column to its own `DataType` (only the `Field`'s nullability,
/// name, or metadata changes) is a zero-copy relabeling: the cast kernel's
/// same-type fast path (`cast_array_by_name`) just clones the `Arc<dyn
/// Array>`, so this carries no runtime overhead over the schema it replaces.
///
/// See <https://github.com/apache/datafusion/issues/15394>.
fn coerce_schema(
input: Arc<dyn ExecutionPlan>,
schema: &SchemaRef,
) -> Result<Arc<dyn ExecutionPlan>> {
let input_schema = input.schema();
if &input_schema == schema {
return Ok(input);
}
let exprs = input_schema
.fields()
.iter()
.zip(schema.fields())
.enumerate()
.map(|(i, (input_field, target_field))| {
if input_field.data_type() != target_field.data_type() {
return plan_err!(
"UnionExec/InterleaveExec requires all inputs to have the same \
data type per column; column {i} has type {} in one input, but \
the union schema expects {}",
input_field.data_type(),
target_field.data_type()
);
}
let column: Arc<dyn PhysicalExpr> =
Arc::new(Column::new(input_field.name(), i));
let expr = if input_field == target_field {
column
} else {
Arc::new(CastExpr::new_with_target_field(
column,
Arc::clone(target_field),
None,
)) as Arc<dyn PhysicalExpr>
};
Ok(ProjectionExpr {
expr,
alias: target_field.name().clone(),
})
})
.collect::<Result<Vec<_>>>()?;
Ok(Arc::new(ProjectionExec::try_new(exprs, input)?))
}
/// `UnionExec`: `UNION ALL` execution plan.
///
/// `UnionExec` combines multiple inputs with the same schema by
/// concatenating the partitions. It does not mix or copy data within
/// or across partitions. Thus if the input partitions are sorted, the
/// output partitions of the union are also sorted.
///
/// For example, given a `UnionExec` of two inputs, with `N`
/// partitions, and `M` partitions, there will be `N+M` output
/// partitions. The first `N` output partitions are from Input 1
/// partitions, and then next `M` output partitions are from Input 2.
///
/// ```text
/// ▲ ▲ ▲ ▲
/// │ │ │ │
/// Output │ ... │ │ │
/// Partitions │0 │N-1 │ N │N+M-1
/// (passes through ┌────┴───────┴───────────┴─────────┴───┐
/// the N+M input │ UnionExec │
/// partitions) │ │
/// └──────────────────────────────────────┘
/// ▲
/// │
/// │
/// Input ┌────────┬─────┴────┬──────────┐
/// Partitions │ ... │ │ ... │
/// 0 │ │ N-1 │ 0 │ M-1
/// ┌────┴────────┴───┐ ┌───┴──────────┴───┐
/// │ │ │ │
/// │ │ │ │
/// │ │ │ │
/// │ │ │ │
/// │ │ │ │
/// │ │ │ │
/// │Input 1 │ │Input 2 │
/// └─────────────────┘ └──────────────────┘
/// ```
#[derive(Debug, Clone)]
pub struct UnionExec {
/// Input execution plan
inputs: Vec<Arc<dyn ExecutionPlan>>,
/// Execution metrics
metrics: ExecutionPlanMetricsSet,
/// Cache holding plan properties like equivalences, output partitioning etc.
cache: Arc<PlanProperties>,
}
impl UnionExec {
/// Try to create a new UnionExec.
///
/// # Errors
/// Returns an error if:
/// - `inputs` is empty
///
/// # Optimization
/// If there is only one input, returns that input directly rather than wrapping it in a UnionExec
pub fn try_new(
inputs: Vec<Arc<dyn ExecutionPlan>>,
) -> Result<Arc<dyn ExecutionPlan>> {
match inputs.len() {
0 => exec_err!("UnionExec requires at least one input"),
1 => Ok(inputs.into_iter().next().unwrap()),
_ => {
let schema = union_schema(&inputs)?;
// The schema of the inputs and the union schema is consistent when:
// - They have the same number of fields, and
// - Their fields have same types at the same indices.
let inputs = inputs
.into_iter()
.map(|input| coerce_schema(input, &schema))
.collect::<Result<Vec<_>>>()?;
let cache = Self::compute_properties(&inputs, schema)?;
Ok(Arc::new(UnionExec {
inputs,
metrics: ExecutionPlanMetricsSet::new(),
cache: Arc::new(cache),
}))
}
}
}
/// Get inputs of the execution plan
pub fn inputs(&self) -> &Vec<Arc<dyn ExecutionPlan>> {
&self.inputs
}
/// Maps a global output partition index to the `(input index, local
/// partition index)` of the input that owns it, or `None` if out of range.
fn owning_input(&self, partition: usize) -> Option<(usize, usize)> {
let mut remaining = partition;
for (i, input) in self.inputs.iter().enumerate() {
let count = input.output_partitioning().partition_count();
if remaining < count {
return Some((i, remaining));
}
remaining -= count;
}
None
}
/// This function creates the cache object that stores the plan properties such as schema, equivalence properties, ordering, partitioning, etc.
fn compute_properties(
inputs: &[Arc<dyn ExecutionPlan>],
schema: SchemaRef,
) -> Result<PlanProperties> {
// Calculate equivalence properties:
let children_eqps = inputs
.iter()
.map(|child| child.equivalence_properties().clone())
.collect::<Vec<_>>();
let eq_properties = calculate_union(children_eqps, schema)?;
// Calculate output partitioning; i.e. sum output partitions of the inputs.
let num_partitions = inputs
.iter()
.map(|plan| plan.output_partitioning().partition_count())
.sum();
let output_partitioning = Partitioning::UnknownPartitioning(num_partitions);
Ok(PlanProperties::new(
eq_properties,
output_partitioning,
emission_type_from_children(inputs),
boundedness_from_children(inputs),
))
}
}
impl DisplayAs for UnionExec {
fn fmt_as(
&self,
t: DisplayFormatType,
f: &mut std::fmt::Formatter,
) -> std::fmt::Result {
match t {
DisplayFormatType::Default | DisplayFormatType::Verbose => {
write!(f, "UnionExec")
}
DisplayFormatType::TreeRender => Ok(()),
}
}
}
impl ExecutionPlan for UnionExec {
fn name(&self) -> &'static str {
"UnionExec"
}
/// Return a reference to Any that can be used for downcasting
fn properties(&self) -> &Arc<PlanProperties> {
&self.cache
}
fn check_invariants(&self, check: InvariantLevel) -> Result<()> {
check_default_invariants(self, check)?;
(self.inputs().len() >= 2).then_some(()).ok_or_else(|| {
internal_datafusion_err!("UnionExec should have at least 2 children")
})
}
fn maintains_input_order(&self) -> Vec<bool> {
// If the Union has an output ordering, it maintains at least one
// child's ordering (i.e. the meet).
// For instance, assume that the first child is SortExpr('a','b','c'),
// the second child is SortExpr('a','b') and the third child is
// SortExpr('a','b'). The output ordering would be SortExpr('a','b'),
// which is the "meet" of all input orderings. In this example, this
// function will return vec![false, true, true], indicating that we
// preserve the orderings for the 2nd and the 3rd children.
if let Some(output_ordering) = self.properties().output_ordering() {
self.inputs()
.iter()
.map(|child| {
if let Some(child_ordering) = child.output_ordering() {
output_ordering.len() == child_ordering.len()
} else {
false
}
})
.collect()
} else {
vec![false; self.inputs().len()]
}
}
fn benefits_from_input_partitioning(&self) -> Vec<bool> {
vec![false; self.children().len()]
}
fn children(&self) -> Vec<&Arc<dyn ExecutionPlan>> {
self.inputs.iter().collect()
}
fn apply_expressions(
&self,
_f: &mut dyn FnMut(&Arc<dyn PhysicalExpr>) -> Result<TreeNodeRecursion>,
) -> Result<TreeNodeRecursion> {
Ok(TreeNodeRecursion::Continue)
}
fn replace_children(
self: Arc<Self>,
children: Vec<Arc<dyn ExecutionPlan>>,
options: ReplaceChildrenOptions,
) -> Result<Arc<dyn ExecutionPlan>> {
validate_child_count!(self, children);
match options.children_properties {
ChildrenPropertiesMode::Keep => Ok(Arc::new(Self {
inputs: children,
metrics: ExecutionPlanMetricsSet::new(),
..Self::clone(&*self)
})),
ChildrenPropertiesMode::Recompute => UnionExec::try_new(children),
}
}
fn with_new_children(
self: Arc<Self>,
children: Vec<Arc<dyn ExecutionPlan>>,
) -> Result<Arc<dyn ExecutionPlan>> {
self.replace_children(
children,
ReplaceChildrenOptions::new(ChildrenPropertiesMode::Recompute),
)
}
fn with_new_children_and_same_properties(
self: Arc<Self>,
children: Vec<Arc<dyn ExecutionPlan>>,
) -> Result<Arc<dyn ExecutionPlan>> {
self.replace_children(
children,
ReplaceChildrenOptions::new(ChildrenPropertiesMode::Keep),
)
}
fn execute(
&self,
mut partition: usize,
context: Arc<TaskContext>,
) -> Result<SendableRecordBatchStream> {
trace!(
"Start UnionExec::execute for partition {} of context session_id {} and task_id {:?}",
partition,
context.session_id(),
context.task_id()
);
let baseline_metrics = BaselineMetrics::new(&self.metrics, partition);
// record the tiny amount of work done in this function so
// elapsed_compute is reported as non zero
let elapsed_compute = baseline_metrics.elapsed_compute().clone();
let _timer = elapsed_compute.timer(); // record on drop
// find partition to execute
for input in self.inputs.iter() {
// Calculate whether partition belongs to the current partition
if partition < input.output_partitioning().partition_count() {
let stream = input.execute(partition, context)?;
debug!("Found a Union partition to execute");
return Ok(Box::pin(ObservedStream::new(
stream,
baseline_metrics,
None,
)));
} else {
partition -= input.output_partitioning().partition_count();
}
}
warn!("Error in Union: Partition {partition} not found");
exec_err!("Partition {partition} not found in Union")
}
fn metrics(&self) -> Option<MetricsSet> {
Some(self.metrics.clone_inner())
}
fn child_stats_requests(&self, partition: Option<usize>) -> Vec<ChildStats> {
if let Some(partition_idx) = partition {
// For a specific partition, compute stats only for the input that
// owns it; the other inputs are not needed and are skipped.
let targeted = self.owning_input(partition_idx);
self.inputs
.iter()
.enumerate()
.map(|(i, _)| match targeted {
Some((target_i, target_partition)) if i == target_i => {
ChildStats::At(Some(target_partition))
}
_ => ChildStats::Skip,
})
.collect()
} else {
vec![ChildStats::At(None); self.inputs.len()]
}
}
fn statistics_from_inputs(
&self,
input_stats: &[Arc<Statistics>],
args: &StatisticsArgs,
) -> Result<Arc<Statistics>> {
if let Some(partition_idx) = args.partition() {
// For a specific partition, find which input it belongs to
if let Some((target_i, _)) = self.owning_input(partition_idx) {
// This partition belongs to this input - return its stats
return Ok(Arc::clone(&input_stats[target_i]));
}
// If we get here, the partition index is out of bounds
Ok(Arc::new(Statistics::new_unknown(&self.schema())))
} else {
let stats_refs = input_stats.iter().map(|s| s.as_ref()).collect::<Vec<_>>();
Ok(Arc::new(Statistics::try_merge_iter_with_ndv_fallback(
stats_refs,
self.schema().as_ref(),
NdvFallback::Sum,
)?))
}
}
fn cardinality_effect(&self) -> CardinalityEffect {
// Union combines rows from multiple inputs, so output rows are not tied
// to any single input and can only be constrained as greater-or-equal.
CardinalityEffect::GreaterEqual
}
fn supports_limit_pushdown(&self) -> bool {
true
}
fn limit_behavior(&self) -> LimitBehavior {
LimitBehavior::CopyToChildren
}
/// Tries to push `projection` down through `union`. If possible, performs the
/// pushdown and returns a new [`UnionExec`] as the top plan which has projections
/// as its children. Otherwise, returns `None`.
fn try_swapping_with_projection(
&self,
projection: &ProjectionExec,
) -> Result<Option<Arc<dyn ExecutionPlan>>> {
// If the projection doesn't narrow the schema, we shouldn't try to push it down.
if projection.expr().len() >= projection.input().schema().fields().len() {
return Ok(None);
}
let new_children = self
.children()
.into_iter()
.map(|child| make_with_child(projection, child))
.collect::<Result<Vec<_>>>()?;
Ok(Some(UnionExec::try_new(new_children.clone())?))
}
fn gather_filters_for_pushdown(
&self,
_phase: FilterPushdownPhase,
parent_filters: Vec<Arc<dyn PhysicalExpr>>,
_config: &ConfigOptions,
) -> Result<FilterDescription> {
FilterDescription::from_children(parent_filters, &self.children())
}
fn handle_child_pushdown_result(
&self,
phase: FilterPushdownPhase,
child_pushdown_result: ChildPushdownResult,
_config: &ConfigOptions,
) -> Result<FilterPushdownPropagation<Arc<dyn ExecutionPlan>>> {
// Pre phase: handle heterogeneous pushdown by wrapping individual
// children with FilterExec and reporting all filters as handled.
// Post phase: use default behavior to let the filter creator decide how to handle
// filters that weren't fully pushed down.
if phase != FilterPushdownPhase::Pre {
return Ok(FilterPushdownPropagation::if_all(child_pushdown_result));
}
// UnionExec needs specialized filter pushdown handling when children have
// heterogeneous pushdown support. Without this, when some children support
// pushdown and others don't, the default behavior would leave FilterExec
// above UnionExec, re-applying filters to outputs of all children—including
// those that already applied the filters via pushdown. This specialized
// implementation adds FilterExec only to children that don't support
// pushdown, avoiding redundant filtering and improving performance.
//
// Example: Given Child1 (no pushdown support) and Child2 (has pushdown support)
// Default behavior: This implementation:
// FilterExec UnionExec
// UnionExec FilterExec
// Child1 Child1
// Child2(filter) Child2(filter)
// Collect unsupported filters for each child
let mut unsupported_filters_per_child = vec![Vec::new(); self.inputs.len()];
for parent_filter_result in child_pushdown_result.parent_filters.iter() {
for (child_idx, &child_result) in
parent_filter_result.child_results.iter().enumerate()
{
if matches!(child_result, PushedDown::No) {
unsupported_filters_per_child[child_idx]
.push(Arc::clone(&parent_filter_result.filter));
}
}
}
// Wrap children that have unsupported filters with FilterExec
let mut new_children = self.inputs.clone();
for (child_idx, unsupported_filters) in
unsupported_filters_per_child.iter().enumerate()
{
if !unsupported_filters.is_empty() {
let combined_filter = conjunction(unsupported_filters.clone());
new_children[child_idx] = Arc::new(FilterExec::try_new(
combined_filter,
Arc::clone(&self.inputs[child_idx]),
)?);
}
}
// Check if any children were modified
let children_modified = new_children
.iter()
.zip(self.inputs.iter())
.any(|(new, old)| !Arc::ptr_eq(new, old));
let all_filters_pushed =
vec![PushedDown::Yes; child_pushdown_result.parent_filters.len()];
let propagation = if children_modified {
let updated_node = UnionExec::try_new(new_children)?;
FilterPushdownPropagation::with_parent_pushdown_result(all_filters_pushed)
.with_updated_node(updated_node)
} else {
FilterPushdownPropagation::with_parent_pushdown_result(all_filters_pushed)
};
// Report all parent filters as supported since we've ensured they're applied
// on all children (either pushed down or via FilterExec)
Ok(propagation)
}
#[cfg(feature = "proto")]
fn try_to_proto(
&self,
ctx: &crate::proto::ExecutionPlanEncodeCtx<'_>,
) -> Result<Option<datafusion_proto_models::protobuf::PhysicalPlanNode>> {
use datafusion_proto_models::protobuf;
// Destructure exhaustively (no `..`) so that adding a field to
// `UnionExec` is a compile error here until it is either serialized or
// explicitly documented as not needing to be.
let Self {
inputs,
// Runtime metrics, not part of the plan shape.
metrics: _,
// Derived plan properties, recomputed on decode.
cache: _,
} = self;
let inputs = ctx.encode_children(inputs)?;
Ok(Some(protobuf::PhysicalPlanNode {
physical_plan_type: Some(
protobuf::physical_plan_node::PhysicalPlanType::Union(
protobuf::UnionExecNode { inputs },
),
),
}))
}
}
#[cfg(feature = "proto")]
impl UnionExec {
pub fn try_from_proto(
node: &datafusion_proto_models::protobuf::PhysicalPlanNode,
ctx: &crate::proto::ExecutionPlanDecodeCtx<'_>,
) -> Result<Arc<dyn ExecutionPlan>> {
use datafusion_proto_models::protobuf;
let union = crate::expect_plan_variant!(
node,
protobuf::physical_plan_node::PhysicalPlanType::Union,
"UnionExec",
);
// Destructure exhaustively so that a new field on `UnionExecNode` is a
// compile error here rather than a silently dropped field.
let protobuf::UnionExecNode { inputs } = union;
let inputs = inputs
.iter()
.map(|input| ctx.decode_child(input))
.collect::<Result<Vec<_>>>()?;
UnionExec::try_new(inputs)
}
}
/// Combines multiple input streams by interleaving them.
///
/// All inputs must share an identical [`Partitioning::Hash`] or [`Partitioning::Range`] so that
/// partition `k` covers the same data across every input. Each output partition is the
/// interleaving of the same-indexed partition from all inputs:
/// `output[k] = input[0][k] + input[1][k] + ... + input[n-1][k]`
///
/// # Data Flow
/// ```text
/// +---------+
/// | |---+
/// | Input 1 | |
/// | |-------------+
/// +---------+ | |
/// | | +---------+
/// +------------------>| |
/// +---------------->| Combine |-->
/// | +-------------->| |
/// | | | +---------+
/// +---------+ | | |
/// | |-----+ | |
/// | Input 2 | | |
/// | |---------------+
/// +---------+ | | |
/// | | | +---------+
/// | +-------->| |
/// | +------>| Combine |-->
/// | +---->| |
/// | | +---------+
/// +---------+ | |
/// | |-------+ |
/// | Input 3 | |
/// | |-----------------+
/// +---------+
/// ```
#[derive(Debug, Clone)]
pub struct InterleaveExec {
/// Input execution plan
inputs: Vec<Arc<dyn ExecutionPlan>>,
/// Execution metrics
metrics: ExecutionPlanMetricsSet,
/// Cache holding plan properties like equivalences, output partitioning etc.
cache: Arc<PlanProperties>,
}
impl InterleaveExec {
/// Create a new InterleaveExec
pub fn try_new(inputs: Vec<Arc<dyn ExecutionPlan>>) -> Result<Self> {
assert_or_internal_err!(
can_interleave(inputs.iter()),
"Not all InterleaveExec children have a consistent hash or range partitioning"
);
Self::try_new_unchecked(inputs)
}
/// Like [`Self::try_new`], but does not require the inputs to be
/// interleavable.
///
/// Optimizer rules rebuild every parent from its rewritten children while
/// walking the plan, so a rewrite that changes a child's partitioning
/// (join side swaps, removed repartitions, ...) hands this node children
/// that are no longer interleavable before any rule has had the chance to
/// repair it. Such a node reports [`Partitioning::UnknownPartitioning`],
/// so nothing downstream can rely on a hash layout it does not have, and
/// [`ExecutionPlan::check_invariants`] rejects it at
/// [`InvariantLevel::Executable`] if it is never repaired. This mirrors
/// how unmet distribution requirements are handled for every other
/// operator.
fn try_new_unchecked(inputs: Vec<Arc<dyn ExecutionPlan>>) -> Result<Self> {
let schema = union_schema(&inputs)?;
let inputs = inputs
.into_iter()
.map(|input| coerce_schema(input, &schema))
.collect::<Result<Vec<_>>>()?;
let cache = Self::compute_properties(&inputs, schema)?;
Ok(InterleaveExec {
inputs,
metrics: ExecutionPlanMetricsSet::new(),
cache: Arc::new(cache),
})
}
/// Get inputs of the execution plan
pub fn inputs(&self) -> &Vec<Arc<dyn ExecutionPlan>> {
&self.inputs
}
/// This function creates the cache object that stores the plan properties such as schema, equivalence properties, ordering, partitioning, etc.
fn compute_properties(
inputs: &[Arc<dyn ExecutionPlan>],
schema: SchemaRef,
) -> Result<PlanProperties> {
let eq_properties = EquivalenceProperties::new(schema);
// Get output partitioning. Only claim the shared hash / range layout
// when every input actually has it (see `try_new_unchecked`).
let output_partitioning = if can_interleave(inputs.iter()) {
inputs[0].output_partitioning().clone()
} else {
// Non-interleavable inputs need not even agree on a partition
// count. Report the largest one: `execute` errors out for a
// partition that some input lacks, so an unrepaired node fails
// loudly instead of silently dropping the extra partitions of
// the widest input.
let partition_count = inputs
.iter()
.map(|input| input.output_partitioning().partition_count())
.max()
.unwrap_or(0);
Partitioning::UnknownPartitioning(partition_count)
};
Ok(PlanProperties::new(
eq_properties,
output_partitioning,
emission_type_from_children(inputs),
boundedness_from_children(inputs),
))
}
}
impl DisplayAs for InterleaveExec {
fn fmt_as(
&self,
t: DisplayFormatType,
f: &mut std::fmt::Formatter,
) -> std::fmt::Result {
match t {
DisplayFormatType::Default | DisplayFormatType::Verbose => {
write!(f, "InterleaveExec")
}
DisplayFormatType::TreeRender => Ok(()),
}
}
}
impl ExecutionPlan for InterleaveExec {
fn name(&self) -> &'static str {
"InterleaveExec"
}
/// Return a reference to Any that can be used for downcasting
fn properties(&self) -> &Arc<PlanProperties> {
&self.cache
}
fn children(&self) -> Vec<&Arc<dyn ExecutionPlan>> {
self.inputs.iter().collect()
}
fn maintains_input_order(&self) -> Vec<bool> {
vec![false; self.inputs().len()]
}
fn apply_expressions(
&self,
_f: &mut dyn FnMut(&Arc<dyn PhysicalExpr>) -> Result<TreeNodeRecursion>,
) -> Result<TreeNodeRecursion> {
Ok(TreeNodeRecursion::Continue)
}
fn replace_children(
self: Arc<Self>,
children: Vec<Arc<dyn ExecutionPlan>>,
options: ReplaceChildrenOptions,
) -> Result<Arc<dyn ExecutionPlan>> {
validate_child_count!(self, children);
match options.children_properties {
ChildrenPropertiesMode::Keep => Ok(Arc::new(Self {
inputs: children,
metrics: ExecutionPlanMetricsSet::new(),
..Self::clone(&*self)
})),
ChildrenPropertiesMode::Recompute => {
// The new children may no longer be interleavable; see
// `try_new_unchecked` for why this is not rejected here.
Ok(Arc::new(InterleaveExec::try_new_unchecked(children)?))
}
}
}
fn check_invariants(&self, check: InvariantLevel) -> Result<()> {
check_default_invariants(self, check)?;
if matches!(check, InvariantLevel::Executable) {
assert_or_internal_err!(
can_interleave(self.inputs.iter()),
"Not all InterleaveExec children have a consistent hash or range partitioning"
);
}
Ok(())
}
fn with_new_children(
self: Arc<Self>,
children: Vec<Arc<dyn ExecutionPlan>>,
) -> Result<Arc<dyn ExecutionPlan>> {
self.replace_children(
children,
ReplaceChildrenOptions::new(ChildrenPropertiesMode::Recompute),
)
}
fn with_new_children_and_same_properties(
self: Arc<Self>,
children: Vec<Arc<dyn ExecutionPlan>>,
) -> Result<Arc<dyn ExecutionPlan>> {
self.replace_children(
children,
ReplaceChildrenOptions::new(ChildrenPropertiesMode::Keep),
)
}
fn execute(
&self,
partition: usize,
context: Arc<TaskContext>,
) -> Result<SendableRecordBatchStream> {
trace!(
"Start InterleaveExec::execute for partition {} of context session_id {} and task_id {:?}",
partition,
context.session_id(),
context.task_id()
);
let baseline_metrics = BaselineMetrics::new(&self.metrics, partition);
// record the tiny amount of work done in this function so
// elapsed_compute is reported as non zero
let elapsed_compute = baseline_metrics.elapsed_compute().clone();
let _timer = elapsed_compute.timer(); // record on drop
let mut input_stream_vec = Vec::with_capacity(self.inputs.len());
for input in self.inputs.iter() {
if partition < input.output_partitioning().partition_count() {
let stream = input.execute(partition, Arc::clone(&context))?;
input_stream_vec.push(stream);
} else {
// Do not find a partition to execute
break;
}
}
if input_stream_vec.len() == self.inputs.len() {
let stream = Box::pin(CombinedRecordBatchStream::new(
self.schema(),
input_stream_vec,
));
return Ok(Box::pin(ObservedStream::new(
stream,
baseline_metrics,
None,
)));
}
warn!("Error in InterleaveExec: Partition {partition} not found");
exec_err!("Partition {partition} not found in InterleaveExec")
}
fn metrics(&self) -> Option<MetricsSet> {
Some(self.metrics.clone_inner())
}
fn child_stats_requests(&self, partition: Option<usize>) -> Vec<ChildStats> {
vec![ChildStats::At(partition); self.inputs.len()]
}
fn statistics_from_inputs(
&self,
input_stats: &[Arc<Statistics>],
_args: &StatisticsArgs,
) -> Result<Arc<Statistics>> {
let stats = input_stats
.iter()
.map(|s| s.as_ref().clone())
.collect::<Vec<_>>();
Ok(Arc::new(Statistics::try_merge_iter_with_ndv_fallback(
stats.iter(),
self.schema().as_ref(),
NdvFallback::Sum,
)?))
}
fn benefits_from_input_partitioning(&self) -> Vec<bool> {
vec![false; self.children().len()]
}
#[cfg(feature = "proto")]
fn try_to_proto(
&self,
ctx: &crate::proto::ExecutionPlanEncodeCtx<'_>,
) -> Result<Option<datafusion_proto_models::protobuf::PhysicalPlanNode>> {
use datafusion_proto_models::protobuf;
// Destructure exhaustively (no `..`) so that adding a field to
// `InterleaveExec` is a compile error here until it is either
// serialized or explicitly documented as not needing to be.
let Self {
inputs,
// Runtime metrics, not part of the plan shape.
metrics: _,
// Derived plan properties, recomputed on decode.
cache: _,
} = self;
let inputs = ctx.encode_children(inputs)?;
Ok(Some(protobuf::PhysicalPlanNode {
physical_plan_type: Some(
protobuf::physical_plan_node::PhysicalPlanType::Interleave(
protobuf::InterleaveExecNode { inputs },
),
),
}))
}
}
#[cfg(feature = "proto")]
impl InterleaveExec {
pub fn try_from_proto(
node: &datafusion_proto_models::protobuf::PhysicalPlanNode,
ctx: &crate::proto::ExecutionPlanDecodeCtx<'_>,
) -> Result<Arc<dyn ExecutionPlan>> {
use datafusion_proto_models::protobuf;
let interleave = crate::expect_plan_variant!(
node,
protobuf::physical_plan_node::PhysicalPlanType::Interleave,
"InterleaveExec",
);
// Destructure exhaustively so that a new field on `InterleaveExecNode`
// is a compile error here rather than a silently dropped field.
let protobuf::InterleaveExecNode { inputs } = interleave;
let inputs = inputs
.iter()
.map(|input| ctx.decode_child(input))
.collect::<Result<Vec<_>>>()?;
Ok(Arc::new(InterleaveExec::try_new(inputs)?))
}
}
/// Returns true if all inputs have the same [`Partitioning::Hash`] or [`Partitioning::Range`]
/// spec, making them safe to interleave. Two inputs are interleave-compatible when partition
/// `k` covers the identical key range or hash bucket across every input.
///
/// Note: compatibility is checked sequentially against the first input, so
/// `InputDistributionRequirements::co_partitioned` is not needed here.
///
/// It might be too strict here in the case that the input partition specs are compatible but not exactly the same.
/// For example one input partition has the partition spec Hash('a','b','c') and
/// other has the partition spec Hash('a'), It is safe to derive the out partition with the spec Hash('a','b','c').
pub fn can_interleave<T: Borrow<Arc<dyn ExecutionPlan>>>(
mut inputs: impl Iterator<Item = T>,
) -> bool {
let Some(first) = inputs.next() else {
return false;
};
let reference = first.borrow().output_partitioning();
matches!(reference, Partitioning::Hash(_, _) | Partitioning::Range(_))
&& inputs
.map(|plan| plan.borrow().output_partitioning().clone())
.all(|partition| partition == *reference)
}
fn union_schema(inputs: &[Arc<dyn ExecutionPlan>]) -> Result<SchemaRef> {
if inputs.is_empty() {
return exec_err!("Cannot create union schema from empty inputs");
}
let first_schema = inputs[0].schema();
// Fast path: when every input already shares the first input's schema, the
// field-by-field metadata/nullability merge below is redundant work.
// This is common in practice: unions built from
// repartitioned copies of the same plan (e.g. observed in InfluxDB) hand us
// children that all carry the exact same schema. A pointer-equality check
// catches the shared-`Arc` case for free, and a content `==` comparison
// catches distinct-but-equal schemas; both let us return early and hand back
// the first schema unchanged.
if inputs[1..].iter().all(|input| {
let schema = input.schema();
Arc::ptr_eq(&schema, &first_schema) || schema == first_schema
}) {
return Ok(first_schema);
}
let first_field_count = first_schema.fields().len();
// validate that all inputs have the same number of fields
for (idx, input) in inputs.iter().enumerate().skip(1) {
let field_count = input.schema().fields().len();
if field_count != first_field_count {
return exec_err!(
"UnionExec/InterleaveExec requires all inputs to have the same number of fields. \