Optimizing database-backed applications with query synthesis

By Alvin Cheung, Armando Solar-Lezama, Samuel Madden. 2013

172 citations recorded by the source corpus.

Object-relational mapping libraries are a popular way for applications to interact with databases because they provide transparent access to the database using the same language as the application. Unfortunately, using such frameworks often leads to poor performance, as modularity concerns encourage developers to implement relational operations in application code. Such application code does not take advantage of the optimized relational implementations that database systems provide, such as efficient implementations of joins or push down of selection predicates. In this paper we present QBS, a system that automatically transforms fragments of application logic into SQL queries. QBS differs from traditional compiler optimizations as it relies on synthesis technology to generate invariants and postconditions for a code fragment. The postconditions and invariants are expressed using a new theory of ordered relations that allows us to reason precisely about both the contents and order of the records produced complex code fragments that compute joins and aggregates. The theory is close in expressiveness to SQL, so the synthesized postconditions can be readily translated to SQL queries. Using 75 code fragments automatically extracted from over 120k lines of open-source code written using the Java Hibernate ORM, we demonstrate that our approach can convert a variety of imperative constructs into relational specifications and significantly improve application performance asymptotically by orders of magnitude.

Subfields: Artificial Intelligence, Computer Networks and Communications, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Optimization & Training

Citations in the corpus

CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis (2022, background): “Previous work (Joshi et al., 2002; Panchekha et al., 2015; Cheung et al., 2013) leverages domain-specific language to restrict the search space; however, this limits the applicability of synthesized programs.”
Cosette: An Automated Prover for SQL (2017, methodology): “The data models used in C OSETTE are inspired by prior work on modeling relations, including work on test generation [33] and program compilation [14].”
A Conversational Paradigm for Program Synthesis (2022, background): “Previous work (Joshi et al., 2002; Panchekha et al., 2015; Cheung et al., 2013) leverages domain-specific language to restrict the search space; however, this limits the applicability of the synthesized programs.”
Foofah: Transforming Data By Example (2017, methodology): “Researchers have applied program synthesis techniques to a variety of problem domains: parsers [25], regular expressions [5], bit-manipulation programs [14,21], data structures [39]; code snippets and suggestions in IDEs [29, 35], and SQL query based on natural language queries [26] and data handlin”