[DB Seminar] Spring 2016: Huanchen Zhang

Using indexes for query execution is crucial for achieving high performance in modern on-line transaction processing databases. For a main-memory database, however, these indexes consume a large fraction of the total memory available and are thus a major source of storage overhead of in-memory databases. To reduce this overhead, we propose using a two-stage index: The first stage ingests all incoming entries and is kept small for fast read and write operations. The index periodically migrates entries from the first stage to the second, which uses a more compact, read-optimized data structure. Our first contribution is hybrid index, a dual-stage index architecture that achieves both space efficiency and high performance. Our second contribution is Dual-Stage Transformation (DST), a set of guidelines for converting any order-preserving index structure into a hybrid index. Our third contribution is applying DST to four popular order-preserving index structures and evaluating them in both standalone microbenchmarks and a full in-memory DBMS using several transaction processing workloads. Our results show that hybrid indexes provide comparable throughput to the original ones while reducing the memory overhead by up to 70%.

Short bio of the speaker:

Huanchen is a third year PhD student advised by Professor Dave Andersen in the Computer Science Department at Carnegie Mellon University. Huanchen received B.S. degrees in Computer Engineering, Computer Sciences and Mathematics from University of Wisconsin-Madison. His research interests are in database systems and distributed systems. He has a particular interest in indexing techniques for in-memory databases.

Note: this is a SIGMOD practice talk.

Notice: After Huanchen’s talk, there will be a short celebration for Alex Beutel.