CUBIT: Concurrent Updatable Bitmap Indexing

Download PDF

Abstract

Bitmap indexes are widely used for read-intensive analytical work-Bitmap indexes are widely used for read-intensive analytical workloads because they are clustered and offer efficient reads with a small memory footprint. However, they are generally inefficient to update. As analytical applications are increasingly fused with transactional applications, leading to the emergence of hybrid trans-transactional applications, leading to the emergence of hybrid transactional/analytical processing (HTAP), it is desirable that bitmap indexes support efficient concurrent real-time updates. In this pa-indexes support efficient concurrent real-time updates. In this paper, we propose C oncurrent U pdatable Bit map indexing (CUBIT) that offers efficient real-time updates that scale with the number of CPU cores used and do not interfere with queries. Our design relies on three principles. First, we employ a horizontal bitwise rep-relies on three principles. First, we employ a horizontal bitwise representation of updated bits, which enables efficient atomic updates without locking entire bitvectors. Second, we propose a lightweight snapshotting mechanism that allows queries to run on separate snapshots and provides a wait-free progress guarantee. Third, we consolidate updates in a latch-free manner, providing a strong progress guarantee. Our evaluation shows that CUBIT offers 3–16× higher throughput and 3–220× lower latency than state-of-the-art updatable bitmap indexes. CUBIT’s update-friendly nature widens the applicability of bitmap indexing. Experimenting with OLAP workloads with standard, batched updates shows that CUBIT over-workloads with standard, batched updates shows that CUBIT overcomes the maintenance downtime and outperforms DuckDB by 1.2–2.7× on TPC-H. For HTAP workloads with real-time updates, CUBIT achieves 2–11× performance improvement over the state-CUBIT achieves 2–11× performance improvement over the stateof-the-art approaches.