Abstract
Data compression is widely used in contemporary column-oriented DBMSes to lower space usage and to speed up query processing. Pioneering systems have introduced compression to tackle the disk bandwidth bottleneck by trading CPU processing power for it. The main issue of this is a trade-off between the compression ratio and the decompression CPU cost. Existing results state that light-weight compression with small decompression costs outperforms heavy-weight compression schemes in column-stores. However, since the time these results were obtained, CPU, RAM, and disk performance have advanced considerably. Moreover, novel compression algorithms have emerged.
In this paper, we revisit the problem of compression in disk-based column-stores. More precisely, we study the I/O-RAM compression scheme which implies that there are two types of pages of different size: disk pages (compressed) and in-memory pages (uncompressed). In this scheme, the buffer manager is responsible for decompressing pages as soon as they arrive from disk. This scheme is rather popular as it is easy to implement: several modern column and row-stores use it.
We pose and address the following research questions: 1) Are heavy-weight compression schemes still inappropriate for disk-based column-stores?, 2) Are new light-weight compression algorithms better than the old ones?, 3) Is there a need for SIMD-employing decompression algorithms in case of a disk-based system? We study these questions experimentally using a columnar query engine and Star Schema Benchmark.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abadi, D., Boncz, P., Harizopoulos, S.: The Design and Implementation of Modern Column-Oriented Database Systems. Now Publishers Inc., Hanover (2013)
Abadi, D., Madden, S., Ferreira, M.: Integrating compression and execution in column-oriented database systems, SIGMOD 2006, pp. 671–682. ACM, New York (2006)
Alakuijala, J., et al.: Brotli: a general-purpose data compressor. ACM Trans. Inf. Syst. 37(1), (2018). https://doi.org/10.1145/3231935
Bains, S.: InnoDB transparent page compression (August 2015). https://mysqlserverteam.com/innodb-transparent-page-compression/
Binnig, C., Hildenbrand, S., Färber, F.: Dictionary-based order-preserving string compression for main memory column stores. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, SIGMOD 2009, pp. 283–296. Association for Computing Machinery, New York (2009). https://doi.org/10.1145/1559845.1559877
Chernishev, G.A., Galaktionov, V.A., Grigorev, V.D., Klyuchikov, E.S., Smirnov, K.K.: PosDB: an architecture overview. Program. Comput. Softw. 44(1), 62–74 (2018)
Damme, P., Habich, D., Hildebrandt, J., Lehner, W.: Insights into the comparative evaluation of lightweight data compression algorithms. In: Markl, V., Orlando, S., Mitschang, B., Andritsos, P., Sattler, K., Breß, S. (eds.) Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, 21–24 March 2017, pp. 562–565. OpenProceedings.org (2017). https://doi.org/10.5441/002/edbt.2017.70
Damme, P., Habich, D., Hildebrandt, J., Lehner, W.: Lightweight data compression algorithms: An experimental survey (experiments and analyses). In: Markl, V., Orlando, S., Mitschang, B., Andritsos, P., Sattler, K., Breß, S. (eds.) Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, 21–24 March 2017. pp. 72–83. OpenProceedings.org (2017). https://doi.org/10.5441/002/edbt.2017.08
Galaktionov, V., Klyuchikov, E., Chernishev, G.A.: Position caching in a column-store with late materialization: An initial study. In: Song, I., Hose, K., Romero, O. (eds.) Proceedings of the 22nd International Workshop on Design, Optimization, Languages and Analytical Processing of Big Data co-located with EDBT/ICDT 2020 Joint Conference, DOLAP@EDBT/ICDT 2020, Copenhagen, Denmark, March 30, 2020. CEUR Workshop Proceedings, vol. 2572, pp. 89–93. CEUR-WS.org (2020). http://ceur-ws.org/Vol-2572/short14.pdf
Ghita, B., Tomé, D.G., Boncz, P.A.: White-box compression: Learning and exploiting compact table representations. In: 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, 12–15 January 2020, Online Proceedings. www.cidrdb.org (2020). http://cidrdb.org/cidr2020/papers/p4-ghita-cidr20.pdf
Goldstein, J., Ramakrishnan, R., Shaft, U.: Compressing relations and indexes. In: Proceedings 14th International Conference on Data Engineering, pp. 370–379 (1998). https://doi.org/10.1109/ICDE.1998.655800
Graefe, G., Shapiro, L.: Data compression and database performance. In: 1991 Symposium on Applied Computing, pp. 22–27. IEEE Computer Society, Los Alamitos, CA, USA (April 1991). https://doi.org/10.1109/SOAC.1991.143840
Habich, D., et al.: MorphStore – in-memory query processing based on morphing compressed intermediates live. In: Proceedings of the 2019 International Conference on Management of Data, SIGMOD 2019, pp. 1917–1920. Association for Computing Machinery, New York (2019). https://doi.org/10.1145/3299869.3320234
Harizopoulos, S., Abadi, D., Boncz, P.: Column-Oriented Database Systems, VLDB 2009 Tutorial. (2009). nms.csail.mit.edu/ stavros/pubs/tutorial2009-column_stores.pdf
Hellerstein, J.M., Stonebraker, M., Hamilton, J.: Architecture of a database system. Found. Trends Databases 1(2), 141–259 (2007). https://doi.org/10.1561/1900000002
Iyer, B.R., Wilhite, D.: Data compression support in databases. In: Proceedings of the 20th International Conference on Very Large Data Bases, VLDB 1994, pp. 695–704. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1994)
Jiang, H., Liu, C., Jin, Q., Paparrizos, J., Elmore, A.J.: PIDS: attribute decomposition for improved compression and query performance in columnar storage. Proc. VLDB Endow 13(6), 925–938 (2020). https://doi.org/10.14778/3380750.3380761
Jianzhong L., Srivastava, J.: Efficient aggregation algorithms for compressed data warehouses. IEEE Trans. Knowl. Data Eng. 14(3), 515–529 (2002). https://doi.org/10.1109/TKDE.2002.1000340
Johnson, T.: Performance measurements of compressed bitmap indices. In: Proceedings of the 25th International Conference on Very Large Data Bases, VLDB 1999, pp. 278–289. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1999)
Lemire, D., Boytsov, L.: Decoding billions of integers per second through vectorization. Softw. Pract. Exper. 45(1), 1–29 (2015). https://doi.org/10.1002/spe.2203
Li, D.: Compressing longs in druid (December 2016). https://imply.io/post/compressing-longs
Lipcon, T., Alves, D., Burkert, D., Cryans, J.D., Dembo, A.: Kudu: Storage for fast analytics on fast data (2016). https://kudu.apache.org/kudu.pdf
Liu, H., Ji, Y., Xiao, J., Tan, H., Luo, Q., Ni, L.M.: TICC: Transparent inter-column compression for column-oriented database systems. In: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM 2017, pp. 2171–2174. Association for Computing Machinery, New York (2017). https://doi.org/10.1145/3132847.3133077
Mullins, C.M., Lim, L., Lang, C.A.: Query-aware compression of join results. In: Guerrini, G., Paton, N.W. (eds.) Joint 2013 EDBT/ICDT Conferences, EDBT 2013 Proceedings, Genoa, Italy, 18–22 March 2013, pp. 29–40. ACM (2013). https://doi.org/10.1145/2452376.2452381
O’Connell, S.J., Winterbottom, N.: Performing joins without decompression in a compressed database system. SIGMOD Rec. 32(1), 6–11 (2003). https://doi.org/10.1145/640990.640991
O’Neil, P., Chen, X.: Star Schema Benchmark (June 2009). http://www.cs.umb.edu/~poneil/StarSchemaB.PDF
Valduriez, P.: Join Indices. ACM Trans. Database Syst. 12(2), 218–246 (1987)
Wandelt, S., Sun, X., Leser, U.: Column-wise compression of open relational data. Inf. Sci. 457-458, 48–61 (2018). https://doi.org/10.1016/j.ins.2018.04.074
Wang, J., Lin, C., Papakonstantinou, Y., Swanson, S.: An experimental study of bitmap compression vs. inverted list compression. In: Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD 2017, pp. 993–1008. Association for Computing Machinery, New York (2017). https://doi.org/10.1145/3035918.3064007
Zukowski, M., Heman, S., Nes, N., Boncz, P.: Super-scalar RAM-CPU cache compression. In: 22nd International Conference on Data Engineering (ICDE 2006), p. 59 (2006). https://doi.org/10.1109/ICDE.2006.150
Acknowledgments
We would like to thank Anna Smirnova for her help with the preparation of the paper.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Slesarev, A., Klyuchikov, E., Smirnov, K., Chernishev, G. (2021). Revisiting Data Compression in Column-Stores. In: Attiogbé, C., Ben Yahia, S. (eds) Model and Data Engineering. MEDI 2021. Lecture Notes in Computer Science(), vol 12732. Springer, Cham. https://doi.org/10.1007/978-3-030-78428-7_22
Download citation
DOI: https://doi.org/10.1007/978-3-030-78428-7_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-78427-0
Online ISBN: 978-3-030-78428-7
eBook Packages: Computer ScienceComputer Science (R0)