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...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2475-1421
2475-1421
DOI:10.1145/3428238