Accurately and efficiently estimating the number of distinct values for some attribute(s) or sets of attributes in a data set is of critical importance to many database operations, such as query optimization and approximation query answering. Previous work has focused on the estimation of the number of distinct values for a single attribute and most existing work adopts a data sampling approach. This paper addresses the equally important issue of estimating the number of distinct value combinations for multiple attributes which we call COLSCARD (for COLumn Set CARDinality). It also takes a different approach that uses existing statistical information (e.g., histograms) available on the individual attributes to assist estimation. We start with cases where exact frequency information on individual attributes is available, and present a pair of lower and upper bounds on COLSCARD that are consistent with the available information, as well as an estimator of COLSCARD based on probability. We then proceed to study the case where only partial information (in the form of histograms) is available on individual attributes, and show how the proposed estimator can be adapted to this case. We consider two types of widely used histograms and show how they can be constructed in order to obtain optimal approximation. An experimental evaluation of the proposed estimation method on synthetic as well as two real data sets is provided.

We describe the design and implementation of the Exedra continuous media server, and experimentally evaluate alternative resource management policies using a prototype system that we built. Exedra has been designed to provide scalable and efficient support for variable bit-rate media streams whose compression efficiency leads to reduced storage space and bandwidth requirements in comparison to constant bit-rate streams of equivalent quality. We examine alternative disk striping policies, and quantify the benefits of innovative techniques for storage space allocation, buffer management, and resource reservation, which we developed to achieve both predictability and high-performance in handling disk and network data transfers of variable size. Additionally, we investigate the differences between diverse data replication schemes over disk arrays, and compare methods for disk access time reservation that enable tolerance of disk failures at minimal cost. Overall, we demonstrate the feasibility of building network media servers that exploit the latest advances in media compression technology towards reducing the cost of wide-scale streaming services for stored data.

Being named recipient of the 2004 ACM Sigmetrics Achievement Award has done several things to me. It brought me surprise that I would be singled out from the many people who have made significant and sustained contributions to the field of performance evaluation. It also brought me deep appreciation for all the students and colleagues with whom I have worked and come to know as friends over the years. Finally, it has caused me to ponder and reminisce about many of the research projects and consulting studies in which I have participated.In this talk, I will describe various systems I have used and studied, various applications of interest, and various models that I, and others, have used to try to gain insights into the performance of systems. Some lessons of possible future relevance that emerge from this retrospective look at a wide variety of projects are the following:

We introduce an algorithm that uses buffer space available at the server for smoothing disk transfers of variable bit-rate streams. Previous smoothing techniques prefetched stream data into the client buffer space, instead. However, emergence of personal computing devices with widely different hardware configurations means that we should not always assume abundance of resources at the client side. The new algorithm is shown to have optimal smoothing effect under the specified constraints. We incorporate it into a prototype server, and demonstrate significant increase in the number of streams concurrently supported at different system scales. We also extend our algorithm for striping variable bit-rate streams on heterogeneous disks. High bandwidth utilization is achieved across all the different disks, which leads to server throughput improved by several factors at high loads.

Current data repositories include a variety of data types, including audio, images, and time series. State-of-the-art techniques for indexing such data and doing query processing rely on a transformation of data elements into points in a multidimensional feature space. Indexing and query processing then take place in the feature space. We study algorithms for finding relationships among points in multidimensional feature spaces, specifically algorithms for multidimensional joins. Like joins of conventional relations, correlations between multidimensional feature spaces can offer valuable information about the data sets involved. We present several algorithmic paradigms for solving the multidimensional join problem and we discuss their features and limitations. We propose a generalization of the size separation spatial join algorithm, named multidimensional spatial join (MSJ), to solve the multidimensional join problem. We evaluate MSJ along with several other specific algorithms, comparing their performance for various dimensionalities on both real and synthetic multidimensional data sets. Our experimental results indicate that MSJ, which is based on space filling curves, consistently yields good performance across a wide range of dimensionalities.

Current data repositories include a variety of data types, including audio, images and time series. State of the art techniques for indexing such data and doing query processing rely on a transformation of data elements into points in a multidimensional feature space. Indexing and query processing then take place in the feature space. We study algorithms for finding relationships among points in multidimensional feature spaces, specifically algorithms for multidimensional joins. Like joins of conventional relations, correlations between multidimensional feature spaces can offer valuable information about the data sets involved. We present several algorithmic paradigms for solving the multidimensional join problem, and we discuss their features and limitations. We propose a generalization of the Size Separation Spatial Join algorithm, named Multidimensional Spatial Join (MSJ), to solve the multidimensional join problem. We evaluate MSJ along with several other specific algorithms, comparing their performance for various dimensionalities on both real and synthetic multidimensional data sets. Our experimental results indicate that MSJ, which is based on space filling curves, consistently yields good performance across a wide range of dimensionalities.

