arXiv CSopen access

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

Sema-SQL: Extending Relational Queries with Large Language Models Yin Lin, Tianjing Zeng, Zhongjun Ding, Rong Zhu, Bolin Ding∗ , H. V. Jagadish§ , Jingren Zhou Alibaba Group § University of Michigan

arXiv:2604.23477v1 [cs.DB] 26 Apr 2026

{yin.lin, zengtianjing.ztj, dingzhongjun.dzj, red.zr, bolin.ding, jingren.zhou}@alibaba-inc.com [email protected]

ABSTRACT Relational databases excel at structured data analysis, but realworld 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.

1

INTRODUCTION

Relational database systems have long been the dominant paradigm for storing and managing structured data. Business analysts, data scientists, and decision-makers often need complex database queries, but many lack the required technical expertise. Recently, systems that provide natural language interfaces to databases have become a prominent research focus, with recent advances in large language models (LLMs) showing particular promise for SQL generation [16, 38, 39, 48, 51]. Can these approaches truly handle the complexity of real-world queries that users demand? Widely recognized text-to-SQL benchmarks such as BIRD [27] and Spider [56] are constrained by the expressive limitations of relational algebra and assume that all information needed to answer user questions is contained within the original database schema. However, many real-world user queries go beyond these capabilities. Consider the following examples abridged from real-world user questions:

x (a): Joining customer information (left table) with sales revenue (right table) based on semantic entity matching.

(b): Extracting NBA players’ draft year.

(c): Determining customer’s favorite dishes from reviews.

Figure 1: Motivating examples: extending relational querying with LLM capabilities. Figure 1(a) shows an IT supplier querying sales revenue by customer, requiring non-equi-joins of two tables. Standard SQL using string equality matching will fail, and traditional similarity-based extensions [11, 25] often suffer from parameter sensitivity, poor scalability, and limitations to syntactic similarity [20]. Figure 1(b) demonstrates a sports journalist analyzing the gap between NBA players’ draft years and their first NBA MVP award. However, the draft year information is missing from the original database. SQL queries traditionally operate under the closed-world assumption, being unable to handle questions that require information not explicitly captured in the database schema [58]. The final example, shown in Figure 1(c), illustrates a restaurant owner seeking to summarize customers’ favorite dishes from freetext reviews. This task requires semantic analysis of unstructured text to extract information and sentiment, extending beyond standard SQL capabilities that can only operate on structured numerical or categorical data. To support these analytical requirements, a novel class of data processing systems [13, 22, 29, 36, 45, 46] has recently emerged that extends relational algebra with LLM capabilities through semantic operators, including semantic filters, joins, mappings, rankings, classifications, and summarizations. These operators enable the queries shown in Figure 1: (a) a semantic join combines tables by

Yin Lin, Tianjing Zeng, Zhongjun Ding, Rong Zhu, Bolin Ding∗ , H. V. Jagadish§ , Jingren Zhou

Input Question

Evidence

① Query Generation (Sec. 3) Columns Domain notes Relationships

Database Semantic data & Schema model

Semantic data model filtering

Question

LLM UDFs Ops

② Query Optimization (Sec. 4) Hybrid Query in HRA

Query Question decomposition synthesis

Query Execution

UDF rewrite

Query parsing

Cost-based query optimization

③ Query Execution (Sec. 5)

Optimized plan

Answer

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. matching entities in the join columns; (b) a semantic mapping extracts missing information from parametric or external knowledge; and (c) a semantic summarization performs sentiment analysis on unstructured text to infer preferences. However, a critical challenge remains: how can we automatically translate natural language questions into efficient queries that combine both relational and semantic operations? Existing approaches fall short in complementary ways. Hybrid question answering systems [9, 52] utilize LLMs directly to answer questions over textual and relational data, without producing queries—making answers hard to verify and results difficult to reproduce. Conversely, systems with semantic operators [5, 13, 18, 22, 29, 36, 46] require users to manually implement semantic operators and orchestrate both query construction and execution optimization—demanding expertise in both database systems and LLM-based operators. Our Approach. We present Sema-SQL1 , a system that answers natural language questions over relational data by combining relational operations with LLM semantic reasoning. As shown in Figure 2, given a natural language question, evidence (i.e., external knowledge), and a relational database, Sema-SQL transforms the question into a declarative query in Hybrid Relational Algebra (HRA), a database-agnostic formalism that incorporates LLM-powered userdefined functions (UDFs). This query is then compiled into an optimized execution plan via cost-based transformations and UDF rewrites, then executed using specialized algorithms for semantic operators to generate the answer. Building an end-to-end system requires addressing three key challenges. First, LLMs are unfamiliar with semantic operators, making it challenging to synthesize queries that correctly determine when semantic operators are needed, which data they should operate on, and how to generate appropriate natural language prompts within LLM UDFs. To address this, Sema-SQL develops a structured prompting framework that: (1) provides a compact semantic representation of databases; (2) decomposes the query task into reasoning steps that iteratively apply Sema-SQL’s relational and semantic operators; and (3) guides accurate LLM UDF generation through curated instructions and few-shot examples. Second, generated queries may exhibit suboptimal execution efficiency. Existing optimization approaches suffer from distinct limitations: rule-based rewriting [18, 33, 46, 47] applies predetermined transformation rules (e.g., always push down predicates, always defer LLM operations) without considering actual costs; 1 Please check the open-sourced code: https://github.com/semasql/SEMA-SQL.

LLM-based rewriting [2, 44, 59] generates plans without access to cost models or formal correctness guarantees (see Section 7). Sema-SQL extends relational query optimizers to account for LLM invocation costs—often orders of magnitude higher than relational operations. We develop a dynamic programming algorithm that optimally places LLM UDFs within query plans to minimize execution runtime while ensuring plan equivalence through symbolic execution [50]. We further introduce UDF rewriting to replace LLM UDFs with equivalent SQL expressions where possible. Third, efficient execution of semantic operators remains challenging. Existing systems like LOTUS [36] and Palimpzest [29] implement semantic joins using a nested-loop approach, invoking the LLM for each row pair, which becomes prohibitively expensive. Sema-SQL introduces a smart-batching algorithm that dynamically groups rows from both tables into batches, adapting batch sizes to context length and task complexity. This enables the LLM to identify all matching row pairs in one invocation per batch pair, achieving significant efficiency gains while preserving accuracy. Contributions. We summarize our contributions as follows: • We introduce Hybrid Relational Algebra (HRA), a formal algebraic framework that unifies relational operators with LLM-based semantic operations, providing a declarative target language for automatic query generation from natural language questions. • We develop a systematic query generation approach for HRA addressing semantic schema representation, question decomposition, and precise UDF synthesis, achieving 93.3% query generation accuracy across three correctness criteria (syntactic validity, semantic accuracy, executability). On benchmarks requiring semantic reasoning beyond relational operations, our approach matches stateof-the-art systems that rely on manually constructed pipelines. • We propose a cost-based optimization framework that integrates LLM invocation costs with traditional relational metrics, featuring an algorithm with equivalence guarantees for optimal UDF placement and automatic rewriting of LLM UDFs into equivalent SQL operations. Our optimizations reduce execution runtime by 28% and token consumption by 21%. • We design specialized execution algorithms that integrate LLM UDF execution into database engines, including a batching optimization for semantic joins that reduces LLM invocations by 5—300× without accuracy loss.

Sema-SQL : Extending Relational Queries with Large Language Models

scores_df = pd.read_csv("satscores.csv") schools_df = pd.read_csv("schools.csv") unique_counties = pd.DataFrame(schools_df["County"].unique(), columns=[" County"]) unique_counties = unique_counties.sem_map( "What is the population of {County} in California? Answer with only the number without commas. Respond with your best guess." ) counties_over_2m = set() for _, row in unique_counties.iterrows(): try: if int(re.findall(r"\d+", row._map)[-1]) > 2000000: counties_over_2m.add(row.County) except: pass schools_df = schools_df[schools_df["County"].isin(counties_over_2m)] merged = pd.merge(scores_df, schools_df, left_on="cds", right_on="CDSCode") prediction = int(merged["NumTstTakr"].sum())

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

(a) LOTUS program. 𝛾 SUM(NumTstTakr)→total_test_takers (satscores ⊲⊳cds = CDSCode (𝜎population > 2000000 (Π ExtractPopulation(County)→population (schools)))) (b) HRA representation.

Figure 3: Example query from the TAG benchmark: “How many test takers are there at the school/s in a county with population over 2 million?”. (a) LOTUS: expert-written program with explicit execution logic. (b) HRA: declarative algebraic operators.

2

HYBRID RELATIONAL ALGEBRA

We introduce Hybrid Relational Algebra (HRA), which extends relational algebra with LLM-based semantic operations. HRA provides a declarative algebraic representation for queries that combine structured relational data processing with semantic reasoning. Figure 3 compares how LOTUS [36] (using Python semantic analytical programs) and HRA express a query from the TAG benchmark that answers the natural language question: “How many test takers are there at schools in counties with population over 2 million?” This query requires a semantic mapping operation to extract the population of each California county. In the LOTUS program (Figure 3a), the semantic mapping is performed using a pandas-like API: sem_map (line 4). Users must specify detailed prompts, handle LLM result parsing, and optimize query execution. For example, the program extracts unique County values first to avoid redundant LLM calls (line 3). However, even this expert-written program is suboptimal; performing the join (line 15) before the expensive sem_map operation would filter counties before the semantic map. Such procedural specifications make it difficult for users (both human experts and LLMs) to write optimal analytical programs. HRA (Figure 3b) specifies queries in concise algebraic form. Semantic operations invoke LLMs through user-defined functions (UDFs), represented as function symbols embedded in relational operators (e.g., ExtractPopulation in projection). LLM UDFs extend relational operators in multiple ways, as shown in Figure 4: they may serve as binary predicates within joins to determine entity equivalence (e.g., SameEntity in Figure 4a) or as aggregation functions that summarize groups of textual

(a): LLM UDF for semantic join

JOIN

SELECT

SameEntity(Company Name, Client Name)

c.Company Name

(b): LLM UDF for semantic aggregation

s.Client Name

FavoriteDish(Review)

Review

Figure 4: Examples of LLM UDFs in HRA for semantic operations.

content through semantic processing (e.g., FavoriteDish in Figure 4b). We formally define an LLM UDF as follows: Definition 2.1 (LLM User-Defined Function). Let 𝑇 be input relations and 𝐶 be a subset of columns from 𝑇 , where 𝑇 [𝐶] denotes the 𝑙 leverages projection of 𝑇 onto columns 𝐶. An LLM-powered UDF 𝑈𝑀 a language model 𝑀 to evaluate a natural language expression 𝑙 that constructs prompts from input 𝑇 [𝐶]. The language model 𝑀 induces
a probabilistic distribution Pr𝑀 𝑦 | 𝑙 (𝑇 [𝐶]) and returns output 𝑦 from the output space Y. SameEntity

