abstract

Column Partition and Permutation for Run Length Encoding in Columnar Databases

Author:

Jia ShiAuthors Info & Claims

SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data

Pages 2873 - 2874

https://doi.org/10.1145/3318464.3384413

Published: 31 May 2020 Publication History

Get Access

Abstract

Effective compression is essential when databases are used in Big Data applications. For in-memory columnar databases, compression can help to load the columns faster and speed up query evaluation. In this paper, we consider compressing columns using the Run Length Encoding (RLE). This algorithm encodes each region with identical value using a single run. The question we study in this paper is 'how to rearrange table columns for better compression?' We observe that not every column of a table benefits from column compression in an ideal column arrangement. Because finding the optimal column arrangement is NP-hard, we propose an incremental heuristic that identifies the set of columns to be compressed and the order of rows that offer a better compression ratio. Our preliminary experiments confirm that our algorithm improves the compression rate by up to 25% on test data, compared with compressing all columns of a table.

References

[1]

Adam L. Buchsbaum, Glenn S. Fowler, and Raffaele Giancarlo. 2002. Improving table compression with combinatorial optimization. ACM SODA (2002), 213--222.

Google Scholar

[2]

Lemke Christian, Sattler Kai-Uwe, Faerber Franz, and Zeier Alexander. 2010. Speeding up queries in column stores: a case for compression. DaWaK (2010), 117--129.

Google Scholar

[3]

Jane Jovanovski, Nino Arsov, Evgenija Stevanoska, Maja Siljanoska Simons, and Goran Velinov. 2019. A meta-heuristic approach for RLE compression in a column store table. Soft Computing, Vol. 23, 12 (2019), 4255--4276.

Digital Library

Google Scholar

[4]

Daniel Lemire and Owen Kaser. 2011. Reordering columns for smaller indexes. Information Sciences, Vol. 181, 12 (2011), 2550--2570.

Digital Library

Google Scholar

[5]

Daniel Lemire, Owen Kaser, and Eduardo Gutarra. 2012. Reordering rows for better compression: Beyond the lexicographic order. ACM TODS, Vol. 37, 3 (2012), 20:1--20:29.

Digital Library

Google Scholar

Cited By

View all

Hansert PMichel S(2024)Partition, Don't Sort! Compression Boosters for Cloud Data Ingestion PipelinesProceedings of the VLDB Endowment10.14778/3681954.368201317:11(3456-3469)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682013
Liu CPavlenko AInterlandi MHaynes B(2023)A Deep Dive into Common Open Formats for Analytical DBMSsProceedings of the VLDB Endowment10.14778/3611479.361150716:11(3044-3056)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611507
Ferragina PManzini GGagie TKöppl DNavarro GStriani MTosoni F(2022)Improving matrix-vector multiplication via lossless grammar-compressed matricesProceedings of the VLDB Endowment10.14778/3547305.354732115:10(2175-2187)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.14778/3547305.3547321
Show More Cited By

Index Terms

Column Partition and Permutation for Run Length Encoding in Columnar Databases
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data layout
        Data compression

Recommendations

Good to the Last Bit: Data-Driven Encoding with CodecDB
SIGMOD '21: Proceedings of the 2021 International Conference on Management of Data

Columnar databases rely on specialized encoding schemes to reduce storage requirements. These encodings also enable efficient in-situ data processing. Nevertheless, many existing columnar databases are encoding-oblivious. When storing the data, these ...
Wavelet transform and bit-plane encoding
ICIP '95: Proceedings of the 1995 International Conference on Image Processing (Vol. 1)-Volume 1 - Volume 1

In this work a new approach for wavelet transform (WT) based image compression is presented. Employing a simple region representation coding scheme previously used with bi-level facsimile pictures, the wavelet transform coefficients are first quantized ...
Run-Length Base-Delta Encoding for High-Speed Compression
ICPP Workshops '18: Workshop Proceedings of the 47th International Conference on Parallel Processing

In modern supercomputers, nodes are connected by networking hardware capable of up to 40 Gb/s. Data compression could allow for even higher effective bandwidth. However, data compression for such systems requires a unique tradeoff between the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data

June 2020

2925 pages

ISBN:9781450367356

DOI:10.1145/3318464

General Chairs:
David Maier
Portland State University, USA
,
Rachel Pottinger
University of British Columbia, Canada
,
Program Chairs:
AnHai Doan
University of Wisconsin, USA
,
Wang-Chiew Tan
Megagon Labs, USA
,
Publications Chairs:
Abdussalam Alawini
University of Illinois at Urbana-Champaign, USA
,
Hung Q. Ngo
RelationalAI, USA

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2020

Check for updates

Author Tags

Qualifiers

Abstract

Conference

SIGMOD/PODS '20

Sponsor:

SIGMOD

SIGMOD/PODS '20: International Conference on Management of Data

June 14 - 19, 2020

OR, Portland, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
390
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)3

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hansert PMichel S(2024)Partition, Don't Sort! Compression Boosters for Cloud Data Ingestion PipelinesProceedings of the VLDB Endowment10.14778/3681954.368201317:11(3456-3469)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682013
Liu CPavlenko AInterlandi MHaynes B(2023)A Deep Dive into Common Open Formats for Analytical DBMSsProceedings of the VLDB Endowment10.14778/3611479.361150716:11(3044-3056)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611507
Ferragina PManzini GGagie TKöppl DNavarro GStriani MTosoni F(2022)Improving matrix-vector multiplication via lossless grammar-compressed matricesProceedings of the VLDB Endowment10.14778/3547305.354732115:10(2175-2187)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.14778/3547305.3547321
Hansert PMichel SGroppe SGruenwald LHsu C(2022)Ameliorating data compression and query performance through cracked ParquetProceedings of the International Workshop on Big Data in Emergent Distributed Environments10.1145/3530050.3532923(1-7)Online publication date: 12-Jun-2022
https://dl.acm.org/doi/10.1145/3530050.3532923
Han SLiu XLi J(2022)Chunk-oriented dimension ordering for efficient range query processing on sparse multidimensional dataWorld Wide Web10.1007/s11280-022-01098-z26:4(1395-1433)Online publication date: 9-Sep-2022
https://doi.org/10.1007/s11280-022-01098-z

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Good to the Last Bit: Data-Driven Encoding with CodecDB

Wavelet transform and bit-plane encoding

Run-Length Base-Delta Encoding for High-Speed Compression