In this paper we investigate techniques that allow for on-line updates to columnar databases, leaving intact their high read-only performance. Rather than keeping differential structures organized by the table key values, the core proposition of this paper is that this can better be done by keeping track of the tuple position of the modifications. Not only does this minimize the computational overhead of merging in differences into read-only queries, but this makes the differential structure oblivious of the value of the order keys, allowing it to avoid disk I/O for retrieving the order keys in read-only queries that otherwise do not need them -a crucial advantage for a column-store. We describe a new data structure for maintaining such positional updates, called the Positional Delta Tree (PDT), and describe detailed algorithms for PDT/column merging, updating PDTs, and for using PDTs in transaction management. In experiments with a columnar DBMS, we perform microbenchmarks on PDTs, and show in a TPC-H workload that PDTs allow quick on-line updates, yet significantly reduce their performance impact on read-only queries compared with classical value-based differential methods. Categories and Subject Descriptors H.2.8 [Database Management]: Database Applications Algorithms, Experimentation, Performance Database systems that use columnar storage (DSM [8]) have recently re-gained commercial and research momentum [22, 3, 3, 21] , especially for performance intensive readmostly application areas such as data warehousing, as they can significantly reduce the cost of disk I/O with respect to row-wise disk storage (NSM). Modern columnar data warehousing systems additionally employ techniques like comPermission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SIGMOD'10, June 6-11, 2010, Indianapolis, Indiana, USA. Copyright 2010 ACM 978-1-4503-0032-2/10/06 ...$10.00. pression, data clustering, and replication that make them truly read-friendly and write-unfriendly. In this paper we address the question how such systems can still efficiently provide update functionality. Analytical query workloads inspect large amounts of tuples, but typically only a small subset of the columns; hence columnar storage avoids data access (I/O, CPU cache misses) for unused columns. Three techniques are often added to further increase performance: first, columnar systems often store data in a certain order (or clustering), to further reduce data access cost when range-predicates are used. Second, by using multiple replicas of such tables in different orders, the amount of predicates in a query workload that can benefit from this increases. Data compression, finally, reduces the data access cost needed to answer a query, because the data gets smaller, and more data fits in the buffer pool when compressed, reducing the page miss ratio. The challenge facing updates in analytical column stores is that one I/O per column (replica) is needed, hence a single-row update that can be handled in a row-store with a single disk I/O will lead to many disk I/Os in a column store. These disk I/Os are scattered (random) I/Os, even if the database users only do inserts, because of the ordered or clustered table storage. Finally, compression makes updates computationally more expensive and complex since data needs to be de-compressed, updated and re-compressed before being written back to disk. Extra complications occur if the updated data no longer fits its original location. Differential Updates. Some analytical columnar database systems, such as C-Store [22] , handle updates by splitting their architecture in a "read-store" that manages the bulk of all data and a "write-store" that manages updates that have been made recently. Consequently, all queries access both base table information from the read-store, as well as all corresponding differences from the write-store and merge these on-the-fly. Also, in order to keep the write-store small (it resides typically in RAM), changes in it are periodically propagated into the read-store [22] . The topic of this paper is what data structures and algorithms should be used for implementing the write-store of a column-oriented database system that aims to support generic update workloads (inserts, deletes, modifications; batch or trickle). The natural "value-based" way to implement the write-store is to keep track of which tuples were deleted, inserted or modified in a RAM-resident data structure that organizes these items in the sort key (SK) order of the underlying read-store table and contains these keys; for example in a RAM friendly B-tree [6] . Such a data struc-543
The authors of REF also use a dedicated differential buffer in order to improve update performance in a column store.
Positional update handling in column stores
SIGMOD Conference
Computer Science