Incorrect results for join condition against current master branch #4844

DDtKey · 2023-01-07T17:07:23Z

Describe the bug
Join condition(on with between) works incorrectly.
Looks like ignored and returned cartesian product.

It used to work for latest stable release (15.0.0 from crates.io)
But I tested it against current master branch, hash 3cc607de4ce6e9e1fd537091e471858c62f58653.

To Reproduce
Steps to reproduce the behavior:
students.csv:

name,mark
Stuart,28
Amina,89
Christen,50
Salma,77
Samantha,21

grades.csv:

grade,min,max
1,0,14
2,15,35
3,36,55
4,56,79
5,80,100

MRE:

use datafusion::prelude::{CsvReadOptions, SessionContext};

#[tokio::main]
async fn main() -> anyhow::Result<()> {
    let students_path = "../students.csv";
    let grades_path = "../grades.csv";

    // Datafusion execution
    let ctx = SessionContext::new();

    ctx.register_csv("students", students_path, CsvReadOptions::default())
        .await?;

    ctx.register_csv("grades", grades_path, CsvReadOptions::default())
        .await?;

    let data_frame = ctx.sql("SELECT s.*, g.grade FROM students s join grades g on s.mark between g.min and g.max WHERE grade > 2 ORDER BY s.mark DESC").await?;

    data_frame.show().await?;

    Ok(())
}

It will return:

+----------+------+-------+
| name     | mark | grade |
+----------+------+-------+
| Amina    | 89   | 3     |
| Amina    | 89   | 4     |
| Amina    | 89   | 5     |
| Salma    | 77   | 3     |
| Salma    | 77   | 4     |
| Salma    | 77   | 5     |
| Christen | 50   | 3     |
| Christen | 50   | 4     |
| Christen | 50   | 5     |
| Stuart   | 28   | 3     |
| Stuart   | 28   | 4     |
| Stuart   | 28   | 5     |
| Samantha | 21   | 3     |
| Samantha | 21   | 4     |
| Samantha | 21   | 5     |
+----------+------+-------+

Expected behavior
It should be the same as for datafusion = "15.0.0":

+----------+------+-------+
| name     | mark | grade |
+----------+------+-------+
| Amina    | 89   | 5     |
| Salma    | 77   | 4     |
| Christen | 50   | 3     |
+----------+------+-------+

The text was updated successfully, but these errors were encountered:

ozankabak · 2023-01-07T20:29:28Z

Wow, let's make sure to add some tests so regressions like this do not stealthily go through in the future 🤔

Jefffrey · 2023-01-08T00:14:21Z

