Enhancing an Extensible Query Optimizer with Support for Multiple Equivalence Types

Giedrius Slivinskas, Christian S. JensenADBIS 2001 · DOI

TL;DR

This paper enhances the Volcano extensible query optimizer to handle a richer relational algebra, including temporal operators and multiple equivalence types (list, multiset, set). This work is crucial for building more sophisticated database systems that can efficiently process complex temporal queries and manage diverse data structures.

What Problem Does This Paper Address?

Modern database management systems are increasingly expected to handle new data types and complex queries. However, existing commercial query optimizers are often rigid and difficult to extend with new operators, transformation rules, or cost models. This inflexibility hinders the development of advanced database functionalities. To address this, the research community has focused on creating extensible query optimizers. This paper specifically tackles the challenge of extending Volcano, a well-known extensible optimizer, to support a more expressive relational algebra that includes temporal operations and a nuanced understanding of relation equivalences beyond simple sets. This is important because real-world data often has temporal aspects, and the way data is structured (as lists, multisets, or sets) can significantly impact query processing efficiency and correctness.

Methods

The core of this work involves modifying the Volcano query optimizer to accommodate a temporally extended relational algebra and six types of relation equivalences: list, multiset, and set equivalences, and their temporal counterparts (snapshot-list, snapshot-multiset, snapshot-set).

The authors extended Volcano's two-stage optimization process:

  • Search-Space Generation: This stage involves applying transformation rules to generate all possible logical query plans. The authors introduced new transformation rules and modified the existing Generate and MatchRule functions to handle the new equivalence types. A key challenge was determining the "type" of new elements generated, which represents the combination of properties (OrderRequired, DuplicatesRelevant, PeriodPreserving) that the resulting relation satisfies. This type is crucial for ensuring rule applicability.
  • Plan Search: This stage involves finding the most efficient physical plan from the generated search space. The authors modified the FindBestPlan and Optimize functions to incorporate the new equivalence types. This included passing property information down the optimization tree and checking for plans that are at least as strong as the required equivalence type.

They also discuss the implementation of temporal operators, transfer operators (for moving data between middleware and DBMS), and the associated cost and selectivity estimation formulas.

Datasets

Not discussed in the paper. The paper focuses on the theoretical and implementation aspects of enhancing a query optimizer rather than evaluating it on specific datasets.

Key Insights and Ideas

  • Beyond Sets: The paper highlights that treating relations solely as sets is insufficient for many modern applications, especially those involving temporal data or requiring specific ordering. The introduction of list and multiset equivalences, alongside their temporal variants, is a significant step towards more accurate query optimization.
  • Equivalence Type Propagation: A critical insight is the need to carefully manage and propagate the "equivalence type" of relations throughout the optimization process. This type, derived from properties like order preservation and duplicate handling, dictates which transformation rules can be applied and influences the choice of physical plans.
  • Search Space Complexity: Supporting multiple equivalence types dramatically increases the complexity of the search space. The authors' approach of filtering invalid elements during plan search, rather than during generation, is a pragmatic way to manage this complexity.
  • Extensibility Challenges: While Volcano provides a good framework, integrating new equivalence types required significant modifications to its core search-space generation and plan-search algorithms, underscoring the inherent difficulty of extending optimizers with fundamental changes to their equivalence model.
  • Middleware Integration: The work is situated within a middleware architecture, demonstrating how extensible optimizers can be used to offload complex operations from the DBMS, leading to better performance for specialized queries.

Key Results

The paper details the successful enhancement of the Volcano optimizer to support the extended relational algebra with multiple equivalence types. While specific quantitative performance improvements are not the primary focus, the work demonstrates the feasibility of integrating these advanced concepts into an existing optimizer. The authors report on the implementation effort, noting that adding support for multiple equivalence types was the most difficult task, despite resulting in a relatively small amount of code. They also found that adding new operators and algorithms was more straightforward using Volcano's framework.

Limitations and Future Work

  • Coalescing and Duplicate Elimination: Coalescing (merging adjacent time periods with identical attributes) and duplicate elimination were not fully implemented in Volcano within this study. The authors suggest that treating these as operators with transformation rules, rather than solely as physical properties, could simplify the plan-search complexity.
  • Two-Stage Optimization: The paper suggests that Volcano's two-stage optimization strategy might be a limitation. A single-stage, top-down approach could potentially offer better control over rule applicability and improve performance.
  • User-Friendliness of Interface: The authors found Volcano's interface for adding support functions and transformation rules to be not always user-friendly, requiring substantial code modifications.
  • Future Work: The authors propose several avenues for future research:
  • Exploring heuristic guidance for ordering transformation rules to improve performance.
  • Investigating a single-stage optimization strategy.
  • Further research into integrating support for sets, multisets, and lists from the ground up in new optimizer designs.
  • The potential of extensible optimizers for building middleware systems and for use in conventional DBMSs with user-defined routines.

Summary updated

BibTeX
@inproceedings{slivinskas2001enhancing,
  author = {Giedrius Slivinskas and Christian S. Jensen},
  title = {{Enhancing an Extensible Query Optimizer with Support for Multiple Equivalence Types}},
  booktitle = {ADBIS},
  year = {2001},
  doi = {10.1007/3-540-44803-9\_6},
}
Figure