Flip Korn

Over the last decades, improvements in CPU speed have outpaced improvements in main memory and disk access rates by orders of magnitude, enabling the use of data com-pression techniques to improve the performance of database systems. Previous work describes the benefits of compres-sion for numerical attributes, where data is stored in com-pressed format on disk. Despite the abundance of string-valued attributes in relational schemas there is little work on compression for string attributes in a database context. Moreover, none of the previous work suitably addresses the role of the query optimizer: During query execution, data is either eagerly decompressed when it is read into main mem-ory, or data lazily stays compressed in main memory and is decompressed on demand only. In this paper, we present an effective approach for database compression based on lightweight, attribute-level compres-sion techniques. We propose a Hierarchical Dictionary En-coding strategy that intelligently selects the most effective compression method for string-valued attributes. We show that eager and lazy decompression strategies produce sub-optimal plans for queries involving compressed string at-tributes. We then formalize the problem of compression-aware query optimization and propose one provably opti-mal and two fast heuristic algorithms for selecting a query plan for relational schemas with compressed attributes; our algorithms can easily be integrated into existing cost-based query optimizers. Experiments using TPC-H data demon-strate the impact of our string compression methods and show the importance of compression-aware query optimiza-tion. Our approach results in up to an order speed up over existing approaches. 1