In this paper, processor scheduling policies that "save" processors are introduced and studied. In a multiprogrammed parallel system, a "processor saving" scheduling policy purposefully keeps some of the available processors idle in the presence of work to be done. The conditions under which processor saving policies can be more effective than their greedy counterparts, i.e., policies that never leave processors idle in the presence of work to be done, are examined. Sensitivity analysis is performed with respect to application speedup, system size, coefficient of variation of the applications' execution time, variability in the arrival process, and multiclass workloads. Analytical, simulation, and experimental results show that processor saving policies outperform their greedy counterparts under a variety of system and workload characteristics.

We introduce a new algorithm to compute the spatial join of two or more spatial data sets, when indexes are not available on them. Size Separation Spatial Join (S3J) imposes a hierarchical decomposition of the data space and, in contrast with previous approaches, requires no replication of entities from the input data sets. Thus its execution time depends only on the sizes of the joined data sets.

An important issue in multiprogrammed multiprocessor systems is the scheduling of parallel jobs. Most research in the area has focussed solely on the allocation of processors to jobs. However, since memory is also a critical resource for many parallel jobs, the allocation of memory and processors must be coordinated to allow the system to operate most effectively.To understand how to design such coordinated scheduling disciplines, it is important to have a theoretical foundation. To this end, we develop bounds on the achievable system throughput when both memory and processing time are in demand. We then propose and simulate a simple discipline and relate its performance to the throughput bounds. An important result of our work is for the situation in which the workload speedup is convex (from above), but the speedup characteristics of individual jobs are unknown. It shows that an equi-allocation strategy for processors can achieve near-maximum throughput, yet offer good mean response times, when both memory and processors are considered.

In this paper we present an analytical-based framework for parallel program performance prediction. The main thrust of this work is to provide a means for treating realistic applications within a single unified framework. Our approach is based upon the specification of a set of non-linear equations which describe the application, processor configuration, network and memory operations. These equations are solved iteratively since the application execution rate depends on the communication latencies. The iterative solution technique is found to be efficient as it typically requires only few iterations to reach convergence. Our modeling methodology achieves a good balance between abstraction and accuracy. This is attained by accounting for both time and space dimensions of memory references, while maintaining a simple description of the workload. We demonstrate both the practicality and the accuracy of our approach by comparing predicted results with measurements taken on a commercial mul...

Dynamic software cache coherence strategies use information about program sharing behaviour to manage caches at run-time and at a granularity defined by the application. The program-level information is obtained through annotations placed into the application by the user or the compiler. The coherence protocols may range from simple static algorithms to dynamic algorithms that use run-time data structures similar to the directories used in hardware strategies. In this paper, we present an analytic study of five dynamic software cache coherence algorithms and compare these to a representative hardware coherence strategy. The analytic model is constructed using four input parameters --- write probability, locality, granularity, and system size --- and solved by analysis of a Markov chain. We show that the fundamental tradeoffs between the different hardware and software strategies are captured in this model. The results of the study show that hardware schemes perform better for fine-grained data structures for much of the parameter space that we study. However, for coarse-grained data structures, various software algorithms are dominant over most of the parameter space. Further, hardware strategies are found to be more susceptible to the effects of contention, and also perform worse for the asymmetric workload that we study.

Distributed applications are being developed that contain one or more layers of software servers. Software processes within such systems suffer contention delays both for shared hardware and at the software servers. The responsiveness of these systems is affected by the software design, the threading level and number of instances of software processes, and the allocation of processes to processors. The Method of Layers (MOL) is proposed to provide performance estimates for such systems. The MOL uses the mean value analysis (MVA) linearizer algorithm as a subprogram to assist in predicting model performance measures.>

Large knowledge bases that are intended for applications such as CAD, corporate repositories or process control will have to be shared by multiple users. For these systems to scale up, to give acceptable performance and to exhibit consistent behavior, it is mandatory to synchronize user transactions using a concurrency control algorithm. In this paper, we examine a novel concurrency control policy called Dynamic Directed Graph (or DDG) policy that effectively exploits the rich semantic structure of a knowledge base.

Cache affinity is important to the performance of scalable shared memory multiprocessors. For multiprocessors without hardware cache coherence support, software cache coherence is the only alternative. Most existing software cache schemes ignore cache affinity across parallel loops. In this paper, we propose a new scheme, Cache Affinity-based Software cache coherence scheme (CAS), that exploits cache affinity across parallel loops to achieve high cache hit ratios without requiring extra hardware support. The experimental results show that the new scheme outperforms other existing schemes.