Looks to be regression introduced by fddb3d3 (#4562)

On the commit prior to it (2792113), I get this explain plan:

+------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| plan_type                                                  | plan                                                                                                                                                                    |
+------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| initial_logical_plan                                       | Sort: s.mark DESC NULLS FIRST                                                                                                                                           |
|                                                            |   Projection: s.name, s.mark, g.grade                                                                                                                                   |
|                                                            |     Filter: g.grade > Int64(2)                                                                                                                                          |
|                                                            |       Filter: s.mark BETWEEN g.min AND g.max                                                                                                                            |
|                                                            |         CrossJoin:                                                                                                                                                      |
|                                                            |           SubqueryAlias: s                                                                                                                                              |
|                                                            |             TableScan: students                                                                                                                                         |
|                                                            |           SubqueryAlias: g                                                                                                                                              |
|                                                            |             TableScan: grades                                                                                                                                           |
| logical_plan after inline_table_scan                       | SAME TEXT AS ABOVE                                                                                                                                                      |
| logical_plan after type_coercion                           | SAME TEXT AS ABOVE                                                                                                                                                      |
| logical_plan after simplify_expressions                    | Sort: s.mark DESC NULLS FIRST                                                                                                                                           |
|                                                            |   Projection: s.name, s.mark, g.grade                                                                                                                                   |
|                                                            |     Filter: g.grade > Int64(2)                                                                                                                                          |
|                                                            |       Filter: s.mark >= g.min AND s.mark <= g.max                                                                                                                       |
|                                                            |         CrossJoin:                                                                                                                                                      |
|                                                            |           SubqueryAlias: s                                                                                                                                              |
|                                                            |             TableScan: students                                                                                                                                         |
|                                                            |           SubqueryAlias: g                                                                                                                                              |
|                                                            |             TableScan: grades                                                                                                                                           |
...
| logical_plan after eliminate_cross_join                    | SAME TEXT AS ABOVE                                                                                                                                                      |
...
| logical_plan after push_down_filter                        | Sort: s.mark DESC NULLS FIRST                                                                                                                                           |
|                                                            |   Projection: s.name, s.mark, g.grade                                                                                                                                   |
|                                                            |     Filter: s.mark >= g.min AND s.mark <= g.max                                                                                                                         |
|                                                            |       CrossJoin:                                                                                                                                                        |
|                                                            |         SubqueryAlias: s                                                                                                                                                |
|                                                            |           TableScan: students                                                                                                                                           |
|                                                            |         SubqueryAlias: g                                                                                                                                                |
|                                                            |           Filter: grades.grade > Int64(2)                                                                                                                               |
|                                                            |             TableScan: grades, partial_filters=[grades.grade > Int64(2)]
...

And on commit fddb3d3 I get this plan instead:

+------------------------------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------+
| plan_type                                                  | plan                                                                                                                                                       |
+------------------------------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------+
| initial_logical_plan                                       | Sort: s.mark DESC NULLS FIRST                                                                                                                              |
|                                                            |   Projection: s.name, s.mark, g.grade                                                                                                                      |
|                                                            |     Filter: g.grade > Int64(2)                                                                                                                             |
|                                                            |       Inner Join:  Filter: s.mark BETWEEN g.min AND g.max                                                                                                  |
|                                                            |         SubqueryAlias: s                                                                                                                                   |
|                                                            |           TableScan: students                                                                                                                              |
|                                                            |         SubqueryAlias: g                                                                                                                                   |
|                                                            |           TableScan: grades                                                                                                                                |
| logical_plan after inline_table_scan                       | SAME TEXT AS ABOVE                                                                                                                                         |
| logical_plan after type_coercion                           | SAME TEXT AS ABOVE                                                                                                                                         |
| logical_plan after simplify_expressions                    | Sort: s.mark DESC NULLS FIRST                                                                                                                              |
|                                                            |   Projection: s.name, s.mark, g.grade                                                                                                                      |
|                                                            |     Filter: g.grade > Int64(2)                                                                                                                             |
|                                                            |       Inner Join:  Filter: s.mark >= g.min AND s.mark <= g.max AS s.mark BETWEEN g.min AND g.max                                                           |
|                                                            |         SubqueryAlias: s                                                                                                                                   |
|                                                            |           TableScan: students                                                                                                                              |
|                                                            |         SubqueryAlias: g                                                                                                                                   |
|                                                            |           TableScan: grades                                                                                                                                |
...
| logical_plan after eliminate_cross_join                    | Sort: s.mark DESC NULLS FIRST                                                                                                                              |
|                                                            |   Projection: s.name, s.mark, g.grade                                                                                                                      |
|                                                            |     Filter: g.grade > Int64(2)                                                                                                                             |
|                                                            |       CrossJoin:                                                                                                                                           |
|                                                            |         SubqueryAlias: s                                                                                                                                   |
|                                                            |           TableScan: students                                                                                                                              |
|                                                            |         SubqueryAlias: g                                                                                                                                   |
|                                                            |           TableScan: grades                                                                                                                                |
...
| logical_plan after push_down_filter                        | Sort: s.mark DESC NULLS FIRST                                                                                                                              |
|                                                            |   Projection: s.name, s.mark, g.grade                                                                                                                      |
|                                                            |     CrossJoin:                                                                                                                                             |
|                                                            |       SubqueryAlias: s                                                                                                                                     |
|                                                            |         TableScan: students                                                                                                                                |
|                                                            |       SubqueryAlias: g                                                                                                                                     |
|                                                            |         Filter: grades.grade > Int64(2)                                                                                                                    |
|                                                            |           TableScan: grades, partial_filters=[grades.grade > Int64(2)]

The actual regression seems to be caused by the SQL planner generating the initial logical plan with an Inner Join instead of a Cross Join, and this propagates down to cause the bug.

However it seems to highlight the actual flaw which is in eliminate_cross_join optimizer rule which converts the plan from:

Sort: s.mark DESC NULLS FIRST
  Projection: s.name, s.mark, g.grade
    Filter: g.grade > Int64(2)
      Inner Join:  Filter: s.mark >= g.min AND s.mark <= g.max AS s.mark BETWEEN g.min AND g.max
        SubqueryAlias: s
          TableScan: students
        SubqueryAlias: g
          TableScan: grades

to

Sort: s.mark DESC NULLS FIRST
  Projection: s.name, s.mark, g.grade
    Filter: g.grade > Int64(2)
      CrossJoin:
        SubqueryAlias: s
          TableScan: students
        SubqueryAlias: g
          TableScan: grades

Where it completely discards the Filter on the Inner Join when converting it to a Cross Join, causing the buggy behaviour

ygf11 · 2023-01-08T02:25:17Z

It seems the EliminateCrossJoin rule only collect and consider the equijoin predicates when finding an appropriate right input of join. We can extend equijoin to all join predicate(equijoin and non-equi join), this issue will be fixed I think.

I will submit a pr later if others do not fix it.

alamb · 2023-01-08T22:35:52Z

cc @liukun4515

alamb · 2023-01-08T22:36:30Z

Definitely it would be great to get some test coverage for this case.

ozankabak · 2023-01-09T17:34:58Z

IMO it would be a good idea to fix this before releasing, this seems like a regression on fundamental functionality. Happy to help with reviewing the fix PR.

alamb · 2023-01-10T06:30:06Z

IMO it would be a good idea to fix this before releasing,

I agree -- I have mentioned it on the mailing list vote thread. @ygf11 can you work on a PR for this issue soon?

ygf11 · 2023-01-10T06:46:49Z

I agree -- I have mentioned it on the mailing list vote thread. @ygf11 can you work on a PR for this issue soon?

Of course @alamb , I will submit a pr today or tomorrow.

liukun4515 · 2023-01-10T11:03:55Z

It seems the EliminateCrossJoin rule only collect and consider the equijoin predicates when finding an appropriate right input of join. We can extend equijoin to all join predicate(equijoin and non-equi join), this issue will be fixed I think.

I will submit a pr later if others do not fix it.

I think the plan should be the inner join not the cross join

liukun4515 · 2023-01-10T11:07:02Z

eliminate_cross_join

Yes, we can just fix this bug in the eliminate_cross_join rule.
cc @alamb

jackwener · 2023-01-10T11:13:36Z

I debug it, it is because find join_key just consider equal instead of consider non-equal

liukun4515 · 2023-01-10T11:15:02Z

I agree -- I have mentioned it on the mailing list vote thread. @ygf11 can you work on a PR for this issue soon?

Of course @alamb , I will submit a pr today or tomorrow.

@ygf11 waiting for your PR

ygf11 · 2023-01-10T16:19:22Z

I meet a strange problem when I do the pr #4866.

After I fix the test, the tcph-q11 will panic when run sqllogictests(the plan of q11 is modified), the direct panic message:

thread 'tokio-runtime-worker' panicked at 'partition not used yet', datafusion/core/src/physical_plan/repartition.rs:405:14 ... at tests/sqllogictests/test_files/tpch.slt:456.

I have no idea about it now, need to investigate more.
More info: https://github.com/apache/arrow-datafusion/actions/runs/3884323174/jobs/6626733651

To not block the release, I think maybe we can skip EliminateCrossJoin rule when it meet any inner-join input who has non-empty filter(this is consistent with datafusion 15).

With the patch, the sql of this issue will get the correct result.
For the feature of #4866, some query in datafusion 15 will get wrong result, and if we skip EliminateCrossJoin, datafusion 16(release soon) will get correct result, although the plan is not better optimized.

cc @alamb @liukun4515 @jackwener

ygf11 · 2023-01-10T16:34:06Z

I create #4869 to show the patch.

jackwener · 2023-01-10T16:50:30Z

This problem remind me the importance of #4615.

andygrove · 2023-01-11T20:10:21Z

Should this issue be closed now that #4869 is merged?

alamb · 2023-01-11T20:19:39Z

Should this issue be closed now that #4869 is merged?

yes I think we should use this ticket to track the incorrect result. I will file another ticket to track the improvement proposed in #4866

alamb · 2023-01-11T20:23:12Z

Filed #4877 to track the work to properly support this case. Thank you all for your work to fix this issue

DDtKey added the bug Something isn't working label Jan 7, 2023

DDtKey mentioned this issue Jan 7, 2023

SQL statement (UNION + EXCEPT) causes panic #4837

Closed

DDtKey changed the title ~~Incorrect results for join broken in current master branch~~ Incorrect results for join condition against current master branch Jan 7, 2023

ygf11 mentioned this issue Jan 10, 2023

Support non-equijoin predicate for EliminateCrossJoin #4866

Closed

alamb closed this as completed Jan 11, 2023

alamb mentioned this issue Jan 11, 2023

Support non-equijoin predicate for EliminateCrossJoin #4866 #4877

Closed

epsio-banay mentioned this issue Sep 12, 2023

Incorrect results for nested joins after applying EliminateCrossJoin rule #7530

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Incorrect results for join condition against current master branch #4844

Incorrect results for join condition against current master branch #4844

DDtKey commented Jan 7, 2023 •

edited

Loading

ozankabak commented Jan 7, 2023

Jefffrey commented Jan 8, 2023

ygf11 commented Jan 8, 2023 •

edited

Loading

alamb commented Jan 8, 2023

alamb commented Jan 8, 2023 •

edited

Loading

ozankabak commented Jan 9, 2023 •

edited

Loading

alamb commented Jan 10, 2023

ygf11 commented Jan 10, 2023

liukun4515 commented Jan 10, 2023

liukun4515 commented Jan 10, 2023

jackwener commented Jan 10, 2023

liukun4515 commented Jan 10, 2023

ygf11 commented Jan 10, 2023

ygf11 commented Jan 10, 2023

jackwener commented Jan 10, 2023 •

edited

Loading

andygrove commented Jan 11, 2023

alamb commented Jan 11, 2023

alamb commented Jan 11, 2023

Incorrect results for join condition against current master branch #4844

Incorrect results for join condition against current master branch #4844

Comments

DDtKey commented Jan 7, 2023 • edited Loading

MRE:

ozankabak commented Jan 7, 2023

Jefffrey commented Jan 8, 2023

ygf11 commented Jan 8, 2023 • edited Loading

alamb commented Jan 8, 2023

alamb commented Jan 8, 2023 • edited Loading

ozankabak commented Jan 9, 2023 • edited Loading

alamb commented Jan 10, 2023

ygf11 commented Jan 10, 2023

liukun4515 commented Jan 10, 2023

liukun4515 commented Jan 10, 2023

jackwener commented Jan 10, 2023

liukun4515 commented Jan 10, 2023

ygf11 commented Jan 10, 2023

ygf11 commented Jan 10, 2023

jackwener commented Jan 10, 2023 • edited Loading

andygrove commented Jan 11, 2023

alamb commented Jan 11, 2023

alamb commented Jan 11, 2023

DDtKey commented Jan 7, 2023 •

edited

Loading

ygf11 commented Jan 8, 2023 •

edited

Loading

alamb commented Jan 8, 2023 •

edited

Loading

ozankabak commented Jan 9, 2023 •

edited

Loading

jackwener commented Jan 10, 2023 •

edited

Loading