Multiple Query Optimization with Depth-First Branch-and-Bound and Dynamic Query Ordering
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.
Databases and Information Systems | Numerical Analysis and Scientific Computing
Data Management and Analytics
Journal of Database Management
LIM, Ee Peng; Cosar, A.; and Srivastava, J..
Multiple Query Optimization with Depth-First Branch-and-Bound and Dynamic Query Ordering. (1995). Journal of Database Management. 6, (1), 14-19. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/185