For example, in Figure 4a, the LLM UDF 𝑈𝑀 evaluates whether two company names refer to the same entity. Given input columns Company_Name from 𝑇𝑐 and Client_Name from 𝑇𝑠 , the language model 𝑀 produces a boolean output (Y = {True, False}) for each tuple pair. Consider the input pair (“International Business Machines”, “IBM”); the UDF evaluates it to True. The semantic join then SameEntity returns all matching pairs: {(𝑡𝑖 ∈ 𝑇𝑐 , 𝑡 𝑗 ∈ 𝑇𝑠 ) | 𝑈𝑀 (𝑡𝑖 [Company_Name], 𝑡 𝑗 [Client_Name]) = True}. Table 1 lists the operators supported by Sema-SQL in HRA. We now demonstrate their semantic extensions using LLM UDFs. 𝑙 Selection. The semantic selection incorporates an LLM UDF 𝑈𝑀 as a selection predicate, which evaluates a natural language condition 𝑙 using model 𝑀. This UDF is applied to each row 𝑡𝑖 , returning a Boolean value indicating whether 𝑡𝑖 satisfies the condition, i.e., 𝑙 (𝑡 [𝐶]) → {True, False}, ∀𝑡 ∈ 𝑅. The operator then leverages 𝑈𝑀 𝑖 𝑖 𝑙 within the selection predicate to filter table 𝑅. the output of 𝑈𝑀 Projection. The semantic projection incorporates an LLM UDF 𝑙 as an AI-powered transformation function that extracts new 𝑈𝑀 columns through natural language-guided inference using model 𝑀. This UDF is applied to each row 𝑡𝑖 ∈ 𝑅, returning a tuple of derived 𝑙 (𝑡 [𝐶]) → y, ∀𝑡 ∈ 𝑅. values y = ⟨𝑦1, ..., 𝑦𝑘 ⟩ for new columns: 𝑈𝑀 𝑖 𝑖 𝑙 as a join Join. The semantic join incorporates an LLM UDF 𝑈𝑀 predicate, which evaluates pairs of rows from the input relations and 𝑙 (𝑡 [𝐶 ], 𝑡 [𝐶 ]) → predicts a Boolean outcome using model 𝑀 as: 𝑈𝑀 𝑖 𝐿 𝑗 𝑅 {True, False}, ∀𝑡𝑖 ∈ 𝐿, 𝑡 𝑗 ∈ 𝑅. The operator returns row pairs for 𝑙 evaluates to True. which 𝑈𝑀 TopK. The semantic TopK incorporates an LLM UDF as a pair𝑙 (𝑡 [𝐶], 𝑡 [𝐶]) → {True, False}, ∀𝑡 , 𝑡 ∈ 𝑅, wise comparator 𝑈𝑀 𝑖 𝑗 𝑖 𝑗 𝑙 where 𝑈𝑀 returns a Boolean value indicating whether 𝑡𝑖 should be ranked before 𝑡 𝑗 , producing the ordered output table. Aggregation. The semantic aggregation incorporates an LLM 𝑙 as the aggregation function, enabling semantic summarizaUDF 𝑈𝑀 tion over groups of rows. We define such an aggregation function 𝑙 (𝑡 [𝐶], . . . , 𝑡 [𝐶]) → 𝑦 as 𝑈𝑀 1 agg , where{𝑡 1 , . . . , 𝑡𝑘 } ⊆ 𝑅, returning 𝑘 an aggregate result that summarizes the input rows based on the natural language instruction.

Yin Lin, Tianjing Zeng, Zhongjun Ding, Rong Zhu, Bolin Ding∗ , H. V. Jagadish§ , Jingren Zhou

Table 1: Summary of HRA operators with their definitions, LLM UDF extensions, and UDF execution algorithms. Operator

Definition

LLM UDF Extension

UDF Execution Algorithm

Selection

𝜎𝜑 (𝑅) Π𝑐𝑜𝑙1 ,... (𝑅) Π 𝑓 :(𝑐𝑜𝑙1 ,...)→𝑐𝑜𝑙new (𝑅)

