Dictionary-based order-preserving string compression for main memory column stores

ABSTRACT

Column-oriented database systems [19, 23] perform better than traditional row-oriented database systems on analytical workloads such as those found in decision support and business intelligence applications. Moreover, recent work [1, 24] has shown that lightweight compression schemes significantly improve the query processing performance of these systems. One such a lightweight compression scheme is to use a dictionary in order to replace long (variable-length) values of a certain domain with shorter (fixedlength) integer codes. In order to further improve expensive query operations such as sorting and searching, column-stores often use order-preserving compression schemes.

In contrast to the existing work, in this paper we argue that orderpreserving dictionary compression does not only pay off for attributes with a small fixed domain size but also for long string attributes with a large domain size which might change over time. Consequently, we introduce new data structures that efficiently support an order-preserving dictionary compression for (variablelength) string attributes with a large domain size that is likely to change over time. The main idea is that we model a dictionary as a table that specifies a mapping from string-values to arbitrary integer codes (and vice versa) and we introduce a novel indexing approach that provides efficient access paths to such a dictionary while compressing the index data. Our experiments show that our data structures are as fast as (or in some cases even faster than) other state-of-the-art data structures for dictionaries while being less memory intensive.

REFERENCES

• 1: Daniel Abadi , Samuel Madden , Miguel Ferreira, Integrating compression and execution in column-oriented database systems, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142548]
• 2: 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
• 3: Nikolas Askitis , Ranjan Sinha, HAT-trie: a cache-conscious trie-based data structure for strings, Proceedings of the thirtieth Australasian conference on Computer science, p.97-105, January 30-February 02, 2007, Ballarat, Victoria, Australia
• 4: N. Askitis and J. Zobel. Cache-Conscious Collision Resolution in String Hash Tables. In SPIRE, pages 91--102, 2005.
• 5: Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977 [doi>10.1145/320521.320530]
• 6: Jon L. Bentley , Robert Sedgewick, Fast algorithms for sorting and searching strings, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.360-369, January 05-07, 1997, New Orleans, Louisiana, United States
• 7: Philip Bohannon , Peter Mcllroy , Rajeev Rastogi, Main-memory index structures with fixed-size partial keys, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.163-174, May 21-24, 2001, Santa Barbara, California, United States
• 8: Zhiyuan Chen , Johannes Gehrke , Flip Korn, Query optimization in compressed database systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.271-282, May 21-24, 2001, Santa Barbara, California, United States
• 9: H. Garcia-Molina , K. Salem, Main Memory Database Systems: An Overview, IEEE Transactions on Knowledge and Data Engineering, v.4 n.6, p.509-516, December 1992 [doi>10.1109/69.180602]
• 10: 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
• 11: Goetz Graefe , Per-Åke Larson, B-Tree Indexes and CPU Caches, Proceedings of the 17th International Conference on Data Engineering, p.349-358, April 02-06, 2001
• 12: Stavros Harizopoulos , Velen Liang , Daniel J. Abadi , Samuel Madden, Performance tradeoffs in read-optimized databases, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 13: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 14: David Lomet, The evolution of effective B-tree: page organization and techniques: a personal account, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603878]
• 15: Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968 [doi>10.1145/321479.321481]
• 16: Jun Rao , Kenneth A. Ross, Cache Conscious Indexing for Decision-Support in Main Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.78-89, September 07-10, 1999
• 17: Jun Rao , Kenneth A. Ross, Making B+- trees cache conscious in main memory, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.475-486, May 15-18, 2000, Dallas, Texas, United States
• 18: Ranjan Sinha , Justin Zobel , David Ring, Cache-efficient string sorting using copying, Journal of Experimental Algorithmics (JEA), 11, 2006 [doi>10.1145/1187436.1187439]
• 19: Mike Stonebraker , Daniel J. Abadi , Adam Batkin , Xuedong Chen , Mitch Cherniack , Miguel Ferreira , Edmond Lau , Amerson Lin , Sam Madden , Elizabeth O'Neil , Pat O'Neil , Alex Rasin , Nga Tran , Stan Zdonik, C-store: a column-oriented DBMS, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 20: Steven P. Vanderwiel , David J. Lilja, Data prefetch mechanisms, ACM Computing Surveys (CSUR), v.32 n.2, p.174-199, June 2000 [doi>10.1145/358923.358939]
• 21: 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
• 22: Jingren Zhou , Kenneth A. Ross, Buffering accesses to memory-resident index structures, Proceedings of the 29th international conference on Very large data bases, p.405-416, September 09-12, 2003, Berlin, Germany
• 23: M. Zukowski, P. A. Boncz, N. Nes, and S. Héman. MonetDB/X100 -- A DBMS In The CPU Cache. IEEE Data Eng. Bull., 28(2):17--22, 2005.
• 24: Marcin Zukowski , Sandor Heman , Niels Nes , Peter Boncz, Super-Scalar RAM-CPU Cache Compression, Proceedings of the 22nd International Conference on Data Engineering, p.59, April 03-07, 2006 [doi>10.1109/ICDE.2006.150]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data dictionary/directory

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

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Dictionaries; Indexing methods

General Terms:
Algorithms, Design, Performance

Keywords:
column store, string compression