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 create, 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 space. 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.5x slower. Our user study with 13 participants reveals that our specification increases user efficiency and confidence on challenging tasks.
Introduction
While standard SQL is effective for basic data retrieval, Analytical SQL—which encompasses tasks like moving averages, rankings, and cumulative sums—presents a significant hurdle for non-experts. These queries rely heavily on partitioning and grouping operators (such as PARTITION BY and window functions) that are notoriously difficult to write and debug.
Traditional Programming-by-Example (PBE) tools attempt to lower this barrier by allowing users to provide input-output pairs. However, for analytical queries, PBE faces two primary obstacles: high user effort and search space explosion. Manually calculating complex aggregates across multiple rows to provide an example is error-prone and tedious. Furthermore, synthesizers must navigate a massive search space of possible SQL operators to find a match, often leading to a combinatorial explosion that renders tools slow or unusable for complex tasks.
Programming by Computation Demonstration
To address these challenges, we introduce Sickle, a tool that shifts the paradigm from Programming-by-Example to Programming-by-Computation-Demonstration.
In this model, instead of providing only a final numeric result (e.g., "45"), the user provides a partial output table where specific cells contain Excel-like formulas (e.g., sum(T[1,4], T[2,4])). This demonstration shows the system how a value was derived rather than just what the value is. To further reduce user effort, Sickle supports "incomplete expressions" using a diamond symbol ($\\diamond$) to indicate that other, omitted values were part of the calculation, allowing users to provide just a few "anchor" cells to define the logic.
Technical Approach: Provenance-Tracking and Pruning
The core innovation of Sickle lies in its Provenance-Tracking Semantics. We redefined SQL semantics to treat operators as "term rewriters." Instead of merely calculating values, the system tracks the "provenance"—the specific path from input cells to output cells.
During the query synthesis process, Sickle employs Abstract Data Provenance. This technique over-approximates where data could potentially originate for any given partial query. If a candidate query's data flow does not align with the user’s demonstration (for instance, if the user utilized data from Row 8 but the query only considers Rows 1-4), Sickle immediately prunes that entire branch of the search space. This abstraction-based pruning is highly effective, reducing the search space by an average of 97%.
Evaluation and Results
We evaluated Sickle against 80 real-world analytical SQL tasks, including 60 harvested from online help forums (like StackOverflow) and 20 drawn from the industry-standard TPC-DS benchmark.
Performance and Effectiveness
Sickle demonstrated significant improvements over prior state-of-the-art tools:
- Success Rate: Sickle solved 76 out of 80 benchmarks. In comparison, previous tools like Morpheus and Scythe solved only 60 and 51 tasks, respectively.
- Efficiency: On average, Sickle synthesized the correct query in just 12.8 seconds. On benchmarks where all tools were successful, Sickle was 22.5x faster than value-based approaches and nearly 70x faster than type-based approaches.
User Study
A study involving 13 participants compared computation demonstrations against traditional example-based specifications. While simple tasks were manageable across both methods, participants were significantly more efficient and reported higher confidence when using Sickle for complex, "hard" tasks. The study confirmed that knowing which cells were used to calculate a result provides a much stronger and more intuitive signal for synthesis than the final numeric result alone.
Conclusion and Future Work
Sickle demonstrates that provenance-based synthesis is a powerful alternative to traditional PBE for complex analytical tasks. By focusing on the "how" of a calculation, the tool achieves both higher accuracy and vastly superior performance.
Future work will focus on scaling the tool to handle tables with very high column counts and improving the discovery of constants for filters (e.g., WHERE price > 100). Additionally, developing a more integrated, spreadsheet-like user interface will be essential for making computation demonstrations a natural part of the end-user workflow.
Summary updated