Over the past 15 years, data warehousing and OLAP technologies have matured to the point whereby they have become a cornerstone for the decision making process in organizations of all sizes. With the underlying databases growing enormously in size, parallel DBM systems have become a popular target platform. Perhaps the most ``obvious'' approach to scalable warehousing is to combine a small collection of conventional relational DBMSs into a loosely connected parallel DBMS. Such systems, however, benefit little, if at all, from advances in OLAP indexing, storage, compression, modeling, or query optimization. In the current paper, we discuss a parallel analytics server that has been designed from the ground up as a high performance OLAP query engine. Moreover, its indexing and query processing model directly exploits an OLAP-specific algebra that enables performance optimizations beyond the reach of simple relational DBMS clusters. Taken together, the server provides class-leading query performance with the scalability of shared nothing databases and, perhaps most importantly, achieves this balance with a modest physical architecture.

Database query engines typically rely upon query size estimators in order to evaluate the potential cost of alternate query plans. In multi-dimensional database systems, such as those typically found in large data warehousing environments, these selectivity estimators often take the form of multi-dimensional histograms. But while single dimensional histograms have proven to be quite accurate, even in the presence of data skew, the multi-dimensional variations have generally been far less reliable. In this paper, we present a new histogram model that is based upon an r-tree space partitioning. The localization of the r-tree boxes is in turn controlled by a Hilbert space filling curve, while a series of efficient area equalization heuristics restructures the initial boxes to provide improved bucket representation. Experimental results demonstrate significantly improved estimation accuracy relative to state of the art alternatives, as well as superior consistency across a variety of record distributions.

Online Analytical Processing is a database paradigm that provides for the rich analysis of multi-dimensional data. OLAP is often supported by a logical structure known as the Cube. However, supporting efficient OLAP query resolution in enterprise scale environments is an issue of considerable complexity. In practice, the difficulty of the problem is exacerbated by the existence of dimension hierarchies that sub-divide core dimensions into aggregation layers of varying granularity. Common hierarchy-sensitive query operations such as Rollup and Drilldown can be very costly on large cubes. Moreover, facilities for the representation of more complex hierarchical relationships are not well supported by conventional techniques. This paper presents a robust hierarchy infrastructure called mapGraph that supports the efficient and transparent manipulation of attribute hierarchies within OLAP environments. Experimental results verify that, when compared to the alternatives, very little additional overhead is introduced, even when advanced functionality is exploited.

Over the past ten to fifteen years, data warehouse platformshave grown enormously, both in terms of their importance and their sheer size. Traditionally, such systems have been based upon a dimensional model known as the Star Schema that consists of a central fact table and a series of related dimension tables. Given the enormous size of the fact table, virtually all current systems augment the primary fact table with a small number of focused summary tables. Previous research has addressed the issue of the selection or identification of the most cost-effective summaries. However, the problem of efficiently computing a given view subset has received far less attention. In this paper, we present a suite of greedy algorithms for the construction of these view subsets. Experimental results demonstrate cost savings of between 20% and 70% relative to the naive alternatives, depending upon the degree of materialization required.

In multi-dimensional database environments, we typically require effective indexing mechanisms for all but the smallest data sets. While numerous such methods have been proposed, the R-tree has emerged as one of the most common and reliable indexing models. Nevertheless, as user queries grow in terms of both size and dimensionality, R- tree performance can deteriorate significantly. In some application areas, however, it is possible to exploit data and query specific features to obtain dramatic improvements in query performance. We propose a variation of the classic R-tree that specifically targets data warehousing architectures. The new model not only improves performance on common user-defined range queries, but gracefully degrades to a linear scan of the data on pathologically large queries. Experimental results demonstrate reductions in disk seeks of more than 50% relative to more conventional R-tree designs.

