apache / apache/datafusion

A More General Approach for Optimizing Projections in Physical Plans

Open
#9,111 10 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

### Is your feature request related to a problem or challenge?

In the current version of `ProjectionPushdown`, there are some algorithmic limitations and it is not very friendly to be extendable. To solve this optimization in theoretical limits within the strategy of "pushing down" is not possible. We will need another approach. Also any custom plan should be easily integrable with this optimization.

### Describe the solution you'd like

The new rule aims achieving the most effective use of projections in plans. It will ensures that query plans are free from unnecessary projections and that no unused columns are propagated unnecessarily between plans. The rule is designed to enhance query performance by:
1. Preventing the transfer of unused columns from leaves to root.
2. Ensuring projections are used only when they contribute to narrowing the schema, or when necessary for evaluation or aliasing.

The optimization is conducted in two phases:

Top-down Phase:
---------------
- Traverses the plan from root to leaves. If the node is:
1. Projection node, it may:
a) Merge it with its input projection if merge is beneficial.
b) Remove the projection if it is redundant.
c) Narrow the Projection if possible.
d) The projection can be nested into the source.
e) Do nothing, otherwise.
2. Non-Projection node:
a) Schema needs pruning. Insert the necessary projections to the children.
b) All fields are required. Do nothing.

Bottom-up Phase:
----------------
This pass is required because modifying a plan node can change the column indices used by output nodes. When such a change occurs, we store the old and new indices of the columns in the node's state. We then proceed from the leaves to the root, updating the indices of columns in the plans by referencing these mapping records. After the top-down phase, also some unnecessary projections may emerge. When projections check its input schema mapping, it can remove itself and assign new schema mapping to the new node which was the projection's input formerly.

The designed node structure is:
```
struct ProjectionOptimizer {
pub plan: Arc,
/// The node above expects it can reach these columns.
pub required_columns: HashSet,
/// The nodes above will be updated according to these mathces. First element indicates
/// the initial column index, and the second element is for the updated version.
pub schema_mapping: HashMap,
pub children_nodes: Vec,
}
```
To summarize, with two state variables for each plan node (one for transferring the required columns and one for the notifying changes of column indices), and with two passes (it is actually one pass, the bottom-up pass will be done implicitly during the attachment of transformed children to the self node), we will have a future-proof projection optimizer rule.

### Describe alternatives you've considered

_No response_

### Additional context

I am currently working on this issue. I will plan to open a PR for suggestions, especially on how to update the ExecutionPlan API to get rid of if else structure of all plans. It will be ready likely next week. It's not expected to significantly alter our current plans, but it will be a solid step towards optimizing potential outcomes following other existing optimizations and future ones.

Contributor guide

Open the contributing guide

Research direction

Start by reviewing the current ProjectionPushdown implementation and the ExecutionPlan API, then compare them with the proposed ProjectionOptimizer state and two-phase traversal. Done means unnecessary projections and unused columns are removed while required column indices remain correct across the transformed physical plan.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.