A new approach to parallel sorting called Parallel Sorting by OverPartitioning (PSOP) is presented.The approach limits the communication cost by moving each element between processors at most once, and leads to good load balancing with high probability y.The PSOP framework can be applied to both comparison and non-comparison sorts.Implementations on the KSR1 and Hector shared memory multiprocessors show that PSOP achieves nearly linear speedup and outperforms alternative approaches.An analytical model for PSOP has been developed that predicts the performance within 10% accuracy.

An improtant issue in the parallel execution of loops is how to partition and schedule the loops onto the available processors. While most existing dynamic scheduling algorithms manage to load imbalance well, they fail to take locality into account and therefore perform poorly on parallel systems with non-uniform memory access times.

Scalable multiprocessors that support a shared-memory image to application programmers are typically based on physical memory modules that are distributed. Consequently, the access times for a particular processor to various parts of physical memory differ. In this paper, we explore the implications of this non-uniformity in memory access times. In particular, we study the effect of hot-spots in hierarchical large scale NUMA multiprocessors. Hot-spot analysis is of interest because coordinated threads of parallel programs lead to hot spots whose impact on performance may be substantial or even dominant. We have developed an analytical model of access latencies and contention for shared resources in the interconnection network that links the processors and memory modules. Our objective is to provide a better understanding of non-uniform memory access times in scalable architectures. We show the extent to which a variable can be shared before it becomes a performance bottleneck, and asse...

A performance model of buffer management is presented that is appropriate for use in the context of a multilayer database performance model. Some empirical evidence that supports the model's hypothesis that database page references are Bradford-Zipf-distributed is provided. A validation of the buffer performance model against data from a real-life environment is reported. Overall, the database buffer management model proposed has accuracy commensurate with that of the other components of multilayer database performance models, yet it does not require extensive parametrization or excessive computation.>

As multiprocessors with large numbers of processors become more prevalent, we face the task of developing scheduling algorithms for the multiprogrammed use of such machines. The scheduling decisions must take into account the number of processors available, the overall system load, and the ability of each application awaiting activation to make use of a given number of processors.

Several patterns of structure and locality of communication among software components assigned to processors are considered. In each case, a mapping between components and processors is identified so that high-volume communication paths correspond to connections supported most efficiently by the interconnection network. It is shown that locality of communication can have a profound effect on the efficiency of communication in a multicomputer. Several types of multiprocessors and multicomputers being designed for applications in artificial intelligence are likely to exhibit locality of communication of a form suitable for use by such interconnection networks.>

In multiprocessor architectures, it is frequently necessary to provide parallel communication among a potentially large number of processors and memories. Among the many interconnection schemes that have been proposed and analyzed, shuffle-exchange networks have received much attention due to their ability to allow a message to pass from any node to any other node in a number of steps that grows only logarithmically with the number of interconnected nodes (in the absence of contention) while keeping the number of hardware connections per node independent of the number of nodes.

The FDDI Token Ring Protocol controls communication over fiber optic rings with transmission rates in the range of 100 megabits per second. It is intended to give guaranteed response to time-critical messages by using a "timed token" protocol, in which non-critical messages may be transmitted only if recent movement of the token among stations has been sufficiently fast relative to a "target" token rotation time (TTRT).

Communication technology now makes it possible to support high data transmission rates at relatively low cost. In particular, optical fiber can be used as the medium in local area networks with data rates in the range of 100 megabits per second. Unfortunately, local area network topologies and communication protocols that work well with lower speed media are not necessarily appropriate when the data transmission rate is scaled up by approximately an order of magnitude. Recognizing this fact, an ANSI sub-committee (ANSIX3T9) has been working for the past two years on a proposed standard for a token ring protocol tailored to a transmission medium with transmission rate in the 100 megabits per second range. The protocol is referred to as the FDDI (Fiber Distributed Data Interface) Token Ring protocol. The proposal for the standard is now quite mature and nearly stable.

An algorithm for computing bounds on the performance measures of multiple-class, product-form queuing networks is presented. The algorithm offers the user a hierarchy of bounds with differing accuracy levels and computational cost requirements. Unlike previously proposed bounding algorithms, the algorithm is applicable to all of the types of product-form queuing networks that are commonly used in computer system and computer-communication network applications.

Traditional file structures that provide multikey access to records, for example, inverted files, are extensions of file structures originally designed for single-key access. They manifest various deficiencies in particular for multikey access to highly dynamic files. We study the dynamic aspects of file structures that treat all keys symmetrically, that is, file structures which avoid the distinction between primary and secondary keys. We start from a bitmap approach and treat the problem of file design as one of data compression of a large sparse matrix. This leads to the notions of a grid partition of the search space and of a grid directory , which are the keys to a dynamic file structure called the grid file . This file system adapts gracefully to its contents under insertions and deletions, and thus achieves an upper bound of two disk accesses for single record retrieval; it also handles range queries and partially specified queries efficiently. We discuss in detail the design decisions that led to the grid file, present simulation results of its behavior, and compare it to other multikey access file structures.

