Improving LZ4 for Effective Compression and Efficient Query
Open Access
- 2 April 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (1) , 1-26
Abstract
LZ4 is a compression algorithm widely adopted in many database systems, which surprisingly has no support for directly querying the compressed data. Existing systems rely on full decompression for query processing, leading to increased query latency. Moreover, the LZ4 compression algorithm has issues like long match dependency, which reduces both compression effectiveness and the efficiency of compressed-data query processing. In this paper, (1) we propose LZV, a compression algorithm that employs a variable-length hash mechanism to identify maximal matches, significantly improving the compression ratio and reducing the compressed-data query overhead. (2) We propose compressed index search method that leverages auxiliary structure to efficiently query compressed data in LZ4 format directly. (3) Leveraging the ordered, quasi-uniformly spaced nature of the key column, we introduce compressed key search method that integrates prediction with binary search to retrieve the corresponding index for a given key efficiently. Finally, we implement the compressed-data query pipeline in Apache TsFile, an open-source KV storage system. Experimental results show that our approach significantly improves compression effectiveness and query efficiency.Keywords
Funding Information
- National Center for Research and Development (2025ZD1601701, 2024YFB3311901, 2021YFB3300500)
- National Natural Science Foundation of China-Liaoning Joint Fund (62232005, 92267203, 62021002)
- State Grid Ningxia Electric Power Co. Science and Technology Project (SGNXYX00SCJS2400058)
- Beijing National Research Center For Information Science And Technology (BNR2025RC01011)
This publication has 16 references indexed in Scilit:
- A Rolling Hash Algorithm and the Implementation to LZ4 Data CompressionIEEE Access, 2020
- High Throughput and Low Latency LZ4 Compressor on FPGA2019
- Efficient regular expression matching on LZ77 compressed strings using negative factorsWorld Wide Web, 2019
- The Case for Learned Index Structures2018
- LZ4 compression algorithm on FPGA2015
- Simpler and Faster Lempel Ziv Factorization2013
- LZ77-Like Compression with Fast Random Access2010
- Column-stores vs. row-stores2008
- Compression of individual sequences via variable-rate codingIEEE Transactions on Information Theory, 1978
- A universal algorithm for sequential data compressionIEEE Transactions on Information Theory, 1977