[Epic] A collection of issues to improve planning performance / speed / efficiency

[alamb]

This is a collection of tickets related to making DataFusion's planning speed faster. Planning speed is the time from a SQL string being created to when the ExecutionPlan is created

• Benchmarks for planning queries #8638
• Make DfSchema wrap SchemaRef #4680
• Make a faster way to check column existence in optimizer (not is_err()) #5309
• Improve efficiency of multiple optimizer passes #3892
• SQL planning benchmarks for very wide tables #5256
• Performance Regression: Backtraces in errors slow down planning time (Expensive backtraces) #7522
• Refactor TreeNode recursions #7942
• Stop copying Exprs and LogicalPlans so much during Common Subexpression Elimination #9873
• [EPIC] Stop copying LogicalPlan during OptimizerPasses #9637
• Optimizer is slow: Avoid too many string cloning in the optimizer #5157
• Make CommonSubexprEliminate faster by stop copying so many strings #10426
• Optimize planner to avoid excessive schema transform functions #9144
• Optimize planning speed / stop cloning Strings / Fields so much #18413
• Bad performance on wide tables (1000+ columns) #7698
• Remove Arc<LogicalPlan> from LogicalPlan, stop copying LogicalPlans #4628
• Replace Boxes with Arc in the Expr enum. #9577

[karlovnv]

Also I'd like to consider replace list in DFSchema by case_insensitive_hashmap or something similar in order to get value with O(1) complexity instead of O(N).

As I understand, now complexity is O(N^2) due two loops of iterations (datafusion_common::dfschema::DFSchema::index_of_column_by_name and datafusion_common::table_reference::TableReference::resolved_eq)

[alamb]

Yes, I think there is a lot of room for improvement (though we need to be careful about taking on crate dependencies that might not have a good long term maintenance story)