[Discuss] Different implementation style between Expr, LogicalPlan and ExecutionPlan

[mingmwang]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

In current DataFusion code base, Expr, LogicalPlan and ExecutionPlan are represented in different ways. Actually they are all tree based structures. Expr and LogicalPlan are Enums, ExecutionPlan is a Trait.
The LogicalPlan enum wrapped the different logical operator structs like Projection and Filter, etc.

pub enum LogicalPlan {
    Projection(Projection),
    Filter(Filter),
    ............
}

But the Expr enum doesn't wrap the expression structs and define the different expressions directly in the enum.

pub enum Expr {
    Alias(Box<Expr>, String),
    Column(Column),
    ............
    AggregateFunction {
        fun: aggregate_function::AggregateFunction,
        args: Vec<Expr>,
        distinct: bool,
    },
    WindowFunction {
        fun: window_function::WindowFunction,
        args: Vec<Expr>,
        partition_by: Vec<Expr>,
        order_by: Vec<Expr>,
        window_frame: Option<window_frame::WindowFrame>,
    },
    ............
}

I think we should unify the coding style, at least the Expr and LogicalPlan representations should follow the same style. And for physical ExecutionPlan, it is Trait/Trait Objects, I would prefer to use Enum also. Want to hear thoughts from other members.

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.

[mingmwang]

@alamb @yjshen @andygrove @thinkharderdev @liukun4515

[jackwener]

And for physical ExecutionPlan, it is Trait/Trait Objects, I would prefer to use Enum also

I also agree this point.

[yjshen]

The LogicalPlan moved to its current style in #1228 thanks to @xudong963 and @liukun4515. I agree we could apply this style to expressions as well.

[tustvold]

Thank you for raising this, its really good to have these discussions. I would definitely support making the enumeration style consistent, and the expression struct pattern has the non-trivial advantage of being able to name the variant types 👍

With respect to making ExecutionPlan an enumeration:

• ExecutionPlan has a fairly large number of member functions, and having a massive match block for each of these seems somewhat sub-optimal
• We would still need to have a dyn Trait in the topology for extensions, much like we have UserDefinedLogicalNode for LogicalPlan
• The major advantage of an enumeration is being able to enumerate all the possible states, I'm struggling to devise a use-case that wouldn't be equally well served by a member function
• Traits provide encapsulation by object, whereas enumerations provide encapsulation by function. Taking the example of a serialization routine, with trait objects each operator would define its serialization routine alongside its other functionality, with an enumeration you would instead define serialization for all operators in one function. It's possibly subjective but I prefer the former
• I'm currently working on scheduling of plan execution, with an eventual hope to implement something akin to morsel-driven parallelism. Currently this fudges around the interface of ExecutionPlan, but may eventually warrant non-trivial changes to it (e.g. making it less async), churning this interface multiple times in quick succession is probably something we want to avoid if possible

That being said, I don't really feel strongly about any particular design, just putting the information out there 😄

[alamb]

And for physical ExecutionPlan, it is Trait/Trait Objects, I would prefer to use Enum also

I agree this would be nice for code consistency. The fact it is a trait has always bothered me (mostly as I can't explain any good reason isn't the same as LogicalPlan.

I remember discussion in the past (maybe from @jorgecarleitao and @andygrove?) that using trait objects would allow for people to plug in their own physical plan / physical expr implementations. However, I haven't seen anyone try to do that recently (though I also haven't looked).

I think we should unify the coding style, at least the Expr and LogicalPlan representations should follow the same style.

I think the rationale for extracting variants from LogicalPlan was that many of the enum variants had several fields and it was convenient in some places to pass a known type of LogicalPlan.

I am not as convinced that adding an extra level of wrappers to Expr would make the code easier to work with

For example, when I did out an example of what I think this proposal would lead to for Expr::Not and Expr::Column I got something like:

struct Not(Expr);

struct Column(schema::Column);

