sunchao commented on code in PR #25053:
URL: https://github.com/apache/datafusion/pull/25053#discussion_r3963555317
##########
datafusion/physical-expr/src/equivalence/properties/joins.rs:
##########
@@ -49,56 +49,17 @@ pub fn join_equivalence_properties(
..
} = right;
match maintains_input_order {
- [true, false] => {
- // In this special case, right side ordering can be prefixed with
- // the left side ordering.
- if matches!(join_type, JoinType::Inner | JoinType::Left)
- && probe_side == Some(JoinSide::Left)
- {
- updated_right_ordering_equivalence_class(
- &mut right_oeq_class,
- join_type,
- left_size,
- )?;
-
- // Right side ordering equivalence properties should be
prepended
- // with those of the left side while constructing output
ordering
- // equivalence properties since stream side is the left side.
- //
- // For example, if the right side ordering equivalences contain
- // `b ASC`, and the left side ordering equivalences contain `a
ASC`,
- // then we should add `a ASC, b ASC` to the ordering
equivalences
- // of the join output.
- let out_oeq_class =
left_oeq_class.join_suffix(&right_oeq_class);
- result.add_orderings(out_oeq_class);
- } else {
- result.add_orderings(left_oeq_class);
- }
- }
+ // Only the maintained side's ordering is guaranteed. With duplicate
+ // probe keys, the other side's matches repeat for each probe row, so
+ // its ordering cannot be appended as a suffix.
+ [true, false] => result.add_orderings(left_oeq_class),
[false, true] => {
updated_right_ordering_equivalence_class(
&mut right_oeq_class,
join_type,
left_size,
)?;
- // In this special case, left side ordering can be prefixed with
- // the right side ordering.
- if matches!(join_type, JoinType::Inner | JoinType::Right)
- && probe_side == Some(JoinSide::Right)
- {
- // Left side ordering equivalence properties should be
prepended
- // with those of the right side while constructing output
ordering
- // equivalence properties since stream side is the right side.
- //
- // For example, if the left side ordering equivalences contain
- // `a ASC`, and the right side ordering equivalences contain
`b ASC`,
- // then we should add `b ASC, a ASC` to the ordering
equivalences
- // of the join output.
- let out_oeq_class =
right_oeq_class.join_suffix(&left_oeq_class);
- result.add_orderings(out_oeq_class);
- } else {
- result.add_orderings(right_oeq_class);
- }
+ result.add_orderings(right_oeq_class);
Review Comment:
[P2] Preserve constraint-proven ordering for unique-build streaming joins
Unconditionally dropping the build-side suffix can make a previously
productive streaming query wait indefinitely, even when the input metadata
proves that suffix safe. I reproduced this with an inner hash join:
- Bounded build input: physical `PRIMARY KEY(k)` metadata, ordering `(k,
v)`, and rows `(1, 100), (2, 200)`.
- Unbounded probe input: ordered by `k`, emitting several `k = 1` rows and
then remaining pending.
- Required output: `ORDER BY probe.k, build.v LIMIT 1`.
The parent returns a row immediately. This head inserts `PartialSortExec`
with `TopK(fetch=1)` and `common_prefix_length=1`; it times out and cannot emit
until the key changes or the input ends. If the equal-key group never ends, it
never returns. Finite-input and equivalent-key-suffix controls still return
correctly.
The uniqueness premise is present on the physical build source and survives
all physical optimizer passes. Since each probe key matches at most one build
row, `build.v` is constant within each equal-`probe.k` group, making this
particular suffix valid for all inputs satisfying those guarantees.
Please preserve the narrowly proven inner-join case and add an unbounded
regression test. This needs both a suitable build unique/primary key and a
maintained ordering that determines the corresponding join keys; a primary-key
check alone would not justify restoring the old blanket `join_suffix` rule.
##########
datafusion/sqllogictest/test_files/joins.slt:
##########
@@ -6300,3 +6300,86 @@ reset datafusion.optimizer.repartition_file_scans;
statement ok
set datafusion.execution.target_partitions = 4;
+
+# Duplicate probe keys restart the build-side ordering for each matching row.
+statement ok
+set datafusion.execution.target_partitions = 2;
+
+statement ok
+set datafusion.optimizer.prefer_hash_join = false;
+
+statement ok
+CREATE TABLE duplicate_join_left AS VALUES (1, 10), (1, 20), (2, 30);
+
+statement ok
+CREATE TABLE duplicate_join_right AS VALUES (1, 100), (1, 200), (2, 300);
+
+# Sorting the build side alone must not satisfy the output ordering.
+query II
+SELECT l.column1, r.column2
+FROM duplicate_join_left l JOIN duplicate_join_right r ON l.column1 = r.column1
+ORDER BY l.column1, r.column2;
+----
+1 100
+1 100
+1 200
+1 200
+2 300
+
+query II
+SELECT l.column1, r.column2
+FROM duplicate_join_left l JOIN duplicate_join_right r ON l.column1 = r.column1
+ORDER BY l.column1, r.column2 LIMIT 2;
Review Comment:
Consider adding a LIMIT case that fails without the fix
This exact `LIMIT 2` query also passes on the parent commit: a `SortExec:
TopK(fetch=2)` remains above the sort-merge join. The new plain ORDER BY,
ranking, and ordered-source right-join tests do reproduce the bug, but this
particular test does not establish the LIMIT impact.
A direct physical-plan regression can cover it: keep an explicit
`SortExec(left.k, right.v).with_fetch(Some(2))` above an inner
`SortMergeJoinExec`, with the left input sorted by `k` and the right input
sorted by `(k, v)`. With two left rows for `k=1` and right values `100, 200`,
the parent returns `100, 200` while this head correctly returns `100, 100`.
That also exercises the runtime sort-skipping path used by direct physical-plan
consumers.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
