FULL OUTER JOIN and LIMIT produces wrong results

[alamb]

Describe the bug

LIMITs are incorrectly pushed through FULL OUTER Joins

To Reproduce

COPY (values (1), (2), (3), (4), (5))  TO '/tmp/t1.csv' STORED AS CSV;
-- store t2 in different order so the top N rows are not the same as the top N rows of t1
COPY (values (5), (4), (3), (2), (1))  TO '/tmp/t2.csv' STORED AS CSV;

statement ok
create external table t1(a int) stored as CSV location '/tmp/t1.csv';

statement ok
create external table t2(b int) stored as CSV location '/tmp/t2.csv';

-- FULL join produces 5 rows (all have matches)
select * from t1 FULL JOIN t2 ON t1.a = t2.b;
/*
+---+---+
| a | b |
+---+---+
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
+---+---+
*/

-- the output of this query should be two rows from the previous query, there
-- should be no nulls
select * from t1 FULL JOIN t2 ON t1.a = t2.b LIMIT 2;

/*
+------+------+
| a    | b    |
+------+------+
| 1    | NULL |
| NULL | 4    |
+------+------+
*/

Expected behavior

Any two rows from

+---+---+
| a | b |
+---+---+
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
+---+---+

There should be no nulls introduced

Additional context

Found while working with @zhuqi-lucas on:

• fix: LimitPushdown rule uncorrect remove some GlobalLimitExec #14245

[alamb]

I think @zhuqi-lucas found the issue. This line is almost certainly wrong:

datafusion/datafusion/optimizer/src/push_down_limit.rs

Line 258 in e3db359

Full => (Some(limit), Some(limit)),

[alamb]

I wrote some tests for this here:

• Add test case for incorrect FULL OUTER JOIN + LIMIT pushdown @alamb #14336

[alamb]

I don't think this is a regression (it has been like this for while)

It seems to have been introduced in

• Optimization: support push down limit when full join #12963

[alamb]

I also filed this ticket to track making it easier to test for this kind of thing

• Implement fetch limit for MemoryExec #14337

[zhuqi-lucas]

take

[zhuqi-lucas]

Thank you @alamb!

I want to take this task, and for the first step, i think we should disable full outer join push down limit.

For further improvement, we can investigate if we have some cases which we can support push down limit for full outer join.

[zhuqi-lucas]

Submitted a PR for review!