enum Expr {
  ...
  Column(Column),
  Not(Not)
  ...
}

And I think it makes the code significantly harder to read and work with (as now .0 would get sprinkled around)

If we feel a deep need for consistency, I would personally prefer to expand LogicalPlan back to direct variants

[thinkharderdev]

I agree with @alamb that if we want to go for consistency then it would be better to make LogicalPlan a trait rather than to make ExecutionPlan and enum. Since this is a potential extension point it seems a little awkward to model it as a sum type where we have add an additional layer of indirection for defining user-defined physical/logical plan nodes. In our project, we do create a custom UserDefinedLogicalNode and an associated custom ExecutionPlan and it feels much more ergonomic to create the custom ExecutionPlan than it does to create the UserDefinedLogicalNode.

That said, in things like serde logic where we need to handle all possible variants it is nicer (and will be even nicer still once deref patterns lands :)) to be able to pattern match all the variants rather than do the long chain of "if downcast_ref" conditions, so I don't feel strongly either way.

[xudong963]

Though they are all tree based structures, each module has some qualities of each module itself. The code style, although important, but not the most important :)

[mingmwang]

Besides the code style, the reason that I prefer to use Enum than Trait/Trait Objects is because Trait is simple but Trait Object is a quite complex concept in Rust and not all the Traits can be used as Trait Objects: the return type of the Trait can not be the 'Self' and there should be no generic types parameters.

For example in this PR #2168, the new method with_new_children_if_necessary can not be implemented as a Trait method

/// Can not compile
fn with_new_children_if_necessary(
    self: Arc<Self>,
    children: Vec<Arc<dyn ExecutionPlan>>,
) -> Result<Arc<dyn ExecutionPlan>> {
    if children.len() != self.children().len() {
        Err(DataFusionError::Internal(
            "Wrong number of children".to_string(),
        ))
    } else if children.is_empty()
        || children
            .iter()
            .zip(self.children().iter())
            .any(|(c1, c2)| !Arc::ptr_eq(c1, c2))
    {
        self.with_new_children(children)
    } else {
        Ok(self)
    }
}

/// Can not compile 
fn with_new_children_if_necessary(
    &self,
    children: Vec<Arc<dyn ExecutionPlan>>,
) -> Result<Arc<dyn ExecutionPlan>> {
    if children.len() != self.children().len() {
        Err(DataFusionError::Internal(
            "Wrong number of children".to_string(),
        ))
    } else if children.is_empty()
        || children
            .iter()
            .zip(self.children().iter())
            .any(|(c1, c2)| !Arc::ptr_eq(c1, c2))
    {
        self.with_new_children(children)
    } else {
        Ok(Arc::new(self.clone()))
    }
}

/// Can not compile 
fn with_new_children_if_necessary(
    self: Arc<Self>,
    children: Vec<Arc<dyn ExecutionPlan>>,
) -> Result<Arc<Self>> {
    if children.len() != self.children().len() {
        Err(DataFusionError::Internal(
            "Wrong number of children".to_string(),
        ))
    } else if children.is_empty()
        || children
            .iter()
            .zip(self.children().iter())
            .any(|(c1, c2)| !Arc::ptr_eq(c1, c2))
    {
        self.with_new_children(children)
    } else {
        Ok(self)
    }
}

And we have to implement the as_any() method for all the Trait implementations, so that in the places where the trait
is consumed, it can be downcast to the original type. And the Any Trait is qualified with 'static lifecycle. That means the original type which implements the ExecutionPlan Trait can not hold any non-static references, the Struct that implements the Trait must be owned type.

 fn as_any(&self) -> &dyn Any;

There is other pitfall to use Trait Objects, for example:
https://stackoverflow.com/questions/67109860/how-to-compare-trait-objects-within-an-arc

I searched the internet and find this blog, I think the points are quite valid.
https://bennetthardwick.com/dont-use-boxed-trait-objects-for-struct-internals/

