Skip to content

Commit b82f5ea

Browse files
authored
feat: add support for comet cartesian join (apache#6938)
* add support for comet cartesian join * address review: make native cartesian product opt-in (default false) DataFusion's CrossJoinExec buffers the whole left input and cannot spill, so a large left can OOM where Spark's spillable CartesianProduct succeeds (sunchao's P2). Default the flag to false until the native path can spill; add a regression test that a cross join stays on Spark by default. Part of apache#199. * add benchmarks for comet cartesian join * add benchmarks for comet cartesian join move ests to sql file * update documentation per review * update documentation per review * update documentation abd tests per review * update documentation per review
1 parent 5252c82 commit b82f5ea

13 files changed

Lines changed: 512 additions & 15 deletions

File tree

‎docs/source/user-guide/latest/operators.md‎

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -53,7 +53,6 @@ The following operator families fall back to Spark and are not on the current ro
5353
omitted from the tables below and may be reconsidered based on demand:
5454

5555
- **Structured Streaming operators** (`StateStoreSaveExec`, `StateStoreRestoreExec`, `StreamingSymmetricHashJoinExec`, and similar): Comet targets batch execution.
56-
- **Cartesian / cross joins** (`CartesianProductExec`): rare and expensive, with little acceleration benefit.
5756
- **Pickled (non-Arrow) Python UDFs** (`BatchEvalPythonExec`): Comet accelerates Arrow-based Python UDFs only ([#4234](https://github.com/apache/datafusion-comet/pull/4234)).
5857
- **Typed Dataset operators** (`DeserializeToObjectExec`, `SerializeFromObjectExec`, `MapElementsExec`, `MapPartitionsExec`, `MapGroupsExec`, `CoGroupExec`, `AppendColumnsExec`, and similar): produced by `map`, `mapPartitions`, `groupByKey`, `cogroup`, and other typed `Dataset` transformations. They exist to run user JVM functions on JVM objects, which Comet cannot do natively. The operators above them can still run natively: set `spark.comet.convert.typedDataset.enabled=true` and Comet converts the output of a typed operation to Arrow. This is disabled by default because it can be slower than Spark when the operators above do little work, such as an aggregate over a few groups, which Spark compiles together with the typed operation into one loop.
5958

@@ -97,12 +96,13 @@ omitted from the tables below and may be reconsidered based on demand:
9796

9897
## Joins
9998

100-
| Operator | Status | Notes |
101-
| ----------------------------- | ------ | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
102-
| `BroadcastHashJoinExec` | ✅ | Falls back to Spark for a `NOT IN` (null-aware anti join) whose streamed side reports an ordering. |
103-
| `ShuffledHashJoinExec` | ✅ | |
104-
| `SortMergeJoinExec` | ✅ | Supports `BINARY` join keys. Nested-type (struct, array, map) and collated-string join keys fall back to Spark. |
105-
| `BroadcastNestedLoopJoinExec` | ✅ | Falls back to Spark when the preserved side is broadcast (for example LEFT OUTER with BROADCAST on the left) ([#4429](https://github.com/apache/datafusion-comet/pull/4429)). |
99+
| Operator | Status | Notes |
100+
| ----------------------------- | ------ | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
101+
| `BroadcastHashJoinExec` | ✅ | Falls back to Spark for a `NOT IN` (null-aware anti join) whose streamed side reports an ordering. |
102+
| `ShuffledHashJoinExec` | ✅ | |
103+
| `SortMergeJoinExec` | ✅ | Supports `BINARY` join keys. Nested-type (struct, array, map) and collated-string join keys fall back to Spark. |
104+
| `BroadcastNestedLoopJoinExec` | ✅ | Falls back to Spark when the preserved side is broadcast (for example LEFT OUTER with BROADCAST on the left) ([#4429](https://github.com/apache/datafusion-comet/pull/4429)). |
105+
| `CartesianProductExec` | ⚠️ | Opt-in (`spark.comet.exec.cartesianProduct.enabled`). Runs natively only without a join condition and when each input reports exactly one partition. Row order can differ from Spark's. |
106106

107107
`ExistenceJoin` (produced when `EXISTS` / `IN` is combined with another predicate via `OR`) runs
108108
natively on `BroadcastHashJoinExec` and `ShuffledHashJoinExec`. Existence sort-merge joins, residual

‎native/core/src/execution/jni_api.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -498,6 +498,7 @@ fn op_name(op: &OpStruct) -> &'static str {
498498
OpStruct::CsvScan(_) => "CsvScan",
499499
OpStruct::ShuffleScan(_) => "ShuffleScan",
500500
OpStruct::BroadcastNestedLoopJoin(_) => "BroadcastNestedLoopJoin",
501+
OpStruct::CrossJoin(_) => "CrossJoin",
501502
OpStruct::Sample(_) => "Sample",
502503
OpStruct::MergeRows(_) => "MergeRows",
503504
OpStruct::RangeScan(_) => "RangeScan",

‎native/core/src/execution/planner/join.rs‎

Lines changed: 46 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -15,8 +15,8 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18-
//! Builders for the native join operators (hash join, sort-merge join, and broadcast nested loop
19-
//! join), and the join-key and join-filter planning they share.
18+
//! Builders for the native join operators (hash join, sort-merge join, broadcast nested loop
19+
//! join, and cross join), and the join-key and join-filter planning they share.
2020
2121
use std::{collections::HashMap, sync::Arc};
2222

@@ -37,7 +37,8 @@ use datafusion::{
3737
physical_plan::{
3838
filter::FilterExec,
3939
joins::{
40-
utils::JoinFilter, HashJoinExec, NestedLoopJoinExec, PartitionMode, SortMergeJoinExec,
40+
utils::JoinFilter, CrossJoinExec, HashJoinExec, NestedLoopJoinExec, PartitionMode,
41+
SortMergeJoinExec,
4142
},
4243
projection::ProjectionExec,
4344
sorts::sort::SortExec,
@@ -420,6 +421,48 @@ impl OperatorBuilder for BroadcastNestedLoopJoinBuilder {
420421
}
421422
}
422423

424+
/// Builder for `CrossJoin` (Spark's `CartesianProductExec`).
425+
pub struct CrossJoinBuilder;
426+
427+
impl OperatorBuilder for CrossJoinBuilder {
428+
fn build(
429+
&self,
430+
spark_plan: &Operator,
431+
inputs: &mut Vec<Arc<Global<JObject<'static>>>>,
432+
partition_count: usize,
433+
planner: &PhysicalPlanner,
434+
) -> PlanCreationResult {
435+
let children = &spark_plan.children;
436+
437+
// No keys or condition. The join type only satisfies the helper; CrossJoinExec emits left
438+
// then right columns, as Spark does.
439+
let (join_params, scans, shuffle_scans) = planner.parse_join_parameters(
440+
inputs,
441+
children,
442+
&[],
443+
&[],
444+
JoinType::Inner as i32,
445+
&None,
446+
partition_count,
447+
)?;
448+
449+
let left = Arc::clone(&join_params.left.native_plan);
450+
let right = Arc::clone(&join_params.right.native_plan);
451+
452+
let cross_join = Arc::new(CrossJoinExec::new(left, right));
453+
454+
Ok((
455+
scans,
456+
shuffle_scans,
457+
Arc::new(SparkPlan::new(
458+
spark_plan.plan_id,
459+
cross_join,
460+
vec![join_params.left, join_params.right],
461+
)),
462+
))
463+
}
464+
}
465+
423466
impl PhysicalPlanner {
424467
/// Keep Spark metric identities for the small set of nodes whose children
425468
/// runtime-filter placement can replace. Stop at native/Spark tree boundaries.

‎native/core/src/execution/planner/operator_registry.rs‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -63,6 +63,7 @@ pub enum OperatorType {
6363
MergeRows,
6464
Explode,
6565
BroadcastNestedLoopJoin,
66+
CrossJoin,
6667
WindowGroupLimit,
6768
}
6869

@@ -151,7 +152,9 @@ impl OperatorRegistry {
151152

152153
/// Register join operators
153154
fn register_join_operators(&mut self) {
154-
use super::join::{BroadcastNestedLoopJoinBuilder, HashJoinBuilder, SortMergeJoinBuilder};
155+
use super::join::{
156+
BroadcastNestedLoopJoinBuilder, CrossJoinBuilder, HashJoinBuilder, SortMergeJoinBuilder,
157+
};
155158

156159
self.builders
157160
.insert(OperatorType::HashJoin, Box::new(HashJoinBuilder));
@@ -161,6 +164,8 @@ impl OperatorRegistry {
161164
OperatorType::BroadcastNestedLoopJoin,
162165
Box::new(BroadcastNestedLoopJoinBuilder),
163166
);
167+
self.builders
168+
.insert(OperatorType::CrossJoin, Box::new(CrossJoinBuilder));
164169
}
165170

166171
/// Register window operators
@@ -236,6 +241,7 @@ fn get_operator_type(spark_operator: &Operator) -> Option<OperatorType> {
236241
OpStruct::CsvScan(_) => Some(OperatorType::CsvScan),
237242
OpStruct::ShuffleScan(_) => Some(OperatorType::ShuffleScan),
238243
OpStruct::BroadcastNestedLoopJoin(_) => Some(OperatorType::BroadcastNestedLoopJoin),
244+
OpStruct::CrossJoin(_) => Some(OperatorType::CrossJoin),
239245
OpStruct::RangeScan(_) => None,
240246
OpStruct::Sample(_) => None, // Not yet in OperatorType enum
241247
OpStruct::MergeRows(_) => Some(OperatorType::MergeRows),

‎native/proto/src/proto/operator.proto‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -71,6 +71,7 @@ message Operator {
7171
RangeScan range_scan = 121;
7272
MergeRows merge_rows = 122;
7373
ArrowPythonUdf arrow_python_udf = 123;
74+
CrossJoin cross_join = 124;
7475
// Extension point for optional, out-of-tree contrib scans (Delta, Lance, ...). The concrete
7576
// scan message (e.g. `DeltaScan`) is packed into this envelope on the JVM side and dispatched
7677
// by `type_url` on the native side. Using a single permanent field -- rather than a new oneof
@@ -1163,6 +1164,10 @@ message BroadcastNestedLoopJoin {
11631164
optional spark.spark_expression.Expr condition = 3;
11641165
}
11651166

1167+
// Spark's CartesianProductExec without a condition (one with a condition falls back to Spark).
1168+
message CrossJoin {
1169+
}
1170+
11661171
enum JoinType {
11671172
Inner = 0;
11681173
LeftOuter = 1;

‎spark/src/main/scala/org/apache/comet/CometConf.scala‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -372,6 +372,14 @@ object CometConf extends ShimCometConf {
372372
createExecEnabledConfig("broadcastNestedLoopJoin", defaultValue = true)
373373
val COMET_EXEC_SORT_MERGE_JOIN_ENABLED: ConfigEntry[Boolean] =
374374
createExecEnabledConfig("sortMergeJoin", defaultValue = true)
375+
val COMET_EXEC_CARTESIAN_PRODUCT_ENABLED: ConfigEntry[Boolean] =
376+
createExecEnabledConfig(
377+
"cartesianProduct",
378+
defaultValue = false,
379+
notes = Some(
380+
"Opt-in: DataFusion's CrossJoinExec buffers the left input and cannot spill " +
381+
"(https://github.com/apache/datafusion/issues/26383). Runs natively only without a " +
382+
"join condition and when each input reports exactly one partition"))
375383
val COMET_EXEC_SORT_MERGE_JOIN_RIGHT_KEY_REDUCTION_ENABLED: ConfigEntry[Boolean] =
376384
conf(s"$COMET_EXEC_CONFIG_PREFIX.sortMergeJoin.rightKeyReduction.enabled")
377385
.category(CATEGORY_EXEC)

‎spark/src/main/scala/org/apache/comet/rules/CometCoalesceShufflePartitions.scala‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -104,7 +104,8 @@ case object CometCoalesceShufflePartitions extends AQEShuffleReadRule {
104104

105105
// A Comet operator whose Spark original's children Spark's rule coalesces one by one, with that
106106
// original. The class match mirrors Spark's, and Spark's rule decides, for its version, which
107-
// of these it actually treats that way. Comet has no counterpart of `CartesianProductExec`.
107+
// of these it actually treats that way. `CometCartesianProductExec` is left out because each of
108+
// its children is a single partition, so there is nothing to coalesce.
108109
private object Replaced {
109110
def unapply(plan: SparkPlan): Option[SparkPlan] = plan match {
110111
case comet: CometExec if comet.outputPartitioning.isInstanceOf[UnknownPartitioning] =>

‎spark/src/main/scala/org/apache/comet/rules/CometExecRule.scala‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -52,7 +52,7 @@ import org.apache.spark.sql.execution.datasources.v2.json.JsonScan
5252
import org.apache.spark.sql.execution.datasources.v2.parquet.ParquetScan
5353
import org.apache.spark.sql.execution.datasources.v2.text.TextScan
5454
import org.apache.spark.sql.execution.exchange.{BroadcastExchangeExec, BroadcastExchangeLike, Exchange, ReusedExchangeExec, ShuffleExchangeExec, ShuffleExchangeLike}
55-
import org.apache.spark.sql.execution.joins.{BaseJoinExec, BroadcastHashJoinExec, BroadcastNestedLoopJoinExec, ShuffledHashJoinExec, SortMergeJoinExec}
55+
import org.apache.spark.sql.execution.joins.{BaseJoinExec, BroadcastHashJoinExec, BroadcastNestedLoopJoinExec, CartesianProductExec, ShuffledHashJoinExec, SortMergeJoinExec}
5656
import org.apache.spark.sql.execution.window.WindowExec
5757
import org.apache.spark.sql.internal.SQLConf
5858
import org.apache.spark.sql.types._
@@ -120,6 +120,7 @@ object CometExecRule {
120120
classOf[BroadcastNestedLoopJoinExec] -> CometBroadcastNestedLoopJoinExec,
121121
classOf[ShuffledHashJoinExec] -> CometHashJoinExec,
122122
classOf[SortMergeJoinExec] -> CometSortMergeJoinExec,
123+
classOf[CartesianProductExec] -> CometCartesianProductExec,
123124
classOf[SortExec] -> CometSortExec,
124125
classOf[LocalTableScanExec] -> CometLocalTableScanExec,
125126
classOf[RangeExec] -> CometRangeExec,

‎spark/src/main/scala/org/apache/spark/sql/comet/operators.scala‎

Lines changed: 74 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,7 @@ import org.apache.spark.sql.execution.aggregate.{BaseAggregateExec, HashAggregat
4646
import org.apache.spark.sql.execution.columnar.InMemoryTableScanExec
4747
import org.apache.spark.sql.execution.datasources.v2.DataSourceV2ScanExecBase
4848
import org.apache.spark.sql.execution.exchange.ReusedExchangeExec
49-
import org.apache.spark.sql.execution.joins.{BroadcastHashJoinExec, BroadcastNestedLoopJoinExec, HashJoin, ShuffledHashJoinExec, SortMergeJoinExec}
49+
import org.apache.spark.sql.execution.joins.{BroadcastHashJoinExec, BroadcastNestedLoopJoinExec, CartesianProductExec, HashJoin, ShuffledHashJoinExec, SortMergeJoinExec}
5050
import org.apache.spark.sql.execution.metric.{SQLMetric, SQLMetrics}
5151
import org.apache.spark.sql.internal.SQLConf
5252
import org.apache.spark.sql.types.{ArrayType, BinaryType, BooleanType, ByteType, DataType, DateType, DecimalType, DoubleType, FloatType, IntegerType, IntegralType, LongType, MapType, ShortType, StringType, StructField, StructType, TimestampNTZType, TimestampType}
@@ -3289,6 +3289,79 @@ object CometBroadcastNestedLoopJoinExec extends CometOperatorSerde[BroadcastNest
32893289
}
32903290
}
32913291

3292+
case class CometCartesianProductExec(
3293+
override val nativeOp: Operator,
3294+
override val originalPlan: SparkPlan,
3295+
override val output: Seq[Attribute],
3296+
override val left: SparkPlan,
3297+
override val right: SparkPlan,
3298+
override val serializedPlanOpt: SerializedPlan)
3299+
extends CometBinaryExec {
3300+
3301+
// Inherits Spark's UnknownPartitioning from originalPlan, so exchange planning is unchanged.
3302+
3303+
// Each input must stay one partition. Without this, AQE's ValidateRequirements lets
3304+
// OptimizeSkewInRebalancePartitions split a REBALANCE(1) input after the product went native.
3305+
override def requiredChildDistribution: Seq[Distribution] = Seq(AllTuples, AllTuples)
3306+
3307+
override def withNewChildrenInternal(newLeft: SparkPlan, newRight: SparkPlan): SparkPlan =
3308+
this.copy(left = newLeft, right = newRight)
3309+
3310+
override def stringArgs: Iterator[Any] = Iterator(left, right)
3311+
3312+
override def equals(obj: Any): Boolean = {
3313+
obj match {
3314+
case other: CometCartesianProductExec =>
3315+
this.output == other.output &&
3316+
this.left == other.left &&
3317+
this.right == other.right &&
3318+
this.serializedPlanOpt == other.serializedPlanOpt
3319+
case _ =>
3320+
false
3321+
}
3322+
}
3323+
3324+
override def hashCode(): Int = Objects.hashCode(output, left, right)
3325+
3326+
override lazy val metrics: Map[String, SQLMetric] =
3327+
CometMetricNode.joinMetrics(sparkContext)
3328+
}
3329+
3330+
object CometCartesianProductExec extends CometOperatorSerde[CartesianProductExec] {
3331+
3332+
override def enabledConfig: Option[ConfigEntry[Boolean]] =
3333+
Some(CometConf.COMET_EXEC_CARTESIAN_PRODUCT_ENABLED)
3334+
3335+
override def getSupportLevel(op: CartesianProductExec): SupportLevel = {
3336+
// CartesianProductExec carries its own condition, and CrossJoinExec has no post-product filter.
3337+
if (op.condition.isDefined) {
3338+
Unsupported(Some("CartesianProduct with a join condition is not supported natively"))
3339+
} else if (op.left.outputPartitioning.numPartitions != 1 ||
3340+
op.right.outputPartitioning.numPartitions != 1) {
3341+
// A native plan runs per partition and cannot add an exchange here, so a cross product is
3342+
// only correct when both inputs are a single partition.
3343+
Unsupported(
3344+
Some(
3345+
"Native CartesianProduct requires single-partition inputs (a multi-partition " +
3346+
"cross product cannot be expressed per-partition)"))
3347+
} else {
3348+
Compatible(None)
3349+
}
3350+
}
3351+
3352+
override def convert(
3353+
op: CartesianProductExec,
3354+
builder: Operator.Builder,
3355+
childOp: Operator*): Option[Operator] = {
3356+
val joinBuilder = OperatorOuterClass.CrossJoin.newBuilder()
3357+
Some(builder.setCrossJoin(joinBuilder).build())
3358+
}
3359+
3360+
override def createExec(nativeOp: Operator, op: CartesianProductExec): CometNativeExec = {
3361+
CometCartesianProductExec(nativeOp, op, op.output, op.left, op.right, SerializedPlan(None))
3362+
}
3363+
}
3364+
32923365
object CometBroadcastHashJoinExec extends CometOperatorSerde[HashJoin] with CometHashJoin {
32933366

32943367
override def enabledConfig: Option[ConfigEntry[Boolean]] =

0 commit comments

Comments
 (0)