Deductive Optimization of Relational Data Storage
Optimizing the physical data storage and retrieval of data are two key database management problems. In this paper, we propose a language that can express both a relational query and the layout of its data. Our language can express a wide range of physical database layouts, going well beyond the row- and column-based methods that are widely used in database management systems. We use deductive program synthesis to turn a high-level relational representation of a database query into a highly optimized low-level implementation which operates on a specialized layout of the dataset. We build an optimizing compiler for this language and conduct experiments using a popular database benchmark, which shows that the performance of our specialized queries is better than a state-of-the-art in memory compiled database system while achieving an order-of-magnitude reduction in memory use.
Wed 20 OctDisplayed time zone: Central Time (US & Canada) change
10:50 - 12:10 | OOPSLA 2020 Papers 1SIGPLAN Papers at Zurich G Chair(s): John Renner University of California at San Diego, USA | ||
10:50 15mTalk | Can Advanced Type Systems Be Usable? An Empirical Study of Ownership, Assets, and Typestate in Obsidian SIGPLAN Papers Michael Coblenz University of Maryland at College Park, Jonathan Aldrich Carnegie Mellon University, Brad A. Myers Carnegie Mellon University, Joshua Sunshine Carnegie Mellon University Link to publication | ||
11:05 15mTalk | Designing Types for R, Empirically SIGPLAN Papers Alexi Turcotte Northeastern University, Aviral Goel Northeastern University, Filip Křikava Czech Technical University, Jan Vitek Northeastern University; Czech Technical University | ||
11:20 15mTalk | Deductive Optimization of Relational Data Storage SIGPLAN Papers Jack Feser Massachusetts Institute of Technology, Sam Madden Massachusetts Institute of Technology, Nan Tang QCRI HBKU, Armando Solar-Lezama Massachusetts Institute of Technology | ||
11:35 15mTalk | Digging for Fold: Synthesis-Aided API Discovery for Haskell SIGPLAN Papers Michael B. James University of California at San Diego, Zheng Guo University of California, San Diego, Ziteng Wang University of California at San Diego, Shivani Doshi University of California at San Diego, Hila Peleg Technion, Ranjit Jhala University of California at San Diego, Nadia Polikarpova University of California at San Diego | ||
11:50 20mLive Q&A | Discussion, Questions and Answers SIGPLAN Papers | ||