Authors: Johannes Wehrstein, Tiemo Bang, Roman Heinrich, Carsten Binnig

In modern database systems, User-Defined Functions (UDFs) have become indispensable for encapsulating logic that goes beyond traditional SQL capabilities. Yet, despite their ubiquity, UDFs remain a thorn in the side of query optimizers. Conventional cost models often treat UDFs as black boxes or rely on static assumptions, which can lead to suboptimal execution plans. With GRACEFUL (GRAph-based Cost Estimator For User-defined Logic), we have published a novel approach tackling this decades-old challenge.

The Challenge

UDFs pose unique optimization challenges due to their complexity and variability:

• Unpredictable Costs: UDFs often involve loops, branches, or external calls, making it hard to estimate their runtime.
• Impact on Query Plans: Decisions like whether to push-down or pull-up UDF-based filters can drastically affect performance. Conventional heuristics frequently fall short when UDFs are involved, leading to significant inefficiencies.

As an example, a standard filter push-down might yield disastrous runtimes when applied to a computationally expensive UDF. Conversely, pulling up a UDF filter at the right stage could result in orders-of-magnitude speedups.

How does GRACEFUL work?

GRACEFUL introduces a learned, graph-based cost model capable of accurately predicting the runtime of SQL queries containing UDFs.

1. Graph Representation of UDFs and Queries: We transform UDF code into a control flow graph (CFG) and integrate it with the query plan graph. This joint representation allows us to capture both query structure and UDF-specific nuances.

2. Machine Learning at the Core: By training a Graph Neural Network (GNN) on this representation, GRACEFUL generalizes to previously unseen UDFs, workloads, and datasets. The model leverages database statistics to predict branch hit ratios, ensuring accurate runtime predictions.

3. Zero-Shot Learning: GRACEFUL is designed to work out-of-the-box on new databases and UDFs without requiring retraining—a critical feature for real-world deployment.

Results

In our evaluation, GRACEFUL delivered remarkable results:

• Broad Generalization: Across 20 diverse datasets, GRACEFUL consistently outperformed baseline methods. Using estimated cardinalities, GRACEFUL achieved a median Q-Error of 1.25, far surpassing traditional approaches.
• 1.46x Speedups with Pull-Up Advisor: By making informed decisions on whether to push down or pull up UDF filters, GRACEFUL reduced runtimes from 5.1 hours to 3.5 hours on our benchmark – reaching close to the optimum, far outperforming other baselines.
• Minimal Overheads & Regressions: Experiments show high robustness of GRACEFUL against UDF complexity, including length of the code, number of branches, different code patterns, etc., leading to very few false positives. Overheads of our system are measured at around 3-3.5% of the total benchmark runtime (the system is not optimized for online latency).

Paving the Way for Future Research

To spur innovation in UDF cost modeling, we’ve released a benchmark dataset of over 90,000 UDF queries across 20 databases. This resource, along with our code, is aimed at fostering collaboration and driving further advancements in this space.

GRACEFUL not only addresses blind spots in UDF optimization but also sets the stage for a new generation of cost-aware query optimizers.

Learn More

Stay tuned for our upcoming ICDE 2025 presentation, where we’ll dive deeper into the methodology and share insights into the development of GRACEFUL.

The paper can be found here on arxiv.