[IMPALA-13109] Use RoaringBitmap in IcebergDeleteNode

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: Impala 4.5.0
• Labels: impala-iceberg
• Epic Color: ghx-label-10
• Assignee: Zoltán Borók-Nagy
• Reporter: Zoltán Borók-Nagy
• Created: 28/May/24 09:53
• Updated: 17/Jul/24 09:49
• Resolved: 17/Jul/24 09:49

Description

IcebergDeleteNode currently uses an ordered int64_t array for each data file to hold the deleted positions. This can consume significant amount of memory when there are lots of deleted records.
E.g. 100 Million delete records consume 800 MiB memory.

RoaringBitmap is a highly compressed and highly efficient data structure to store bitmaps:
https://arxiv.org/pdf/1603.06549
https://github.com/RoaringBitmap/CRoaring

We could use it to store the deleted file positions instead of the sorted arrays, as

• it consumes significantly less memory
• makes the code simpler
• might have perf benefits

Sub-Tasks

• Backport Clang compiler fix to Toolchain Clang 5.0.1: Open