# Corra: Correlation-Aware Column Compression

Hanwen Liu<EMAIL_ADDRESS>TUM ,  Mihail Stoian<EMAIL_ADDRESS>UTN ,
Alexander van Renen<EMAIL_ADDRESS>UTN and  Andreas Kipf
<EMAIL_ADDRESS>UTN

###### Abstract.

Column encoding schemes have witnessed a spark of interest lately. This is not
surprising – as data volume increases, being able to keep one’s dataset in
main memory for fast processing is a coveted desideratum. However, it also
seems that single-column encoding schemes have reached a plateau in terms of
the compression size they can achieve.

We argue that this is because they do not exploit correlations in the data.
Consider for instance the column pair (city, zip-code) of the DMV dataset: a
city has only a few dozen unique zip codes. Such information, if properly
exploited, can significantly reduce the space consumption of the latter
column.

In this work, we depart from the established, well-trodden path of compressing
data using only single-column encoding schemes and introduce _correlation-
aware_ encoding schemes. We demonstrate their advantages compared to single-
column encoding schemes on the well-known TPC-H’s lineitem, LDBC’s message,
DMV, and Taxi. For example, we obtain a saving rate of 58.3% for lineitem’s
shipdate, while the dropoff timestamps in Taxi witness a saving rate of 30.6%.

column correlation, column encoding schemes, data compression

††ccs: Information systems Data compression

##  1\. Introduction

Column encoding schemes lie at the heart of the storage layer of any database
system. There are several single-column encoding schemes which are by now
already ad-hoc: Frame-of-Reference (FOR), Frequency, Dictionary, Delta (and
its sibling, DoubleDelta), Run-Length Encoding (RLE), FSST (Boncz et al.,
2020), among many others (see, e.g., Lemire and Boytsov (Lemire and Boytsov,
2013)).

However, data in the wild is highly correlated and the current encoding
schemes do not exploit this fact. Only recently did Lyu et al. (Lyu et al.,
2023) make the case for correlation-aware _bitmaps_ , showing that one can
indeed lower the space requirement while maintaining a decent runtime overhead
during decompression.

In this work, we propose Corra, a unified collection of novel correlation-
aware column encoding schemes that reduce the compressed size beyond what it
is possible with current single-column encoding schemes, while maintaining a
negligible query runtime overhead.

shipdate | commitdate
---|---
1998-12-01 | 1998-09-04
1992-01-02 | 1992-03-10
2024-03-08 | 2024-03-16
(a) Without diff-encoding

shipdate | commitdate
---|---
1998-12-01 | -88
1992-01-02 | +68
2024-03-08 | +8
(b) With diff-encoding

Figure 1. Peer encoding: Exploiting the (bounded) difference between date
columns. We demonstrate this on the column pair
$(\texttt{shipdate},\texttt{commitdate})$ of TPC-H’s lineitem table (with a
custom row at the end). The goal is to reduce the bit-width for the diff-
encoded column, commitdate; the reference column, shipdate, remains unchanged.

Related Work. There is a line of research focusing on single-column encoding
schemes, with a recent spark of attention with works such as BtrBlocks
(Kuschewski et al., 2023) and FastLanes (Afroozeh and Boncz, 2023). With
BtrBlocks, Kuschewski et al. (Kuschewski et al., 2023) argue that open formats
such as Apache’s Parquet tend to be rather inefficient in terms of
decompression time, resulting in scans begin CPU-bound, thus increasing query
time. To address this, they employ several encoding schemes for different data
types, which can also be applied recursively. FastLanes (Afroozeh and Boncz,
2023) enables efficient vectorized execution by cleverly reordering tuples to
maximize the effect of SIMD operations. BitWeaving (Li and Patel, 2013) takes
a different approach by interleaving the bits of the column values. Orthogonal
to these, FSST (Boncz et al., 2020) and Fast & Strong (Lasch et al., 2019)
specialize in improved string compression, while other works focus on
floating-point compression (Afroozeh et al., 2023; Liakos et al., 2022); in
particular, these are orthogonal to our work since we do not constrain the
encoding scheme of the reference column (see a definition in the upcoming
section).

