The effectiveness of parallel processing of relational join operations is examined. The skew in the distribution of join attribute values and the stochastic nature of the task processing times are identified as the major factors that can affect the effective exploitation of parallelism. Expressions for the execution time of parallel hash join and semijoin are derived and their effectiveness analyzed. When many small processors are used in the parallel architecture, the skew can result in some processors becoming sources of bottleneck while other processors are being underutilized. Even in the absence of skew, the variations in the processing times of the parallel tasks belonging to a query can lead to high task synchronization delay and impact the maximum speedup achievable through parallel execution. For example, when the task processing time on each processor is exponential with the same mean, the speedup is proportional to P/ln(P) where P is the number of processors. Other factors such as memory size, communication bandwidth, etc., can lead to even lower speedup. These are quantified using analytical models.>

The effectiveness of parallel processing of relational join operations is examined. The skew in the distribution of join attribute values and the stochastic nature of the task processing times are identified as the major factors that can affect the effective utilization of parallelism. When many small processors are used in the parallel architecture, the skew can result in some processors becoming sources of bottleneck while other processors are being under utilized. Even in the absence of skew, the variations in the processing times of the parallel tasks belonging to a query can lead to high task synchronization delay and impact the maximum speedup achievable through parallel execution. Analytic expressions for join execution time are developed for different task time distributions with or without skew.>

The performance of a hypothetical multiprocessor back-end database machine is compared to that of a mainframe database system. The hypothetical database machine uses standard microprocessors and disks as well as processors and disks projected to be available in the future. The class of workloads considered is high-volume transaction processing. Analytic queueing models of the two architectures are constructed and used in parametric performance studies. The performance sensitivities with respect to transactions complexity, the amount of overhead required to implement the distributed database function, the amount of skew in the data access pattern, and the buffer miss ratio are determined.>

Database machine architectures consisting of multiple microprocessors or mini-computers are attracting wide attention. There have been several proposals and prototypes (see, e.g., DeWitt, Gerber, Graefe, Heytens, Kumar and Muralikrishna (1986), Fishman, Lai and Wilkinson (1984), Hsiao (1983), or the 1983 and 1985 Proceedings of the International Workshop on Database Machines). There is also a commercially available system based on multiple microprocessors (Teradata (1984)). With these architectures it is possible to exploit parallelism at three levels: within a single query, within a single transaction, and by simultaneously executing multiple independent transactions. The rationale behind these multiple microprocessor architectures is primarily to take advantage of the potential lower cost per MIPS (Millions of Instructions per Second, a measure of processing power) of microprocessors as opposed to mainframes. In addition, database machines may offer incremental capacity growth as well as improved performance for large queries by exploiting parallelism within a single query. However, it is not clear if database machines made of multiple microprocessors indeed have any cost/performance advantage over a more conventional mainframe based database management systems. Several papers on the performance analysis of database machines can be found in the literature (e.g., Salza, Terranova and Velardi (1983) or Bit and Hartman (1985)). Most of these studies have focused on determining the execution time of a single query in a particular database machine architecture.

A Mean Value Analysis (MVA) approximation is presented for computing the average performance measures of closed-, open-, and mixed-type multiclass queuing networks containing Preemptive Resume (PR) and nonpreemptive Head-Of-Line (HOL) priority service centers.The approximation has essentially the same storage and computational requirements as MVA, thus allowing computationally efficient solutions of large priority queuing networks.The accuracy of the MVA approximation is systematically investigated and presented.It is shown that the approximation can compute the average performance measures of priority networks to within an accuracy of 5 percent for a large range of network parameter values.Accuracy of the method is shown to be superior to that of Sevcik's shadow approximation.