In the last few years, Large Language Models (LLMs) have been widely adopted for data science tasks such as data extraction. In this scenario, textual documents are fed in the context of the LLM - as in a RAG setting - and tabular data is extracted via declarative queries. However, LLMs often struggle with complex queries, resulting in low precision and recall. This challenge highlights the limitations of existing data processing assumptions when applied to LLM-based query execution. Traditional optimization techniques are exclusively cost-based, while LLMs also present challenges over the output quality, and rely on catalog metadata, unavailable in this context. Our results show that traditional query optimization principles fail to generate the best plans in terms of result quality. To address this issue, we present a novel approach for optimizing SQL query results by introducing techniques tailored for LLMs. We present Galois, an intermediary between SQL queries and LLMs, treating the latter as a storage layer. We extend traditional optimization strategies to incorporate alternative physical operators designed for LLM-based query execution. Given the absence of a conventional data catalog, we introduce confidence-based metadata collection techniques for query optimization. Our results demonstrate the efectiveness of using such metadata in logical and physical optimization, ultimately showing that Galois successfully balances the trade-of between result's quality and execution cost in querying textual documents.
Large Language Models (LLMs) have proved to be a valid solution in direct question answering
and data processing tasks [
The Problem with Data Outputs. Despite being able to process simple NL queries, more NL Natural Language Question What are name, size and population of European cities with more than 1M people and more than fifteen private hospitals?
Text to SQL SQL SQL Query SELECT name, size, population FROM EUCities WHERE population>1M, num_private_hospitals>15
GALOIS Prompt
Prompt Prompt LLM
Worst results
Most errors
More results
Some errors
Most results
Least errors
complex instances that require structured results as output often prove to be a challenge for
those models [
FROM EU_Cities
WHERE population > 1M AND num_private_hospitals > 15 improves results w.r.t. natural language, but still lacks correctness and completeness. These limitations underscore the inherent design constraints of LLMs. If prompted with queries that require complex reasoning, such as with multiple conditions or aggregates, the models are not able to produce a satisfactory result. Therefore, to get the best possible results, we argue that a database management system should be used to handle the query execution while using the LLM exclusively as a storage layer, as shown in the bottom part of Figure 1. Challenges. This approach comes with a series of challenges. First, when querying LLMs with SQL, a trade-of between the accuracy of the results and the execution costs must be considered. While direct execution of SQL queries comprises the most cost-efective approach, decomposing these queries into a sequence of small operator executions, akin to the plans in a DBMS, yields superior result quality. As a result the traditional optimization principles, primarily focused on cost, are only partially applicable. Additionally, LLMs do not provide access to crucial metadata such as schema details, column statistics or histograms, significantly complicating query optimization eforts.
The Framework. Galois [
n1 LLMScan h select name, country [...] from EUCities sopu LLM LnPiasabmroisen cPoourtnutgry. population # pvt hosp
France 20..15MM 196 N Madrid Spain 3.2M 20 p1 Filter-LLMScan ll swehleercet npaompuel,actioounn>tr1yM[..a.]nfdro#mpEvtUhCoistipe>s1 5 sauhP LLM MRnaaomdmreied coSIutpaanlyitnry pop23u..82laMMtion # pv2t30hosp liteecves1 swehleercet n#aFpmvietlt,hecoros-upLn>Lt1ry5M[.S..]cfaronm EUCities sh LLM Znuarmiceh country population # pvt hosp s u Utrecht NSewthitez.r. 00..34MM 1108 P
population > 1M AND # pvt hosp > 15 name country population # pvt hosp Madrid Spain 3.2M 20
Filter Filter <empty> name country population # pvt hosp MRaodmried SItpaalyin 23..82MM 230
Filter
population > 1M
name country population # pvt hosp
focusing on estimating the confidence of LLM output to bridge the gap typically filled by
catalog information. Experimental evaluations show the efectiveness of the proposed approach,
reporting improvements in result quality while maintaining a competitive edge in terms of
resource eficiency. While Galois can also handle querying the LLMs over their parametric
knowledge [
The core challenge is executing SQL queries that cannot be answered by existing databases
but can be resolved using textual documents. The goal is to feed the queries directly to the
LLM that acts as an extractor, returning structured data from unstructured text. This setting
combines traditional DBMS challenges (eficiency) with LLM-specific ones (output quality and
token cost). Traditional optimizations focused on performance fail to ensure high-quality results
with LLMs. A major limitation is the lack of a catalog. Traditional metadata (e.g., column stats)
nor LLM-specific metadata is readily available, yet both are essential for optimization. Our
solution enables dynamic data extraction from documents provided at runtime, leaving the
broader case of accessing LLM pretraining knowledge to the full paper [
Logical Level. In traditional DBMSs, logical optimization focuses on minimizing resource usage, such as CPU and memory. With LLMs, however, output quality becomes a key metric.
Consider query Q1 in the top part of Figure 2. The simplest logical plan uses a single prompt to retrieve all tuples (operator n1), followed by a filtering step outside the LLM (operator n2). c1'
This yields high precision but low recall as only one tuple is returned.
A key optimization is condition pushdown. While it reduces execution cost by limiting LLM interactions, it can create complex prompts that degrade quality. For instance, pushing both population and hospital conditions (operator p1) saves tokens but overwhelms the LLM’s ability to handle multi-faceted queries. Even pushing only the most selective condition (operator s1) might lead to errors preventing the identification of relevant data and ultimately producing an empty result. Achieving a balance between cost and quality requires analyzing each query component’s efect on the LLM. In the last example in Figure 2 (c1), pushing the condition for which the model is most confident leads to the best results.
Physical Level. The next challenge is adapting query execution to treat LLMs as the data storage layer. In the physical plan, this requires new operators, as data is accessed via natural language prompts. Prompt generation becomes critical, balancing variability in data quality and cost. Unlike traditional systems where a single command retrieves data, querying LLMs demands more flexible strategies.
For instance, a straightforward scanning technique retrieves the entire tuple set directly with a prompt, as in the Table-Scan operator c1’ in Figure 3 that retrieves all tuples in one prompt, minimizing interactions but often producing low-quality results. An alternative physical scan operator first identifies values for key attributes and then iteratively requests additional data, as with Key-Scan for operator c1” in Figure 3. This improves quality with more focused prompts but increases the number of LLM calls. These trade-ofs highlight the complexity of designing prompt-based operators that balance execution cost with result quality.
Moreover, LLMs face two key limitations in knowledge extraction. First, they generate the most likely next word based on prior text, often favoring frequent values from their training data—making rare information harder to retrieve without multiple interactions. Second, their output length is constrained, so a single response often fails to capture all relevant data.
These challenges highlight the need for new operators and optimization strategies tailored to LLMs. While traditional methods provide a foundation, they must be extended to support LLM-based data processing. Crucially, dynamic metadata generation is essential, as it directly impacts both logical and physical query planning.
In traditional DBMSs, query execution involves generating a logical plan to define the steps needed to produce the results, followed by a physical plan to determine how the query will be executed. However, querying LLMs requires diferent strategies to efectively manage logical and physical optimization.
Filter-LLMScan (LLM) Fetch data from LLM w.r.t. cond
LLMScan Selection Projection
Join Distinct Grouping Symbol (LLM) ⋊⋉
Fetch data from LLM Select tuples w.r.t. cond Extract attrs from tuples Join two table given cond
Removes duplicate tuples Groups tuples on common values and compute over groups 3) single pushdown, where the Filter-LLMScan retrieves the tuples that match a single condition.
Despite the inherent limitations in the considered pushdown strategies, the number of possible logical plans for a given query can still be substantial. A natural strategy for reducing token consumption is to push down all filter conditions into the LLMScan operator. While it minimizes the required tokens, it does not always produce the most accurate results. In certain cases, pushing down only a subset of conditions improves data quality because simpler prompts reduce complex reasoning and the risk of hallucination.
To guide logical optimization, Galois employs the LLM itself as a source of information for estimating the most eficient logical plan. Using a classification prompt (that uses the table schema and the query ), it estimates a “high” or “low” confidence score for each atom in the WHERE clause. All the atoms with “high” confidence are pushed down in the Filter-LLMScan. Physical Level. The goal of LLMScan and Filter-LLMScan is to extract structured data from the LLM, which is then processed by the logical plan. Galois achieves this by generating natural language prompts tailored to the query.
The natural strategy, called Table-Scan, prompts the LLM to extract all relevant tuples for
a given query . Given a logical plan and schema , Galois uses an iterative prompting
approach for each LLMScan operator in . The initial prompt requests all table attributes and
instructs the LLM to return results in JSON format, aligned with the schema derived from .
Due to space limits, a template for this prompt is shown in the full paper [
LLMs are known to benefit from techniques like Chain-of-Thought (CoT) prompting [
For each SQL query , Galois must choose between two scan strategies: Table-Scan and KeyScan. While Key-Scan, based on CoT prompting, generally ofers higher accuracy, Table-Scan can outperform it in cases where additional context (i.e., the full table structure) helps the LLM generate more reliable data.
By choosing the right physical scan operator is therefore possible to improve the result data quality. For this goal we rely again on metadata generated by the LLM itself.
Given a query we estimate the confidence of the model in returning factual data in the Scan operation. To do so we prompt the LLM to gather a confidence value between 0 and 1 ( ()). To leverage the strengths of both Key-Scan and Table-Scan, we introduce a confidence threshold, . If () > , we use Key-Scan; otherwise, Table-Scan is selected. The rationale is that when the model’s confidence is low, the accuracy of key retrieval in Key-Scan may be compromised. In such scenarios, Table-Scan provides a more reliable alternative by incorporating additional context from other attributes, potentially improving the quality of data extraction. The drawback of this approach is that it requires an extra interaction with the LLM, increasing the total costs measured in the number of tokens.
Galois can be seamlessly integrated with frameworks like Retrieval Augmented Generation (RAG), which combine traditional information retrieval with the generative power of LLMs. This experiment demonstrates how Galois’s optimizations enhance both the accuracy and eficiency of LLM-based data retrieval in in-context learning settings.
To evaluate the ability to handle novel information, we use the Premier and Fortune
datasets, containing 60 and 500 documents respectively. These corpora are designed to include
information not present in the LLM’s training data. Premier includes reports from the first six
match-days of the 2024–2025 Premier League season (scraped from BBC News), while Fortune
comprises data on the 2024 Fortune 500 companies, collected from Kaggle. Both datasets are
processed via a RAG engine built using LangChain4j. Each document is divided into text
segments with 128 tokens for Premier and 400 tokens for Fortune. Segments are encoded
using the “WhereIsAI/UAE-Large-V1” model [
We evaluate variants of Galois against three baselines: NL, SQL, and Palimpzest [
Each experiment comprises a query and a database . We compute the expected tuple set
by executing over ( = ()). We aim to compare with the tuple set produced by
executing on Galois (). As quality metrics to compare those two sets of tuples, we adopt
metrics used to benchmark SQL queries on LLMs [
To prevent false negatives, we normalize cell values in and before evaluation. We use
string similarity (Edit Distance [
Results are shown in Table 2. NL and SQL perform poorly due to the challenges of complex queries. The unstructured nature of natural language in NL and the rigid structure of SQL restrict the LLM’s ability to interpret and respond to intricate queries accurately. Both Galois versions outperform them, with Galois scoring higher. Palimpzest achieves the highest quality, but at a cost 11 times higher than Galois . Palimpzest’s high costs are due to its
Metric
AVG-Score # TOKENS in M 0.389 1.448
SQL multi-step processing, which involves repeated LLM interactions. In contrast, in Galois only the scan operator interacts with the LLM (once per query), thus reducing computational costs.
In summary, Galois efectively integrates with in-context learning (like RAG), achieving
comparable quality to the best baseline while reducing token costs. Moreover, Galois only
requires users to write SQL scripts. Experiments with queries executed over the parametric
knowledge of the LLMs confirm these results and are reported in the full paper [
Galois adopts a DB-first architecture, integrating the LLM directly within the database
operators. This direction opens several problems, such as the design of mechanisms to simulate
index-like eficiency using LLMs, e.g., through caching techniques based on prior interactions
[
Another promising research direction involves support for queries spanning multiple
modalities, such as text, image, and structured data [
Beyond iterative refinement, another open challenge arises from the inherent biases within
LLMs. These models may not return rare values unless explicitly prompted. For example, when
asking for “private hospitals”, the LLM may return the list of US hospitals first. Instead, if we
are interested in querying EU hospitals, our approach relies on the users specifying precisely
their intent, which may not always be the case in practice [
Our work shows the increasing need to refine LLM confidence estimation mechanisms [
Acknowledgments. Veltri was partially supported by the TECH4YOU project.
the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), 2024, pp. 6577–6595. [28] L. Chen, A. Perez-Lebel, F. M. Suchanek, G. Varoquaux, Reconfidencing llms from the grouping loss perspective, arXiv preprint arXiv:2402.04957 (2024).