Trummer investigates whether LLMs can infer correlations from the schema
itself (Trummer, 2023). Correlations have been considered for indexes to
improve query processing, namely Kimura et al. (Kimura et al., 2009) introduce
the Correlation Map as a secondary index, concept later generalized in Cortex
(Nathan et al., 2020). Instead, we exploit correlations for data compression.
We thus depart from the established, well-trodden path of compressing data
using only single-column encoding schemes and introduce _correlation-aware_
encoding schemes that push the boundaries of what is possible with single-
column coding schemes in terms of compression size.

##  2\. Compressing Correlated Columns

The key idea behind correlation-aware column compression is to express the
values of one column, which we call the _diff-encoded_ column, in terms of the
other, which we call the _reference_ column. The intuition is that this
reduces the range of values the diff-encoded values can take, so the bit-width
required to compress the column decreases accordingly. In the following, we
propose two correlation-aware encoding schemes that follow this paradigm, and
present real-world datasets which these schemes are applicable to.

###  2.1. Peer Encoding

Let us take a closer look at TPC-H’s lineitem table: It has three date-valued
columns, shipdate, commitdate, and receiptdate. In particular, it is a well-
known fact that the differences between these dates are bounded (at most
several months apart from each other). A such correlation can be indeed
exploited: Namely, instead of storing the column commitdate as is, one can
instead store the _difference_ to shipdate, hence reducing the bit-width
required to store it; similarly for receiptdate. To see why this is the case,
consider Fig. 1, where we illustrate this case: We fix shipdate and commitdate
as the _reference_ and _diff-encoded_ column, respectively. Hence, we compute
the difference of commitdate to shipdate and only store that value, thus
reducing the necessary bit-width to store it.

Optimal Diff-Encoding. The careful reader may be interested in how we can
actually configure which columns to diff-encode and which to compress using
standard single-column compression. We can use a strategy similar to the one
used in CorBit (Lyu et al., 2023). To this end, consider Fig. 2, which
visualizes our method:111To avoid clutter, we round up the exact numbers. The
vertices represent the column, so for each directed edge $a\rightarrow b$ we
measure what the compressed size would be if we diff-encoded $a$ w.r.t. $b$.
Using a cost-based greedy strategy, we can then decide which columns will be
reference columns and which will not. In our case, l_shipdate will be the
reference column for both l_commitdate and l_receiptdate, saving 82.5 MB over
just bit-packing the individual columns (TPC-H, sf 10); the exact numbers can
be found in Tab. 1. Naturally, considering cases where a diff-encoded column
becomes itself a reference column is an interesting future work (we did not
focus on this type of diff-encoding configuration).

Note that our scheme is beneficial if there exists a _bounded_ difference in
the diff-encoded column. In case the difference is not always bounded, we can
always store outliers separately as done in HERMIT (Wu et al., 2019) for
secondary indexing; however, in the datasets we analyzed, this was not
necessary.

Figure 2. Detecting the optimal diff-encoding configuration in TPC-H (sf 10).
The weight of an $a\rightarrow b$ edge is the size of column $a$ when diff-
encoded w.r.t. reference column $b$.

city | zip-code
---|---
Cortland | 13045
Naples | 34102
Naples | 34112
Naples | 34102
NYC | 10016
NYC | 10001
(a) Without diff-encoding

city | zip-code
---|---
0 | 0
1 | 0
1 | 1
1 | 0
2 | 1
2 | 0
(b) With diff-encoding

Meta-data for diff-encoding:city_dict: {0 : ”Cortland”, 1 : ”Naples”, 2 :
”NYC”}zip_codes: [13045, 34102, 34112, 10001, 10016]offsets: [0, 1, 3]

Figure 3. Subaltern encoding: Exploiting the correlation of the column-pair
$(\texttt{city},\texttt{zip-code})$ in the DMV dataset. The metadata is the
list of zip_codes for each individual city along with the offsets where its
zip_code list starts from. The city-dictionary is used to encode the city
column.

###  2.2. Subaltern Encoding

