TL;DR
This paper tackles the challenge of optimizing multiple related database queries simultaneously by proposing a novel approach that combines a more informed heuristic function, dynamic query ordering, and a Depth-First Branch-and-Bound (DFBB) search algorithm. Their experimental results demonstrate significant performance improvements over existing methods, making it more efficient to process groups of queries.
What Problem Does This Paper Address?
In many database applications, such as deductive or recursive query processing, a single complex query can be broken down into a set of smaller, related queries. Executing these queries individually can be inefficient, especially when they share common sub-expressions or tasks (like joins). Multiple Query Optimization (MQO) aims to address this by identifying these shared tasks and creating a single, unified execution plan (a "multi-plan") that executes common parts only once, thereby saving computation. The challenge lies in finding the optimal multi-plan efficiently, as the search space of possible plans can be enormous. Existing methods often rely on static query ordering and less informed heuristic functions, which can lead to suboptimal performance or excessive computation.
Methods
The authors introduce three key innovations:
- A New Heuristic Function (f_c): They propose a refined heuristic function,
f_c, designed to provide a more accurate lower bound on the cost of a potential multi-plan. This function is proven to be more "informed" than previous heuristics (f_s), meaning it offers a tighter estimate, which is crucial for guiding search algorithms effectively. - Dynamic Query Ordering: Traditional MQO approaches often fix the order in which queries are considered for merging into the multi-plan. This paper argues that this static ordering can become ineffective as the multi-plan evolves. Their "dynamic query ordering" approach re-evaluates the best query to merge at each step, based on the current state of the partial multi-plan, aiming to maximize sharing and prune the search space more aggressively.
- Depth-First Branch-and-Bound (DFBB): The authors advocate for DFBB as a more suitable search algorithm for MQO compared to the commonly used A algorithm. They argue that DFBB, while potentially exploring more states than A in some cases, uses significantly less memory and can be more efficient in practice, especially for problems with high "solution density" (where many potential plans lead to a valid solution). They also introduce a method for calculating an initial upper bound using "Successive Augmentation" to further prune the search space early on.
Datasets
Not discussed in the paper. The authors generated experimental query sets with 10-20 queries, each having 3-5 randomly generated alternative plans.
Key Insights and Ideas
- The "aha moment" of dynamic ordering: The core insight is that fixing query order upfront is a significant limitation. As a multi-plan is built, the potential for sharing changes, making a dynamic re-evaluation of query order crucial for efficiency.
- Heuristic accuracy matters: A more informed heuristic function (
f_c) directly translates to fewer states explored and faster convergence to a solution, highlighting the importance of good cost estimation in optimization. - DFBB's practical advantage: While A* is theoretically optimal in terms of states expanded, DFBB's lower memory footprint and potential for faster execution in practice make it a compelling alternative for MQO, especially as problem sizes grow.
- Optimal multi-plans aren't always built from optimal individual plans: The paper illustrates with an example that the cheapest multi-plan might not necessarily be composed of the cheapest individual plans for each query, emphasizing the need for holistic optimization.
Key Results
The experimental results demonstrate substantial improvements:
- The new heuristic function
f_csignificantly outperforms the previous heuristicf_s, reducing the number of states expanded by orders of magnitude (e.g., from 61,635 to 51 states for 10 queries). - Dynamic query ordering, when combined with
f_cand A*, drastically reduces the number of states expanded compared to static ordering (e.g., from 179 to 51 states for 15 queries). - DFBB, when used with
f_cand dynamic query ordering, shows comparable or even better performance in terms of states explored, but often executes much faster due to fewer "plan merge" operations (which are computationally intensive). For instance, with 18 queries, both methods explored 132 states, but DFBB performed significantly fewer plan merges (786 vs. 1096).
Limitations and Future Work
- Limitations: The paper acknowledges that while DFBB is memory-efficient, it can still expand nodes costlier than an optimal solution, unlike A*. The experimental setup used randomly generated query sets and plans, which might not fully represent real-world database workloads.
- Future Work: The authors suggest further research into determining sufficient conditions on query sets where optimal plans might not involve any sharing, allowing for separate optimization of such queries. They also imply that further exploration of DFBB's advantages and potential optimizations for its heuristic calculations could be beneficial.
Summary updated