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
번호 | 제목 | 글쓴이 | 날짜 | 조회 수 |
---|---|---|---|---|
46 | 실습예제2 | 관리자 | 2006.04.10 | 897 |
45 | sqlite실행 | 관리자 | 2006.04.24 | 832 |
44 | sqlite | 관리자 | 2006.04.24 | 756 |
43 | stack | 관리자 | 2006.04.27 | 825 |
42 | sqlite | 관리자 | 2006.05.01 | 900 |
41 | Large Block Flash Memeory | 관리자 | 2006.05.15 | 880 |
40 | LSTAFF (Flash Memeory) | 관리자 | 2006.05.29 | 887 |
39 | BinaryTree | 관리자 | 2006.06.01 | 1010 |
38 | 바이너리트리 | 관리자 | 2006.06.05 | 1092 |
37 | Specification을 볼때 알아야할 의미 | 관리자 | 2009.01.21 | 905 |
36 | The shortest path is not always a straight line [1] | 관리자 | 2017.04.25 | 392 |
» | UpBit: Scalable In-Memory Updatable Bitmap Indexing [1] | 관리자 | 2017.04.25 | 524 |
34 | 인터넷 DB 5월 18일(목) 수업 오후 2:30부터 시작합니다 | 관리자 | 2017.05.18 | 610 |
33 | UML 소개 | 관리자 | 2017.09.11 | 376 |
32 | 데이터베이스및실습 9월 12일(화) 수업 오후 4:00부터 시작합니다 | 관리자 | 2017.09.12 | 584 |
31 | 데이터베이스및실습 중간고사 안내 | 관리자 | 2017.09.29 | 961 |
30 | JDBCExample.java | 관리자 | 2017.11.06 | 328 |
29 | 데이터베이스및실습 기말고사 안내 | 관리자 | 2017.12.07 | 1254 |
28 | 2017-2학기 캡스톤디자인 결과물 제출 | 관리자 | 2017.12.15 | 351 |
27 | 인터넷DB응용 중간고사 안내 | 관리자 | 2018.04.17 | 2484 |