𝑙 : 𝑅 → 𝑏𝑜𝑜𝑙 ) UD-selection predicate (𝑈𝑀

𝑙 on distinct inputs, filter and join back with 𝑅 . Evaluate 𝑈𝑀 𝑙 on distinct inputs to generate value mappings, join with 𝑅 Apply 𝑈𝑀 to produce 𝑐𝑜𝑙 new . Partition join keys into adaptive batches, evaluate batch pairs to find matches for joining 𝐿 and 𝑅 . 𝑙 , aggregate comparison results to obtain ranks, Compare distinct row pairs via 𝑈𝑀 join with 𝑅 to produce top-𝑘 results.

Projection Join

𝑙 : 𝐿 × 𝑅 → 𝑏𝑜𝑜𝑙 ) UD-join predicate (𝑈𝑀

𝐿 ⊲⊳𝜑 𝑅

TopK Aggregation

𝑙 : 𝑅 → 𝑅′ ) UD-transform function (𝑈𝑀

𝜔 ⊳(col1 ,... ) (𝑅) 𝜔 ⊳𝑘 (col1 ,... ) (𝑅) 𝛾 agg(𝑐𝑜𝑙 ) (𝑅) 𝛾 G;agg(𝑐𝑜𝑙 ) (𝑅)

𝑙 : 𝑅 × 𝑅 → 𝑏𝑜𝑜𝑙 ) UD-compare function (𝑈𝑀 𝑙 :𝑅 →𝑅 ) UD-aggregation function (𝑈𝑀 𝐴

TASK: Given the following database schema and the user question, generate a query in HRA grammar. [DATABASE SCHEMA] <semantic_data_model> [QUESTION] <user_question>, <question_decomposition>

𝑙 to each partition to produce results. Partition by G (if present), apply 𝑈𝑀

where 𝜙ˆ satisfies the following properties: (1) Syntactic Validity: 𝜙ˆ must conform to the HRA grammar and pass parser validation: ˆ S) ≠ ⊥ 𝜙ˆ ∈ L (GHRA ) ∧ Parse(𝜙,

[INSTRUCTIONS] - Generate queries using HRA grammar syntax - When using LLM UDFs, follow <llm_udf_instructions>

where Parse validates both syntactic correctness and schema consistency with 𝑆. (2) Semantic Correctness: When executed on database 𝐷, 𝜙ˆ produces results equivalent to the ground truth query 𝜙 ∗ : 𝜙ˆ (𝐷) = 𝜙 ∗ (𝐷)

[EXAMPLES] ...

Figure 5: Prompt template for HRA query generation.

3

When 𝜙 ∗ is unavailable, semantic correctness is verified through manual inspection or predefined test cases. (3) Executability: 𝜙ˆ must execute successfully without runtime errors on the target database: ˆ 𝐷) ≠ ⊥ Execute(𝜙,

QUERY GENERATION

Automatically synthesizing HRA queries from natural language poses three core technical challenges: (1) semantic-aware schema encoding—representing database schemas to enable accurate operator selection and target data identification, (2) compositional query decomposition—mapping natural language questions to reasoning steps that align with Sema-SQL’s operator algebra, and (3) precise UDF synthesis—generating LLM UDFs that correctly capture query semantics while ensuring executability within HRA. Rather than requiring fine-tuning, Sema-SQL leverages LLMs’ generalization capabilities through an in-context learning framework with three key components (Figure 5): (1) Semantic Data Model 𝑆: We transform the database schema into a semantic representation that encodes column semantics, table relationships, and domain constraints to ensure accurate data usage in the generated query. (2) Question Decomposition I: We decompose the user question into reasoning steps. Each step identifies which operator to use and what parameters to apply, continuing until the query task is complete. (3) Instructions and Exemplars E: We provide explicit instructions for accurate LLM UDF generation, along with examples that demonstrate how to correctly integrate UDFs within HRA queries. We formalize the query generation problem as follows: Problem 3.1 (Query Generation). Given a natural language question q and a relational database 𝐷, Sema-SQL constructs a prompt comprising: a semantic data model S, a question decomposition I, and an example set E. We then synthesize an HRA query via in-context learning using an LLM 𝑀𝑞 : 𝜙ˆ = arg max P𝑀𝑞 (𝜙 | q, S, I, E) 𝜙

We next present the methodology for constructing each component to enable effective query generation.

3.1

Semantic Data Model

To enable effective natural language querying, the LLM must understand the structure and semantics of the underlying database through an appropriate schema representation. Data Definition Language (DDL) schemas are the most commonly used representation, defining tables and columns through their structural properties. However, DDL lacks descriptive information such as table and column explanations. To address this limitation, many text-to-SQL systems propose enhanced schema representations [16, 51], while benchmarks such as BIRD [27] incorporate database description files to explain abbreviated names and terminologies. In Sema-SQL, we propose a hierarchical semantic data model that organizes database information as a YAML configuration, providing a compact and structured representation for both users and LLMs. This model is automatically constructed from database metadata and description files, incorporating three key components: (a) Table Schemas: Each table and view is represented with its name, description, and column specifications. For each column, we specify: • Name: The column identifier from the database metadata. • Data type: The SQL type (e.g., INTEGER, VARCHAR), enabling type-appropriate operations and preventing errors. • Sample values: Three representative values from the actual data (e.g., 2014-09-14 00:00:00.0 for timestamps) that demonstrate formatting conventions and data patterns.

Sema-SQL : Extending Relational Queries with Large Language Models

• Description: A natural language explanation of the column’s meaning and constraints (e.g., primary keys). (b) Relationships: Explicit specifications of table relationships through foreign key constraints and join conditions. These serve two purposes: (1) guiding the LLM toward valid join paths during query generation, and (2) enabling the system to leverage efficient structural joins over expensive semantic joins when appropriate relational constraints exist. (c) Domain Notes: Domain-specific knowledge capturing business rules and context: • Computation rules: Application-specific formulas and calculation methods (e.g., derived metrics). • Semantic mappings: Correspondences between natural language expressions and database schema elements (e.g., "revenue" maps to price * quantity). • Terminology: Definitions of technical terms and business concepts relevant to the domain. This component enables the LLM to apply domain-specific knowledge appropriately, distinguishing specialized business rules from general reasoning. Users can extend the model with additional domain knowledge as needed. Semantic Data Model Filtering. During query generation, Sema-SQL filters the semantic data model to reduce context size and improve accuracy. Given a semantic data model S comprising table schemas, relationships, and domain notes, Sema-SQL identifies the relevant subset S ′ needed to answer the user’s question. We employ an LLM to identify relevant columns. The LLM interprets column semantics using their descriptions and sample values, resolves terminology between questions and schema using domain notes, and identifies columns required by computation rules. The filtered model S ′ retains all selected columns along with any domain notes referenced during selection. Beyond explicitly mentioned columns, the LLM also includes entity-identifying columns for semantic reasoning—for example, when the question asks about “players from Germany” without a nationality column present in the database, it retains player surname and given name to enable LLMbased inference. Once relevant columns are identified, we extract the minimal set of relationships that connect the tables containing these columns, ensuring valid join paths in the generated query.

3.2

Question Decomposition

To generate executable HRA queries from complex user questions, we decompose questions into structured reasoning steps aligned with Sema-SQL’s operator algebra. Inspired by the ReAct [55] reasoning paradigm, we provide the LLM with Sema-SQL’s operator documentation and the semantic data model, then prompt it to iteratively select operators and determine their parameters until the query intent is satisfied. We format operator documentation as structured descriptions. Each operator specification includes its semantic description, parameter constraints, and usage examples. For instance, semantic_ projection describes its capability to extract implicit attributes via LLM inference, specifies parameters including a source relation, input columns, and a target column name, and provides examples illustrating when semantic projection is necessary versus when standard projection suffices.

The decomposition process begins with query intent identification. The LLM analyzes the natural language question to determine its computational goal, such as aggregation (e.g., counting, averaging), filtering (e.g., subset selection), ranking (e.g., top-𝑘 retrieval), or existence checking. This identified intent acts as a termination criterion—the LLM continues composing operators until the resulting decomposition produces outputs matching this intent. At each reasoning step, the LLM selects an operator from the available catalog and determines its parameters by consulting the semantic data model. Each step outputs a natural language description of the operator and its application to the data. For semantic operators, the LLM also provides explicit justification, as these operations are substantially more expensive due to LLM inference costs. This encourages judicious use of semantic extensions—invoking them only when queries need information absent from the schema or require operations beyond standard relational algebra. Consider the example query in Figure 3: "How many test takers are there at the school/s in a county with population over 2 million?" The question decomposition yields: (1) Semantic Projection: Extract the population for each county in Table schools. Justification: Population is not stored in the database and must be inferred from county names. (2) Select: Filter Table [#1] where population > 2,000,000. (3) Join: Join Table [#2] with Table satscores on cds = CDSCode. (4) Aggregate: Sum NumTstTakr from Table [#3] to compute the total number of test takers.

3.3

Instructions and Exemplars

Beyond the semantic data model and question decomposition, SemaSQL requires carefully designed in-context instructions and exemplars to ensure accurate UDF synthesis and integration. We employ two complementary strategies: (1) Contrastive Prompting. The natural language expression 𝑙 in LLM UDFs must precisely capture query semantics. Since Sema-SQL automatically constructs prompts from 𝑙 and input data 𝑇 [𝐶] (Definition 2.1), ambiguous expressions can produce erroneous or unstructured outputs that fail to execute correctly. To address this, we provide paired examples contrasting precise and ambiguous expressions. For instance, is_R1_research_university (precise) versus is_prestigious (ambiguous), or extract_population (precise) versus get_info (ambiguous). For operators requiring specific output types (e.g., integers for semantic projection), we explicitly instruct the LLM to include type annotations in 𝑙. (2) End-to-End Query Exemplars. We curate five representative question-query pairs that balance coverage and prompt efficiency. These exemplars span varying complexity (2–6 operators, up to 4 tables) and collectively cover all operator types in Sema-SQL’s algebra. We include examples for complex query patterns such as comparative aggregations (AVG(T1.val) > AVG(T2.val)) and queries combining multiple semantic operations to guide correct formulation.

4

QUERY OPTIMIZATION

Generated queries may be suboptimal in execution efficiency. Our cost optimization framework jointly accounts for LLM operation

Yin Lin, Tianjing Zeng, Zhongjun Ding, Rong Zhu, Bolin Ding∗ , H. V. Jagadish§ , Jingren Zhou

𝑣

Agg: Count(driverId) LLM selection: {d.nationality} is Asian

Join LLM selection: {d.nationality} is Asian

Select: r.name = … & r.year = …

Table: drivers

Table: races

(1): Original query plan

Agg: Count(driverId)

𝑆!

𝑐

Join Select: r.name = … & r.year = …

Table: drivers

Table: races

(2): Query plan with lazy LLM evaluation

Figure 6: Example: query optimization with lazy LLM evaluation. costs and relational database operation costs, leveraging symbolic execution [50] to ensure plan equivalence across transformations. The optimization process first parses the HRA query into a logical plan, during which Sema-SQL’s parser validates syntax and verifies that all referenced tables and columns exist in the database. Definition 4.1 (Query Plan). A query plan Q = (𝑉 , 𝐸, 𝑟 ) is a rooted tree where 𝑉 = {op1, op2, . . . , op𝑘 } is the set of operator nodes, 𝐸 ⊆ 𝑉 × 𝑉 is a set of directed edges representing data flow from child to parent operators, and 𝑟 ∈ 𝑉 is the root operator that produces the final query result. Each node in the query tree corresponds to either a relational operator or a semantic operator that incorporates an LLM UDF to perform language-based functions. Problem Statement. Given a query plan Q = (𝑉 , 𝐸, 𝑟 ) as defined in Definition 4.1, its execution cost (estimated runtime) can be represented as: ∑︁ ∑︁ cost(Q) = costsql (𝑣) + costllm (𝑣), 𝑣 ∈D

𝑣 ∈M

where D ⊆ 𝑉 is the set of relational operators and M ⊆ 𝑉 is the set of semantic operators in Q. Let P(Q) denote the set of all query plans that are semantically equivalent to Q. The objective of query optimization is to identify an optimal plan that satisfies: Q̂ = arg ′min cost(Q ′ ). Q ∈P( Q )

Identifying Q̂ is NP-hard, and traditional DBMS cost models and optimization heuristics do not account for the distinct cost characteristics of LLM operations. For instance, predicate pushdown—which moves selection predicates closer to input tables—increases costs for semantic selections by requiring an LLM invocation per input row. Deferring such operators to process smaller intermediate results often reduces LLM invocations and overall cost. Our query optimization builds on two insights. First, traditional DBMS optimizations can still reduce costsql for relational operators in Q. Second, strategically placing LLM UDFs later in the query plan—where they operate on smaller inputs—can reduce costllm . Based on these insights, Sema-SQL introduces a two-phase optimization strategy. Phase one applies standard relational optimizations (e.g., predicate pushdown, join ordering) to minimize intermediate result sizes. Phase two uses a cost-based algorithm to determine optimal LLM UDF placement given the optimized relational plan skeleton. Compared with optimization strategies that jointly consider relational and expensive operators [7, 40], our approach achieves a more tractable search space by first leveraging mature relational query optimization techniques, then strategically positioning expensive semantic operators.

Lazy LLM Evaluation. We define the problem as follows: Problem 4.1 (LLM UDF Placement). Given a query plan Q = (𝑉 , 𝐸, 𝑟 ) and a set of semantic operators M ⊆ 𝑉 that incorporate LLM UDFs, the task is to find a semantically equivalent plan Q ′ that minimizes cost(Q ′ ) by optimally placing the operators in M within the query plan. Consider an example using a Formula 1 dataset to answer "How many Asian drivers competed in the 2008 Malaysian Grand Prix?". The original plan (Figure 6 (1)) applies an LLM-based semantic selection on the nationality column of the drivers table. By deferring the execution of this semantic selection (Figure 6 (2)), we avoid expensive LLM invocations on all drivers and instead evaluate only the subset of drivers who actually participated in the specified race, thereby reducing overall execution cost. To solve Problem 4.1, we first define our cost model that unifies LLM invocation costs and relational operation costs. Definition 4.2 (Query Cost Model). For a query plan Q, the execution cost of an operator op ∈ Q is defined as follows: Unary operators: cost(op𝑇 ) = 𝛽 op × |𝑇 |

(1)

where 𝛽 op is the average cost coefficient for operator op to process each tuple, and |𝑇 | denotes the cardinality of the input relation 𝑇 . Binary operators: cost(op𝐿,𝑅 ) = 𝛽 op × 𝑓 (|𝐿|, |𝑅|)

(2)

where 𝐿 and 𝑅 are the left and right input relations, and 𝑓 : N × N → R+ is a function that depends on the algorithm used by the operator. The cost coefficient 𝛽 op captures the per-tuple execution cost. For relational operators, this includes disk I/O, CPU processing, and memory access costs [37]. For semantic operators, 𝛽 op estimates model inference overhead based on token consumption (input/output) and per-token processing time. We obtain initial estimates of 𝛽 op and operator selectivity through workload sampling for each supported UDF type, which users can optionally refine based on observed performance. For cardinality estimation, we adopt the standard predicate independence assumption [43]. Algorithm 1 presents our approach. We use a memoization table 𝑐𝑜𝑠𝑡 ∗ [𝑣, 𝑆] that stores the minimum cost of executing the query subplan rooted at node 𝑣 with semantic operator set 𝑆. The algorithm processes nodes in bottom-up order (line 1). For leaf nodes, we initialize 𝑐𝑜𝑠𝑡 ∗ [𝑣, ∅] to the table access cost (lines 3-4). For each internal node 𝑣, we consider all possible subsets 𝑆 ⊆ M𝑣 of semantic operators (lines 5-6). For any subset 𝑆, let 𝑆 𝑣 ⊆ 𝑆 denote semantic operators repositioned to execute immediately under node 𝑣 (line 7). We only consider valid placements 𝑆 𝑣 that preserve plan equivalence. Here, cost𝑆 (𝑣) represents the execution cost of node 𝑣 with operator set 𝑆 in its subtree, and cost𝑣,𝑆 (𝑆 𝑣 ) represents the cost of executing operators 𝑆 𝑣 under node 𝑣. For unary nodes, we find the optimal subset 𝑆 𝑣 ⊆ 𝑆 to place under 𝑣 that minimizes total cost (lines 8-9). For binary nodes, we find the optimal partition of the operators in 𝑆 among the left child (𝑆 ℓ ), right child (𝑆𝑟 ), and those placed under 𝑣 (𝑆 𝑣 ) (lines 10-11). The algorithm returns the minimum cost and optimized plan Q ′ (line 12).

Sema-SQL : Extending Relational Queries with Large Language Models

Algorithm 1: Lazy LLM evaluation input : Query plan Q = (𝑉 , 𝐸, 𝑟 ), set of semantic operators M output : Optimal 𝑐𝑜𝑠𝑡 ∗ [𝑟, M] and corresponding query plan Q ′ foreach node 𝑣 ∈ Q in postorder traversal do // bottom-up order 3 if 𝑣 is a leaf (table initialization) then 4 𝑐𝑜𝑠𝑡 ∗ [𝑣, ∅ ] ← cost(𝑣) 5 foreach subset 𝑆 ⊆ M𝑣 do 6 // M𝑣 : semantic ops in subtree of 𝑣 7 // 𝑆 𝑣 : subset of 𝑆 placed immediately under 𝑣 8 if 𝑣 is unary with child 𝑐 then 9 𝑐𝑜𝑠𝑡 ∗ [𝑣, 𝑆 ] ←
min𝑆 𝑣 ⊆𝑆 𝑐𝑜𝑠𝑡 ∗ [𝑐, 𝑆 \𝑆 𝑣 ] +cost𝑣,𝑆 (𝑆 𝑣 ) +cost𝑆 (𝑣)

1

2

else if 𝑣 is binary with children ℓ, 𝑟 then 𝑐𝑜𝑠𝑡 ∗ [𝑣, 𝑆 ] ← min 𝑐𝑜𝑠𝑡 ∗ [ℓ, 𝑆 ℓ ] + 𝑆 ℓ ,𝑆𝑟 ,𝑆 𝑣 ⊆𝑆 disjoint, 𝑆 ℓ ∪𝑆𝑟 ∪𝑆 𝑣 =𝑆
𝑐𝑜𝑠𝑡 ∗ [𝑟, 𝑆𝑟 ] + cost𝑣,𝑆 (𝑆 𝑣 ) + cost𝑆 (𝑣)

10 11

12

return 𝑐𝑜𝑠𝑡 ∗ [𝑟, M] and the corresponding query plan Q ′ (1). Symbolic Tables 𝑇& , 𝑇% driverId

nationality

raceId

driverId

𝑣!

𝑣"

𝑣#

𝑣$

(2a). Execute 𝜎''( 𝑇&

(2b). Execute 𝑇& ⨝ 𝑇%

driverId nationality row-exist 𝑣!

𝑣"

driverId nationality raceId driverId row-exist

isAsian(𝑣" )

𝑣!

𝑣"

𝑣#

𝑣$

𝑣! == 𝑣$

(3). Execute 𝜎''( 𝑇& ⋈ 𝑇% / Execute 𝜎''( (𝑇& ⋈ 𝑇% ) driverId nationality raceId driverId row-exist 𝑣!

𝑣"

𝑣#

𝑣$

𝑣! == 𝑣$ && isAsian(𝑣" )

𝜎**+ 𝑇, ⋈ 𝑇- = 𝜎**+ (𝑇, ⋈ 𝑇- ) is satisfied. The two plans in Figure 6 are equivalent!

Figure 7: Verification for plan equivalence. The worst-case time complexity of the algorithm is 𝑂 (𝑘 · 2𝑚 ), where 𝑘 is the number of operators in the query plan and 𝑚 is the number of semantic operators. At each node, for each of the 𝑚 semantic operators, we have two choices: either reposition it immediately under node 𝑣 (𝑆 𝑣 ) or leave it in the subtree(s) below. To determine whether the transformation produces an equivalent plan, we employ symbolic execution [12, 42, 50, 53] with SMT solvers such as Z3 [14] to verify equivalence. We model LLM UDFs as uninterpreted functions [34]2 , enabling verification without executing the queries. We illustrate the algorithm using the example in Figure 6. The algorithm processes nodes in bottom-up order, updating the memoization table 𝑐𝑜𝑠𝑡 ∗ [𝑣, 𝑆] for each node 𝑣 and each subset 𝑆 of semantic operators. As shown in Figure 6(2), when processing the aggregation node 𝑣 with 𝑆 = {𝜎𝑙𝑙𝑚 }, the algorithm compares two possible 𝑆 𝑣 : (1) 𝑆 𝑣 = ∅, which keeps the semantic operator 𝜎𝑙𝑙𝑚 within the subtree, or (2) 𝑆 𝑣 = {𝜎𝑙𝑙𝑚 }, which repositions 𝜎𝑙𝑙𝑚 to execute immediately under 𝑣. If the second option yields a equivalent and more efficient plan, the optimization is applied. To verify plan equivalence of the two execution plans, we use symbolic execution to check 𝜎𝑙𝑙𝑚 (𝑇𝑑 ) ⊲⊳ 𝑇𝑟 = 𝜎𝑙𝑙𝑚 (𝑇𝑑 ⊲⊳ 𝑇𝑟 ). We first create symbolic tables 𝑇𝑑 and 𝑇𝑟 , each containing a single tuple with cell values represented as symbols 𝑣 1, 𝑣 2, 𝑣 3, 𝑣 4 , and use a rowexist indicator for each row to represent filtering conditions (Figure 2While LLMs may be stochastic in practice, we treat LLM UDFs as deterministic for

the purpose of verifying algebraic plan equivalence.

7). We then symbolically execute both query plans: (1) The original plan executes the semantic selection on table 𝑇𝑑 first, updating the row-exist indicator to isAsian(𝑣 2 ) (Figure 7(2a)), then executes the join. (2) The optimized plan executes the join first, producing a rowexist indicator 𝑣 1 == 𝑣 4 (Figure 7(2b)), then executes the semantic selection. As shown in Figure 7(3), the two plans yield equivalent outputs. While this verification is undecidable, the SMT solver provides sound results when it finds equivalence [1]. We revert to the original plan if the solver times out or returns unknown. UDF Rewrite. In addition to optimally placing LLM UDFs, we observe that certain LLM UDFs can be eliminated from runtime execution by converting them into equivalent SQL expressions. This applies to UDFs that process each row independently and always produce the same output for the same input, such as certain semantic selections and projections. For instance, consider an LLM 𝑙 with 𝑙 : "Is the user ({dob}) an Aquarius?" within a seUDF 𝑈𝑀 mantic selection. Using the LLM’s knowledge, we could synthesize the equivalent SQL condition strftime(’%m-%d’, dob) BETWEEN ’01-20’ AND ’02-18’. In Sema-SQL, we prompt an LLM to analyze the semantics of 𝑙 based on its natural language expression 𝑙, the each LLM UDF 𝑈𝑀 input column description, and sampled values. When the LLM determines that a UDF is both stateless and deterministic, it synthesizes an equivalent relational expression that can replace the semantic operator. Otherwise, we retain the original LLM UDF. Our evaluation shows that this technique often rewrites UDFs that perform comparisons against real-world constants or rule-based classifications Additional Optimization Opportunities. Our framework also creates opportunities for integrating orthogonal physical execution optimizations that could further reduce LLM inference costs. Model cascades [24, 36, 57] dynamically route queries to differentsized models based on task complexity, delegating simple tasks to smaller, faster models while reserving larger models for complex reasoning. Proxy models [36, 54] pre-filter candidates using cheaper models before invoking expensive models for final predictions, reducing unnecessary expensive inference calls. Prompt optimization [29] techniques reduce token counts either as preprocessing steps or through dynamic adaptation based on observed performance. Prompt caching [17, 23, 26, 32] stores and reuses attention states from frequently used prompt segments across similar invocations. This is particularly beneficial when applying the same LLM UDF with shared prompt prefixes to large datasets. We leave the integration of these techniques for future work.

5

QUERY EXECUTION

Sema-SQL integrates LLM UDFs into database query execution through a UDF executor. When encountering a semantic opera𝑙 (𝑇 [𝐶]), the UDF executor first constructs tor with LLM UDF 𝑈𝑀 prompts by instantiating operator-specific templates with the natural language expression 𝑙 and inputs from 𝑇 [𝐶]. For example, for the semantic filter with LLM UDF 𝑈𝑀isAsian (nationality), the executor generates prompts such as: "Does {Japanese} satisfy {isAsian}? Answer: yes/no" for each distinct value in the nationality column. The executor then issues parallel LLM calls for these prompts, which return predictions as (nationality, prediction)

Yin Lin, Tianjing Zeng, Zhongjun Ding, Rong Zhu, Bolin Ding∗ , H. V. Jagadish§ , Jingren Zhou

Algorithm 2: Nested-loop semantic join 𝑙 : Relations 𝐿, 𝑅, distinct join keys 𝐾1 , 𝐾2 , LLM UDF 𝑈𝑀

input output : Set of joinable key pairs 𝐽 1 𝐽 ← ∅ 2 foreach 𝑘 1 ∈ 𝐾1 do 3 foreach 𝑘 2 ∈ 𝐾2 do 𝑙 (𝑘 , 𝑘 ) returns True then 4 if 𝑈𝑀 1 2 5 𝐽 ← 𝐽 ∪ { ⟨𝑘 1 , 𝑘 2 ⟩ } 6

return 𝐽

Algorithm 3: Smart-batching semantic join 𝑙 input : Relations 𝐿, 𝑅, distinct join keys 𝐾1 , 𝐾2 , LLM UDF 𝑈𝑀 output : Set of joinable key pairs 𝐽 1 𝐽 ← ∅ 2 𝑠 ← sample(𝐾1 , 3) ∪ sample(𝐾2 , 3) 𝑙 3 𝑏 1 , 𝑏 2 ← 𝑀𝑏 (𝑠, |𝐾1 |, |𝐾2 |, 𝑈 ) // LLM determines batch size 𝑀 4 𝐵 1 ← partition(𝐾1 , 𝑏 1 ) 5 𝐵 2 ← partition(𝐾2 , 𝑏 2 ) 𝑖 6 foreach 𝐵 1 ∈ 𝐵 1 do 𝑗 7 foreach 𝐵 2 ∈ 𝐵 2 do 𝑙 𝑗 8 𝐽𝑖 𝑗 ← 𝑈𝑀batch (𝐵𝑖1 , 𝐵 2 ) // Single LLM call for each batch pair 9 𝐽 ← 𝐽 ∪ 𝐽𝑖 𝑗 10

return 𝐽

pairs. These pairs are then joined back to the original relation on the nationality column, and the filtered relation flows to the next operator in the query plan. To minimize redundant LLM invocations, the executor extracts distinct values from input columns before LLM processing for operators where deduplication preserves semantics (selection, projection, join, and top-k). Table 1 summarizes the UDF execution algorithms for each semantic operator in Sema-SQL. Smart-Batching for Semantic Join. Existing semantic operator systems [29, 36] often implement semantic joins using a nestedloop approach (Algorithm 2), which enumerates all possible pairs of distinct join keys from relations 𝐿 and 𝑅 (lines 2-3) and evaluates 𝑙 (line 4). This incurs each pair independently using the predicate 𝑈𝑀 O (|𝐾1 | · |𝐾2 |) LLM calls, becoming prohibitively expensive for large join relations. To improve join efficiency, a naive batching approach combines all |𝐾1 | keys from 𝐿 and all |𝐾2 | keys from 𝑅 into a single prompt, asking the LLM to identify and return all matching pairs in one call [18]. While this works for simple tasks with short text and small relations, it fails when: (1) the combined context exceeds the LLM’s effective context window, (2) complex semantic reasoning degrades with too many pairs in one prompt, or (3) parsing structured output becomes unreliable for large result sets. Sema-SQL introduces a smart-batching algorithm (Algorithm 3) that adaptively determines optimal batch sizes to balance cost and accuracy. The algorithm samples three rows from each relation (line 2) and invokes an LLM 𝑀𝑏 that analyzes: (1) join complex𝑙 requires simple ity—whether the semantic matching through 𝑈𝑀

text similarity (e.g., nationality-to-country) or deep semantic reasoning (e.g., matching research methodologies to grant requirements), (2) context length—the text length per row based on samples 𝑠 from each relation, and (3) data size—the cardinalities |𝐾1 | and |𝐾2 | of the input relations. Based on these factors, 𝑀𝑏 returns batch sizes 𝑏 1 and 𝑏 2 (line 3): larger batches (e.g., 𝑏 1 = 𝑏 2 = 10) for simple short-text joins to maximize cost savings, and smaller batches (down to 𝑏 1 = 𝑏 2 = 1) for complex or lengthy text to maintain accuracy. The algorithm then partitions each key set into batches of their respective sizes (lines 4-5) and processes each batch pair with a single LLM invocation (lines 6-9), reducing LLM calls to O (⌈|𝐾1 |/𝑏 1 ⌉ · ⌈|𝐾2 |/𝑏 2 ⌉). Consider joining 7 Formula 1 constructor nationalities with 32 circuit countries using semantic matching (e.g., “British” ↔ “UK”). The nested-loop approach requires 7 × 32 = 224 LLM calls. Smartbatching samples the input data and 𝑀𝑏 determines 𝑏 1 = 10 and 𝑏 2 = 10, recognizing this as a simple similarity-based matching task suitable for batching. The algorithm partitions the relations into ⌈7/10⌉ = 1 and ⌈32/10⌉ = 4 batches respectively. Processing 1 × 4 = 4 batch pairs plus 1 batch-sizing call yields just 5 total LLM invocations—a 45× reduction over nested-loop join. Conversely, for complex joins involving lengthy text or nuanced semantic reasoning, 𝑀𝑏 adaptively selects smaller batch sizes to preserve accuracy. By balancing between the nested-loop approach (accurate but expensive) and aggressive batching (efficient but error-prone), smartbatching achieves both cost savings and high prediction quality, ensuring efficient execution across diverse workloads.

6

EVALUATION

We conduct an experimental study to evaluate Sema-SQL’s performance and capabilities. We seek to answer the following questions: • RQ1: What capabilities does Sema-SQL enable that are challenging with traditional relational querying? We extended the tableaugmentation-generation (TAG) benchmark [6], which features data-analytics questions that require LLM-based semantic reasoning over relational queries. We systematically evaluated Sema-SQL’s ability to handle these queries and compared it against a set of baselines, including text-to-SQL systems [27] and state-of-the-art LLM-powered data processing systems [6, 18, 29, 58]. • RQ2: Can Sema-SQL automatically generate queries that integrate LLM UDFs, and how reliable is this process? We enhanced the benchmark with expert-calibrated ground-truth queries and evaluated generated queries for syntactic validity, semantic correctness, and executability. We performed an ablation study examining each component of our framework and its impact on accuracy. • RQ3: How effective is Sema-SQL’s query optimization? We compared the query execution latency and token usage of optimized versus unoptimized queries. • RQ4: How effective is the smart-batching algorithm for semantic join? We compared our smart-batching algorithm against the nested-loop join baseline, measuring LLM call reduction and execution performance. • RQ5: What is the cost efficiency of Sema-SQL? We analyzed token usage across query generation, optimization, and execution, identifying key factors influencing costs.

Sema-SQL : Extending Relational Queries with Large Language Models

Table 2: Comparison of baseline approaches. Methods

System Interface

Text2SQL HQDL BlendSQL

Natural Language Question LLM tables + SQL BlendSQL Query

Query Generation

Query Plan Optimization

Semantic Execution

✗a ✔ ✗ ✗

✗ ✗ ✗c ✔

✗ ✗b ✔ ✔{LLMValidate, LLMMap, LLMQA, LLMJoin} ✔{sem_filter, sem_map, sem_topk, sem_join, sem_agg} ✔{sem_filter, sem_map, sem_join, sem_agg} ✔LLM UDFs incorporated in selection, projection, join, top-𝑘 , and aggregation

LOTUS

Python (LOTUS API)

✗

✗

Palimpzest

Python (Palimpzest API)

✗

✔Cascade-style optimization

Sema-SQL

Natural Language Question

✔

✔Lazy LLM evaluation, UDF rewrite

a Generates only traditional SQL queries. b Supports only row-level LLM reasoning; cannot handle semantic joins or aggregations. c Rule-based plan transformations.

6.1

Experimental Setup

6.1.1 Question Corpus. We evaluated Sema-SQL on TAG [6], a state-of-the-art benchmark for assessing database queries that incorporate LLM reasoning. TAG extends the widely used text-to-SQL benchmark BIRD [27] by reformulating questions to require LLM capabilities for world knowledge and semantic reasoning over textual columns. For example, in the California Schools, a modified query adds an additional clause asking for schools that are in the Bay Area. The benchmark questions span 5 diverse domains from BIRD: California Schools, Debit Card Specializing, Formula One, Codebase Community, and European Football. These databases contain up to 13 relations, with the largest reaching 597.8 MB. TAG includes 60 queries covering three question types (match-based, comparison, and ranking) with expert-labeled ground truth, plus 20 aggregation queries that perform summarization over textual columns. Extending TAG. To enable more comprehensive evaluation, we extend TAG in two ways. First, we add explicit ground-truth queries. TAG provides only question-answer pairs without intermediate reasoning paths; we engaged three experienced database experts to construct analytical ground-truth queries for each question. This enables direct evaluation of automatically generated queries and independent verification of answer correctness. Second, we expand the benchmark to include reasoning patterns that commonly arise in real-world AI-powered data analytics [18, 27, 29, 36, 58] but are not covered in TAG: semantic joins (semantic matching across columns beyond string equivalence), semantic categorization (classification into categories not represented in the schema), information extraction (deriving structured attributes from free text), and computational reasoning (applying external knowledge to perform computations). We added 10 queries per pattern (40 total), introducing multi-hop reasoning, subqueries, and multiple LLM invocations to increase complexity beyond TAG’s original scope. We refer to this extended benchmark as TAG+. 6.1.2 Baselines. We compared the following data querying systems. Table 2 summarizes their characteristics. Text2SQL [27] uses an LLM to generate SQL queries from natural language questions, which are then executed in database engines. We adopt the BIRD prompt format with few-shot examples to generate executable queries with relational operations. HQDL [58] augments relational databases using LLMs for data imputation, allowing answers to beyond-database questions by filling in missing attributes with LLM-generated values. We specified target attributes and applied the same prompt as [58] to generate missing values via row-level LLM invocations. With the LLM-augmented tables, we constructed SQL queries to answer the questions.

BlendSQL [18] extends SQLite to support LLM functions, including LLMMap, LLMQA, and LLMJoin, which enable row-level data transformation, aggregation, and table joins. BlendSQL provides a query interface for users to write and execute queries in BlendSQL syntax. We evaluated it using expert-crafted scripts for each question. BlendSQL applies rule-based optimizations such as predicate pushdown and deferred LLM execution, but does not consider execution costs and uses test sets to verify query equivalence. LOTUS [36] implements semantic operators based on the DataFrame abstraction. Each operator is executed using optimized algorithms with statistical accuracy guarantees relative to a "gold algorithm". Users write Python programs using the LOTUS API to manually construct query plans. We implemented Python scripts for each question using LOTUS operators. LOTUS’s operator-level physical optimizations trade accuracy for efficiency; we disable them to focus on execution accuracy. LOTUS does not support logical query plan optimization. Palimpzest [29] implements semantic operators based on the DataFrame abstraction with a cascades-style optimizer that explores logical and physical implementations to discover a Pareto frontier for quality, cost, and latency trade-offs. Palimpzest requires users to manually write programs using its operators. We implemented Python scripts for each question using Palimpzest operators and configured the optimizer to maximize quality (max_quality policy) without cost or latency constraints, ensuring fair comparison of query execution accuracy. Sema-SQL automatically generates and executes HRA queries through cost-based optimization with lazy LLM evaluation and UDF rewriting, and employs specialized algorithms for executing semantic operators, such as smart-batching for semantic joins. 6.1.3 Implementation Details. All baseline methods used SQLite3 as the database engine, except LOTUS and Palimpzest, which used Pandas DataFrames. We evaluated all systems using four LLMs: GPT-5 [35], Claude Sonnet 4.5 [3], Gemini 3 [15], and an openweight model Qwen3-256B [49]. All LLM-based approaches had a 1-hour timeout per query and allowed up to 3 retries to handle API failures and malformed outputs. For reproducibility, we set the temperature to 0 unless otherwise stated. We set the degree of parallelism for LLM invocations to 10 for all applicable systems (BlendSQL, LOTUS, Palimpzest, and Sema-SQL).

6.2

Baseline Evaluation

6.2.1 End-to-End Query Performance. Table 3 presents the execution accuracy and token usage of all systems, where we interact with each system via its natural language or code interface as summarized in Table 2. For TAG+ questions, we consider results identical

Yin Lin, Tianjing Zeng, Zhongjun Ding, Rong Zhu, Bolin Ding∗ , H. V. Jagadish§ , Jingren Zhou

to ground truth as correct. For subjective tasks (e.g., summarizing textual comments or ranking schools by perceived promise), we use GPT-5 as an LLM judge to assess whether summarization outputs capture key information effectively, and whether ranking results demonstrate sound reasoning. LOTUS, Palimpzest, and Sema-SQL achieve the best accuracy, as their semantic operator designs better address query requirements. Among these, Sema-SQL is the only fully automated approach, while LOTUS and Palimpzest require experts to construct the query pipeline. Sema-SQL performs best with Claude Sonnet 4.5, which excels at query generation, and achieves comparable results to LOTUS and Palimpzest with GPT-5 and Gemini 3. With the open-weight LLM Qwen3-256B, Sema-SQL reaches 76.7% accuracy, demonstrating effective performance with open-weight models. Sema-SQL also achieves comparable token usage to LOTUS and Palimpzest despite requiring additional LLM invocations for automated query generation. This stems from efficient prompt design, query optimization, and smart-batching for semantic joins. LOTUS shows reduced accuracy on questions requiring LLM parametric knowledge due to its system prompt design, and timeouts on large join inputs from its nested-loop join implementation. Palimpzest shows weaker aggregation performance with Gemini 3, listing high-level information without meaningful summarization. BlendSQL’s lower execution accuracy stems from two factors: (1) batching multiple entries per LLM call increases errors, although this strategy improves token efficiency, and (2) its LLMMap function for semantic top-𝑘 and aggregation yields lower ranking and summarization performance. HQDL achieves relatively low accuracy and high token usage because its row-wise data imputation requires extensive LLM calls to fill missing columns in large relations. This imputation-then-query approach cannot leverage query optimization, causing timeouts on large inputs and failing to support queries requiring cross-row LLM reasoning such as pairwise ranking, aggregation, and joins. Text2SQL automatically synthesizes SQL queries but cannot handle questions beyond SQL’s capabilities. It performs well when reasoning can be expressed through relational operations but poorly on questions requiring LLM inference during execution. 6.2.2 Sema-SQL Error Analysis. Table 4 categorizes errors across three core model capabilities—instruction following, query understanding, and parametric knowledge—revealing how Sema-SQL’s design remains effective across diverse LLMs while highlighting opportunities for enhancement of open-weight models. Instruction following errors (1.7%–5.8%) reflect adherence to grammar and output specifications: Syntax errors involve grammar violations such as column hallucination or invalid UDF generation, while Parsing errors indicate a failure to produce correctly structured outputs. Claude 4.5 Sonnet excels with only 1.7% errors, while GPT5 shows the highest rate at 5.8%. Query understanding errors (5.0%–10.0%) arise from failures in question comprehension and query synthesis: Misaligned errors occur when the generated query does not match the natural language intent (e.g., counting wrong objects or missing filters); UDF errors stem from incorrect understanding of required input columns or inability to express operations accurately; Relational errors involve flawed predicates or join conditions. Qwen3-256B exhibits the

Table 3: Execution accuracy and token usage on TAG+. Sema-SQL achieves the highest accuracy among automated methods while remaining competitive with manual pipelines (▲ = best per model). Methods

Auto.

Models

Exec. Acc. (%)

Avg. Tokens

Text2SQL

✔

Claude 4.5 Sonnet GPT-5 Gemini 3 Qwen3-256B

32.5% 34.2% 25.0% 27.5%

1781.2 3076.4 4273.8 1836.3

HQDL

✗

Claude 4.5 Sonnet GPT-5 Gemini 3 Qwen3-256B

13.3% 12.5% 12.5% 11.7%

159126.9 92063.3 268573.7 82597.6

BlendSQL

✗

Claude 4.5 Sonnet GPT-5 Gemini 3 Qwen3-256B

68.3% 65.0% 70.0% 65.8%

4214.8 4206.8 3633.3 3179.5

LOTUS

✗

Claude 4.5 Sonnet GPT-5 Gemini 3 Qwen3-256B

80.0% 90.8% ▲ 83.3% ▲ 82.5%

19686.9 31833.6 46940.2 8218.8

Palimpzest

✗

Claude 4.5 Sonnet GPT-5 Gemini 3 Qwen3-256B

85.0% 85.0% 77.5% 85.0% ▲

39428.6 33939.7 35385.3 41723.5

Sema-SQL

✔

Claude 4.5 Sonnet GPT-5 Gemini 3 Qwen3-256B

89.2% ▲ 83.3% 81.7% 76.7%

29009.0 35125.1 45664.4 25394.8

Table 4: Error type breakdown on Sema-SQL by model capability. Error Type

Claude 4.5

GPT-5

Gemini 3

Qwen3-256B

Instruction Following Syntax Error Parsing Error

– 1.7%

3.3% 2.5%

1.7% 1.7%

1.7% 2.5%

Query Understanding Misaligned UDF Error Relational Error

1.7% 3.3% –

0.8% 2.5% 1.7%

4.2% 4.2% –

5.0% 4.2% 0.8%

Parametric Knowledge Factual Error

4.1%

5.8%

6.6%

9.1%

Total Errors

10.8%

16.7%

18.3%

23.3%

highest rate at 10.0%, suggesting it may benefit from task-specific fine-tuning to improve query understanding capabilities. Parametric knowledge errors (4.1%–9.1%) reflects world knowledge gaps and the quality of knowledge inference. Qwen3-256B’s 9.1% rate is 2.2× higher than Claude’s 4.1%, underscoring that retrieval augmentation or continued pretraining on domain-specific corpora could further elevate open-weight models to competitive performance levels.

6.3

Sema-SQL Performance Evaluation

6.3.1 Accuracy of Query Generation. We evaluated query generation accuracy across three dimensions: syntactic validity, semantic correctness, and executability (Problem 3.1). For semantic correctness, we compared the execution results of the LLM-generated queries against those of the ground-truth queries. Figure 9 demonstrates that Sema-SQL achieves highly reliable query generation across all models, with accuracy consistently above 85%. Claude 4.5 Sonnet achieves the highest accuracy at 93.3%, while Qwen3-256B achieves 85.8%. Syntactic errors (e.g., parsing

Sema-SQL : Extending Relational Queries with Large Language Models

Figure 8: Query generation accuracy.

90.0 76.7 64.2 64.2

60.8

65.8

65.0 63.3 52.5 52.5 Full System w/o Semantic Model w/o Semantic Data Model Filtering w/o Few-Shot Examples w/o Question Decomposition

2 × 102

Mean

102 6 × 101 4 × 101

105

Token Usage

1.7%

2.5% 10.0% 1.7%

90 80 70 60 50 40 30 20

Execution Time (s)

1.7% 8.3%

2.5% 5.0% 3.3%

Execution Accuracy (%)

1.7% 5.0%

62.9 45.1

Mean

6 × 104 4 × 104 3 × 104 2 × 104

25.0k

31.5k

Claude 4.5 Sonnet Qwen3-256B with Opt. w/o Opt. with Opt. w/o Opt. Figure 9: Ablation study of query generation Figure 10: Execution time and token usage comcomponents in execution accuracy. parison with and without query optimization.

failures and hallucinated columns) are detected by the Sema-SQL parser, whereas execution errors (e.g., value/type mismatches and other database exceptions) are detected by the UDF executor. When such errors are identified, Sema-SQL retries query generation using the resulting error message as feedback, up to a maximum retry limit. The remaining errors are predominantly semantic—queries that fail to capture precise intent—typically due to ambiguous question interpretations. Improvements in ambiguity resolution and schema grounding offer promising directions to address these. 6.3.2 Ablation Study of Prompt Components. To explore the effect of the key components in query generation—(1) semantic data model, (2) question decomposition, and (3) in-context examples—we conducted an ablation study on Claude 4.5 Sonnet (best performing) and Qwen3-256B (lowest performing) to assess the impact of each component on execution accuracy. Qwen3-256B is most sensitive to database representation. Removing either the semantic data model representation (compared to BIRD’s default schema format [27]) or semantic data model filtering decreases accuracy by 24.2%. Without these components, generated queries exhibit higher rates of column hallucinations and incorrect operator application. This sensitivity likely stems from Qwen3-256B’s shorter context length (∼32K tokens) and lower capability, making compact, relevant schema representation essential for performance. Claude 4.5 Sonnet benefits most from in-context examples. Question decomposition proves crucial for both models. Without it, direct mapping from natural language to HRA queries results in missing computation steps and incorrect semantic operator usage, highlighting the importance of explicit reasoning steps and detailed operator documentation for accurate query generation. 6.3.3 Effectiveness of Query Optimization. We assessed the impact of query optimization in Sema-SQL. Of the 120 benchmark queries, optimization transformed 33 query plans. The remaining queries were already optimal from the generation phase or contained LLM UDFs that could not be rewritten. Figure 10 reports query execution latency (in seconds) and LLM invocation costs for these queries under Claude 4.5 Sonnet. With optimization enabled, we achieved both runtime and cost reduction: average query execution time drops from 62.9 seconds to 45.1 seconds (28% reduction), while average token consumption decreases from 31.5K to 25.0K (21% reduction).

Analyzing the optimized plans versus their unoptimized variants reveals how each technique contributes to these improvements. Our two-phase optimization with lazy LLM evaluation optimally places LLM UDFs within query plans so they process smaller intermediate results, reducing LLM invocation costs. For instance, in the TAG+ query shown in Figure 6, our optimization repositions the UDF after the join predicate, reducing the input from 73 to 42 rows after the join filters irrelevant data. In another TAG+ query containing both a semantic selection and a semantic join, our optimization places the selection before the join, as the selection provides higher selectivity and lower per-row execution cost. UDF rewriting provides complementary benefits by replacing LLM invocations with equivalent SQL expressions. For example, the TAG+ query contains a semantic selection to determine if a county is in the Bay Area. Without optimization, this would require 57 separate LLM calls (one per row). UDF rewriting recognizes that this semantic condition can be expressed as a SQL predicate: County IN (’Alameda’, ’Contra Costa’, ’Marin’, ’San Francisco’, ’San Mateo’, ’Santa Clara’, ’Santa Cruz’, ’Solano’, ’Sonoma’). This transformation eliminates all 57 LLM calls during query execution, reducing both execution time and costs for this operation. 6.3.4 Smart-Batching for Semantic Joins. We evaluated our smartbatching against the nested-loop baseline widely used in existing systems [29, 36, 46], including LOTUS and Palimpzest. Figure 11 shows that across 10 benchmark join queries using Claude 4.5 Sonnet, smart-batching reduces LLM calls by 93.3% while maintaining 100% execution accuracy (other models show similar results). The algorithm’s adaptive behavior explains its effectiveness across diverse join scenarios. Figure 11 annotates batch sizes as [L:R], indicating the number of records processed per call from the left and right relations, respectively. For simple similaritybased joins with compact contexts—nationality-to-country matching (Joins 1, 2) and team-to-country mapping (Joins 7, 8)—the smartbatching algorithm selects large batch sizes (often processing entire tables in a single prompt), yielding up to 100× cost reductions without accuracy loss. Conversely, for joins requiring deep semantic reasoning—post-to-comment matching (Joins 4, 6) or comment-totag mapping (Join 5)—the algorithm dynamically reduces batch sizes or processes records individually. This adaptive fallback prevents the accuracy degradation that naive batching as in BlendSQL [18] would cause. For intermediate-complexity joins (Joins 3, 9, 10), batch sizes also scale proportionally with context lengths and problem complexity.

Yin Lin, Tianjing Zeng, Zhongjun Ding, Rong Zhu, Bolin Ding∗ , H. V. Jagadish§ , Jingren Zhou

# of LLM Calls

103 102

Avg reduction: 93.3%

[L:R] = Batch Sizes Nested Loop Smart-Batching [1:5]

101 [3:18]

[6:18]

[1:20]

[1:5] [5:50]

[5:3]

[6:50]

[11:11] [10:10]

100

Join1 Join2 Join3 Join4 Join5 Join6 Join7 Join8 Join9 Join10

Figure 11: Comparison for semantic join algorithms. Table 5: Average token cost efficiency per query for Sema-SQL. Phase

Claude Sonnet 4.5

GPT-5

Gemini 3

Qwen3-256B

Query Generation Query Optimization Query Execution

18331.9 1609.0 9068.1

20813.4 2014.7 12297.0

25021.1 1347.2 19296.1

16774.4 1333.1 7287.3

Total

29009.0

35125.1

45664.4

25394.8

Join 10 (1,000+ pairwise comparisons) exposes the nested-loop baseline’s scalability limitations: it causes end-to-end execution timeouts in LOTUS and incurs high execution overhead in Palimpzest due to excessive latency, while smart-batching consistently completes successfully with significantly lower overhead. 6.3.5 Cost Analysis. We reported Sema-SQL’s token usage across three phases of query processing (query generation, optimization, and execution) and examined the key factors influencing consumption. Table 5 shows that each query consumes 25K–46K tokens on average, with query generation accounting for 60–75% of total cost, execution consuming 20–35%, and optimization using only 3–8%. Query generation dominates token usage by processing the complete semantic data model, which scales with schema size. For instance, the European Football dataset (13 relations) consumes 4.9× more tokens than Debit Card Specializing (5 relations). Query optimization incurs low token consumption (under 2K tokens on average), requiring only UDF characteristic analysis and SQL synthesis from natural language expressions and input samples. Query execution costs correlate directly with input data volume and semantic processing context—larger inputs result in proportionally higher token consumption.

7

RELATED WORK

Hybrid Question Answering. Hybrid question answering addresses queries over both structured and unstructured data. LLMs excel at semantic processing but lack correctness guarantees for precise operations. SQL provides efficient, verifiable operations but cannot handle semantic ambiguity or reasoning across heterogeneous contexts. Hybrid systems combine structured relations with semistructured information including free-form text [9, 33, 36], LLM knowledge [33, 41, 58], and knowledge bases [52]. Retrievalaugmented generation (RAG) extends to tabular data [8, 21] and multi-hop reasoning [9], but remains limited to point-wise retrieval and simple filtering. This paper explores richer queries requiring coordinated relational operations and LLM reasoning [6]. Semantic Operator Systems. Recent work has explored integrating LLM functionalities to extend the scope of relational data processing. Several commercial DBMSs [5, 13, 19, 45, 46] enable

LLM inference within SQL execution. Academic research has also proposed systems that expose LLMs via declarative operator APIs to extend query languages. BINDER [10] provides a unified API for integrating LLM reasoning into languages like SQL and Python, while BlendSQL [18] introduces an SQLite extension with LLM functions for reasoning over multi-table databases. Several systems have implemented optimized LLM operations for specialized data analytical tasks. ZenDB [28], EVAPORATE [4], Galois [41], and HQDL [58] use LLMs to extract unstructured and semi-structured data into relational formats to support downstream analysis. SUQL [33] augments SQL with LLM operators to summarize free-form text and support conversational question answering. Recent systems including DocETL [44], Aryn [2], LOTUS [36], Palimpzest [30, 31, 40], and ThalamusDB [22] provide declarative semantic operators for AI workloads over unstructured data. They integrate LLMs as native operators in data pipelines, enabling users to perform complex semantic operations—such as extraction, classification, transformation, and joining—on text, documents, and multi-modal data through high-level abstractions. These systems often require manual query composition, and only a few works [10, 31, 33] attempt automated synthesis. However, these approaches support limited operator types and lack a comprehensive solution for end-to-end query processing. Sema-SQL provides fully automated processing across all stages—query generation, optimization, and execution—for complex queries requiring both relational and semantic processing. Semantic Query Optimization Approaches. Existing frameworks take different approaches to optimizing the execution of semantic queries: (1) Proxy-based execution optimization. LOTUS [36] predefines a set of "gold algorithms"—the ideal but expensive implementations of semantic operators using powerful models. It then optimizes execution by approximating them with cheaper alternatives. Similarly, [54] injects lightweight proxy models before expensive UDFs to filter unlikely inputs early. While these approaches effectively optimize physical operator execution, they require users to manually design the query pipeline, where join ordering and operator placement critically impact execution costs. (2) Rule-based optimization. Systems like [18, 33, 46, 47] apply predetermined transformation rules such as predicate pushdown and deferred LLM execution, regardless of data characteristics. This approach has two key limitations: it may miss valuable optimization opportunities, and certain rules may not always yield optimal performance. (3) LLM-based logical plan rewriting. DocETL [44] uses LLM agents to rewrite query plans, employing validation agents to select plans based on accuracy metrics. Aryn [2] translates natural language queries to semantic plans via Luna, relying on human verification through plan inspection and modification. Nirvana [59] applies LLM-based rewriting with natural-language rules for logical optimization and employs a cost-aware physical optimizer for LLM backend selection. However, these approaches require additional verification mechanisms due to the inherent unreliability of LLMs. (4) Cost-based optimization. Palimpzest employs Abacus [40], a Cascade-style optimizer that estimates operator cost, latency, and quality through sampling. Abacus performs Pareto optimization to balance multiple objectives (e.g., maximizing quality under cost constraints). In contrast, Sema-SQL leverages traditional DBMS

Sema-SQL : Extending Relational Queries with Large Language Models

optimizations and a cost-based algorithm to determine the optimal placement of expensive LLM UDFs, achieving efficient plans through a tractable search space.

8

CONCLUSION

We present Sema-SQL, a system that automatically translates natural language questions into efficient queries combining relational operations with LLM-based semantic reasoning. Sema-SQL introduces Hybrid Relational Algebra (HRA), which extends relational algebra with semantic operators via LLM UDFs. The system provides an end-to-end pipeline: in-context learning for query generation, cost optimization accounting for expensive LLM operations, and efficient execution algorithms including smart-batching for semantic joins. Experiments show that Sema-SQL significantly enhances querying capabilities compared to baseline approaches.

REFERENCES [1] S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995. [2] E. Anderson, J. Fritz, A. Lee, B. Li, M. Lindblad, H. Lindeman, A. Meyer, P. Parmar, T. Ranade, M. A. Shah, B. Sowell, D. Tecuci, V. Thapliyal, and M. Welsh. The design of an llm-powered unstructured analytics system. CoRR, abs/2409.00847, 2024. [3] Anthropic. Introducing claude sonnet 4.5. https://www.anthropic.com/ news/claude-sonnet-4-5, September 2025. Model identifier: claude-sonnet-4-520250929. Accessed: 2026-01-03. [4] S. Arora, B. Yang, S. Eyuboglu, A. Narayan, A. Hojel, I. Trummer, and C. Ré. Language models enable simple systems for generating structured views of heterogeneous data lakes. Proc. VLDB Endow., 17(2):92–105, 2023. [5] B. Bamiduro and A. Challa. Large language models for sentiment analysis with amazon redshift ml (preview). https://aws.amazon.com/blogs/bigdata/large-language-models/-for-sentiment-analysis-with-amazon-redshiftml-preview/. [6] A. Biswal, L. Patel, S. Jha, A. Kamsetty, S. Liu, J. E. Gonzalez, C. Guestrin, and M. Zaharia. Text2sql is not enough: Unifying AI and databases with TAG. CoRR, abs/2408.14717, 2024. [7] S. Chaudhuri and K. Shim. Optimization of queries with user-defined predicates. In VLDB’96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India, pages 87–98. Morgan Kaufmann, 1996. [8] P. B. Chen, Y. Zhang, and D. Roth. Is table retrieval a solved problem? exploring join-aware multi-table retrieval. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2024, Bangkok, Thailand, August 11-16, 2024, pages 2687–2699. Association for Computational Linguistics, 2024. [9] W. Chen, H. Zha, Z. Chen, W. Xiong, H. Wang, and W. Y. Wang. Hybridqa: A dataset of multi-hop question answering over tabular and textual data. In Findings of the Association for Computational Linguistics: EMNLP 2020, Online Event, 16-20 November 2020, volume EMNLP 2020 of Findings of ACL, pages 1026–1036. Association for Computational Linguistics, 2020. [10] Z. Cheng, T. Xie, P. Shi, C. Li, R. Nadkarni, Y. Hu, C. Xiong, D. Radev, M. Ostendorf, L. Zettlemoyer, N. A. Smith, and T. Yu. Binding language models in symbolic languages. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. [11] V. Christophides, V. Efthymiou, T. Palpanas, G. Papadakis, and K. Stefanidis. An overview of end-to-end entity resolution for big data. ACM Comput. Surv., 53(6):127:1–127:42, 2021. [12] S. Chu, D. Li, C. Wang, A. Cheung, and D. Suciu. Demonstration of the cosette automated SQL prover. In Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD Conference 2017, Chicago, IL, USA, May 14-19, 2017, pages 1591–1594. ACM, 2017. [13] Databricks. Ai functions on databricks. https://docs.databricks.com/en/index. html. [14] L. De Moura, N. Bjørner, et al. Z3 theorem prover, 2008. Version 4.x. [15] G. DeepMind. Gemini 3: Introducing the latest gemini ai model from google. https://blog.google/products/gemini/gemini-3/, November 2025. Accessed: 202601-03. [16] Y. Gao, Y. Liu, X. Li, X. Shi, Y. Zhu, Y. Wang, S. Li, W. Li, Y. Hong, Z. Luo, J. Gao, L. Mou, and Y. Li. Xiyan-sql: A multi-generator ensemble framework for text-to-sql. CoRR, abs/2411.08599, 2024.

[17] I. Gim, G. Chen, S. Lee, N. Sarda, A. Khandelwal, and L. Zhong. Prompt cache: Modular attention reuse for low-latency inference. In P. B. Gibbons, G. Pekhimenko, and C. D. Sa, editors, Proceedings of the Seventh Annual Conference on Machine Learning and Systems, MLSys 2024, Santa Clara, CA, USA, May 13-16, 2024. mlsys.org, 2024. [18] P. Glenn, P. Dakle, L. Wang, and P. Raghavan. Blendsql: A scalable dialect for unifying hybrid question answering in relational algebra. In L. Ku, A. Martins, and V. Srikumar, editors, Findings of the Association for Computational Linguistics, ACL 2024, Bangkok, Thailand and virtual meeting, August 11-16, 2024, pages 453–466. Association for Computational Linguistics, 2024. [19] Google. Bigframes ai operator tutorial. http://github.com/googleapis/pythonbigquery-dataframes/blob/main/notebooks/experimental/ai_operators.ipynb. [20] Y. He, K. Ganjam, and X. Chu. SEMA-JOIN: joining semantically-related tables using big table corpora. Proc. VLDB Endow., 8(12):1358–1369, 2015. [21] J. Herzig, T. Müller, S. Krichene, and J. M. Eisenschlos. Open domain question answering over tables via dense retrieval. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2021, Online, June 6-11, 2021, pages 512–519. Association for Computational Linguistics, 2021. [22] S. Jo and I. Trummer. Thalamusdb: Approximate query processing on multimodal data. Proc. ACM Manag. Data, 2(3):186, 2024. [23] J. Juravsky, B. C. A. Brown, R. Ehrlich, D. Y. Fu, C. Ré, and A. Mirhoseini. Hydragen: High-throughput LLM inference with shared prefixes. CoRR, abs/2402.05099, 2024. [24] D. Kang, E. Gan, P. Bailis, T. Hashimoto, and M. Zaharia. Approximate selection with guarantees using proxies. Proc. VLDB Endow., 13(11):1990–2003, 2020. [25] H. Köpcke and E. Rahm. Frameworks for entity matching: A comparison. Data Knowl. Eng., 69(2):197–210, 2010. [26] W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. Gonzalez, H. Zhang, and I. Stoica. Efficient memory management for large language model serving with pagedattention. In J. Flinn, M. I. Seltzer, P. Druschel, A. Kaufmann, and J. Mace, editors, Proceedings of the 29th Symposium on Operating Systems Principles, SOSP 2023, Koblenz, Germany, October 23-26, 2023, pages 611–626. ACM, 2023. [27] J. Li, B. Hui, G. Qu, J. Yang, B. Li, B. Li, B. Wang, B. Qin, R. Geng, N. Huo, X. Zhou, C. Ma, G. Li, K. C. Chang, F. Huang, R. Cheng, and Y. Li. Can LLM already serve as A database interface? A big bench for large-scale database grounded text-to-sqls. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. [28] Y. Lin, M. Hulsebos, R. Ma, S. Shankar, S. Zeighami, A. G. Parameswaran, and E. Wu. Towards accurate and efficient document analytics with large language models. CoRR, abs/2405.04674, 2024. [29] C. Liu, M. Russo, M. Cafarella, L. Cao, P. B. Chen, Z. Chen, M. Franklin, T. Kraska, S. Madden, R. Shahout, et al. Palimpzest: Optimizing ai-powered analytics with declarative query processing. In Proceedings of the Conference on Innovative Database Research (CIDR), page 2, 2025. [30] C. Liu, M. Russo, M. J. Cafarella, L. Cao, P. B. Chen, Z. Chen, M. J. Franklin, T. Kraska, S. Madden, and G. Vitagliano. A declarative system for optimizing AI workloads. CoRR, abs/2405.14696, 2024. [31] C. Liu, G. Vitagliano, B. Rose, M. Printz, D. A. Samson, and M. Cafarella. Palimpchat: Declarative and interactive ai analytics. In Companion of the 2025 International Conference on Management of Data, pages 183–186, 2025. [32] S. Liu, A. Biswal, A. Cheng, X. Mo, S. Cao, J. E. Gonzalez, I. Stoica, and M. Zaharia. Optimizing LLM queries in relational workloads. CoRR, abs/2403.05821, 2024. [33] S. Liu, J. Xu, W. Tjangnaka, S. J. Semnani, C. J. Yu, and M. Lam. SUQL: conversational search over structured and unstructured data with large language models. In Findings of the Association for Computational Linguistics: NAACL 2024, Mexico City, Mexico, June 16-21, 2024, pages 4535–4555. Association for Computational Linguistics, 2024. [34] Microsoft. Uninterpreted functions and constants. https://microsoft.github.io/ z3guide/docs/logic/Uninterpreted-functions-andconstants/, 2023. Z3 Guide. [35] OpenAI. Gpt-5. https://openai.com/index/introducing-gpt-5/, August 2025. Accessed: 2026-01-03. [36] L. Patel, S. Jha, M. Pan, H. Gupta, P. Asawa, C. Guestrin, and M. Zaharia. Semantic operators and their optimization: Enabling llm-based data processing with accuracy guarantees in lotus. Proceedings of the VLDB Endowment, 18(11):4171–4184, 2025. [37] PostgreSQL Global Development Group. Using EXPLAIN. PostgreSQL Global Development Group, 2015. PostgreSQL Documentation, Version 9.0. [38] M. Pourreza, H. Li, R. Sun, Y. Chung, S. Talaei, G. T. Kakkar, Y. Gan, A. Saberi, F. Ozcan, and S. Ö. Arik. CHASE-SQL: multi-path reasoning and preference optimized candidate selection in text-to-sql. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025. [39] M. Pourreza and D. Rafiei. DIN-SQL: decomposed in-context learning of text-tosql with self-correction. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023.

Yin Lin, Tianjing Zeng, Zhongjun Ding, Rong Zhu, Bolin Ding∗ , H. V. Jagadish§ , Jingren Zhou

[40] M. Russo, S. Sudhir, G. Vitagliano, C. Liu, T. Kraska, S. Madden, and M. J. Cafarella. Abacus: A cost-based optimizer for semantic operator systems. CoRR, abs/2505.14661, 2025. [41] M. Saeed, N. D. Cao, and P. Papotti. Querying large language models with SQL. In Proceedings 27th International Conference on Extending Database Technology, EDBT 2024, Paestum, Italy, March 25 - March 28, pages 365–372. OpenProceedings.org, 2024. [42] M. Schlaipfer, K. Rajan, A. Lal, and M. Samak. Optimizing big-data queries using program synthesis. In Proceedings of the 26th Symposium on Operating Systems Principles, Shanghai, China, October 28-31, 2017, pages 631–646. ACM, 2017. [43] P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston, Massachusetts, USA, May 30 - June 1, pages 23–34. ACM, 1979. [44] S. Shankar, T. Chambers, T. Shah, A. G. Parameswaran, and E. Wu. Docetl: Agentic query rewriting and evaluation for complex document processing. Proc. VLDB Endow., 18(9):3035–3048, 2025. [45] Snowflake. Large language model (llm) functions (snowflake cortex) | snowflake documentation. https://docs.snowflake.com/user-guide/snowflake-cortex/aisql. [46] A. Sukumaran. Llm with vertex ai only using sql queries in bigquery. https://cloud.google.com/blog/products/ai-machine-learning/llm-withvertex-ai-only-using-sql-queries-in-bigquery. [47] J. Sun, G. Li, P. Zhou, Y. Ma, J. Xu, and Y. Li. Agenticdata: An agentic data analytics system for heterogeneous data. CoRR, abs/2508.05002, 2025. [48] S. Talaei, M. Pourreza, Y. Chang, A. Mirhoseini, and A. Saberi. CHESS: contextual harnessing for efficient SQL synthesis. CoRR, abs/2405.16755, 2024. [49] Q. Team. Qwen3 technical report. arXiv preprint arXiv:2505.09388, May 2025. [50] M. Veanes, P. Grigorenko, P. de Halleux, and N. Tillmann. Symbolic query exploration. In Formal Methods and Software Engineering, 11th International Conference on Formal Engineering Methods, ICFEM 2009, Rio de Janeiro, Brazil, December 9-12, 2009. Proceedings, volume 5885 of Lecture Notes in Computer Science, pages 49–68. Springer, 2009.

[51] B. Wang, C. Ren, J. Yang, X. Liang, J. Bai, L. Chai, Z. Yan, Q. Zhang, D. Yin, X. Sun, and Z. Li. MAC-SQL: A multi-agent collaborative framework for text-to-sql. In Proceedings of the 31st International Conference on Computational Linguistics, COLING 2025, Abu Dhabi, UAE, January 19-24, 2025, pages 540–557. Association for Computational Linguistics, 2025. [52] S. Wu, S. Zhao, M. Yasunaga, K. Huang, K. Cao, Q. Huang, V. N. Ioannidis, K. Subbian, J. Y. Zou, and J. Leskovec. Stark: Benchmarking LLM retrieval on textual and relational knowledge bases. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, 2024. [53] C. Yan, Y. Lin, and Y. He. Predicate pushdown for data science pipelines. Proc. ACM Manag. Data, 1(2):136:1–136:28, 2023. [54] Z. Yang, Z. Wang, Y. Huang, Y. Lu, C. Li, and X. S. Wang. Optimizing machine learning inference queries with correlative proxy models. Proc. VLDB Endow., 15(10):2032–2044, 2022. [55] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), 2023. [56] T. Yu, R. Zhang, K. Yang, M. Yasunaga, D. Wang, Z. Li, J. Ma, I. Li, Q. Yao, S. Roman, Z. Zhang, and D. R. Radev. Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-sql task. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 - November 4, 2018, pages 3911–3921. Association for Computational Linguistics, 2018. [57] M. Yue, J. Zhao, M. Zhang, L. Du, and Z. Yao. Large language model cascades with mixture of thoughts representations for cost-efficient reasoning. CoRR, abs/2310.03094, 2023. [58] F. Zhao, D. Agrawal, and A. E. Abbadi. Hybrid querying over relational databases and large language models. CoRR, abs/2408.00884, 2024. [59] J. Zhu, L. Chen, X. Ke, Z. Fang, T. Li, Y. Gao, and C. S. Jensen. Beyond relational: Semantic-aware multi-modal analytics with llm-native query optimization, 2025.

Related documents

• Databases with Missing Values that are Governed by Missingness Mechanisms#1043177
• Proof-of-Retention: A Framework for Auditable Cross-Organization Data Sharing#1043178
• AkasicMEM: Governed Enterprise Memory for Agents#1043179
• Spend Classification Without Leakage: An Evaluation Harness and What It Changed in a Deployed System#1043180
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#1043181