We present the cgmOLAP server, the first fully functional parallel OLAP system able to build data cubes at a rate of more than 1 Terabyte per hour. cgmOLAP incorporates a variety of novel approaches for the parallel computation of full cubes, partial cubes, and iceberg cubes as well as new parallel cube indexing schemes. The cgmOLAP system consists of an application interface, a parallel query engine, a parallel cube materialization engine, meta data and cost model repositories, and shared server components that provide uniform management of I/O, memory, communications, and disk resources.

Online Analytical Processing is a powerful framework for the analysis of organizational data. OLAP is often supported by a logical structure known as a data cube, a multidimensional data model that offers an intuitive array-based perspective of the underlying data. Supporting efficient indexing facilities for multi-dimensional cube queries is an issue of some complexity. In practice, the difficulty of the indexing problem is exacerbated by the existence of attribute hierarchies that sub-divide attributes into aggregation layers of varying granularity. In this paper, we present a hierarchy and caching framework that supports the efficient and transparent manipulation of attribute hierarchies within a parallel ROLAP environment. Experimental results verify that, when compared to the non-hierarchical case, very little overhead is required to handle streams of arbitrary hierarchical queries.

We present "Pipe 'n Prune" (PnP), a new hybrid method for iceberg-cube query computation. The novelty of our method is that it achieves a tight integration of top-down piping for data aggregation with bottom-up a priori data pruning. A particular strength of PnP is that it is very efficient for all of the following scenarios: (1) Sequential iceberg-cube queries. (2) External memory iceberg-cube queries. (3) Parallel iceberg-cube queries on shared-nothing PC clusters with multiple disks.

This paper addresses the query performance issue for Relational OLAP (ROLAP) datacubes. We present a distributed multi-dimensional ROLAP indexing scheme which is practical to implement, requires only a small communication volume, and is fully adapted to distributed disks. Our solution is efficient for spatial searches in high dimensions and scalable in terms of data sizes, dimensions, and number of processors. Our method is also incrementally maintainable. Using "surrogate" group-bys, it allows for the efficient processing of arbitrary OLAP queries on partial cubes, where not all of the group-bys have been materialized. Our experiments show that the ROLAP advantage of better scalability, in comparison to MOLAP can be maintained while providing, at the same time, a fast and flexible index for OLAP queries.

This paper presents a general methodology for the efficient parallelization of existing data cube construction algorithms . We describe two different partitioning strategies, one for top-down and one for bottom-up cube algorithms. Both partitioning strategies assign subcubes to individual processors in such a way that the loads assigned to the processors are balanced. Our methods reduce inter processor communication overhead by partitioning the load in advance instead of computing each individual group-by in parallel. Our partitioning strategies create a small number of coarse tasks. This allows for sharing of prefixes and sort orders between different group-by computations. Our methods enable code reuse by permitting the use of existing sequential (external memory) data cube algorithms for the subcube computations on each processor. This supports the transfer of optimized sequential data cube code to a parallel setting. The bottom-up partitioning strategy balances the number of single attribute external memory sorts made by each processor. The top-down strategy partitions a weighted tree in which weights reflect algorithm specific cost measures like estimated group-by sizes. Both partitioning approaches can be implemented on any shared disk type parallel machine composed of p processors connected via an interconnection fabric and with access to a shared parallel disk array. We have implemented our parallel top-down data cube construction method in C++ with the MPI message passing library for communication and the LEDA library for the required graph algorithms. We tested our code on an eight processor cluster, using a variety of different data sets with a range of sizes, dimensions, density, and skew. Comparison tests were performed on a SunFire 6800. The tests show that our partitioning strategies generate a close to optimal load balance between processors. The actual run times observed show an optimal speedup of p .

Describes the parallel, cluster-based implementation of an algorithm for the computation of a database operator known as the datacube. Though a number of efficient sequential algorithms have recently been proposed for this problem, very little research effort has been expended upon cost-effective parallelization techniques. Our approach builds directly upon the existing sequential proposals and is designed to be both load-balanced and communication-efficient. We also provide experimental results that demonstrate the viability of our technique under a variety of test conditions. Ultimately, we show that parallel performance relative to the underlying sequential algorithm (speedup) is near-optimal.