In applications of queueing network models to computer system performance prediction, the computational effort required to obtain an exact equilibrium solution of a model may not be justified by the accuracy actually required.In these cases, there is a need for approximation or bounding techniques that can provide the necessary information with less computational effort.This paper presents a new technique that yields performance bounds for single-class separable queueing networks consisting of fixed-rate and delay service centers.Unlike previous approximation or bounding techniques, there is a smooth trade-off between computational effort and accuracy.Any level of accuracy (including the exact solution) can be guaranteed by investing the necessary computational effort.Performance bounds that are sufficiently tight for most practical purposes may be obtained with a fraction of the effort required for the exact solution.Since bounds are produced, as opposed to approximations, guarantees about the accuracy of a model solution can be provided.

The problem of concurrency control in distributed database systems in which site and communication link failures may occur is considered. The possible range of failures is not restricted; in particular, failures may induce an arbitrary network partitioning. It is desirable to attain a high “level of robustness” in such a system; that is, these failures should have only a small impact on system operation. A level of robustness termed maximal partial operability is identified. Under our models of concurrency control and robustness, this robustness level is the highest level attainable without significantly degrading performance. A basis for the implementation of maximal partial operability is presented. To illustrate its use, it is applied to a distributed locking concurrency control method and to a method that utilizes timestamps. When no failures are present, the robustness modifications for these methods induce no significant additional overhead.

Applications of queueing network models to computer system performance prediction typically involve the computation of their equilibrium solution. When numerous alternative systems are to be examined and the numbers of devices and customers are large, however, the expense of computing the exact solutions may not be warranted by the accuracy required. In such situations, it is desirable to be able to obtain bounds on the system solution with very little computation. Asymptotic bound analysis (ABA) is one technique for obtaining such bounds. In this paper, we introduce another bounding technique, called balanced job bounds (BJB), which is based on the analysis of systems in which all devices are equally utilized. These bounds are tighter than ABA bounds in many cases, but they are based on more restrictive assumptions (namely, those that lead to separable queueing network models).

Queuing networks are studied at selected points in the steady state, namely, at the moments when jobs of a given class arrive into a given node (either from the outside or from other nodes) and at the moments when jobs of a given class leave a given node (either for the outside or for other nodes).The processes defined by these points are known to be, in general, non-Potsson, interdependent, and serially correlated; therefore the relation between the distribution of the system state embedded at those moments and the steady-state (or random point) distribution is not obvious a priori.For a large class of networks having product-form equihbrium distribnttons it is shown that (a) if the given job class belongs to an open subchain, the state distributions at input pomts, output points, and random points are identical, and (b) if the job class belongs to a closed subchain, the distribution at input and output points ts the same as the steady-state distribution of a network with one less job in that subchain.

A number of case studies involving the use of queueing network models to investigate actual computer systems are surveyed. After suggesting a framework by which case studies can be classified, we contrast various parameter estimation methods for specifying model parameters based on measurement data. A tabular summary indicates the relationships among nineteen case studies.

A formal model allowing a precise definition of coherence and promptness in a multiple copy information system is presented and used to analyze a class of update synchronization techniques.

RAP (Relational Associative Processor) is a “back-end” database processor that is intended to take over much of the effort of database management in a computer system. In order to enhance RAP's performance its design includes mechanisms for permitting features analogous to multiprogramming and virtual memory as in general purpose computer systems. It is the purpose of this paper to present the detailed design of these mechanisms, along with some analysis that supports their value. Specifically, (1) the response time provided by RAP under several scheduling disciplines involving priority by class is analyzed, (2) the cost effectiveness of the additional hardware in RAP necessary to support multiprogramming is assessed, and (3) a detailed design of the RAP virtual memory system and its monitor is presented.

An associative processor called RAP has been designed to provide hardware support for the use and manipulation of databases. RAP is particularly suited for supporting relational databases. In this paper, the relational operations provided by the RAP hardware are described, and a representative approach to providing the same relational operations with conventional software and hardware is devised. Analytic models are constructed for RAP and the conventional system. The execution times of several of the operations are shown to be vastly improved with RAP for large relations.

An analytic model of a single processor scheduling problem is investigated. The scheduling objective is to minimize the total loss incurred by a finite number of initially available requests when each request has an associated linear loss function. The assumptions of the model are that preemption is allowed with negligible loss of processor time, and that the distribution of actual service times is known for each class of requests. A request is associated with a class by any of its characteristics except its actual service time. A contrived example demonstrates that one reasonable scheduling rule does not always minimize expected total loss. The major results of the paper are the definition of a new scheduling rule based on the known service time distributions, and the proof that expected total loss is always minimized by using this new rule. Brief consideration is given to generalizations of the model in which new requests arrive randomly, and preemption requires a non-negligible amount of processor time.