Query optimization in compressed database systems Zhiyuan Chen, Johannes Gehrke, and Flip Korn   View Paper (PDF)   Return to Compression Abstract Over the last decades,mprovements n CPU speed have outpaced improvements in main memory and disk access rates by orders of magnitude,enabl ng the use of data compression techniques to mprove the performance of database systems.Prev ous work descr bes the benefits of compression for numer cal attr butes,where data s stored n compressed format on d sk.Despite the abundance of str ng-valued attributes in relat onal schemas there is little work on compression for str ng attr butes n a database context. Moreover,none of the prev ous work suitably addresses the role of the query opt m zer:Dur ng query execut on,data s either eagerly decompressed when t s read nto main memory,or data lazily stays compressed n main memory and s decompressed on demand only. In th s paper,we present an effect ve approach for database compress on based on lightweight,attribute-level compression techniques. We propose a Hierarchical Dictionary Encoding strategy that intelligently selects the most effective compress on method for string-valued attributes. We show that eager and lazy decompression strategies produce sub-optimal plans for queries involving compressed string attributes.We then formalize the problem of compression-aware query optimization and propose one provably optimal 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 demonstrate the mpact of our string compression methods and show the mportance of compression-aware query optimization. Our approach results n up to an order speed up over existing approaches. DiSC'02 © 2003 Association for Computing Machinery