Multiple Query Optimization with Depth-First Branch-and-Bound and dynamic query ordering

• Main Authors: LIM, Ee Peng, COSAR, Ahmet, SRIVASTAVA, Jaideep
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 1995
• Subjects: Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/185; https://ink.library.smu.edu.sg/context/sis_research/article/1184/viewcontent/P1993_4.pdf
• Institution: Singapore Management University

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.