UpBit: Scalable In-Memory Updatable Bitmap Indexing
2017.04.25 14:27
ABSTRACT
Bitmap indexes are widely used in both scientific and commercial
databases. They bring fast read performance for specific types
of queries, such as equality and selective range queries. A major
drawback of bitmap indexes, however, is that supporting updates
is particularly costly. Bitmap indexes are kept compressed to minimize
storage footprint; as a result, updating a bitmap index requires
the expensive step of decoding and then encoding a bitvector. Today,
more and more applications need support for both reads and
writes, blurring the boundaries between analytical processing and
transaction processing. This requires new system designs and access
methods that support general updates and, at the same time,
offer competitive read performance.
In this paper, we propose scalable in-memory Updatable Bitmap
indexing (UpBit), which offers efficient updates, without hurting
read performance. UpBit relies on two design points. First, in addition
to the main bitvector for each domain value, UpBit maintains
an update bitvector, to keep track of updated values. Effectively, every
update can now be directed to a highly-compressible, easy-toupdate
bitvector. While update bitvectors double the amount of uncompressed
data, they are sparse, and as a result their compressed
size is small. Second, we introduce fence pointers in all update
bitvectors which allow for efficient retrieval of a value at an arbitrary
position. Using both synthetic and real-life data, we demonstrate
that UpBit significantly outperforms state-of-the-art bitmap
indexes for workloads that contain both reads and writes. In particular,
compared to update-optimized bitmap index designs UpBit is
15-29 faster in terms of update time and 2:7 faster in terms of
read performance. In addition, compared to read-optimized bitmap
index designs UpBit achieves efficient and scalable updates (51-
115 lower update latency), while allowing for comparable read
performance, having up to 8% overhead.
댓글 1
번호 | 제목 | 글쓴이 | 날짜 | 조회 수 |
---|---|---|---|---|
66 | 연구실원 모집 | 관리자 | 2024.10.14 | 110 |
65 | 101분반 게시판입니다. 웅비관(A12) 1320 | 관리자 | 2018.09.04 | 315 |
64 | JDBCExample.java | 관리자 | 2017.11.06 | 328 |
63 | 102분반 게시판입니다. 누리관(A13) 2226 | 관리자 | 2018.09.04 | 333 |
62 | 2017-2학기 캡스톤디자인 결과물 제출 | 관리자 | 2017.12.15 | 351 |
61 | UML 참고자료 | 관리자 | 2018.10.08 | 351 |
60 | UML 소개 | 관리자 | 2017.09.11 | 376 |
59 | The shortest path is not always a straight line [1] | 관리자 | 2017.04.25 | 392 |
58 | 연구실원 모집 | DBADMIN | 2023.08.03 | 491 |
57 | 최종보고서 양식 | 관리자 | 2020.09.07 | 491 |
» | UpBit: Scalable In-Memory Updatable Bitmap Indexing [1] | 관리자 | 2017.04.25 | 524 |
55 | 정보 및 데이터 베이스 연구실 연구생 모집 | 관리자 | 2023.08.04 | 582 |
54 | 데이터베이스및실습 9월 12일(화) 수업 오후 4:00부터 시작합니다 | 관리자 | 2017.09.12 | 584 |
53 | 인터넷 DB 5월 18일(목) 수업 오후 2:30부터 시작합니다 | 관리자 | 2017.05.18 | 610 |
52 | '데이터베이스및실습101분반' 10월 8일(월) 수업 오전 9시부터 시작합니다 | 관리자 | 2018.10.05 | 686 |
51 | 객체지향프로그래밍 7장 강의노트 | 관리자 | 2005.12.14 | 694 |
50 | 분산객체시스템 5장 강의노트 | 관리자 | 2005.12.14 | 707 |
49 | RAID 발표자료(옥충기) | 관리자 | 2005.12.14 | 714 |
48 | 분산객체시스템 8장 강의노트 | 관리자 | 2005.12.14 | 715 |
47 | odbc | 관리자 | 2005.12.14 | 725 |