Deductive optimization of relational data storage

• Published in: Proceedings of ACM on programming languages 2020-11, Vol.4 (OOPSLA), p.1-30, Article 170
• Main Authors: Feser, John, Madden, Sam, Tang, Nan, Solar-Lezama, Armando
• Format: Article
• Language: English
• Subjects: Automatic programming; Context specific languages; Data layout; Data management systems; Data structures; Domain specific languages; Information systems; Query languages; Relational database query languages; Software and its engineering; Software creation and management; Software development techniques; Software notations and tools
• ISSN: 2475-1421; 2475-1421
• DOI: 10.1145/3428238

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.