Query optimization in compressed database systems

ABSTRACT

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 compression techniques to improve the performance of database systems. Previous work describes the benefits of compression for numerical attributes, where data is stored in compressed 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 memory, 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 compression techniques. We propose a IIierarchical Dictionary Encoding 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 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 impact of our string compression methods and show the importance of compression-aware query optimization. Our approach results in up to an order speed up over existing approaches.

REFERENCES

• 1: Transact on processing performance council TPC-H benchmark, http://www.tpc.org 1999.
• 2: Predator DMBS. http://www.cs.cornel l.edu/database/predator, Cornel l Univ., Computer Science Dept.,2000.
• 3: Sihem Amer-Yahia , Theodore Johnson, Optimizing Queries on Compressed Bitmaps, Proceedings of the 26th International Conference on Very Large Data Bases, p.329-338, September 10-14, 2000
• 4: Gennady Antoshenkov , David B. Lomet , James Murray, Order Preserving Compression, Proceedings of the Twelfth International Conference on Data Engineering, p.655-663, February 26-March 01, 1996
• 5: C.Blake and C.Merz.UCI repository of machine learning databases. http://www.ics.uci.edu/~mlearn/MLRepository.html 1998.
• 6: Peter A. Boncz , Stefan Manegold , Martin L. Kersten, Database Architecture Optimized for the New Bottleneck: Memory Access, Proceedings of the 25th International Conference on Very Large Data Bases, p.54-65, September 07-10, 1999
• 7: Surajit Chaudhuri , Kyuseok Shim, Optimization of queries with user-defined predicates, ACM Transactions on Database Systems (TODS), v.24 n.2, p.177-228, June 1999 [doi>10.1145/320248.320249]
• 8: An Algebraic Compression Framework for Query Results, Proceedings of the 16th International Conference on Data Engineering, p.177, February 28-March 03, 2000
• 9: J.G.Cleary and I.H.W tten.Data compression using adaptive coding and partial string matching. IEEE Trans. on Communications COM-32(4),pages 396 -402,April 1984.
• 10: Gordon V. Cormack, Data compression on a database system, Communications of the ACM, v.28 n.12, p.1336-1342, Dec. 1985 [doi>10.1145/214956.214963]
• 11: S.J.Eggers,F.Olken,and A.Shoshani.A compress on techn que for large statist cal data-bases. In Proc.of VLDB pages 424 -434,1981.
• 12: Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, Compressing Relations and Indexes, Proceedings of the Fourteenth International Conference on Data Engineering, p.370-379, February 23-27, 1998
• 13: Squeezing the Most Out of Relational Database Systems, Proceedings of the 16th International Conference on Data Engineering, p.81, February 28-March 03, 2000
• 14: Goetz Graefe, Options in physical database design, ACM SIGMOD Record, v.22 n.3, p.76-83, Sept. 1993 [doi>10.1145/163090.163100]
• 15: G.Graefe and L.Shapiro.Data compression and database performance.In ACM/IEEE-CS Symp. On Applied Computing pages 22 -27,April 1991.
• 16: Rick Greer, Daytona and the foruth-generation language cymbal, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.525-526, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 17: Joseph M. Hellerstein , Michael Stonebraker, Predicate migration: optimizing queries with expensive predicates, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.267-276, May 25-28, 1993, Washington, D.C., United States
• 18: D.Hu .man.A method for the construct on of m nimum-redundanc codes.In Proc. IRE, 40(9), pages 1098 -1101,Sept.1952.
• 19: Balakrishna R. Iyer , David Wilhite, Data Compression Support in Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.695-704, September 12-15, 1994
• 20: Tobin J. Lehman , Michael J. Carey, Query processing in main memory database management systems, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.239-250, May 28-30, 1986, Washington, D.C., United States
• 21: Jianzhong Li , Doron Rotem , Jaideep Srivastava, Aggregation Algorithms for Very Large Compressed Data Warehouses, Proceedings of the 25th International Conference on Very Large Data Bases, p.651-662, September 07-10, 1999
• 22: Hartmut Liefke , Dan Suciu, XMill: an efficient compressor for XML data, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.153-164, May 15-18, 2000, Dallas, Texas, United States
• 23: Wee Keong Ng , Chinya V. Ravishankar, Relational Database Compression Using Augmented Vector Quantization, Proceedings of the Eleventh International Conference on Data Engineering, p.540-549, March 06-10, 1995
• 24: G.Ray,J.R.Harista,and S.Seshadri.Database compression:A performance enhancement tool.In the 7th Int'l Conf. on Management of Data (COMAD), Pune,India,1995.
• 25: Mark A. Roth , Scott J. Van Horn, Database compression, ACM SIGMOD Record, v.22 n.3, p.31-39, Sept. 1993 [doi>10.1145/163090.163096]
• 26: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 27: D.Severance.A pract t oner 's guide to database compression.Information Systems 8(1),pages 51 -62, 1983.
• 28: T.Welch.A technique for high-performance data compression.IEEE Computer 17(6),pages 8 -19,June 1984.
• 29: Till Westmann , Donald Kossmann , Sven Helmer , Guido Moerkotte, The implementation and performance of compressed databases, ACM SIGMOD Record, v.29 n.3, p.55-67, Sept. 2000 [doi>10.1145/362084.362137]
• 30: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 31: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]
• 32: J.Ziv and A.Lempel.On the complexity of .nite sequences.IEEE Trans. on Information Theory, 22(1),pages 75 -81,1976.
• 33: J.Ziv and A.Lempel.A universal algorithm for sequent al data compression.IEEE Trans. on Information Theory, 22(1),pages 337 -343,1977.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory