How to barter bits for chronons: compression and bandwidth trade offs for database scans

ABSTRACT

Two trends are converging to make the CPU cost of a table scan a more important component of database performance. First, table scans are becoming a larger fraction of the query processing workload, and second, large memories and compression are making table scans CPU, rather than disk bandwidth, bound. Data warehouse systems have found that they can avoid the unpredictability of joins and indexing and achieve good performance by using massive parallel processing to perform scans over compressed vertical partitions of a denormalized schema.

In this paper we present a study of how to make such scans faster by the use of a scan code generator that produces code tuned to the database schema, the compression dictionaries, the queries being evaluated and the target CPU architecture. We investigate a variety of compression formats and propose two novel optimizations: tuple length quantization and a field length lookup table, for efficiently processing variable length fields and tuples. We present a detailed experimental study of the performance of generated scans against these compression formats, and use this to explore the trade off between compression quality and scan speed. We also introduce new strategies for removing instruction-level dependencies and increasing instruction-level parallelism, allowing for greater exploitation of multi-issue processors.

REFERENCES

• 1: D. Abadi, S. Madden, and M. Ferreira. Integrating compression and execution in column-oriented database systems. In SIGMOD, 2006.
• 2: G. Antoshenkov, D. Lomet, and J. Murray. Order preserving string compression. In ICDE, 1996.
• 3: P. Boncz, M. Zukowski, and N. Nes. MonetDB/X100: Hyper-pipelining query execution. In CIDR, 2005.
• 4: Z. Chen, J. Gehrke, and F. Korn. Query optimization in compressed database systems. In SIGMOD, 2001.
• 5: 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]
• 6: J. Goldstein, R. Ramakrishnan, and U. Shaft. Compressing relations and indexes. In ICDE, 1998.
• 7: G. Graefe and L. D. Shapiro. Data compression and database performance. In Proc. ACM/IEEE-CS Symp. on Applied Computing, 1991.
• 8: S. Harizopoulos, V. Liang, D. Abadi, and S. Madden. Performance tradeoffs in read-optimized databases. In VLDB, 2006.
• 9: D. Huffman. A method for the construction of minimum-redundancy codes. In Proceedings of the I.R.E., pages 1098--1102, 1952.
• 10: B. R. Iyer and D. Wilhite. Data compression support in databases. In VLDB, 1994.
• 11: T. Lehman and M. Carey. Query processing in main memory database management systems. In SIGMOD, 1986.
• 12: R. MacNicol and B. French. Sybase IQ Multiplex-Designed for analytics. In VLDB, 2004.
• 13: S. J. O'Connell , N. Winterbottom, Performing joins without decompression in a compressed database system, ACM SIGMOD Record, v.32 n.1, p.6-11, March 2003 [doi>10.1145/640990.640991]
• 14: MPöss and D. Potapov. Data compression in Oracle. In VLDB, 2003.
• 15: V. Raman and G. Swart. Entropy compression of relations and querying of compressed relations. In VLDB, 2006.
• 16: G. Ray, J. Haritsa, and S. Seshadri. Database compression: A performance enhancement tool. In COMAD, 1995.
• 17: M. Stonebraker et al. C-store: a column-oriented DBMS. In VLDB, 2005.
• 18: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 19: 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]
• 20: A. Zandi, B. Iyer, and G. Langdon. Sort order preserving data compression for extended alphabets. In Data Compression Conference, 1993.
• 21: M. Zukowski, S. Heman, N. Nes, and P. A. Boncz. Super-Scalar RAM-CPU Cache Compression. In ICDE, April 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Design, Experimentation, Performance

Keywords:
Huffman coding, bandwidth trade offs, compression, difference coding