Skip to content

Commit 668be79

Browse files
committed
[opt](local shuffle) support bucket shuffle for set operation
Re-enable bucket shuffle for set operation / union: the largest natural or storage-bucketed child keeps its bucket distribution and every other child is bucket-shuffled to it, avoiding a full reshuffle of the largest input (the same idea as bucket-shuffle join applied to set operations). This is only valid under the FE local-shuffle planner (enable_local_shuffle_planner): only then can the frontend plan the correct local shuffle type for the set sink/probe. With the BE-side local-shuffle planner the backend cannot infer the type and computes wrong results, so the plan falls back to execution-bucketed shuffle there and behavior is unchanged.
1 parent b5c0bcd commit 668be79

12 files changed

Lines changed: 881 additions & 149 deletions

File tree

‎fe/fe-core/src/main/java/org/apache/doris/nereids/glue/translator/PhysicalPlanTranslator.java‎

Lines changed: 28 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -2496,14 +2496,34 @@ public PlanFragment visitPhysicalSetOperation(
24962496
setOperationNode.setColocate(true);
24972497
}
24982498

2499-
// TODO: open comment when support `enable_local_shuffle_planner`
2500-
// for (Plan child : setOperation.children()) {
2501-
// PhysicalPlan childPhysicalPlan = (PhysicalPlan) child;
2502-
// if (JoinUtils.isStorageBucketed(childPhysicalPlan.getPhysicalProperties())) {
2503-
// setOperationNode.setDistributionMode(DistributionMode.BUCKET_SHUFFLE);
2504-
// break;
2505-
// }
2506-
// }
2499+
// Storage-bucketed children only appear when the FE local shuffle planner is active:
2500+
// ChildrenPropertiesRegulator and RequestPropertyDeriver both gate the bucket-shuffle
2501+
// alternative on enableLocalShufflePlanner. Gate the marker on the same flag so the
2502+
// dependency is explicit and a future planner change that produced a STORAGE_BUCKETED
2503+
// distribution outside the local-shuffle planner cannot silently mark BUCKET_SHUFFLE here.
2504+
//
2505+
// Within that gate a storage-bucketed child means the regulator chose the bucket shuffle
2506+
// alternative (it enforces the other children onto the basic child's buckets), so the marker
2507+
// simply follows that decision. It must not re-check the table id independently: the basic
2508+
// child selection in the regulator is the single place that vets the layout, and re-checking
2509+
// here could suppress a bucket shuffle the property model already committed to and desync a
2510+
// parent that aligned to the set operation output.
2511+
//
2512+
// Unlike hash join, BUCKET_SHUFFLE is not exclusive with isColocate above: for a set
2513+
// operation isColocate describes the bucket-aligned scheduling of the fragment (the
2514+
// basic child scans buckets directly), while BUCKET_SHUFFLE describes how the other
2515+
// children arrive (bucket-shuffle exchanges). Both routes converge to the same
2516+
// bucket-hash local exchange requirement in SetOperationNode.enforceAndDeriveLocalExchange.
2517+
if (context.getSessionVariable() != null
2518+
&& context.getSessionVariable().isEnableLocalShufflePlanner()) {
2519+
for (Plan child : setOperation.children()) {
2520+
PhysicalPlan childPhysicalPlan = (PhysicalPlan) child;
2521+
if (JoinUtils.isStorageBucketed(childPhysicalPlan.getPhysicalProperties())) {
2522+
setOperationNode.setDistributionMode(DistributionMode.BUCKET_SHUFFLE);
2523+
break;
2524+
}
2525+
}
2526+
}
25072527

25082528
return setOperationFragment;
25092529
}

‎fe/fe-core/src/main/java/org/apache/doris/nereids/properties/ChildOutputPropertyDeriver.java‎

Lines changed: 74 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -71,9 +71,11 @@
7171
import com.google.common.collect.Maps;
7272
import com.google.common.collect.Sets;
7373

74+
import java.util.ArrayList;
7475
import java.util.Arrays;
7576
import java.util.Collections;
7677
import java.util.HashSet;
78+
import java.util.LinkedHashMap;
7779
import java.util.List;
7880
import java.util.Map;
7981
import java.util.Objects;
@@ -440,53 +442,78 @@ public PhysicalProperties visitPhysicalSetOperation(PhysicalSetOperation setOper
440442
return PhysicalProperties.GATHER;
441443
}
442444

443-
// TODO: open comment when support `enable_local_shuffle_planner`
444-
// int distributeToChildIndex
445-
// = setOperation.<Integer>getMutableState(PhysicalSetOperation.DISTRIBUTE_TO_CHILD_INDEX).orElse(-1);
446-
// if (distributeToChildIndex >= 0
447-
// && childrenDistribution.get(distributeToChildIndex) instanceof DistributionSpecHash) {
448-
// DistributionSpecHash childDistribution
449-
// = (DistributionSpecHash) childrenDistribution.get(distributeToChildIndex);
450-
// List<SlotReference> childToIndex = setOperation.getRegularChildrenOutputs().get(distributeToChildIndex);
451-
// Map<ExprId, Integer> idToOutputIndex = new LinkedHashMap<>();
452-
// for (int j = 0; j < childToIndex.size(); j++) {
453-
// idToOutputIndex.put(childToIndex.get(j).getExprId(), j);
454-
// }
455-
//
456-
// List<ExprId> orderedShuffledColumns = childDistribution.getOrderedShuffledColumns();
457-
// List<ExprId> setOperationDistributeColumnIds = new ArrayList<>();
458-
// for (ExprId tableDistributeColumnId : orderedShuffledColumns) {
459-
// Integer index = idToOutputIndex.get(tableDistributeColumnId);
460-
// if (index == null) {
461-
// break;
462-
// }
463-
// setOperationDistributeColumnIds.add(setOperation.getOutput().get(index).getExprId());
464-
// }
465-
// // check whether the set operation output all distribution columns of the child
466-
// if (setOperationDistributeColumnIds.size() == orderedShuffledColumns.size()) {
467-
// boolean isUnion = setOperation instanceof Union;
468-
// boolean shuffleToRight = distributeToChildIndex > 0;
469-
// if (!isUnion && shuffleToRight) {
470-
// return new PhysicalProperties(
471-
// new DistributionSpecHash(
472-
// setOperationDistributeColumnIds,
473-
// ShuffleType.EXECUTION_BUCKETED
474-
// )
475-
// );
476-
// } else {
477-
// // keep the distribution as the child
478-
// return new PhysicalProperties(
479-
// new DistributionSpecHash(
480-
// setOperationDistributeColumnIds,
481-
// childDistribution.getShuffleType(),
482-
// childDistribution.getTableId(),
483-
// childDistribution.getSelectedIndexId(),
484-
// childDistribution.getPartitionIds()
485-
// )
486-
// );
487-
// }
488-
// }
489-
// }
445+
// After ChildrenPropertiesRegulator the children distributions are already legal, so the
446+
// output is derived by describing what the children provide:
447+
// 1. one or more NATURAL children: output the first NATURAL child's distribution
448+
// (several NATURAL children behave like colocate);
449+
// 2. no NATURAL but some STORAGE_BUCKETED child: output its STORAGE_BUCKETED distribution;
450+
// 3. all EXECUTION_BUCKETED children: output the execution hash (the generic loop below);
451+
// 4. anything else (e.g. random): output a non-specific property (also below).
452+
// When the basic child does not directly output its shuffle columns, or the children do
453+
// not agree, this falls through to the generic loop below, which is equivalence-set aware
454+
// and checks that every child maps its shuffle columns to the same set-operation output
455+
// positions before it claims a bucketed output. The basic child is recomputed from the
456+
// children distributions instead of being carried as mutable planner state, because mutable
457+
// state does not survive the with-copies in chooseBestPlan() and the
458+
// RecomputePhysicalPropertiesPostProcessor re-derivation, while this recomputation is
459+
// deterministic on any copy of the plan.
460+
int distributeToChildIndex = -1;
461+
int firstStorageBucketedIndex = -1;
462+
for (int i = 0; i < childrenDistribution.size(); i++) {
463+
if (childrenDistribution.get(i) instanceof DistributionSpecHash) {
464+
ShuffleType childShuffleType
465+
= ((DistributionSpecHash) childrenDistribution.get(i)).getShuffleType();
466+
if (childShuffleType == ShuffleType.NATURAL) {
467+
distributeToChildIndex = i;
468+
break;
469+
} else if (childShuffleType == ShuffleType.STORAGE_BUCKETED
470+
&& firstStorageBucketedIndex < 0) {
471+
firstStorageBucketedIndex = i;
472+
}
473+
}
474+
}
475+
if (distributeToChildIndex < 0) {
476+
distributeToChildIndex = firstStorageBucketedIndex;
477+
}
478+
if (distributeToChildIndex >= 0) {
479+
DistributionSpecHash childDistribution
480+
= (DistributionSpecHash) childrenDistribution.get(distributeToChildIndex);
481+
List<SlotReference> childToIndex = setOperation.getRegularChildrenOutputs().get(distributeToChildIndex);
482+
Map<ExprId, Integer> idToOutputIndex = new LinkedHashMap<>();
483+
for (int j = 0; j < childToIndex.size(); j++) {
484+
idToOutputIndex.put(childToIndex.get(j).getExprId(), j);
485+
}
486+
487+
List<ExprId> orderedShuffledColumns = childDistribution.getOrderedShuffledColumns();
488+
List<ExprId> setOperationDistributeColumnIds = new ArrayList<>();
489+
for (ExprId tableDistributeColumnId : orderedShuffledColumns) {
490+
Integer index = idToOutputIndex.get(tableDistributeColumnId);
491+
if (index == null) {
492+
break;
493+
}
494+
setOperationDistributeColumnIds.add(setOperation.getOutput().get(index).getExprId());
495+
}
496+
// check whether the set operation output all distribution columns of the child
497+
if (setOperationDistributeColumnIds.size() == orderedShuffledColumns.size()) {
498+
// Keep the basic child's specific storage layout as the set operation output. When
499+
// the basic child is on the right (shuffleToRight) the output rows are physically
500+
// placed by the right child's storage bucket function, so advertising that layout is
501+
// truthful: a parent can co-locate this set operation against the same layout, while
502+
// a sibling on a different layout is re-aligned rather than wrongly co-located. (The
503+
// earlier "Can not find tablet ... in the bucket" failure came from advertising a
504+
// layout-less EXECUTION_BUCKETED here, which erased the table id so two different-
505+
// layout set operations looked co-locatable; preserving the layout fixes that.)
506+
return new PhysicalProperties(
507+
new DistributionSpecHash(
508+
setOperationDistributeColumnIds,
509+
childDistribution.getShuffleType(),
510+
childDistribution.getTableId(),
511+
childDistribution.getSelectedIndexId(),
512+
childDistribution.getPartitionIds()
513+
)
514+
);
515+
}
516+
}
490517

491518
for (int i = 0; i < childrenDistribution.size(); i++) {
492519
DistributionSpec childDistribution = childrenDistribution.get(i);

0 commit comments

Comments
 (0)