A Comparison of C-Store and Row-Store in a Common Framework

盖国强

200

12页

0次

2022-05-30

5墨值下载

A Comparison of C-Store and Row-Store in a Common

Framework

Alan Halverson Jennifer L. Beckmann Jeﬀrey F. Naughton David J. DeWitt

University of Wisconsin-Madison

1210 W. Dayton St.

Madison, Wisconsin 53706 USA

{alanh,jbe ckmann,naughton,dewitt}@cs.wisc.edu

Paper Id: 355

Abstract

Recently, a “column store” system called C-

Store has shown signiﬁcant performance ben-

eﬁts by utilizing storage optimizations for a

read-mostly query workload. The authors

of the C-Store paper compared their opti-

mized column store to a commercial row store

RDBMS that is optimized for a mixture of

reads and writes, which obscures the relative

beneﬁts of row and column stores. In this pa-

per, we describe two s torage optimizations for

a row store architecture given a read-mostly

query workload – “super tuples” and “column

abstraction.” We implement both our opti-

mized row store and C-Store in a common

framework in order to perform an “apples-

to-apples” comparison of the optimizations in

isolation and combination. We also develop

a detailed cost model for sequential scans to

break down time spent into three categories

– disk I/O, iteration cost, and local tuple re-

construction cost. We conclude that, while

the C-Store sys tem oﬀers tremendous perfor-

mance beneﬁts for scanning a small fraction

of columns from a table, our optimized row

store provides disk storage savings, reduced

sequential scan times, and low additional CPU

overheads while requiring only evolutionary

changes to a standard row store.

Permission to copy without f ee all or part of this material is

granted provided 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 32nd VLDB Conference,

Seoul, Korea, 2006

1 Introduction

Recently, a column-oriented storage system called C-

Store [7] has shown provocative performance results

when compared to a commercial row-oriented DBMS.

Their comparison of the read-optimized C-Store ideas

to a write-optimized commercial DBMS obscures the

relative beneﬁts of row and column storage for read-

mostly workloads. For example, one sequential scan

query in the C-Store e valuation takes 2.54 seconds

for C-Store while the DBMS takes 18.47 seconds –

even with a materialized view that directly answers

the query. In this paper, we show that the row store

can also be optimized for a read-mostly query work-

load, and the query above can be run in as little as 1.42

seconds with our optimized row store. In an attempt

to shed light on the comparison betwe en the two, we

implement both a read-optimized row store and the

C-Store system in a common framework.

The C-Store architecture uses several main tech-

niques to improve performance when compared to cur-

rent com mercial relational systems. First, C-Store

stores each column of a relation separately on disk. In

this way, scanning a small fraction of the columns from

a relation with many columns saves disk I/O. Second,

it carefully packs column values into large page-sized

blocks to avoid per-value overheads. Third, C-Store

uses a combination of sorting and value compression

techniques to further reduce disk storage requirements.

Both the page packing and sorting/compression tech-

niques are an attempt to trade decreased I/O for in-

creased CPU utilization.

The performance evaluation presented in the C-

Store paper uses a mo diﬁed TPC-H [4] schema and

query workload to measure the combined eﬀects of

their performance improvement techniques. The re-

ported results are very impressive – the C-Store system

provides a signiﬁcant performance improvement com-

pared with a commercial row store. Although the com-

mercial row store compares poorly, an optimized row

store can beneﬁt from most of the same performance

techinques proposed for the C-Store system. Speciﬁ-

cally, our optimized row store uses both careful page

packing, which we call “super tuples,” and sorting to

enable compression, which we call “column abstrac-

tion.” The remaining technique – column storage –

is the primary diﬀerence between row- and column-

oriented storage. Careful page packing is particularly

low-hanging fruit for a row store. Enforced sorting of

the relation and storing repeating values only once to

save space is slightly more eﬀort, as it breaks the one-

to-one mapping of the logical relational schema to the

