This assignment requires first reading the Weaving Relations paper and then write a 3 4 pages about it answering the questions where CPSC 332 askes for
Weaving Relations for Cache Performance Anastassia Ailamaki ‡ David J. DeWitt Mark D. Hill Marios Skounakis Carnegie Mellon University Univ. of Wisconsin-Madison Univ. of Wisconsin-Madison Univ. of Wisconsin-Madison
[email protected] [email protected] [email protected] [email protected] Abstract Relational database systems have traditionally optimzed for I/O performance and organized records sequentially on disk pages using the N-ary Storage Model (NSM) (a.k.a., slotted pages). Recent research, however, indicates that cache utilization and performance is becoming increasingly important on modern platforms. In this paper, we first demonstrate that in-page data placement is the key to high cache performance and that NSM exhibits low cache utilization on modern platforms. Next, we pro- pose a new data organization model called PAX (Partition Attributes Across), that significantly improves cache perfor- mance by grouping together all values of each attribute within each page. Because PAX only affects layout inside the pages, it incurs no storage penalty and does not affect I/O behavior. According to our experimental results, when compared to NSM (a) PAX exhibits superior cache and memory bandwidth utiliza- tion, saving at least 75% of NSM’s stall time due to data cache accesses, (b) range selection queries and updates on memory- resident relations execute 17-25% faster, and (c) TPC-H queries involving I/O execute 11-48% faster. 1 Introduction The communication between the CPU and the secondary storage (I/O) has been traditionally recognized as the major database performance bottleneck. To optimize data transfer to and from mass storage, relational DBMSs have long organized records in slotted disk pages using the N- ary Storage Model (NSM). NSM stores records contigu- ously starting from the beginning of each disk page, and uses an offset (slot) table at the end of the page to locate the beginning of each record [27]. Unfortunately, most queries use only a fraction of each record. To minimize unnecessary I/O, the Decompo- sition Storage Model (DSM) was proposed in 1985 [10]. DSM partitions an n-attribute relation vertically into n sub-relations, each of which is accessed only when the corresponding attribute is needed. Queries that involve multiple attributes from a relation, however, must spend tremendous additional time to join the participating sub- relations together. Except for Sybase-IQ [33], today’s rela- tional DBMSs use NSM for general-purpose data place- ment [20][29][32]. Recent research has demonstrated that modern data- base workloads, such as decision support systems and spa- tial applications, are often bound by delays related to the processor and the memory subsystem rather than I/O [20][5][26]. When running commercial database systems on a modern processor, data requests that miss in the cache hierarchy (i.e., requests for data that are not found in any of the caches and are transferred from main memory) are a key memory bottleneck [1]. In addition, only a fraction of the data transferred to the cache is useful to the query: the item that the query processing algorithm requests and the transfer unit between the memory and the processor are typically not the same size. Loading the cache with useless data (a) wastes bandwidth, (b) pollutes the cache, and (c) possibly forces replacement of information that may be needed in the future, incurring even more delays. The challenge is to repair NSM’s cache behavior without com- promising its advantages over DSM. This paper introduces and evaluates Partition Attributes Across (PAX), a new layout for data records that combines the best of the two worlds and exhibits per- formance superior to both placement schemes by eliminat- ing unnecessary accesses to main memory. For a given relation, PAX stores the same data on each page as NSM. Within each page, however, PAX groups all the values of a particular attribute together on a minipage. During a sequential scan (e.g., to apply a predicate on a fraction of the record), PAX fully utilizes the cache resources, because on each miss a number of a single attribute’s val- ues are loaded into the cache together. At the same time, all parts of the record are on the same page. To reconstruct a record one needs to perform a mini-join among minipages, which incurs minimal cost because it does not have to look beyond the page. We evaluated PAX against NSM and DSM using (a) predicate selection queries on numeric data and (b) a vari- ety of queries on TPC-H datasets on top of the Shore stor- age manager [7]. We vary query parameters including selectivity, projectivity, number of predicates, distance between the projected attribute and the attribute in the predicate, and degree of the relation. The experimental results show that, when compared to NSM, PAX (a) incurs 50-75% fewer second-level cache misses due to data ‡ Work done while author was at the University of Wisconsin-Madison. Permission to copy without fee all or part of this material is granted pro- vided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment Proceedings of the 27th VLDB Conference, Roma, Italy, 2001 accesses when executing a main-memory workload, (b) executes range selection queries and updates in 17-25% less elapsed time, and (c) executes TPC-H queries involv- ing I/O 11-42% faster than NSM on the platform we stud- ied. When compared to DSM, PAX executes queries faster and its execution time remains stable as more attributes are involved in the query, while DSM’s execution time increases due to the high record reconstruction cost. Finally, PAX has several additional advantages. Implementing PAX on a DBMS that uses NSM requires only changes to the page-level data manipulation code. PAX can be used as an alternative data layout, and the storage manager can decide to use PAX or not when stor- ing a relation, based solely on the number of attributes. Furthermore, research [13] has shown that compression algorithms work better with vertically partitioned relations and on a per-page basis, and PAX has both of these charac- teristics. Finally, PAX can be used orthogonally to other storage decisions such as affinity graph-based partitioning [11], because it operates at the page level. The rest of this paper is organized as follows. Section 2 presents an overview of the related work, and discusses the strengths and weaknesses of the traditional NSM and DSM data placement schemes. Section 3 explains the design of PAX in detail and analyzes its storage require- ments, while Section 4 describes the implementation of basic query processing and data manipulation algorithms. Section 5 analyzes the effects of PAX on cache perfor- mance on a simple numeric workload. Section 6 demon- strates PAX’s efficiency on a subset of the TPC-H decision-support workload. Finally, Section 7 concludes with a summary of the advantages of PAX and discusses possibilities for further improvement. 2 Related work Several recent workload characterization studies report that database systems suffer from high memory-related processor delays when running on modern platforms. A detailed survey of these studies is provided elsewhere [1][34]. All studies that we are aware of agree that stall time due to data cache misses accounts for 50-70% (OLTP [19]) to 90% (DSS [1]) of the total memory-related stall time, even on architectures where the instruction cache miss rate (i.e., the number of cache misses divided by the number of cache references) is typically higher when exe- cuting OLTP workloads [21]. Research in computer architecture, compilers, and database systems has focused on optimizing data place- ment for cache performance. A compiler-directed approach for cache-conscious data placement profiles a program and applies heuristic algorithms to find a place- ment solution that optimizes cache utilization [6]. Cluster- ing, compression, and coloring are techniques that can be applied manually by programmers to improve cache per- formance of pointer-based data structures [8]. For database management systems, attribute clustering improves both compression [13] and the performance of relational query processing [29]. The remainder of this section describes the advan- tages and disadvantages of the dominant data placement scheme (NSM) and its alternative (DSM), and briefly out- lines their variants. 2.1 The N-ary Storage Model Traditionally, a relation’s records are stored in slotted disk pages [27] obeying the N-ary Storage Model (NSM). NSM stores records sequentially on data pages. Figure 1 depicts an NSM page after inserting four records of a rela- tion R with three attributes: SSN, name, and age. Each record has a record header (RH) containing a null bitmap, offsets to the variable-length values, and other implemen- tation-specific information [20][29][32]. Each new record is typically inserted into the first available free space start- ing at the beginning of the page. Records may have vari- able lengths, and therefore a pointer to the beginning of the new record is stored in the next available slot from the end of the page. One can access the nth record in a page by following the nth pointer from the end of the page. During predicate evaluation, however, NSM exhibits poor cache performance. Consider the query: select name from R where age < 40; to evaluate the predicate, the query processor uses a scan operator [14] that retrieves the value of the attribute age from each record in the relation. assuming that the nsm page in figure 1 is already in main memory and that the cache block size is smaller than the record size, the scan operator will incur one cache miss per record. if age is a 4- byte integer, it is smaller than the typical cache block size figure 1: the cache behavior of nsm. 5523 52susan 20 rh4jim 45 rh3 3589 jane 30 rh cache page header rh1 0962 jane 30 rh2 7658 john 45 rh3 3589 20 rh4jim 5523 52susan nsm page (32-128 bytes). therefore, along with the needed value, each cache miss will bring into the cache the other values stored next to age (shown on the right in figure 1), wast- ing useful cache space to store unreferenced data, and incurring unnecessary accesses to main memory. 2.2 the decomposition storage model vertical partitioning is the process of striping a relation into sub-relations, each containing the values of a subset of the initial relation’s attributes, in order to reduce i/o- related costs [24]. the fully decomposed form of vertical partitioning (one attribute per stripe) is called the decom- position storage model (dsm) [10]. dsm partitions an n- attribute relation vertically into n sub-relations (for exam- ple, figure 2 shows relation r stored in dsm format). each sub-relation contains two attributes, a logical record id (surrogate) and an attribute value (essentially, a sub- relation is a clustered index on the attribute). sub-relations are stored as regular relations in slotted pages, enabling each attribute to be scanned independently. unlike nsm, dsm offers a high degree of spatial locality when sequentially accessing the values of one attribute. during a single-attribute scan, dsm exhibits 40;="" to="" evaluate="" the="" predicate,="" the="" query="" processor="" uses="" a="" scan="" operator="" [14]="" that="" retrieves="" the="" value="" of="" the="" attribute="" age="" from="" each="" record="" in="" the="" relation.="" assuming="" that="" the="" nsm="" page="" in="" figure="" 1="" is="" already="" in="" main="" memory="" and="" that="" the="" cache="" block="" size="" is="" smaller="" than="" the="" record="" size,="" the="" scan="" operator="" will="" incur="" one="" cache="" miss="" per="" record.="" if="" age="" is="" a="" 4-="" byte="" integer,="" it="" is="" smaller="" than="" the="" typical="" cache="" block="" size="" figure="" 1:="" the="" cache="" behavior="" of="" nsm.="" 5523="" 52susan="" 20="" rh4jim="" 45="" rh3="" 3589="" jane="" 30="" rh="" cache="" page="" header="" rh1="" 0962="" jane="" 30="" rh2="" 7658="" john="" 45="" rh3="" 3589="" 20="" rh4jim="" 5523="" 52susan="" nsm="" page="" (32-128="" bytes).="" therefore,="" along="" with="" the="" needed="" value,="" each="" cache="" miss="" will="" bring="" into="" the="" cache="" the="" other="" values="" stored="" next="" to="" age="" (shown="" on="" the="" right="" in="" figure="" 1),="" wast-="" ing="" useful="" cache="" space="" to="" store="" unreferenced="" data,="" and="" incurring="" unnecessary="" accesses="" to="" main="" memory.="" 2.2="" the="" decomposition="" storage="" model="" vertical="" partitioning="" is="" the="" process="" of="" striping="" a="" relation="" into="" sub-relations,="" each="" containing="" the="" values="" of="" a="" subset="" of="" the="" initial="" relation’s="" attributes,="" in="" order="" to="" reduce="" i/o-="" related="" costs="" [24].="" the="" fully="" decomposed="" form="" of="" vertical="" partitioning="" (one="" attribute="" per="" stripe)="" is="" called="" the="" decom-="" position="" storage="" model="" (dsm)="" [10].="" dsm="" partitions="" an="" n-="" attribute="" relation="" vertically="" into="" n="" sub-relations="" (for="" exam-="" ple,="" figure="" 2="" shows="" relation="" r="" stored="" in="" dsm="" format).="" each="" sub-relation="" contains="" two="" attributes,="" a="" logical="" record="" id="" (surrogate)="" and="" an="" attribute="" value="" (essentially,="" a="" sub-="" relation="" is="" a="" clustered="" index="" on="" the="" attribute).="" sub-relations="" are="" stored="" as="" regular="" relations="" in="" slotted="" pages,="" enabling="" each="" attribute="" to="" be="" scanned="" independently.="" unlike="" nsm,="" dsm="" offers="" a="" high="" degree="" of="" spatial="" locality="" when="" sequentially="" accessing="" the="" values="" of="" one="" attribute.="" during="" a="" single-attribute="" scan,="" dsm="">