2010YOUY01 opened a new issue, #26225: URL: https://github.com/apache/datafusion/issues/26225
We've done a holistic rewrite of aggregation to improve maintainability and readability. We could apply similar refactors to other operators (e.g., Hash Join and Nested Loop Join), as their implementation complexity has become quite difficult to manage, while many new feature and performance requirements are still coming in. - https://github.com/apache/datafusion/issues/22710 This issue explains the motivation and proposes a concrete approach, with **one guiding principle and five actionable heuristics** for the refactors. # Motivation Refactoring `ExecutionPlan` implementations for readability **is not for cosmetic purpose**. It has practical benefits: - **Easier reviews and better correctness**: This point should be obvious, and 450+ open PRs is a big issue now. - **Better performance and more functionality:** To understand this point: One major class of optimization is adding specialized fast paths. Imagine there are 10 possible fast paths to implement. If we keep adding them without controlling complexity, the implementation might become too convoluted to extend after just 3 out of 10. A well-organized implementation provides the foundation for more optimizations to coexist. Some concrete observations about readability: - **Aggregation:** After our major cleanup, `AggregateExec` is still one of the most complex operators, but I now find it relatively easy to review non-trivial feature additions, even when they introduce aggressive optimization fast paths. - **Other operators:** HJ and NLJ are harder. For example, I can't easily understand the architectural impact of even local changes to NLJ, even though I wrote most of its original implementation. A further consideration is that **AI coding tools are not good at controlling complexity**. They tend to optimize for completing the immediate task, often with minimal diffs, even if that sacrifices long-term maintainability. Evolving in this direction seems risky. The failure mode I worry about is that the code first reaches some complexity threshold, after that AI always fix one bug while introducing two new bugs. # One Core Idea + Five Heuristics These ideas come from our experience reworking the aggregation operator. We found that following these principles made the code much easier to work with. Many other operators that currently feel difficult to extend violate most, if not all, of them. The core idea behind easy-to-understand implementations is **easy local reasoning**. For example, if a PR fixes a bug with only 10 lines of changes in `NestedLoopJoinExec`, the reviewer with enough background knowledge (specifically, know other operator well but not NLJ) should be able to understand the architectural impact of those changes without reconstructing the entire implementation. In reality, understanding the code often triggers a **chain reaction of understanding**: ```text # Goal Understand the meaning of a local variable `x`. # Understanding Steps 1. Discover that `x` is tightly coupled with 5 other struct fields. 2. Find 3 utility functions manipulating those fields in obscure ways. 3. Trace 5 more functions calling those 3 low-level utilities. 4. Discover 3 different optimization paths also modifying those fields. ``` Another way to think about this is that humans have very limited working memory. We should organize implementations in a **working-memory-friendly** way, much like we design cache-friendly algorithms for performance. # Heuristics Following these five heuristics should help give `ExecutionPlan` implementations a more maintainable structure. I find the first one, **deep modules**, particularly useful. Whenever I encounter a convoluted implementation in DataFusion, I often find opportunities to simplify it by applying this principle. ## 1. Deep Modules Deep modules are functions or structs that provide substantial functionality behind simple interfaces, hiding most of their implementation complexity. Organizing complex software around this principle helps keep the overall complexity manageable. Contrary to this principle, some textbooks recommend that functions should always be short (e.g., fewer than 20 lines). I find this misleading: a short function is not necessarily a simple abstraction. ```text Deep function Shallow (Java getter/setter) ┌──────┐ ┌──────────────────────┐ │ │ └──────────────────────┘ │ │ │ │ │ │ │ │ └──────┘ Height ↑ Functionality provided Width → Interface complexity (harder to understand) ``` If this concept isn't immediately intuitive, here's a talk by the author of the idea - https://youtu.be/bmSAYlu0NcY?si=0ZcDtqRORjmKIFgJ ## 2. Comments with High-Level Intuition and Examples Try to explain the intuition behind local implementations using concrete examples, such as how an optimization is derived from an end-user SQL query. Once readers have the right intuition, they can often infer most implementation details without needing comprehensive comments everywhere. By contrast, local, specification-like comments that merely repeat what the code does often add little value. Example: - https://github.com/apache/datafusion/blob/6663e4348049cc7b70109c9e0f8e39049794ea23/datafusion/physical-plan/src/aggregates/hash_stream.rs#L70-L96 Another related guideline is to **keep related comments together**. For example, maintain one top-level explanation for an optimization and let local functions reference it, rather than scattering the explanation across multiple places. ## 3. Enums (Typed States) A smaller but useful technique for organizing implementations is to use enums instead of flat fields whenever the states are mutually exclusive. Examples: - https://github.com/apache/datafusion/blob/6663e4348049cc7b70109c9e0f8e39049794ea23/datafusion/physical-plan/src/aggregates/ordered_final_stream.rs#L64-L69 - https://github.com/apache/datafusion/blob/6663e4348049cc7b70109c9e0f8e39049794ea23/datafusion/physical-plan/src/aggregates/mod.rs#L851-L885 The alternative is to represent all states with a flat collection of fields, using implicit flags to distinguish the active variant. This makes the code harder to understand for two reasons: - **Invalid states become representable:** Different combinations of flags and optional fields might describe impossible states, and the implementation must manually maintain their consistency. - **More mental bookkeeping:** Readers must understand which fields are meaningful in each state and reconstruct the implicit invariants before reasoning about local code. With enums, the type system makes these distinctions explicit, and each variant only carries the fields relevant to that state. ## 4. Generators Generators are a useful tool for making control-flow logic much more ergonomic to implement. They allow asynchronous stream logic to be written in a more linear style, reducing the need to manually manage suspension points and explicit state-machine transitions. See: - [https://github.com/apache/datafusion/issues/23974](https://github.com/apache/datafusion/issues/23974) ## 5. Split Execution Paths The TL;DR is that HJ and NLJ currently share much of the same state-machine logic between existence-oriented joins (semi/anti/mark joins) and regular joins. Separating these execution paths into dedicated streams might make the implementations significantly easier to maintain and optimize independently. The same principle applies to other operators: **split major semantic variants into dedicated streams**, rather than multiplexing too many execution paths through one shared state machine. See this issue for a more detailed rationale and our experience applying this approach to aggregation: - [https://github.com/apache/datafusion/issues/22710](https://github.com/apache/datafusion/issues/22710) # Implementation Plan Restructure existing operators following the principles above. I think the following are good starting candidates, as they have accumulated considerable complexity and are becoming difficult to maintain: - Hash Join - Nested Loop Join These refactors should be done **incrementally, one operator at a time**, to minimize disruption to ongoing development. We've already successfully refactored `AggregateExec`, which I think is at least the second-most complex operator implementation in DataFusion. That should give us some confidence that similar improvements are achievable for other operators. (The most complex implementation might actually be the Parquet scanner, though I'm not sure how applicable these principles would be there.) ## Progress Tracker I'm currently working on refactoring HJ, expecting it to be 2 major PRs -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