physical tuple on disk.

The main contributions of our paper are as follows:

• We provide descriptions of the “super tuple” and

“column abstraction” performance techniques to

optimize for a read-mostly query workload.

• We build a software artifact to evaluate these per-

formance improvements for both the row and col-

umn stores in isolation and in combination, us-

ing a common storage manager. Our experiments

vary tuple width, number of rows, level of sorting

and column abstraction, and number of columns

scanned to identify performance trends.

• We propose and validate a formal cost model for

sequential scan for both row and column stor-

age. The model takes into account the storage

improvements and their eﬀects on performance

by identifying three factors which contribute to

overall scan time. We compare the mo del predic-

tions with our experimental results. We also use

the mo del to forecast the behavior of systems and

scenarios to gain further insight into performance

trends.

The rest of the paper proceeds as follows. In Sec-

tion 2, we present the storage optimizations and imple-

mentation details. Section 3 describes our experimen-

tal prototype and evaluates the storage optimizations

in isolation and combination to discover performance

trends. We then develop our formal cost model, with

validation and forecasting, in Section 4. We describe

related work in Section 5, and oﬀer conclusions and

future directions for research in Section 6.

2 Storage Optimizations

In this section, we describe the “super tuple” and “col-

umn abstraction” optimizations for the row store ar-

chitecture. To illustrate the eﬀects of each storage

option, we will use an instance of a materialized view

deﬁned in the C-Store [7] paper. The view is based

on a simpliﬁed version of the schema from the TPC-H

benchmark [4], and is deﬁned using SQL as follows:

L RETURNFLAG C NATIONKEY L EXTENDEDPRICE

A 3 23

A 3 34

A 9 64

N 3 88

N 14 49

R 9 16

R 9 53

R 9 7

R 11 63

R 21 72

Table 1: Example instance of materialized view

CREATE VIEW D4 AS

SELECT L RETURNFLAG, C NATIONKEY, L EXTENDEDPRICE

FROM Customer, Orders, Lineitem

WHERE C CUSTID = O CUSTID

AND O ORDERID = L ORDERID

ORDER BY L RETURNFLAG, C NATIONKEY;

The deﬁnition is identical to the view called D4 in

the C-Store paper with the exception of the secondary

ORDER BY on the C NATIONKEY column. Table 1 contains

an instance of the D4 view that we use in all examples

for this section. Figure 1(a) shows how a standard row

store would layout the ﬁrst few rows of the D4 view

on a disk page.

2.1 Super Tuples

All of the major DBMS products use a variant of the

slotted page for storage of tuples in a table. Slotted

pages use an array of slots that point to the actual

tuples within the page. Typically each tuple is pref-

aced by a header that provides metadata about the

tuple. For example, metadata in the Shore storage

manager [2] includes the type of tuple (small or large),

the size of the user-sp ec iﬁed record header, and the

total size of the record if it is larger than one page and

split across disk pages. The tuple header is implemen-

tation speciﬁc, but typically is 8-16 bytes in addition

to the tuple’s slot entry.

While the slotted page design provides a generic

platform for a wide range of data storage needs, these

per-tuple overheads can be problematic. Even for an

80 byte tuple, a 16 byte overhead is 20%. We reduce

per-tuple overhead by packing many tuples into page-

sized “super tuples.” For ﬁxed-length tuples, the super

tuple is an array of tuple-sized entries which can be

indexed directly. For variable length tuples, the tuple

length must be stored. The super tuple design uses a

nested iteration model, which ultimately reduces CPU

overhead and disk I/O.

An important side eﬀect of using super tuples is that

external addressability of individual tuples is more dif-

ﬁcult. Both the C-Store design and our optimized

row store trade the storage beneﬁts derived from tight

packing of values for additional overhead associated

with utilizing and maintaining value indexes.

of 12

5墨值下载

row-stores 列存 paper

关注

评论