[jira] [Created] (SPARK-32687) CostBasedJoinReorder should have deterministic Optimization result

["Yang Jie (Jira)" <ji...@apache.org>]

Yang Jie created SPARK-32687:
--------------------------------

             Summary: CostBasedJoinReorder should have deterministic Optimization result
                 Key: SPARK-32687
                 URL: https://issues.apache.org/jira/browse/SPARK-32687
             Project: Spark
          Issue Type: Improvement
          Components: SQL
    Affects Versions: 3.0.0, 3.0.1, 3.1.0
            Reporter: Yang Jie


In [SPARK-32526|[https://github.com/apache/spark/pull/29434]], we found the optimization result of CostBasedJoinReorder is non-deterministic now, it affected by the input order if there more than one same cost candidate plans.

The test case named "Test 4: Star with several branches" in StarJoinCostBasedReorderSuite is a typical case.

If we use {{permutations of 10 tables(}}{{d1, t3, t4, f1, d2, t5, t6, d3, t1, t2}}{{) as input set, there will be total of 3628000 candidate input plan with different orders.}}

 

We define original expected optimization result as *A:*

 
{code:java}

{code}
*f1.join(d3, Inner, Some(nameToAttr("f1_fk3") === nameToAttr("d3_pk")))
   .join(d1, Inner, Some(nameToAttr("f1_fk1") === nameToAttr("d1_pk")))
   .join(d2, Inner, Some(nameToAttr("f1_fk2") === nameToAttr("d2_pk")))
   .join(t4.join(t3, Inner, Some(nameToAttr("t3_c2") === nameToAttr("t4_c2"))), Inner,
     Some(nameToAttr("d1_c2") === nameToAttr("t3_c1")))
   .join(t2.join(t1, Inner, Some(nameToAttr("t1_c2") === nameToAttr("t2_c2"))), Inner,
     Some(nameToAttr("d3_c2") === nameToAttr("t1_c1")))
   .join(t5.join(t6, Inner, Some(nameToAttr("t5_c2") === nameToAttr("t6_c2"))), Inner,
     Some(nameToAttr("d2_c2") === nameToAttr("t5_c1")))***

 

{{and define the other one optimization result as }}{{*B*}}{{}}

{{}}
{code:java}

{code}
{{f1.join(d3, Inner, Some(nameToAttr("f1_fk3") === nameToAttr("d3_pk")))
   .join(d2, Inner, Some(nameToAttr("f1_fk2") === nameToAttr("d2_pk")))
   .join(d1, Inner, Some(nameToAttr("f1_fk1") === nameToAttr("d1_pk")))
   .join(t4.join(t3, Inner, Some(nameToAttr("t3_c2") === nameToAttr("t4_c2"))), Inner,
     Some(nameToAttr("d1_c2") === nameToAttr("t3_c1")))
   .join(t2.join(t1, Inner, Some(nameToAttr("t1_c2") === nameToAttr("t2_c2"))), Inner,
     Some(nameToAttr("d3_c2") === nameToAttr("t1_c1")))
   .join(t5.join(t6, Inner, Some(nameToAttr("t5_c2") === nameToAttr("t6_c2"))), Inner,
     Some(nameToAttr("d2_c2") === nameToAttr("t5_c1")))}}

 

{{}}

{{then use "Test 4: Star with several branches" in StarJoinCostBasedReorderSuite to test optimization results of 3628000 inputs as described above. We found that 1813600 results were candidate *A* and ** 1814400 results were candidate *B.*}}

Now the result of CostBasedJoinReorder rule is non-deterministic, we need to find a way to make it deterministic even if the input order is different.

 

{{}}

{{}}

{{}}

{{}}

{{}}

{{}}

{{}}

{{}}

{{}}



--
This message was sent by Atlassian Jira
(v8.3.4#803005)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org