Optimal Processor Assignment for Parallel Database Design
Shahram Ghandeharizadeh, Robert R. Meyer, Gary L. Schultz, Jonathan Yackel · 1991
. The computing time benefits of parallelism in database systems (achieved by using multiple processors to execute a query) must be weighed against communication, startup, and termination overhead costs that increase as a function of the number of processors used. We consider problems of minimizing overhead subject to allocating data among the processors according to specified loads. We present lower bounds for these combinatorial problems and demonstrate how processors may be optimally assigned for some problem classes. 1. Introduction. In highly-parallel database machines (e.g., Gamma [2], Bubba [1], Non-Stop SQL [12], XPRS [11] and Volcano [6]) relations are partitioned across multiple processors. (Livny et al [9] and Ries and Epstein [10] introduced the related concept of "horizontal" partitioning.) This allows each processor to execute a portion of a query in parallel with the other processors, resulting in a lower response time for the query. However, there is communication overh...