Proposal: introduced typed expressions, separate AST and IR

Currently DataFusion expressions (Expr) do not know their type. The type can be calculated via <Expr as ExprSchemable::get_type function.

This has drawbacks unfortunately

design: DF being reusable, it needs to account for different coercion rules and type logic of systems building on top of DF. Explicit (provided at construction time) expression type would better support this goal.
perf: as we add more and more optimizers, asking for expression type is going to be a common operation, slowing down planning process
- anecdotally, this was a problem for Trino expressions and recently Trino introduced separate IR expressions that carry explicit type

I believe the current design of expressions come from the fact they are used during initial AST (abstract syntax tree) processing where types aren't known yet. The pair (AST, AST → LogicalPlan conversion function) is an implementation of a language. DF implements its own variant of SQL (#12357) and systems building on top of DF may or may not use it (e.g. Ballista probably uses it and Comet wants to be closely aligned with Spark SQL's semantics).

Proposal plan

introduce datafusion's internal AST layer to support conversion from sqlparser's AST to LogicalPlan
- or maybe simply change the conversion so that it can calculate the types correctly
let Expr carry the type explicitly (that would be "logical type" from [Proposal] Decouple logical from physical types #11513)

@alamb

cc @alamb @notfilippo @jayzhan211 @comphead

I think select_to_plan is actually datafusion's internal AST layer that convert sqlparser AST to LogicalPlan, can you explain more what the difference between them is?

I don't quite understand why explicitly carrying the type in Expr would improve performance. If get_type is slow, wouldn't we face the same cost of determining the type when creating an Expr? If the computing the type is expensive, we could also consider caching the result. We also have a nullable property for Expr, if it makes sense not to explicit carrying nullable for Expr, wouldn't the same logic apply to type as well.

@jayzhan211

Thanks @jayzhan211 @findepi. Youguys are right, currently we using expr.get_type(schema) to get the exact data type, which is recursive and potentially can have some perfomance hit for deep nested types, probably insignificant. Carrying the datatype with Expr itself also has some benefits in runtime type eval.

What I'm trying to say is to make this large change it might be a very good reason for doing it. I think we need to list the exact benefits of having this refactoring

@comphead

why explicitly carrying the type in Expr would improve performance. If get_type is slow, wouldn't we face the same cost of determining the type when creating an Expr?

correct, unless get_type is called more than once. optimizer rules may check types.
DF doesn't have as many optimizer rules yet, but I am basing this on observation and profiling of Trino optimizer.

If the computing the type is expensive, we could also consider caching the result.

The type will be needed sooner or later. No need to have implicit cache for something that is needed and can be "cached" explicitly. Explicitness helps understand the contract -- if something is a field it implies it won't change.

Also, can Expr be used against two different DFSchemas? Currently it can (and may produce different types), but i assume this capability is incidental more than intentional.

We also have a nullable property for Expr, if it makes sense not to explicit carrying nullable for Expr, wouldn't the same logic apply to type as well.

That's a good question.
There are also other type- or value- related properties (aka traits), like range of possible values (intervals).

Not sure yet how these should be handled.

to make this large change it might be a very good reason for doing it. I think we need to list the exact benefits of having this refactoring

@comphead that's a very good call.
my main motivation isn't performance, it's the design & reliability. With DF being "LLVM for data processing", explicit is superior to implicit, especially that DF user could have different type derivation rules. Eg different coercions between types. To be even more concrete with example, Trino and SQL Server has different rules for coercing decimals of different precision and scale.

@comphead

let Expr carry the type explicitly (that would be "logical type"

I think this is the

correct, unless get_type is called more than once. optimizer rules may check types.
DF doesn't have as many optimizer rules yet, but I am basing this on observation and profiling of Trino optimi

FWIW I don't think i have seen get_type appear in the planning profiling traces (this may be because the overhead is mostly dominated by copies so the type calculations are overshadowed.

There are some times when the type of an intermedidate expression is needed (like the simplifier) but it doesn't seem to have been a bottleneck so far

to make this large change it might be a very good reason for doing it. I think we need to list the exact benefits of having this refactoring

I agree with @comphead -- I think this propsoal would be stronger if it was in the context of

I am trying to do X but the current way types are represented makes it not possible
I am trying to do Y but profiling shows a large amount of time being spent recomputing unecessary types

In other words, if we were designing a system from scratch this proposal makes sense to me, but I think at this point we already have a system that seems to work reasonably well for our existing users so just changing the design to be better without some practical improvement is a hard one for me

Eg different coercions between types. To be even more concrete with example, Trino and SQL Server has different rules for coercing decimals of different precision and scale.

I think making an API for user-defined coercion rules in DataFusion would be really nice (not just to support the usecase, but I think forcing the internal implementaiton into a thoughtful API would make the code easier to reason about and better strutured)

Lack of this looks like a blocker for Comet 44 update #13717 (comment)

We do not have access to the logical Expr to call the newer return_type_from_exprs because we are only working with DataFusion's physical plans.

I thought this ticket related to Logical exprs (which Comet doesn't use 🤔 )

Good point. i jumped the gun.
if we had types in the plan directly, it would be fairly trivial to weave them into physical plan.
and we had good IR, then -- maybe -- Comet would not run directly on physical plan.

For additional context on the Comet use case, we use Spark for query planning and then translate Spark's physical plan to a DataFusion physical plan. We do not use any SQL planning or logical planning from DataFusion.

The introduction of a new IR and new Expressions has these challenges

merit: actual design of the IR and new expressions
work: actual step by step evolutionary introduction of the IR and new expressions
buy in from maintainers to 'sponsor' or 'bless' the work

While we didn't make progress on the first two, it seems that at least that we made good progress on the last (but not least!), and there is general agreement that a better structured IR makes sense.

perf: as we add more and more optimizers, asking for expression type is going to be a common operation, slowing down planning process

Summary of my thought for this issue,

DataType, Nullability and maybe more are properties computed with Expr and corresponding Schema. Those properties combines with Expr are close to the "IR" described in this issue or "PlanProperties" similar to the concept used in PhysicalPlan

Plan1
 Plan2 (Expr2, Schema)
  Plan3 Data Soure (Schema)

Compute plan properties for plan2

Plan1
 Plan2 (Expr2 + Schema -> PlanProperties2)
  Plan3 Data Soure (Schema)

Compute plan properties for plan1

Plan1 (Expr1 + Schema + PlanProperties2 to get computed data type or nullability in the children -> PlanProperties1)
 Plan2 (Expr2 + Schema -> PlanProperties2)
  Plan3 Data Soure (Schema)

Whenever we try to rewrite the plan, either the Expr or Schema is changed, we recomputed them and store as part of PlanProperties.

In logical plan, I think we assume the schema is not changed at all if I remember correctly

The solution for this issue is to support plan properties as a cache for LogicalPlan

To implement this, we can follow how we cache such properties in PhysicalPlan, we can add such cache inside each logical plan struct

Navigation Menu

Repository navigation

Proposal: introduced typed expressions, separate AST and IR #12604

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Proposal: introduced typed expressions, separate AST and IR #12604

Description

Activity

findepi commented on Sep 24, 2024

jayzhan211 commented on Sep 24, 2024

comphead commented on Sep 24, 2024

findepi commented on Sep 24, 2024

alamb commented on Sep 26, 2024

findepi commented on Dec 11, 2024

alamb commented on Dec 11, 2024

findepi commented on Dec 11, 2024

andygrove commented on Dec 11, 2024

findepi commented on Dec 14, 2024

jayzhan211 commented on Jan 19, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions