Multiple query optimization with depth first branch and bound and dynamic query ordering

1993-09-01
Coşar, Ahmet
Lım, Ee Peng
Srıvastava, Jaıdeep
In certain database applications such as deductive databases, batch query processing, and recursive query processing etc., a single query can be transformed into a set of closely related database queries. 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 (multiplan) which can be executed to obtain the required outputs for all queries at once. In this paper, a new heuristic function (fc), 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 fc, DFBB, and dynamic query ordering help to improve the performance of our MQO algorithm.
Citation Formats
A. Coşar, E. P. Lım, and J. Srıvastava, “Multiple query optimization with depth first branch and bound and dynamic query ordering,” presented at the Multiple query optimization with depth first branch and bound and dynamic query ordering, CIKM-1993, Amerika Birleşik Devletleri, 1 - 02 Eylül 1993, Washington, DC, USA, 1993, Accessed: 00, 2021. [Online]. Available: http://dl.acm.org/citation.cfm?id=170181.