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.