Synthesizing analytical SQL queries from computation demonstration

Xiangyu Zhou, Rastislav Bodík, Alvin Cheung, Chenglong Wang

TL;DR

Writing complex analytical SQL queries (think PARTITION BY and window functions) is hard for humans and even harder for traditional program-synthesizers. This paper introduces Sickle, a tool that synthesizes these queries from "computation demonstrations"—where users provide a few Excel-like formulas showing how specific cells were calculated—rather than just providing final output values. By tracking the "provenance" (the path from input to output) of data, Sickle solves 95% of real-world benchmarks, performing over 20x faster than previous state-of-the-art methods.

What Problem Does This Paper Address?

Standard SQL is great for retrieving data, but Analytical SQL—used for tasks like moving averages, rankings, and cumulative sums—is a different beast. It relies heavily on partitioning and grouping operators that are notoriously difficult for non-experts to write.

Existing "Programming-by-Example" (PBE) tools try to help by asking users for input-output pairs. However, for analytical queries, this fails for two reasons:

  1. High User Effort: To provide an example, a user must manually calculate complex aggregates across many rows, which is tedious and error-prone.
  2. Search Explosion: Synthesizers have to "guess" which functions were used to reach a value. In a massive search space of possible SQL operators, this leads to a "combinatorial explosion" that makes the tools slow or unusable for complex tasks.

Methods

The authors propose a shift from Programming-by-Example to Programming-by-Computation-Demonstration.

  • The Specification: Instead of just providing a final number (e.g., "45"), the user provides a partial output table where a few cells contain formulas (e.g., sum(T[1,4], T[2,4])). They even support "incomplete expressions" using a diamond symbol ($\diamond$) to indicate that other, omitted values were also part of the calculation.
  • Provenance-Tracking Semantics: The authors redefined SQL semantics to treat operators as "term rewriters." Instead of calculating values, the system tracks which input cells contributed to which output cells.
  • Abstract Data Provenance: This is the core algorithmic innovation. During the search for the right query, Sickle uses an abstraction that over-approximates where data could come from. If a partial query's data flow doesn't match the user's demonstration (e.g., the user used data from Row 8, but the query only looks at Rows 1-4), the system prunes that entire branch of the search space immediately.
  • The Tool (Sickle): An enumerative search engine that builds query "skeletons" and fills them with parameters, using the provenance abstraction to prune the search space by an average of 97%.

Datasets

The authors evaluated Sickle on 80 real-world analytical SQL tasks:

  • 60 tasks were harvested from online help forums and tutorials (like StackOverflow), representing common "how-to" struggles for users.
  • 20 tasks were drawn from the TPC-DS benchmark, an industry-standard suite for decision-support systems that involves highly complex, multi-step analytical queries.

Key Insights and Ideas

  • The "How" is better than the "What": Knowing which cells a user clicked on to calculate a result provides a much stronger pruning signal than the final numeric result itself.
  • Values are volatile, Provenance is stable: Analytical operators often mutate values (e.g., turning a list of prices into a single average). Traditional value-based abstractions struggle here because the "signal" is lost. Provenance (knowing that "this average came from these five rows") remains a constant truth regardless of the specific math used.
  • Laziness is a Feature: By allowing "incomplete expressions" ($\diamond$), the authors acknowledge that users won't want to click every single cell in a 100-row partition. Providing just a few "anchor" cells is often enough to uniquely identify the intended SQL logic.

Key Results

  • Effectiveness: Sickle solved 76 out of 80 benchmarks. Prior state-of-the-art tools (Morpheus and Scythe) could only solve 60 and 51, respectively.
  • Speed: On average, Sickle found the correct query in 12.8 seconds. On benchmarks where all tools succeeded, Sickle was 22.5x faster than value-based approaches and nearly 70x faster than type-based approaches.
  • User Study: A study with 13 participants showed that while simple tasks were easy for everyone, users were significantly more efficient and more confident using computation demonstrations for complex, "hard" tasks.

Limitations and Future Work

  • Complexity Ceiling: Sickle struggles when the input data has a very high number of columns or when the solution requires many deeply nested operators, as the provenance abstraction becomes less precise.
  • Constant Invention: The tool currently doesn't "invent" new constants for filters (e.g., it won't guess WHERE price > 100 unless the user provides the number 100).
  • UI/UX: While the logic is sound, the authors note that a production version would need a more polished drag-and-drop interface to make the "demonstration" feel as natural as using a spreadsheet.

Summary updated

Abstract

Analytical SQL is widely used in modern database applications and data analysis. However, its partitioning and grouping operators are challenging for novice users. Unfortunately, programming by example, shown effective on standard SQL, are less attractive because examples for analytical queries are more laborious to solve by hand. To make demonstrations easier to author, we designed a new end-user specification, programming by computation demonstration, that allows the user to demonstrate the task using a (possibly incomplete) cell-level computation trace. This specification is exploited in a new abstraction-based synthesis algorithm to prove that a partially formed query cannot be completed to satisfy the specification, allowing us to prune the search tree. We implemented our approach in a tool named Sickle and tested it on 80 real-world analytical SQL tasks. Results show that even from small demonstrations, Sickle can solve 76 tasks, in 12.8 seconds on average, while the prior approaches can solve only 60 tasks and are on average 22.5 times slower. Furthermore, our user study with 13 participants reveals that our specification increases user efficiency and confidence on challenging tasks.
BibTeX
@inproceedings{zhou2022synthesizing,
  author = {Xiangyu Zhou and Rastislav Bodík and Alvin Cheung and Chenglong Wang},
  title = {{Synthesizing analytical SQL queries from computation demonstration}},
  booktitle = {PLDI},
  year = {2022},
  doi = {10.1145/3519939.3523712},
}

Loading related content...

Figure