From the Modeling of Parallel Relational Query Processing to Query Optimization and Simulation

This paper presents a novel theoretical model for representing parallel relational query processing. It is based on two components. First, a scheme graph, called DPL graph, describes all possible execution dependencies between operators, including communication and run-time control mechanisms. Second, a timed high-level Petri net is used for modeling the data- and control flow of DPL graphs. Our model provides the framework for implementing a parallel query optimizer which is able to access sub-search spaces not yet considered. Furthermore, based on the DPL graphs and its related timed high-level Petri net, a simulation environment has been designed for testing run-time control strategies as well as query optimization methods.