Multiple Query Optimization with Depth-First Branch-and-Bound and Dynamic Query Ordering

Ahmet Coşar, Ee‐Peng Lim, Jaideep Srivastava

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_c significantly outperforms the previous heuristic f_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_c and 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_c and 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

Abstract

In certain database applications such as deductive databases, batch query processing, and recursive query processing etc., usually a single query gets transformed into a set of closely related database queries. Also, great benefits can be obtained by executing a group of related queries all together in a single unified multi-plan instead of executing each query separately. In order to achieve this Multiple Query Optimization (MQO) identifies common task(s) (e.g. common subexpressions, joins, etc.) among a set of query plans and creates a single unified plan (multi-plan) which can be executed to obtain the required outputs for all queries at once. In this paper a new heuristic function (hc), dynamic query ordering heuristics, and Depth-First Branch-and-Bound (DFBB) are defined and experimentally evaluated, and compared with existing methods which use A* and static query ordering. Our experiments show that all three of hc, DFBB, and dynamic query ordering help to improve the performance of our MQO algorithm.Request access from your librarian to read this article's full text.
BibTeX
@inproceedings{cosar1993multiple,
  author = {Ahmet Coşar and Ee‐Peng Lim and Jaideep Srivastava},
  title = {{Multiple Query Optimization with Depth-First Branch-and-Bound and Dynamic Query Ordering}},
  booktitle = {ACM International Conference on Information and Knowledge Management},
  year = {1993},
  doi = {10.1145/170088.170181},
}
Figure