[Rust][DataFusion] Reduce copies in DataFusion LogicalPlan and Expr creation

[asfimport]

The theme of this overall epic to make the plan and expression rewriting phases of DataFusion more efficient by avoiding copies by leveraging the Rust type system

Benefits:

• More standard / idomatic Rust usage

• faster / more efficient (I don't have numbers to back this up)

  Downsides:

• These will be backwards incompatible changes

  Background

  Many things in DataFusion look like

  Input -tranformation->output

  And the input is not used again. In rust, you can model this by giving ownership to the transformation

  At a high level the idea is to avoid so much cloning in DataFustion

  The basic principle is if the function needs to clone one of its arguments, the caller should be given the choice of when to do that. Often, the caller can give up ownership without issue

  I envision at least the following the following items:

  1. Optimizer passes that take &LogicalPlan and produce a new LogicalPlan even though most callsites do not need the original
  2. Expr builder calls that take &expr and return a new Expr
  3. An expression rewriter (TODO) while running down optimizer passes

  I think this style takes advantage of Rust's ownership model and will let us avoid a lot o copying and allocations and avoid the need for something like slab allocators

Reporter: Andrew Lamb / @alamb

Subtasks:

• [Rust][DataFusion] Avoid Expr::clone in Expr builder methods
• [Rust][DataFusion] Move expressions and inputs into LogicalPlan rather than helpers in util
• [Rust][DataFusion] Implement ExprRewriter to avoid tree traversal redundancy
• [Rust][DataFusion] Rename ExpressionVisitor --> ExprVisitor and standardize input
• [Rust][DataFusion] Introduce PlanRewriter for rewriting plans
• [Rust][DataFusion] Change plan builder signature to take Vec rather than &[Expr]

Related issues:

• [Rust] [Datafusion] Optimize literal expression evaluation (relates to)

_{Note: This issue was originally created as ARROW-11689. Please see the migration documentation for further details.}

[asfimport]

Todd Farmer / @toddfarmer:
This issue was last updated over 90 days ago, which may be an indication it is no longer being actively worked. To better reflect the current state, the issue is being unassigned. Please feel free to re-take assignment of the issue if it is being actively worked, or if you plan to start that work soon.

[thisisnic]

Closing this issue as Rust development has moved to apache/arrow-rs and Datafusion to apache/datafusion.

If this is still relevant, feel free to open a new issue in one of those repos. Thanks!