SEMA-SQL: Beyond Traditional Relational Querying with Large Language Models

Yin Lin, Tianjing Zeng, Zhongjun Ding, Rong Zhu, Bolin Ding, H. V. Jagadish, Jingren ZhouarXiv 2026 · arXiv

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.

Figure 2: Overview of the Sema-SQL system, which operates in three phases: (1) Query Generation translates natural language questions into HRA queries; (2) Query Optimization optimizes query plans via a cost-based algorithm and UDF rewriting; (3) Query Execution executes optimized plans to produce final answers.
  • 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:
    1. 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

Abstract

Relational databases excel at structured data analysis, but real-world queries increasingly require capabilities beyond standard SQL, such as semantically matching entities across inconsistent names, extracting information not explicitly stored in schemas, and analyzing unstructured text. While text-to-SQL systems enable natural language querying, they remain limited to relational operations and cannot leverage the semantic reasoning capabilities of modern large language models (LLMs). Conversely, recent semantic operator systems extend relational algebra with LLM-powered operations (e.g., semantic joins, mappings, aggregations), but require users to manually construct complex query pipelines. To address this gap, we present SEMA-SQL, a system that automatically answers natural language questions by generating efficient queries that combine relational operations with LLM semantic reasoning. We formalize Hybrid Relational Algebra (HRA), a declarative abstraction unifying traditional relational operators with LLM user-defined functions (UDFs). The system automates three critical aspects: (1) query generation via in-context learning that produces HRA queries with precise natural language specifications for LLM UDFs, (2) query optimization via cost-based transformations and UDF rewriting, and (3) efficient execution algorithms that reduce LLM invocations by an average of 93% in semantic joins through intelligent batching. Extensive experiments with known benchmarks, and extensions thereof, demonstrate the significant query capability improvements possible with our design.
BibTeX
@misc{lin2026sema,
  author = {Yin Lin and Tianjing Zeng and Zhongjun Ding and Rong Zhu and Bolin Ding and H. V. Jagadish and Jingren Zhou},
  title = {{SEMA-SQL: Beyond Traditional Relational Querying with Large Language Models}},
  year = {2026},
  eprint = {2604.23477},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2604.23477},
}

Loading related content...

Figure