Bubba is a highly parallel computer system for data-intensive applications. The basis of the Bubba design is a scalable shared-nothing architecture which can scale up to thousands of nodes. Data are declustered across the nodes (i.e. horizontally partitioned via hashing or range partitioning) and operations are executed at those nodes containing relevant data. In this way, parallelism can be exploited within individual transactions as well as among multiple concurrent transactions to improve throughput and response times for data-intensive applications. The current Bubba prototype runs on a commercial 40-node multicomputer and includes a parallelizing compiler, distributed transaction management, object management, and a customized version of Unix. The current prototype is described and the major design decisions that went into its construction are discussed. The lessons learned from this prototype and its predecessors are presented.>

Chaining is the ability to pipeline two or more vector instructions on Cray-1 like machines. The authors show how to optimally use this feature to compute (vector) expression trees in the context of automatic code generation. They present a linear time scheduling algorithm for finding an optimal order of evaluation for a machine with a bounded number of registers.>

Handling parallelism in database systems involves the specification of a storage model, a placement strategy, and a query processing strategy. An important goal is to determine the appropriate combination of these three strategies in order to obtain the best performance advantages. In this paper we present a novel and promising query processing strategy for a decomposed storage model. We discuss some of the qualitative advantages of the scheme. We also compare the performance of the proposed “pivot” strategy with conventional query processing for the n-ary storage model. The comparison is performed using the Wisconsin Benchmarks.

We investigate two schemes for placing data on multiple disks. We show that declustering (spreading each file across several disks) is inherently better than clustering (placing each file on a single disk) due to a number of reasons including parallelism and uniform load on all disks.

In the past few years we have seen in the literature a number of proposals for benchmarks to be used in measuring the performance of database management and transaction processing systems. The TP1 benchmark [Anon et al 1985] and the Wisconsin benchmark [Bitton et al 1983], [Boral and DeWitt 1984], and [Bitton and Turbyfill 1985] have been used to benchmark several systems. Other benchmarks have also been proposed.

This paper presents a methodology for evaluating the performance of database management systems and database machines in a multiuser environment. Three main factors that affect transaction throughput in a multiuser environment are identified: multiprogramming level, degree of data sharing among simultaneously executing transactions, and transaction mix. We demonstrate that only four basic query types are needed to construct a benchmark that will evaluate the performance of a system under a wide variety of workloads. Finally, we present the results of applying our techniques to the Britton-Lee IDM 500 database machine

We introduce the notion of self-adapting concurrency control algorithms --- concurrency control algorithms that consist of several rw and several ww synchronization techniques, and employ combinations of the techniques in a manner that attains a performance objective. We Consider synchronization techniques that use locking and certification. A general proof method for such algorithms is outlined and applied.

This paper presents and analyzes algorithms for parallel processing of relational database operations in a general multiprocessor framework. To analyze alternative algorithms, we introduce an analysis methodology which incorporates I/O, CPU, and message costs and which can be adjusted to fit different multiprocessor architectures. Algorithms are presented and analyzed for sorting, projection, and join operations. While some of these algorithms have been presented and analyzed previously, we have generalized each in order to handle the case where the number of pages is significantly larger than the number of processors. In addition, we present and analyze algorithms for the parallel execution of update and aggregate operations.

This paper is intended to introduce those familiar with database management issues to the problems of managing large statistical databases. We begin with a characterization of statistical databases based on the structure and use of the data in the database. Several data management problems are then described. In particular, we discuss the problem of repetitive computations on large segments of the database during the lifetime of a statistical analysis. The organization of a data management system which avoids this problem by caching previously computed results and automatically maintaining their integrity is presented. We conclude with a list of problems that this organization raises and a discussion of related work.

DIRECT is a multiprocessor database machine designed and implemented at the University of Wisconsin. This paper describes our experiences with the implementation of DIRECT. We start with a brief overview of the original machine proposal and how it differs from what was actually implemented. We then describe the structure of the DIRECT software. This includes software on host computers that interfaces with the database machine; software on the back-end controller of DIRECT; and software executed by the query processors. In addition to describing the structure of the software we will attempt to motivate and justify its design and implementation. We also discuss a number of implementation issues (e.g., debugging of the code across several machines). We conclude the paper with a list of the "lessons" we have learned from this experience.

In this paper four alternative strategies for assigning processors to queries in multiprocessor database machines are described and evaluated. The results demonstrate that SIMD database machines are indeed a poor design when their performance is compared with that of the three MIMD strategies presented. Also introduced is the application of data-flow machine techniques to the processing of relational algebra queries. A strategy that employs data-flow techniques is shown to be superior to the other strategies described by several experiments. Furthermore, if the data-flow query processing strategy is employed, the results indicate that a two-level storage hierarchy (in which relations are paged between a shared data cache and mass storage) does not have a significant impact on performance.

This paper presents a discussion of the application of data-flow machine concepts to the design and implementation of database machines which execute relational algebra queries. We analyze the performance of multiprocessor nested-loops and sort-merge join algorithms and show that the nested-loops algorithm is generally superior. Three levels of operand granularity for data-flow database machines are introduced and compared using the nested-loops join algorithm. We demonstrate that relation-level granularity is too coarse and that tuple-level granularity is too fine. The third level of granularity, a page of a relation, is shown to be the best choice from both hardware and software viewpoints. Finally a preliminary design for a data-flow database machine which utilizes page-level granularity and supports distributed control of instruction execution is presented. (Author)