Support type coercion for subquery

[liukun4515]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.
A clear and concise description of what the problem is. Ex. I'm always frustrated when [...]
(This section helps Arrow developers understand the context and why for this feature, in addition to the what)

When I do #3396, the type coercion should be first do before other optimization.

But for the recursion subquery, we can't do the type coercion before generated the subquery sub expr or plan.

like in this test correlated_recursive_scalar_subquery

If I move the type coercion to the first rule of the optimizer, i will get the changes

Sort: #customer.c_custkey ASC NULLS LAST
  Projection: #customer.c_custkey
    Filter: CAST(#customer.c_acctbal AS Decimal128(25, 2)) < #__sq_2.__value
      Inner Join: #customer.c_custkey = #__sq_2.o_custkey
        TableScan: customer projection=[c_custkey, c_acctbal]
        Projection: #orders.o_custkey, #SUM(orders.o_totalprice) AS __value, alias=__sq_2
          Aggregate: groupBy=[[#orders.o_custkey]], aggr=[[SUM(#orders.o_totalprice)]]
            Filter: CAST(#orders.o_totalprice AS Decimal128(25, 2)) < #__sq_1.__value
              Inner Join: #orders.o_orderkey = #__sq_1.l_orderkey
                TableScan: orders projection=[o_orderkey, o_custkey, o_totalprice]
                Projection: #lineitem.l_orderkey, #SUM(lineitem.l_extendedprice) AS price AS __value, alias=__sq_1
                  Aggregate: groupBy=[[#lineitem.l_orderkey]], aggr=[[SUM(#lineitem.l_extendedprice)]]
                    TableScan: lineitem projection=[l_orderkey, l_extendedprice]

to

Sort: #customer.c_custkey ASC NULLS LAST
  Projection: #customer.c_custkey
    Filter: CAST(#customer.c_acctbal AS Decimal128(25, 2)) < #__sq_2.__value
      Inner Join: #customer.c_custkey = #__sq_2.o_custkey
        TableScan: customer projection=[c_custkey, c_acctbal]
        Projection: #orders.o_custkey, #SUM(orders.o_totalprice) AS __value, alias=__sq_2
          Aggregate: groupBy=[[#orders.o_custkey]], aggr=[[SUM(#orders.o_totalprice)]]
            Filter: #orders.o_totalprice < #__sq_1.__value
              Inner Join: #orders.o_orderkey = #__sq_1.l_orderkey
                TableScan: orders projection=[o_orderkey, o_custkey, o_totalprice]
                Projection: #lineitem.l_orderkey, #SUM(lineitem.l_extendedprice) AS price AS __value, alias=__sq_1
                  Aggregate: groupBy=[[#lineitem.l_orderkey]], aggr=[[SUM(#lineitem.l_extendedprice)]]
                    TableScan: lineitem projection=[l_orderkey, l_extendedprice]

Can't get the type coercion result of Filter: #orders.o_totalprice < #__sq_1.__value

Describe the solution you'd like
A clear and concise description of what you want to happen.

Describe alternatives you've considered
A clear and concise description of any alternative solutions or features you've considered.

Additional context
Add any other context or screenshots about the feature request here.

[liukun4515]

I debug the test case, and find the reason.
In the type coercion, we don't handle the subquery expr and sub query plan.
Below this is log

2022-09-27T03:52:57Z TRACE datafusion_optimizer::optimizer] Full input logical plan:
    Sort: #customer.c_custkey ASC NULLS LAST
      Projection: #customer.c_custkey
        Filter: #customer.c_acctbal < (<subquery>)
          Subquery:
            Projection: #SUM(orders.o_totalprice)
              Aggregate: groupBy=[[]], aggr=[[SUM(#orders.o_totalprice)]]
                Filter: #orders.o_custkey = #customer.c_custkey AND #orders.o_totalprice < (<subquery>)
                  Subquery:
                    Projection: #SUM(lineitem.l_extendedprice) AS price
                      Aggregate: groupBy=[[]], aggr=[[SUM(#lineitem.l_extendedprice)]]
                        Filter: #lineitem.l_orderkey = #orders.o_orderkey
                          TableScan: lineitem
                  TableScan: orders
          TableScan: customer
[2022-09-27T03:52:57Z DEBUG datafusion_optimizer::optimizer] After apply type_coercion rule:

[2022-09-27T03:52:57Z DEBUG datafusion_optimizer::optimizer] Optimized logical plan:
    Sort: #customer.c_custkey ASC NULLS LAST
      Projection: #customer.c_custkey
        Filter: CAST(#customer.c_acctbal AS Decimal128(25, 2)) < (<subquery>)
          Subquery:
            Projection: #SUM(orders.o_totalprice)
              Aggregate: groupBy=[[]], aggr=[[SUM(#orders.o_totalprice)]]
                Filter: #orders.o_custkey = #customer.c_custkey AND #orders.o_totalprice < (<subquery>)
                  Subquery:
                    Projection: #SUM(lineitem.l_extendedprice) AS price
                      Aggregate: groupBy=[[]], aggr=[[SUM(#lineitem.l_extendedprice)]]
                        Filter: #lineitem.l_orderkey = #orders.o_orderkey
                          TableScan: lineitem
                  TableScan: orders
          TableScan: customer

I think the rewrite could handle the sub query plan.
Do you have any comments for that? @andygrove I know you have implemented the subquery.

[liukun4515]

I go through code of trait ExprRewritable, how to rewrite the subquery for the sub query expr like below:

Expr::InSubquery {
                expr,
                subquery,
                negated,
            } => Expr::InSubquery {
                expr: rewrite_boxed(expr, rewriter)?,
                subquery,
                negated,
            },

Above code just rewrite the expr, and don't rewrite the sub query plan, why not rewrite the subquery plan with its exprs?
cc @andygrove

[liukun4515]

I meet the issue when i want to do the type coercion in the sub query.

[Dandandan]

I think you are right - the subquery needs to be visited / type coerced as well.

[liukun4515]

I think you are right - the subquery needs to be visited / type coerced as well.

we use the ExprRewritable framework to rewrite the expr and implement the type coercion function, but the sub query plan will not be handle in the ExprRewritable framework.

Do you have any suggestion or thoughts?
@Dandandan