The next correlation-aware encoding scheme we introduce is _subaltern
encoding_ : It targets column pairs that are endowed with a hierarchical-like
structure.222Another appropriate name would have been hierarchical-
compression, but to avoid name conflicts with other works, e.g., (Teng and
Neuhoff, 1996; Devarajan et al., 2020), we chose this specific name. To this
end, consider the column pair (city, zip-code) of the DMV dataset: While the
column zip-code could have many distinct values, a specific city only has a
few. Intuitively, this reduces the bit-width necessary to store these zip-
codes.

Dataset | Column | Size w/o diff-enc | Encoding | Ref. column | Size w/ diff-enc | Saving rate
---|---|---|---|---|---|---
lineitem (SF 10) | l_commitdate | 89.99 MB | peer | l_shipdate | 59.99 MB | 33.3%
lineitem (SF 10) | l_receiptdate | 89.99 MB | peer | l_shipdate | 37.49 MB | 58.3%
Taxi | tpep_dropff_datetime | 136.64 MB | peer | tpep_pickup_datetime | 94.7 MB | 30.6%
DMV | city | 21.45 MB | subaltern | state | 21.05 MB | 1.8%
DMV | zip-code | 25.88 MB | subaltern | city | 11.96 MB | 53.7%
message (SF 30) | locationip | 195.14 MB | subaltern | locationcountryid | 161.76 MB | 17.1%
Table 1. Space saving over single-column encoding schemes Figure 4. Query
latency for selectivities in $\\{0.001,0.002,\ldots,0.9,1.0\\}$ with
materialization of the query output. Peer encoding is run on TPC-H’s lineitem
(scale-factor 10) for l_shipdate (reference) and l_receiptdate (diff-encoded).
Subaltern encoding is run on LDBC’s message (scale factor 30) for
locationcountryid (reference) and locationip (diff-encoded).

Example. In the following, consider Fig. 3 where we illustrate our compression
scheme for the column pair $(\texttt{city},\texttt{zip-code})$ of the DMV
dataset (dmv, [n. d.]). The key insight is that a specific pair can occur many
times in the dataset – we exemplify this in Fig. 3 using two records (Naples,
34102). Our compression scheme works as follows: We collect the different zip-
codes of each city in a metadata array “zip_codes”. This array is indexed by
each distinct city with an auxiliary “offsets” array, i.e., the zip-codes of
Cortland start at position 0, those of Naples at position 1, while those of
NYC start at position 3 (this is highlighted by the three different colors).
Note that the zip-codes for each city are sorted for sake of simplicity. In
particular, this is not required – in the compression phase, we maintain a
hash table of the column pairs and build the two metadata arrays on the fly.

Algorithm 1 SubalternAccess(tid)

1:$\texttt{ref}\leftarrow$ Fetch(city)[tid]

2:$\texttt{diff}\leftarrow$ Fetch(zip-code)[tid]

3:return zip_codes[offset[ref] + diff]

Decompression. Naturally, as for the other compression scheme we discussed, to
access a certain value within the zip-code column, we need to also access the
corresponding city, as shown in Alg. 1: To decompress the zip-code value of
tuple “tid”, we fetch both the city (which has been dict-encoded in advance)
and access the array zip-codes at the offset _shifted_ by the diff-encoded
value of the zip-code column.

##  3\. Evaluation

Datasets. In our evaluation, we use four datasets (two synthetic): TPC-H’s
lineitem of scale factor 10 (59,986,052 rows) ((2022), TPC), LDBC’s message of
scale factor 30 (76,388,857 rows) (Erling et al., 2015; Szárnyas et al.,
2022),333Download link: https://db.in.tum.de/~birler/data/ldbcbi-sf30.zip DMV
(dmv, [n. d.]) (12,176,621 rows), and the full Taxi dataset over one year
(39,656,099 rows) (tax, [n. d.]).444To our purpose, we clean the dataset
beforehand, i.e., remove rows where the drop-off happens _before_ pickup.

Experimental Setup. For ease of reproducibility, all experiments were
performed on EC2. We used a c5d.4xlarge instance which has an Intel Xeon
Platinum 8275CL processor with 16 vCPUs and 32 GB of memory.

We split all datasets into data blocks of 1M tuples. Each data block is
completely self-contained: all information required to decompress it is
contained within the block itself.