From extension point of view, using Enum is not that straightforward compared with Trait, but I think we can follow the same way as the LogicalPlan, just like the UserDefinedLogicalNode we already have for the LogicalPlan.

[tustvold]

with_new_children_if_necessary

FWIW you could use an associated trait function (or a free function as the PR does)

fn with_new_children_if_necessary(s: Arc<dyn ExecutionPlan>, children: Vec<Arc<dyn ExecutionPlan>>) -> Result<Arc<dyn ExecutionPlan>>;

Which can be invoked as ExecutionPlan::with_new_children_if_necessary(s, children). Whilst perhaps not as ergonomic as s.with_new_children_if_necessary(children), its effectively a constructor so... 🤷

There is other pitfall to use Trait Objects, for example:

I think this is a tad disingenuous, this is a pitfall of using pointer equality on fat pointers, of which trait objects are just one type. If you wish to perform pointer equality, as opposed to actually implementing PartialEq, you should thin the pointers first. I don't think it is fair to say this is an issue with trait objects, but rather one of the many pitfalls of using raw pointers.

That means the original type which implements the ExecutionPlan Trait can not hold any non-static references

This limitation would still exist in the enumeration approach, unless a lifetime parameter were introduced into the enum type definition, which I think would be a very tough sell vs simply using Arc.

And we have to implement the as_any() method for all the Trait implementations, so that in the places where the trait
is consumed, it can be downcast to the original type.

In most cases I suspect you are downcasting to a single concrete type in which case

if let Some(foo) = plan.as_any().downcast_ref::<Sum>() {

}

vs

if let Sum(foo) = &plan {

}

Is not a major difference imo... The major pain comes when matching multiple types, in many cases I think this would be better avoided by lifting into a member function on the trait, but lets say there is some use-case where this is not possible. Perhaps we could introduce an enum like

enum ConcreteExecutionPlan<'a> {
  Sum(&'a Sum),
  Max(&'a Max),
  ...
}

And then add something like

fn downcast(&dyn ExecutionPlan) -> Option<ConcreteExecutionPlan<'_>> {}

I dunno, I'm not really sure I understand the use-case for enumerating the concrete ExecutionPlan types, especially when this set is necessarily unbounded due to extensions... A similar argument could probably be applied to LogicalPlan tbh...

[mingmwang]

with_new_children_if_necessary

FWIW you could use an associated trait function (or a free function as the PR does)

fn with_new_children_if_necessary(s: Arc<dyn ExecutionPlan>, children: Vec<Arc<dyn ExecutionPlan>>) -> Result<Arc<dyn ExecutionPlan>>;

Which can be invoked as ExecutionPlan::with_new_children_if_necessary(s, children). Whilst perhaps not as ergonomic as s.with_new_children_if_necessary(children), its effectively a constructor so... 🤷

I think this can not compile either. For Trait Objects, it requires the first params of the trait method must be the Self type or can be derefed to self

[tustvold]

Aah yes, I missed off the where Self: Sized that marks it as non-dispatchable. Playground.

[mingmwang]

There are other downsides with Trait/Trait Objects, we can not use pattern-matching and destructuring with Trait Objects. Pattern-matching and destructuring are the most important feature of FP and they are valuable for optimizer rules implementation.

https://stackoverflow.com/questions/26126683/how-to-match-trait-implementors

[alamb]

If I was going to change the style of Expr, LogicalPlan and ExecutionPlan I would make ExectionPlan an enum for the reasons that @mingmwang explain, and have one variant that allowed for extension:

enumExecutionPlan {
  ...
  Extension {
    extension: Arc<dyn ExecutionPlanExtension>,
  }
  ... 

Similar to LogicalPlan::Extension: https://github.com/apache/arrow-datafusion/blob/81b5794/datafusion/expr/src/logical_plan/plan.rs#L101-L102

[mingmwang]

@thinkharderdev @yahoNanJing @Dandandan @andygrove