A practical join processing strategy that allows effective utilization of arbitrary degrees of parallelism in both the I/O subsystem and join processing subsystems is presented. Analytic bounds on the minimum execution time, minimum number of processors, and processor utilization are presented along with bounds on the execution time, given a fixed number of processors. These bounds assume that sufficient buffers are available. An analytic lower bound on buffer requirements as well as a practical heuristic for use in limited buffer environments are also presented. A sampling of corroborative simulation results are included.>

A novel relational query optimization technique for use in shared memory multiprocessor database systems is described. A collection of practical algorithms for allocating computational resources to parallel select-project filter (SPJ) query execution plans is presented. The computational resources considered include disk bandwidth, memory buffers and general-purpose processors. The goal of the allocation algorithms is to produce minimum duration execution strategies with computational resource requirements that are less than the given system bounds. Preliminary experimental results indicate that the algorithms can be realized and are effective in producing good execution plans. Disk bandwidth appears to be the critical system resource. The most effective means to decrease complex query response time appears to be by reducing disk contention. This can be achieved by increasing the total number of disks and/or rearranging the placement of data on disks.>

A family of practical algorithms is presented to schedule join execution in a shared-memory multiprocessor environment. The algorithms are based on page connectivity graphs and determine when to read each data page into memory and how to schedule page joins on the available processors. The goal is to overlap page reads with parallel join execution in such a way that both the number of processors and total duration of join processing time are minimized. Upper and lower bounds are derived on the number of processors required to complete join execution in optimal time. A description is given of a general strategy for generating read schedules that it is conjectured can be processed in minimal time (over all read schedules on any number of processors) and a family of practical algorithms utilizing an arbitrary number of lookahead steps to approximate this general strategy.>

In this paper we examine four performance enhancements to a database management system: dynamic compilation, microcoded routines, a special-purpose file system, and a special-purpose operating system. All were examined in the context of the INGRES database management system. Benchmark timings that are included suggest the attractiveness of dynamic compilation and a special-purpose file system. Microcode and a special-purpose operating system are analyzed and appear to be of more limited utility in the INGRES context.