Speaker: Huanchen Zhang Carnegie Mellon University
Time: 2019-10-25 14:00-2019-10-25 15:00
Venue: FIT 1-222

Abstract:

The growing cost gap between DRAM and storage together with increasing database sizes means that database management systems (DBMSs) now operate with a lower memory to storage size ratio than before. On the other hand, modern DBMSs rely on in-memory search trees (e.g., indexes and filters) to achieve high throughput and low latency. These search trees, however, consume a large portion of the total memory available to the DBMS. In this talk, we address the challenge of building compact yet fast in-memory search trees to allow more efficient use of memory in data processing systems. We first present techniques to reduce the memory of a read-optimized search tree to the theoretical limit without compromising its query performance. We then introduce ways to amortize the cost of modifying static data structures with bounded and modest cost in performance and space. Finally, we approach the search tree compression problem from an orthogonal direction by building a fast order-preserving key compressor. Together, these three pieces form a practical recipe for achieving memory-efficiency in search trees and in DBMSs. 

Short Bio:

Huanchen Zhang is a final-year Ph.D. student advised by David G. Andersen in the Computer Science Department at Carnegie Mellon University. He also works closely with Andy Pavlo (CMU), Michael Kaminsky (Intel Labs), and Kimberly Keeton (HP Labs). He received his B.S. degrees in Computer Engineering, Computer Sciences, and Mathematics from University of Wisconsin-Madison advised by Remzi Arpaci-Dusseau. His research interests center on computer systems and databases. He has a particular interest in designing memory-efficient and high-performance search structures for data processing systems.