A methodology, based on analytical modeling, for the design of parallel and distributed architectures for relational database query processors
Timothy G. Kearns · 1987
The design of faster relational database query processors to improve the data retrieval capability of a database was the goal of this research. The emphasis was on evaluating the potential of parallel implementations to allow use of multiprocessing. First, the theoretical considerations of applying relational operations to distributed data was considered to provide an underlying data distribution and parallel processing environment model. Next, analytical models were constructed to evaluate various implementations of the select, project, and join relational operations and the update operations of addition, deletion, and modification for a range of data structures and architectural configurations. To predict the performance of the query processor for all cases, the individual operator models needed to be extended to models for complex queries consisting of several relational operations. The solution to modeling multi-step queries was the use of a general form to express a query. This normal form query tree uses combined operations to express relational algebra equivalent queries in a standard form. This standard tree form was then used to construct analytical models for multi-step queries. These models provide the capability to model the potential of different forms of parallelism in solving complex queries. The results of the analytical models present a logical design for a multiprocessor query processor. This logical query processor using multiple processors and employing parallelism illustrates the potential for an improved query processor using parallel processing when the analytical model results of complex queries are compared to a benchmark of some current database systems.