Performing joins without decompression in a compressed database system

ABSTRACT

There has been much work on compressing database indexes, but less on compressing the data itself. We examine the performance gains to be made by compression outside the index. A novel compression algorithm is reported, which enables the processing of queries without decompressing data needed to perform join operations in a database built on a triple store. The results of modelling the performance of the database with and without compression are given and compared with other recent work in this area. It is found that for some applications, gains in performance of over 50% are achievable, and in OLTP-like situations, there are also gains to be made.

REFERENCES

• 1: Zhiyuan Chen , Johannes Gehrke , Flip Korn, Query optimization in compressed database systems, ACM SIGMOD Record, v.30 n.2, p.271-282, June 2001
• 2: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 3: {Huff52} D Huffman, "A Method for the Construction of Minimum Redundancy Codes", Proc IRE, 40(9), pages 1098--1101, Sept 1952
• 4: Kosmas Karadimitriou , John M. Tyler, Min-max compression methods for medical image databases, ACM SIGMOD Record, v.26 n.1, p.47-52, March 1997 [doi>10.1145/248603.248613]
• 5: Alistair Moffat , Justin Zobel , Neil Sharman, Text Compression for Dynamic Document Databases, IEEE Transactions on Knowledge and Data Engineering, v.9 n.2, p.302-313, March 1997 [doi>10.1109/69.591454]
• 6: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill Higher Education, 2000
• 7: {Sen01} "Sentences DB", based on the Associative Model of Data, from Lazy Software, www.lazysoft.com
• 8: {Shar78} G C H Sharman and N Winterbottom, "The Data Dictionary Facilities of NDB", Proc 4th Int. Conf on Very Large Databases (VLDB), pp 186--197, IEEE 1978
• 9: {Shar88} G C H Sharman and N Winterbottom, "The Universal Triple Machine: a Reduced Instruction Set Repository Manager", Proceedings of BNCOD 6, pp 189--214, 1988
• 10: {TriStarp} TriStarp Web Site: http://www.dcs.bbk.ac.uk/~tristarp
• 11: 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]
• 12: {Ziv77} J Ziv, A Lempel, "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, 22(1), pages 337--343, 1977