When measuring query latency, we generate 10 uniform random selection vectors
for each individual selectivity (as done, e.g., in Harald et al. (Lang et al.,
2020)). In the experiment, we decompress and _materialize_ the values at the
specified positions, which we call the query output.

Figure 5. Peer encoding: Zooming in for different selectivities, including the
“uncompressed” case Figure 6. Subaltern encoding: Zooming in for different
selectivities, including the “uncompressed” case

Baseline. As the single-column encoding scheme of choice, we use FOR- or Dict-
encoding schemes, followed by a bit-packing. We chose these because they allow
for a fast random access into the compressed column; both RLE and Delta
require checkpoints. To store column strings, we use Dict encoding and pack
the distinct strings into a flattened array.

Compression Size. In Table 1, we outline several columns within the four
datasets for which our proposed correlation-aware column encoding schemes
improve over the best configuration of single-column encoding schemes. In the
case of subaltern encoding, the compression size also includes the size of the
meta-data previously shown in Fig. 3.

The best saving rate, 58.3%, is achieved for TPC-H’s lineitem table, when
diff-encoding l_receiptdate w.r.t. l_shipdate. Moreover, diff-encoding zip-
code w.r.t. city also seems to pay off, resulting in a saving rate of 53.7%.
Seemingly, subaltern encoding does not seem to bring a significant improvement
for the column-pair $(\texttt{state},\texttt{city})$, where only a saving rate
2.8% could be achieved. LDBC’s message has also a column-pair that can benefit
from subaltern encoding, namely we diff-encoded locationip w.r.t.
locationcountryid and obtained a saving rate of 17.1%.

Query Latency. Diff-encoding naturally incurs an overhead when the diff-
encoded column has to be queried. Namely, the reference column has to be read
as well. In Fig. 4, we show the query latency for different selectivities in
the set $\\{0.001,0.002,\ldots,0.9,1.0\\}$ when querying (i) the diff-encoded
column (ii) both columns.

_Peer Encoding._ We query over the column pair (l_shipdate, l_commitdate) – as
before, l_shipdate is the reference column, while l_commitdate is the diff-
encoded column. We show the slow-down / speed-up compared to single-column
encoding schemes. Querying the diff-encoded column results in a maximum slow-
down of $1.66x$, while querying _both_ columns gives us an advantage since we
have to access the reference column anyway.

_Subaltern-Encoding._ In this case, we diff-encode locationip w.r.t.
locationcountryid. This is a natural case for subaltern encoding, as the
number of distinct locationcountryid’s is low and the locationip column itself
has a high duplication rate. For the same reason, the best single-column
encoding for locationip is Dict (this is our baseline). When we query the
diff-encoded column, we observe a constant slow-down in the range of
1.38-1.56x, which is dampened when both columns are queried.

Zoom-In. In Fig. 5, we provide a zoom-in for the query latency in the case of
peer encoding, namely, we plot the query latency for four different
selectivities $\\{0.005,0.01,0.05,0.1\\}$. Additionally, we also consider the
“uncompressed” case in which the query is directly executed over the
uncompressed column(s). The overhead of our approach can be seen when
considering the query latencies for the diff-encoded column. However, this
overhead is mitigated when querying both columns, as in this case, we need to
read both columns anyway.

Similarly for subaltern encoding, in Fig. 6 we zoom in the latency plot for
the same four selectivities $\\{0.005,0.01,0.05,0.1\\}$. The query suffers a
small overhead for that we need the (un-prefetchable) lookup into the
“locationips”-array (compare to the “zip_codes”-array in Fig. 3). In this
case, this incurred overhead is not completely mitigated when querying both
columns, as it was the case for peer encoding (in peer encoding, there is no
additional meta-data).

##  4\. Conclusion

With Corra, we have introduced the first correlation-aware column encoding
schemes, namely _peer_ and _subaltern_ , emulating to natural column
correlations that can be found in established datasets. Consequently, we have
shown that Corra achieves significant reductions in the compressed size of
several columns of TPC-H’s lineitem, LDBC’s message, DMV, and Taxi.
Additionally, we provided a strategy to find an optimal diff-encoding
configuration, i.e., which columns to diff-encode and which to compress via
standard single-column encoding schemes. In future work, we envision Corra to
support more fine-grained column-aware correlation types, in particular even
on _tuples_ of correlated columns instead of only pairs, as it can be directly
done for our proposed peer encoding scheme.

