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:
- High User Effort: To provide an example, a user must manually calculate complex aggregates across many rows, which is tedious and error-prone.
- 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 > 100unless 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