Overlay Bitmap Encoding for Efficient Consumption of Apache Parquet Files

Abstract

Apache Parquet has significantly transformed big data processing with its efficient columnar storage capabilities, incorporating techniques such as the Partition Attributes Across (PAX) layout and dictionary-based encoding to enhance data compression and query performance. Despite these advantages, Apache Parquet's limited indexing capabilities can lead to inefficiencies when users need to fetch only a subset of the data. This paper proposes an innovative extension to Apache Parquet by introducing a new encoding format where indexes form the foundational physical representation of a column. Specifically, we introduce overlay bitmaps , a data structure that organizes column chunks into sequences of bitmap parts, each representing distinct column values that are further compressed using run-length encoding. Our implementation within the Apache Parquet C++ libraries and integration into the SAP IQ relational engine demonstrates the dual use of overlay bitmaps as both a storage and indexing mechanism, significantly improving predicate evaluation speed and compression efficiency. Experimental evaluations highlight that overlay bitmap encoding surpasses traditional dictionary encoding in compression and reduces load execution times by up to two orders of magnitude by enabling efficient, row-level, predicate pushdown. This capability allows complex queries, which involve numerous joins and predicates, to be executed up to 10x faster.