Modern Internet applications often produce a large volume of user activity records. Data analysts are interested in cohort analysis, or finding unusual user behavioral trends, in these large tables of activity records. In a traditional database system, cohort analysis queries are both painful to specify and expensive to evaluate. We propose to extend database systems to support cohort analysis. We do so by extending SQL with three new operators. We devise three different evaluation schemes for cohort query processing. Two of them adopt a non-intrusive approach. The third approach employs a columnar based evaluation scheme with optimizations specifically designed for cohort query processing. Our experimental results confirm the performance benefits of our proposed columnar database system, compared against the two non-intrusive approaches that implement cohort queries on top of regular relational databases.
Column-oriented database system architectures invite a re-evaluation of how and when data in databases is compressed. Storing data in a column-oriented fashion greatly increases the similarity of adjacent records on disk and thus opportunities for compression. The ability to compress many adjacent tuples at once lowers the per-tuple cost of compression, both in terms of CPU and space overheads.In this paper, we discuss how we extended C-Store (a column-oriented DBMS) with a compression sub-system. We show how compression schemes not traditionally used in row-oriented DBMSs can be applied to column-oriented systems. We then evaluate a set of compression schemes and show that the best scheme depends not only on the properties of the data but also on the nature of the query workload. In the past decade, advances in the speed of commodity CPUs have far out-paced advances in memory latency. Main-memory access is therefore increasingly a performance bottleneck for many computer applications, including database systems. In this article, we use a simple scan test to show the severe impact of this bottleneck. The insights gained are translated into guidelines for database architecture, in terms of both data structures and algorithms. We discuss how vertically fragmented data structures optimize cache performance on sequential data access. We then focus on equi-join, typically a random-access operation, and introduce radix algorithms for partitioned hash-join. The performance of these algorithms is quantified using a detailed analytical model that incorporates memory access cost. Experiments that validate this model were performed on the Monet database system. We obtained exact statistics on events such as TLB misses and L1 and L2 cache misses by using hardware performance counters found in modern CPUs. Using our cost model, we show how the carefully tuned memory access pattern of our radix algorithms makes them perform well, which is confirmed by experimental results. With the advent of the Internet, access to database servers from autonomous clients will become more and more popular. In this paper, we propose a monitoring service that could be offered by such database servers, and present algorithms for its implementation. In contrast to published view maintenance algorithms, we do not assume that the server has access to the original materialization when computing differential view changes to be notified. We also do not assume any database capabilities on the client side and therefore compute precisely the required differentials rather than just an approximation, as is done by cache coherence techniques in homogeneous clientserver databases. The method has been implemented in ConceptBase, a meta data management system supporting an Internet-based client-server architecture, and tried out in some cooperative design applications. In this paper, we show how compression can be integrated into a relational database system. Specifically, we describe how the storage manager, the query execution engine, and the query optimizer of a database system can be extended to deal with compressed data. Our main result is that compression can significantly improve the response time of queries if very light-weight compression techniques are used. We will present such light-weight compression techniques and give the results of running the TPC-D benchmark on a so compressed database and a non-compressed database using the AODB database system, an experimental database system that was developed at the Universities of Mannheim and Passau. Our benchmark results demonstrate that compression indeed offers high performance gains (up to 50 ) for IO-intensive queries and moderate gains for CPU-intensive queries. Compression can, however, also increase the running time of certain update operations. In all, we recommend to extend today's database systems with light-weight compression techniques and to make extensive use of this feature. This paper focuses on running scans in a main memory data processing system at "bare met al" speed. Essentially, this means that the system must aim to process data at or near the speed of the processor (the fastest component in most system configurations). Scans are common in main memory data processing environments, and with the state-of-the-art techniques it still takes many cycles per input tuple to apply simple predicates on a single column of a table. In this paper, we propose a technique called BitWeaving that exploits the parallelism available at the bit level in modern processors. BitWeaving operates on multiple bits of data in a single cycle, processing bits from different columns in each cycle. Thus, bits from a batch of tuples are processed in each cycle, allowing BitWeaving to drop the cycles per column to below one in some case. BitWeaving comes in two flavors: BitWeaving V which looks like a columnar organization but at the bit level, and BitWeaving H which packs bits horizontally. In this paper we also develop the arithmetic framework that is needed to evaluate predicates using these BitWeaving organizations. Our experimental results show that both these methods produce significant performance benefits over the existing state-of-the-art methods, and in some cases produce over an order of magnitude in performance improvement. Computing multiple related group-bys and aggregates is one of the core operations of On-Line Analytical Processing (OLAP) applications. Recently, [GBLP95] proposed the “Cube” operator, which computes group-by aggregations over all possible subsets of the specified dimensions. The rapid acceptance of the importance of this operator has led to a variant of the Cube being proposed for the SQL standard. Several efficient algorithms for Relational OLAP (ROLAP) have been developed to compute the Cube. However, to our knowledge there is nothing in the literature on how to compute the Cube for Multidimensional OLAP (MOLAP) systems, which store their data in sparse arrays rather than in tables. In this paper, we present a MOLAP algorithm to compute the Cube, and compare it to a leading ROLAP algorithm. The comparison between the two is interesting, since although they are computing the same function, one is value-based (the ROLAP algorithm) whereas the other is position-based (the MOLAP algorithm). Our tests show that, given appropriate compression techniques, the MOLAP algorithm is significantly faster than the ROLAP algorithm. In fact, the difference is so pronounced that this MOLAP algorithm may be useful for ROLAP systems as well as MOLAP systems, since in many cases, instead of cubing a table directly, it is faster to first convert the table to an array, cube the array, then convert the result back to a table.   At the heart of all OLAP or multidimensional data analysis applications is the ability to simultaneously aggregate across many sets of dimensions. Computing multidimensional aggregates is a performance bottleneck for these applications. This paper presents fast algorithms for computing a collection of group bys. We focus on a special case of the aggregation problem - computation of the CUBE operator. The CUBE operator requires computing group-bys on all possible combinations of a list of attributes, and is equivalent to the union of a number of standard group-by operations. We show how the structure of CUBE computation can be viewed in terms of a hierarchy of group-by operations. Our algorithms extend sort-based and hashbased grouping methods with several .optimizations, like combining common operations across multiple groupbys, caching, and using pre-computed group-by8 for computing other groupbys. Empirical evaluation shows that the resulting algorithms give much better performance compared to straightforward meth OptimizingQueriesOnCompressedBitmapsSihem Amer-YahiaAT&T Labs Researchsihem@research.att.comTheo doreJohnsonjohnsont@research.att.comAbstractBitmap indices are used by DBMS's to accelerate decision supp ort queries.A signi cant advantage ofbitmap indices is that complex logical selection op erations can b e p erformed very quickly, by p erformingbit-wiseAND,OR,andNOTop erators.Althoughbitmapindicescanb espaceinecientforhighcardinalityattributes,the space use of compressed bitmapscompares well to other indexingmetho ds.Oracle and Sybase IQ are two commercial pro ducts that make extensive use of compressed bitmap indices.Our recent research showed that there are several fast algorithmsfor evaluatingBo oleanop eratorson compressedbitmaps.Dep endingon the natureof the op erandbitmaps(theirformat, densityandclusterdness) and the op eration to b e p erformed (AND, NOT, ...), these algorithms can have executiontimes that are orders of magnitude di erent.Cho osing an algorithm for p erforming a Bo olean op erationhas global e ects in the Bo olean query expression, requiring global optimization.We present a linear timedynamicprogrammingsearch strategy based on a cost mo delto optimizequeryexpressionevaluationplans.We alsopresentrewritingheuristicsthat rewritethe queryexpressionto anequivalenonetoencourage b etter algorithmsassignments.Our p erformance results show that the optimizerrequiresanegligibl e amount of time to execute, and that optimized complex queries can execute up to three timesfaster than unoptimized queries on real data.1Intro ductionAbitmap indexis a bit string in which each bit is mapp ed to a record ID (RID) of a relation.A bit in thebitmap index is set (to 1) if the corresp onding RID has prop ertyP(i.e., the RID represents a customer thatlives in New York), and is reset (to 0) otherwise.In typical usage, the predicatePis true for a record if it hasthe valueafor attributeA.One such predicate is asso ciated to one bitmap index for each unique value ofthe attributeA.The predicates can b e more complex, for example bitslice indices [OQ97] and precomputedcomplex selection predicates [HEP99].Oneadvantageofbitmapindicesisthatcomplexselectionpredicatescanb ecomputedveryquickly,by p erforming bit-wiseAND, OR, andNOTop erations on the bitmap indices.Furthermore, the indexableselection predicates can involve many attributes.Let's consider some examples, using a customer databasewith schemaCustomer(Name, Livesin, Worksin, Car, Numberofchildren, Hascable, Hasel lular)Supp osethatweanttoselectallcustomerswholivinNewEngland.Thentheselectioncon-ditionisLivesin= "ORin= "in= "in= "in= "ORLivesin= "in= ". Since a bitmap index is createdfor each value of the attributeLivesin, the query translates into mapping the attribute to all its p ossible values.1 Database systems tend to achieve only low IPC (instructions-per-cycle) eciency on modern CPUs in compute-intensive application areas like decision support, OLAP and multimedia retrieval. This paper starts with an in-depth investigation to the reason why this happens, focusing on the TPC-H benchmark. Our analysis of various relational systems and MonetDB leads us to a new set of guidelines for designing a query processor. The second part of the paper describes the architecture of our new X100 query engine for the MonetDB system that follows these guidelines. On the surface, it resembles a classical Volcano-style engine, but the crucial dierence to base all execution on the concept of vector processing makes it highly CPU ecien t. We evaluate the power of MonetDB X100 on the 100GB version of TPC-H, showing its raw execution power to be between one and two orders of magnitude higher than previous technology. 