The blog post argues for an intermediate representation (IR) layer in query compilers between the logical plan and the physical plan, called the "relational algebra IR." This layer would represent queries in a standardized, relational algebra form, enabling greater portability and reusability of optimization rules across different physical execution engines. Currently, optimization logic is often tightly coupled to specific physical plans, making it difficult to adapt to new engines or hardware. By introducing this standardized relational algebra IR, query compilers can achieve better modularity and extensibility, simplifying development and allowing for easier experimentation with new optimization strategies without needing to rewrite code for each backend. This ultimately leads to more efficient query execution across diverse environments.
The blog post "The missing tier for query compilers" argues for a new intermediate representation (IR) layer within database query compilers, situated between the logical plan (representing the query's semantics) and the physical plan (specifying the execution strategy). The author terms this the "algebraic plan." This layer addresses the shortcomings of current compilers, which often conflate logical and physical planning, leading to suboptimal performance and increased complexity in the compiler.
Current query optimizers typically transform a logical plan, like a relational algebra tree, directly into a physical plan. This process involves choosing algorithms for each operation (e.g., hash join vs. nested loop join), ordering joins, and introducing physical operators like scans and sorts. The problem is that this intertwined approach makes it difficult to explore different logical transformations before making physical choices. Optimizations that could drastically simplify the query might be missed because the optimizer is already committed to a certain physical execution path.
The proposed algebraic plan sits at a higher level of abstraction than the physical plan but below the logical plan. It represents the query in terms of algebraic operations, similar to relational algebra, but with key differences. The algebraic plan is normalized, meaning it uses a restricted set of operators with well-defined semantics. This normalization simplifies reasoning about the query and enables more powerful logical optimizations. Furthermore, the algebraic plan is annotated with properties like data cardinality and column distributions. These annotations provide crucial information for cost-based optimization without prematurely committing to specific physical operators.
By introducing this intermediary layer, the compilation process becomes a three-stage pipeline:
- Logical planning: The initial query is translated into a logical plan, capturing the query's meaning.
- Algebraic planning: The logical plan is transformed into a normalized and annotated algebraic plan. Crucially, this stage focuses on high-level logical optimizations that are independent of the physical execution environment. This includes rewriting joins, pushing down predicates, and exploiting functional dependencies.
- Physical planning: The algebraic plan is translated into a physical plan, choosing specific algorithms and data access methods based on the annotations and cost models.
The author emphasizes the benefits of this approach: improved optimization potential by decoupling logical and physical concerns, increased compiler modularity and maintainability, and the possibility of more advanced optimization techniques, such as exploring different algebraic representations of the same query. This separation allows the optimizer to thoroughly explore the logical solution space before delving into the physical details, ultimately leading to more efficient query execution plans. The author acknowledges that implementing this new tier requires significant effort, but argues that the potential performance gains and improved compiler architecture justify the investment.
Summary of Comments ( 8 )
https://news.ycombinator.com/item?id=42996656
HN commenters generally agree with the author's premise that a middle tier is missing in query compilers, sitting between logical optimization and physical optimization. This tier would handle "cross-physical plan" optimizations, allowing for better cost-based decisions that consider different physical plan choices holistically rather than sequentially. Some discuss the challenges in implementing this, particularly the explosion of search space and the difficulty in accurately costing plans. Others offer specific examples where such a tier would be beneficial, such as selecting join algorithms based on data distribution or optimizing for specific hardware like GPUs. A few commenters mention existing systems that implement similar concepts, though not necessarily as a distinct tier, suggesting the idea is already being explored in practice. Some debate the practicality of the proposed solution, suggesting alternative approaches like adaptive query execution or learned optimizers.
The Hacker News post titled "The missing tier for query compilers," linking to an article on scattered-thoughts.net, has generated a modest discussion with a few interesting points.
One commenter highlights the value of the proposed "IR optimizer" tier, agreeing that it sits logically between the logical plan optimization and the physical plan generation. They point out the challenge of optimizations that are neither purely logical nor physical, citing predicate pushdown as a prime example. This commenter further emphasizes the importance of cost-based optimization at this intermediate stage, suggesting it allows for more informed decisions.
Another commenter focuses on the practical difficulties of building such a system. They mention the considerable effort involved in accurately estimating costs without generating a full physical plan, suggesting this might diminish the potential benefits. They also highlight the complexities introduced by supporting diverse execution backends, each with unique performance characteristics.
A third commenter draws a parallel to LLVM, noting its similar tiered architecture and how it effectively bridges the gap between higher-level representations and target-specific optimizations. They propose that adopting a similar approach in query compilers could lead to significant improvements.
A brief comment concurs with the author's premise, mentioning that current query optimizers often struggle with certain types of optimizations. They agree that an intermediate representation could address these shortcomings.
Another commenter makes a more abstract observation, likening the concept to the "no free lunch" theorem. They suggest that while the proposed approach has merit, there will always be trade-offs and challenges associated with building truly universal optimization strategies.
The discussion, while not extensive, provides valuable perspectives on the challenges and potential benefits of introducing an intermediate representation in query compilers. The comments generally agree on the theoretical value but also acknowledge the practical difficulties of implementation and cost estimation. The comparison to LLVM's architecture offers an intriguing potential direction for future research in this area.