## References

  * (1)
  * tax ([n. d.]) [n. d.].  N. Y. C. Taxi, L. C. (TLC), Yellow Taxi trip records.  https://www.nyc.gov/site/tlc/about/tlc-trip-record-data.page
  * dmv ([n. d.]) [n. d.].  State of New York. 2020. Vehicle, snowmobile, and boat registrations.  https://catalog.data.gov/dataset/vehicle-snowmobile-and-boat-registrations
  * Afroozeh and Boncz (2023) Azim Afroozeh and Peter Boncz. 2023.  The FastLanes Compression Layout: Decoding ¿ 100 Billion Integers per Second with Scalar Code.  _Proc. VLDB Endow._ 16, 9 (may 2023), 2132–2144.  https://doi.org/10.14778/3598581.3598587
  * Afroozeh et al. (2023) Azim Afroozeh, Leonardo X. Kuffo, and Peter Boncz. 2023.  ALP: Adaptive Lossless floating-Point Compression.  _Proc. ACM Manag. Data_ 1, 4, Article 230 (dec 2023), 26 pages.  https://doi.org/10.1145/3626717
  * Boncz et al. (2020) Peter Boncz, Thomas Neumann, and Viktor Leis. 2020.  FSST: fast random access string compression.  _Proc. VLDB Endow._ 13, 12 (jul 2020), 2649–2661.  https://doi.org/10.14778/3407790.3407851
  * Devarajan et al. (2020) Hariharan Devarajan, Anthony Kougkas, Luke Logan, and Xian-He Sun. 2020.  HCompress: Hierarchical Data Compression for Multi-Tiered Storage Environments. In _2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_. 557–566.  https://doi.org/10.1109/IPDPS47924.2020.00064
  * Erling et al. (2015) Orri Erling, Alex Averbuch, Josep Larriba-Pey, Hassan Chafi, Andrey Gubichev, Arnau Prat, Minh-Duc Pham, and Peter Boncz. 2015.  The LDBC Social Network Benchmark: Interactive Workload. In _Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data_ (Melbourne, Victoria, Australia) _(SIGMOD ’15)_. Association for Computing Machinery, New York, NY, USA, 619–630.  https://doi.org/10.1145/2723372.2742786
  * Kimura et al. (2009) Hideaki Kimura, George Huo, Alexander Rasin, Samuel Madden, and Stanley B. Zdonik. 2009.  Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies.  _Proc. VLDB Endow._ 2, 1 (2009), 1222–1233.  https://doi.org/10.14778/1687627.1687765
  * Kuschewski et al. (2023) Maximilian Kuschewski, David Sauerwein, Adnan Alhomssi, and Viktor Leis. 2023.  BtrBlocks: Efficient Columnar Compression for Data Lakes.  _Proc. ACM Manag. Data_ 1, 2, Article 118 (jun 2023), 26 pages.  https://doi.org/10.1145/3589263
  * Lang et al. (2020) Harald Lang, Alexander Beischl, Viktor Leis, Peter Boncz, Thomas Neumann, and Alfons Kemper. 2020.  Tree-Encoded Bitmaps. In _Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data_ (Portland, OR, USA) _(SIGMOD ’20)_. Association for Computing Machinery, New York, NY, USA, 937–967.  https://doi.org/10.1145/3318464.3380588
  * Lasch et al. (2019) Robert Lasch, Ismail Oukid, Roman Dementiev, Norman May, Suleyman S. Demirsoy, and Kai-Uwe Sattler. 2019.  Fast & Strong: The Case of Compressed String Dictionaries on Modern CPUs. In _Proceedings of the 15th International Workshop on Data Management on New Hardware_ (Amsterdam, Netherlands) _(DaMoN’19)_. Association for Computing Machinery, New York, NY, USA, Article 4, 10 pages.  https://doi.org/10.1145/3329785.3329924
  * Lemire and Boytsov (2013) D. Lemire and L. Boytsov. 2013.  Decoding billions of integers per second through vectorization.  _Software: Practice and Experience_ 45, 1 (May 2013), 1–29.  https://doi.org/10.1002/spe.2203
  * Li and Patel (2013) Yinan Li and Jignesh M. Patel. 2013.  BitWeaving: fast scans for main memory data processing. In _Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, New York, NY, USA, June 22-27, 2013_ , Kenneth A. Ross, Divesh Srivastava, and Dimitris Papadias (Eds.). ACM, 289–300.  https://doi.org/10.1145/2463676.2465322
  * Liakos et al. (2022) Panagiotis Liakos, Katia Papakonstantinopoulou, and Yannis Kotidis. 2022.  Chimp: Efficient Lossless Floating Point Compression for Time Series Databases.  _Proc. VLDB Endow._ 15, 11 (2022), 3058–3070.  https://doi.org/10.14778/3551793.3551852
  * Lyu et al. (2023) Xi Lyu, Andreas Kipf, Pascal Pfeil, Dominik Horn, Jana Giceva, and Tim Kraska. 2023.  CorBit: Leveraging Correlations for Compressing Bitmap Indexes. In _Joint Proceedings of Workshops at the 49th International Conference on Very Large Data Bases (VLDB 2023), Vancouver, Canada, August 28 - September 1, 2023_ _(CEUR Workshop Proceedings, Vol. 3462)_ , Rajesh Bordawekar, Cinzia Cappiello, Vasilis Efthymiou, Lisa Ehrlinger, Vijay Gadepally, Sainyam Galhotra, Sandra Geisler, Sven Groppe, Le Gruenwald, Alon Y. Halevy, Hazar Harmouch, Oktie Hassanzadeh, Ihab F. Ilyas, Ernesto Jiménez-Ruiz, Sanjay Krishnan, Tirthankar Lahiri, Guoliang Li, Jiaheng Lu, Wolfgang Mauerer, Umar Farooq Minhas, Felix Naumann, M. Tamer Özsu, El Kindi Rezig, Kavitha Srinivas, Michael Stonebraker, Satyanarayana R. Valluri, Maria-Esther Vidal, Haixun Wang, Jiannan Wang, Yingjun Wu, Xun Xue, Mohamed Zaït, and Kai Zeng (Eds.). CEUR-WS.org.  https://ceur-ws.org/Vol-3462/AIDB4.pdf
  * Nathan et al. (2020) Vikram Nathan, Jialin Ding, Tim Kraska, and Mohammad Alizadeh. 2020.  Cortex: Harnessing Correlations to Boost Query Performance.  arXiv:2012.06683 [cs.DB]
  * Szárnyas et al. (2022) Gábor Szárnyas, Jack Waudby, Benjamin A. Steer, Dávid Szakállas, Altan Birler, Mingxi Wu, Yuchen Zhang, and Peter Boncz. 2022.  The LDBC Social Network Benchmark: Business Intelligence Workload.  _Proc. VLDB Endow._ 16, 4 (dec 2022), 877–890.  https://doi.org/10.14778/3574245.3574270
  * Teng and Neuhoff (1996) Chia-Yuan Teng and David L. Neuhoff. 1996.  _Hierarchical data compression_.  Ph. D. Dissertation. USA.  AAI9712100.
  * (20) Transaction Processing Performance Council (TPC). 2022.  TPC BENCHMARK™ H Standard Specification Revision 3.0.1.  https://www.tpc.org/TPC_Documents_Current_Versions/pdf/TPC-H_v3.0.1.pdf.  [Accessed 28-11-2023].
  * Trummer (2023) Immanuel Trummer. 2023.  Can Large Language Models Predict Data Correlations from Column Names?  _Proc. VLDB Endow._ 16, 13 (sep 2023), 4310–4323.  https://doi.org/10.14778/3625054.3625066
  * Wu et al. (2019) Yingjun Wu, Jia Yu, Yuanyuan Tian, Richard Sidle, and Ronald Barber. 2019.  HERMIT in action: succinct secondary indexing mechanism via correlation exploration.  _Proc. VLDB Endow._ 12, 12 (aug 2019), 1882–1885.  https://doi.org/10.14778/3352063.3352090