Traditional columnar storage formats and database systems owe much of their efficiency to vertical compression. By organizing data column by column rather than row by row, systems can compress sequences of identical data types using lightweight techniques like Run-Length Encoding (RLE), dictionary encoding, or bit-packing.
However, this approach relies on a massive assumption: that each column is an independent entity. As Minos N. Garofalakis observed in early data warehousing research, treating data as isolated byte strings fails to exploit the structural relationships inherent in real-world datasets. When we compress columns independently, we hit a "compression plateau" because we ignore the fact that attributes within the same record are frequently highly correlated.
The Intuition: Conditional Entropy
Why does looking across columns unlock better compression? The answer lies in information theory and the concept of conditional entropy.
Consider a database containing real-world information like addresses. A column storing City names will have a certain amount of entropy (uncertainty). A column storing Zip Code values will also have high entropy. If you compress them in isolation, you pay the storage cost for both high-entropy streams.
However, if you know the City is "San Francisco," the uncertainty surrounding the Zip Code plummets. The conditional entropy of the zip code given the city is drastically lower than its standalone marginal entropy. By modeling these statistical dependencies, systems can achieve near-entropy compression rates. For instance, Aditya Parameswaran et al. demonstrated that learning these relationships via Bayesian Networks allows systems to predict values in dependent columns, reducing storage requirements by over 50% compared to standard syntactic tools like gzip.
Traditional Columnar (Vertical Only):
[City 1, City 2, City 3] -> Compressed Independently
[Zip 1, Zip 2, Zip 3] -> Compressed Independently
Correlation-Aware (Horizontal + Vertical):
[City 1, City 2, City 3] -> Compressed Base Column
| | |
v v v
[ Predictive Model ] -> Stores only the "Residuals" or "Diffs"
Mechanisms of Horizontal Encoding
To exploit these inter-column dependencies without destroying query performance, modern research focuses on "horizontal encoding"—compressing a target column relative to one or more reference columns. This is achieved through three primary mechanisms:
1. Exact Functional Dependencies
In many denormalized datasets, the relationship between columns is strictly mathematical or logical. For example, a table might contain columns for Regular_Pay, Overtime_Pay, and Total_Pay. Chang Liu demonstrated that functional dependency mining can systematically identify these internal redundancies in large-scale repositories.
Taking this to its logical conclusion, Mihail Stoian and Jan Kobiolka introduced an automated scanning approach that detects when a column can be perfectly calculated from others. Once a mathematical relationship is found, the database can drop the redundant column entirely from the physical storage and seamlessly reconstruct its values on the fly during query execution.
2. Regression and Residuals ("Soft" Dependencies)
When relationships are strong but not perfectly deterministic—known as "soft functional dependencies"—systems cannot simply drop the column. Instead, they store a predictive model and its residuals (the errors or differences between the prediction and reality).
- Linear and K-Regression: Mihail Stoian et al. utilize sparse $K$-regression to "virtualize" columns. By predicting values across columns and storing only the tiny residual errors, the data becomes highly sparse and uniform, making it incredibly easy for secondary lightweight compressors to shrink. Similarly, in multi-dimensional indexing, Jialin Ding et al. use linear regression to map correlated dimensions, effectively reducing the dimensionality of the search space.
- Temporal and Value Offsets: In many datasets, columns track related events, such as
Order_DateandShipping_Date. Rather than storing two massive timestamp columns, Mihail Stoian et al. show that encoding the second column as a relative difference (an offset) from the first yields massive storage savings because the offsets are small, repetitive integers.
3. Bit-Level XORing
For bitmap indexes, correlations manifest as matching bit patterns across separate column indexes. Andreas Kipf et al. designed a technique that compresses a target bitmap by storing its XOR difference against a highly correlated reference bitmap. Because the columns represent logically related information, the XOR operation cancels out most of the bits, producing a highly sparse bitstream that requires significantly less space than compressing each bitmap independently.
Why It Works: The Decompression Myth
The classic argument against cross-column compression is the decompression penalty. If Column B depends on Column A, then a query requesting only Column B must force the system to fetch and decode Column A as well, introducing unwanted I/O and CPU overhead.
In practice, this penalty is largely an illusion due to how data is queried. As Mihail Stoian et al. point out, logically correlated attributes are almost always accessed together within the same query payload (e.g., filtering by city while selecting the zip code, or comparing shipping dates against order dates). Because the reference column is already loaded into memory for its own sake, the marginal computational cost of using it to decode the dependent column is negligible.
Furthermore, leveraging these correlations can actively accelerate queries. Hideaki Kimura et al. demonstrated this with Correlation Maps, which map values of an unindexed column to a column that already possesses a clustered index. This allows queries on the unclustered attribute to piggyback on the existing physical ordering of the data, bypassing the need for expensive secondary indexes or full table scans. In a similar vein, Manas Joglekar et al. showed that even weak correlations can be used to bypass expensive User-Defined Function (UDF) evaluations by predicting outcomes based on existing attributes.
Application Beyond Relational Tables
The principle of exploiting cross-attribute dependencies is not confined to SQL tables; it is a fundamental property of structured data optimization across domains:
- Machine Learning Matrices: Frederick R. Reiss et al. applied this concept to large-scale machine learning via "co-coding," where correlated columns within a matrix are grouped and compressed together as a single unit, allowing linear algebra operations to execute directly on the compressed data.
- Genomics: Kedar Tatwawadi et al. designed genomic variant compression pipelines that explicitly map conditional dependencies between different data columns, optimizing the encoding of secondary attributes based on primary ones.
- Hardware Architecture: At the hardware level, Hoyong Jin et al. developed GPU memory compression frameworks that identify fixed-ratio correlations between data values inside small memory blocks where traditional redundancy is low.
- 3D Graphics: Even in modern computer vision, Xinshuang Liu et al. demonstrated that compressing spatial and geometric attributes (like rotation, scale, and opacity) as isolated streams is inefficient. By introducing joint attribute quantization, they exploit cross-attribute correlations to compress 3D Gaussian Splatting scenes down to the kilobyte range.
Key Foundational Work
Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies (2009) — contributed 6 concept elements to this direction.
Data Mining Meets Network Management: The NEMESIS Project (2001) — contributed 1 concept elements to this direction.