TL;DR
Sema-SQL bridges the gap between structured relational databases and the semantic reasoning of Large Language Models (LLMs). By introducing Hybrid Relational Algebra (HRA), it automatically translates natural language questions into optimized query plans that seamlessly combine traditional SQL operations with LLM-powered functions, slashing LLM invocation costs by over 93% via intelligent batching.
What Problem Does This Paper Address?
Relational databases are the gold standard for structured data analysis, but they stumble when real-world queries require external knowledge, semantic matching (e.g., recognizing that "IBM" and "International Business Machines" are the same entity), or unstructured text analysis (e.g., extracting sentiment from customer reviews).
While text-to-SQL systems allow users to query databases using natural language, they are strictly bound by the expressive limits of standard relational algebra and operate under a "closed-world" assumption—meaning they cannot handle information missing from the database schema. Conversely, recent "semantic operator" frameworks allow developers to embed LLM functions inside data pipelines, but they require human experts to manually construct, stitch together, and optimize complex execution plans. Sema-SQL solves this by completely automating the generation, optimization, and execution of hybrid relational-semantic queries.
Methods
Sema-SQL operates in three distinct phases: automated query generation, cost-based optimization, and efficient execution.
- Hybrid Relational Algebra (HRA): The authors formalize HRA, an algebraic framework that embeds LLM-powered User-Defined Functions (UDFs) directly into standard relational operators like Selection, Projection, Join, TopK, and Aggregation.
- Structured Query Generation: To help LLMs generate valid HRA queries, Sema-SQL uses a structured prompting framework. It represents the database schema as a compact, hierarchical YAML configuration, decomposes the natural language question into step-by-step reasoning tasks (resembling the ReAct paradigm), and uses contrastive prompting to ensure the generated LLM UDFs are precise and type-safe.
- Two-Phase Cost Optimization:
- Phase 1: Applies standard relational optimizations (like join ordering) to minimize intermediate data sizes.
- Phase 2 (Lazy LLM Evaluation): Uses a dynamic programming algorithm to optimally place expensive LLM UDFs later in the query plan where they operate on fewer rows.
- UDF Rewriting: If an LLM UDF is determined to be stateless and deterministic (e.g., checking if a county is in the Bay Area), Sema-SQL automatically rewrites it into a pure, equivalent SQL expression, completely bypassing LLM runtime costs.
- Smart-Batching for Semantic Joins: Instead of a naive nested-loop join that invokes the LLM for every single row pair, Sema-SQL samples the data to gauge text length and complexity, dynamically determines an optimal batch size, and evaluates multiple row pairs in a single LLM call.
Datasets
The system was evaluated using:
- TAG (Table-Augmentation-Generation): A state-of-the-art benchmark featuring data-analytics questions that require world knowledge and semantic reasoning over textual database columns.
- TAG+: An extended benchmark introduced by the authors. They engaged database experts to construct explicit ground-truth queries for TAG and added 40 highly complex queries covering multi-hop reasoning, subqueries, and advanced semantic patterns (such as semantic categorization and information extraction).
Key Insights and Ideas
- The Predicate Pushdown Paradox: In traditional databases, pushing filters down as close to the raw data as possible is a golden rule. Sema-SQL flips this logic for semantic operations: because LLM calls are orders of magnitude more expensive than relational operations, it is often far cheaper to defer semantic selections until after relational joins have filtered out irrelevant data.
- LLMs as Query Rewriters: A key "aha moment" is leveraging the LLM's reasoning during the compilation/optimization phase rather than the execution phase. By letting the LLM translate its own natural language constraints into deterministic SQL predicates before execution, runtime overhead drops to zero for those operations.
- Adaptive Fallbacks: Naive batching often fails when text contexts grow too large or reasoning becomes too complex. Sema-SQL’s smart-batching dynamically scales down batch sizes for nuanced tasks, balancing aggressive cost savings with strict accuracy preservation.
Key Results
- High Generation Accuracy: Sema-SQL achieved a 93.3% query generation accuracy using Claude 4.5 Sonnet, evaluated across syntactic validity, semantic correctness, and executability.
- Optimizer Efficiency: Enabling the cost-based optimizer reduced average query execution time by 28% and total token consumption by 21%.
- Dramatic LLM Call Reduction: For semantic joins, the smart-batching algorithm reduced the number of LLM invocations by 93.3% (ranging from a 5× to 300× reduction depending on the dataset) compared to standard nested-loop approaches, all while maintaining 100% execution accuracy.
Limitations and Future Work
- Open-Weight Model Performance: While proprietary models like Claude 4.5 Sonnet and GPT-5 performed exceptionally well, open-weight models (e.g., Qwen3-256B) lagged behind due to factual knowledge gaps and weaker query understanding. The authors note that these models would benefit from task-specific fine-tuning or retrieval-augmented generation (RAG).
- Physical Optimizations: The current framework leaves room for integrating orthogonal physical execution optimizations, such as model cascades (routing simpler tasks to smaller, cheaper models), proxy models for pre-filtering, and prompt caching.
Summary updated