Optimizing LLM Queries in Relational Data Analytics Workloads

Optimizing LLM Queries in Relational Data Analytics Workloads

Speakers: Shu Liu, PhD Student, UC Berkeley; Asim Biswal; Amog Kamsetty; Ion Stoica; Joseph E. Gonzalez; Matei Zaharia

Conference: MLSys 2025

YouTube: https://www.youtube.com/watch?v=None

Overview

This talk, presented by Shu Liu from UC Berkeley, along with collaborators from UC Berkeley and Stanford University, addresses the critical challenge of optimizing Large Language Model (LLM) queries within relational data analytics workloads. While much attention has focused on conversational LLM interactions, Liu and the team highlight the equally significant, yet often overlooked, use case of LLMs as operators within analytical queries on structured data. The core problem tackled is the prohibitive cost and latency associated with processing large volumes of relational text data using LLMs, which can amount to hours of computation and thousands of dollars for even moderately sized datasets.

The presented research introduces an innovative approach that leverages the inherent data patterns within relational tables to significantly enhance the efficiency of LLM inference. Specifically, the work focuses on intelligently reordering columns for subsets of rows before constructing prompts, thereby maximizing the hit rate of LLM prefix caches. This strategy exploits the auto-regressive nature of LLMs, where shared prompt prefixes can be cached and reused, leading to substantial speedups and cost reductions.

The significance of this work lies in its practical implications for various industries that increasingly integrate LLMs into their data pipelines for tasks like reporting, analysis, and data science. By demonstrating up to a 3.4x speedup and 79% cost savings on real-world datasets, the research provides a vital blueprint for making LLM-powered relational data analytics economically viable and performant, shifting focus from solely backend inference optimizations to crucial application-level data preparation.

Background

▶ Watch: Introduction: Optimizing LLM queries in relational data analytics (0:00)

The advent of powerful Large Language Models (LLMs) like ChatGPT has spurred a revolution in how users interact with data, primarily through conversational interfaces. However, a less visible but equally impactful paradigm involves integrating LLMs directly into traditional data analytics workflows, where they act as powerful operators capable of understanding and processing natural language within structured datasets. Imagine a large database containing product descriptions and customer reviews. An analyst might want to ask, "Are the product descriptions consistent with user reviews?" This question, when applied across millions of rows, translates into numerous individual LLM calls, each processing concatenated text from specific columns. This pattern is increasingly adopted by major tech companies like Google, Amazon, and Databricks.

The primary obstacle to widespread adoption of this paradigm is the inherent inefficiency of LLM inference. Processing even a modest 100 gigabytes of text data using an Nvidia L4 GPU with a Llama 8B model can take over 30 minutes and incur a cost of $5,000. Migrating to commercial APIs like GPT-4 Mini for the same workload can escalate costs to $15,000. These figures render large-scale LLM-powered analytics impractical for many organizations, prompting the critical question: How can we make LLM queries faster and cheaper?

Existing efforts to accelerate LLM inference primarily focus on backend infrastructure optimizations, with caching being a cornerstone technique. The auto-regressive nature of LLMs means that each token generation depends on preceding tokens. Therefore, if multiple requests share a common prefix, the intermediate Key-Value (KV) cache states for that prefix can be computed once and reused. For example, if two prompts are "What is the capital of China?" and "What is the capital of US?", the prefix "What is the capital of" can be cached. This prefix caching significantly reduces computation and, consequently, cost, with providers like Anthropic charging 10x less for cached inputs or prefixes.

However, the authors identify a critical disconnect between the design of current LLM prefix caching mechanisms and the typical structure of relational data. Relational tables often contain highly repetitive values within columns (e.g., the same product description for multiple reviews, or the same timestamp for many events). When these columns are naively concatenated to form LLM prompts, the repetitive values might appear in the middle or end of the prompt, after distinct values from other columns. This arrangement leads to frequent prefix cache misses, as the shared repetitive segments do not form a contiguous initial prefix, thereby underutilizing the potential of LLM caching and negating its benefits. The problem, therefore, shifts from optimizing the LLM inference engine itself to intelligently preparing the input data to maximize cache hits.

Key Findings

▶ Watch: Core problem: LLM queries are slow and prohibitively expensive (2:30)

The research presented by Shu Liu and colleagues makes several significant contributions to optimizing LLM queries in relational data analytics workloads:

• Underutilization of LLM Caching in Relational Workloads: The authors identified that standard LLM prefix caching mechanisms are severely underutilized when processing relational data due to the common practice of concatenating column values into prompts. While relational tables contain abundant repetitive values, their positioning within prompts often prevents them from forming shared prefixes, leading to cache misses.
• Intelligent Column Reordering for Cache Maximization: The core finding is that strategically reordering columns within relational tables, specifically for subsets of rows, can dramatically increase LLM prefix cache hits. This goes beyond simple global column reordering, which is insufficient because optimal ordering depends on the specific repetition patterns across different groups of rows.
• Novel Greedy Heuristic for Optimal Reordering: The team developed a greedy heuristic algorithm that efficiently determines the best column orderings. This algorithm avoids the computationally intractable combinatorial explosion of brute-force search, which would take hours for typical datasets. The greedy approach achieves orders of magnitude faster execution (e.g., 15 seconds compared to 5-6 hours for a dataset of 15,000 rows and 57 columns) while empirically demonstrating a cache hit rate within 1-2% of the theoretical optimum.
• Integration of Functional Dependencies and Data Statistics: The framework incorporates database metadata such as functional dependencies (FDs) and data statistics (like column cardinality and value length) to further refine the reordering strategy. FDs, which indicate that one column's value determines another's, help identify implicit repetitions and cluster columns for more effective cache utilization.
• Significant Performance and Cost Improvements: Empirical evaluations on seven diverse real-world datasets using Llama 3 8B on Nvidia L4 GPUs and cost estimations with GPT-4 Mini and Anthropic Claude 3.5 Sonnet demonstrated substantial gains:
• Speedup: Up to 3.4 times faster compared to a baseline using caching without reordering.
• Cost Savings: Up to 39% cost savings based on OpenAI's pricing model (which offers 2x less cost for cached inputs) and an impressive 79% cost savings based on Anthropic's pricing model (which offers 10x less cost for cached inputs).
• Application-Level Optimization Importance: The research underscores the critical importance of application-level data preparation and pattern exploitation in LLM workflows, arguing that these are as crucial as backend inference engine optimizations for achieving overall efficiency and cost-effectiveness.

Technical Deep Dive

▶ Watch: Challenge: Naive data input misses cache opportunities (5:30)

The fundamental challenge addressed by this work is the mismatch between the efficiency mechanisms of LLM inference engines and the structure of relational data. Large Language Models operate auto-regressively, meaning each token is generated based on the preceding sequence of tokens. This property enables prefix caching, where the intermediate Key-Value (KV) cache states for common initial sequences of tokens can be stored and reused across multiple prompts. For example, if many queries start with "Summarize the following text:", the KV states for this prefix are computed only once.

When relational data is used as input for LLMs, rows are typically transformed into individual prompts by concatenating column values. Consider a product table with columns like product_description, user_review, and review_time. A query might ask, "Is the description consistent with the review?" For each row, a prompt might be constructed as "Description: [product_description] Review: [user_review] Time: [review_time]".

The problem arises because relational tables frequently exhibit repetitions. A single product_description might be associated with multiple user_review entries over different review_times. If the user_review column (which is often distinct per row) is placed early in the prompt, followed by the product_description (which might be repeated), the shared product_description cannot serve as a prefix for caching. The unique user_review breaks the prefix dependency, leading to a cache miss. Conversely, if product_description were placed first, the shared descriptions could be cached.

The core technical insight is that the optimal column ordering is not static across an entire table; it varies depending on the specific values and repetition patterns present in different subsets of rows. A simple global reordering (e.g., always putting product_description first) might capture some cache hits but miss others where a different column (e.g., review_time) has more repetition for another group of rows.

To address this, the authors propose a strategy that determines different column orderings for different subsets of rows. This problem can be conceptualized recursively:

1. Initial State: Given a table (or sub-table) and a set of available columns.
2. Splitting Heuristic:

• Choose a Column: Select one of the available columns to prioritize.
• Identify a Value Group: Within the chosen column, identify a group of rows that share the same value (i.e., duplicates).
• Split the Table: This choice logically splits the problem into two sub-problems:
• Sub-table 1: Comprising the rows that contain the selected value group. For these rows, the chosen column (with its shared value) forms a common prefix. The remaining columns in these rows become a new sub-problem.
• Sub-table 2: Comprising the rows that do not contain the selected value group. These rows form another sub-problem with all original columns still available for reordering.

1. Recursive Application: The process is applied recursively to these sub-tables until no further splits are beneficial or possible. The total prefix hits are the sum of hits from the chosen value group and the optimal hits from the two sub-tables.

This recursive decomposition, if exhaustively explored, represents a combinatorial problem of immense complexity. For a table with N rows and M columns, exploring all possible column orderings for all possible row subsets is computationally intractable, potentially taking hours for even moderately sized tables.

To make this practical, the authors introduce a greedy heuristic algorithm. Instead of exploring all possible splits and combinations, the greedy approach simplifies the decision at each step:

1. Prioritize Most Duplicates: At each step, the algorithm identifies the column and specific value group within that column that has the most duplicates. This group is chosen as the prefix for the current subset of rows.
2. Recursive Descent: The algorithm then recurses on the remaining columns for the rows that used this prefix, and separately on the remaining rows (those that did not contain the chosen value group) with all columns.

This greedy strategy drastically reduces the search space. For example, in a table with many columns and rows, it might take only 15 seconds to find a near-optimal reordering, compared to 5-6 hours for a brute-force approach. Empirically, this greedy heuristic achieves prefix cache hit rates that are within 1-2% of the theoretically optimal solution.

Further optimizations integrated into the system include:

• Functional Dependencies (FDs): Database schemas often define FDs (e.g., ClassID functionally determines Instructor). If ClassID is chosen as a prefix, the system can infer that Instructor values will also be repeated for those rows, allowing for more intelligent clustering and reordering of dependent columns to maximize cache hits.
• Data Statistics: Leveraging metadata like column cardinality (number of unique values) and average value length helps the optimizer estimate the potential cache hits and cost savings for different reordering choices. Columns with low cardinality and high average length are good candidates for initial prefixes.
• Query Optimization: Beyond reordering, the system performs traditional query optimization. This includes pushing down expensive LLM operators in the query plan, ensuring that data filtering and selection (e.g., WHERE clauses) occur before data is passed to the LLM. This reduces the total volume of text processed by the LLM, further contributing to cost and latency reduction.

The input to the LLM is assumed to be structured as a natural language question followed by a JSON-like object where keys are column names and values are the extracted row values, allowing the reordering to be applied consistently.

Experimental Setup & Results

▶ Watch: Initial solution: Reordering columns to maximize cache hits (6:00)

The research team conducted a comprehensive evaluation to demonstrate the efficacy of their intelligent column reordering approach for LLM queries in relational data analytics.

LLM Models:

• Llama 3 8B: This open-source model was used for on-premise inference, running on dedicated hardware to measure speedup.
• GPT-4 Mini (OpenAI): Used for estimating potential cost savings based on OpenAI's pricing model, which charges approximately 2 times less for cached inputs.
• Anthropic Claude 3.5 Sonnet: Used for estimating potential cost savings based on Anthropic's pricing model, which offers a significant 10 times reduction in cost for cached inputs.

Hardware:

• All on-premise experiments, specifically those involving Llama 3 8B, were conducted on an Nvidia L4 GPU. This choice of hardware represents a common, high-performance GPU used for LLM inference.

Datasets:

• The evaluation utilized seven common, real-world datasets. These datasets varied in size and complexity, featuring up to 15,000 rows and as many as 57 columns. The diversity of these datasets was crucial for testing the robustness of the reordering algorithm across different data distributions and repetition patterns.

Workloads:

• The experiments covered five different types of LLM queries. This ensured that the reordering strategy was evaluated against a range of analytical tasks, from simple consistency checks to more complex reporting or summarization tasks, reflecting typical use cases in relational data analytics.

Baselines:

• The primary baseline for comparison was an LLM inference setup that employed prefix caching but without any intelligent column reordering. This baseline represents the standard, unoptimized approach to utilizing LLM caching for relational data, highlighting the specific gains attributable to the proposed reordering mechanism.

Metrics:

• Speedup: Measured as the factor by which the proposed reordering method accelerated query execution compared to the baseline.
• Estimated Cost Savings: Calculated based on the pricing models of OpenAI and Anthropic, quantifying the monetary benefits of increased cache hits.

Headline Results:

1. Query Speedup: The intelligent column reordering approach achieved a substantial speedup of up to 3.4 times compared to the baseline (caching without reordering). The variations in speedup across the seven datasets were attributed to the differing distributions of repetitive values within each dataset, indicating that datasets with more exploitable repetition patterns benefited more significantly.

1. Cost Savings:

• OpenAI Pricing (GPT-4 Mini): The method yielded up to 39% cost savings. This is significant given OpenAI's policy of charging approximately 2 times less for cached inputs, demonstrating substantial monetary efficiency.
• Anthropic Pricing (Claude 3.5 Sonnet): Even more impressively, the approach resulted in up to 79% cost savings when applying Anthropic's pricing model, which offers a 10 times reduction for cached inputs. This highlights the immense value of maximizing cache hits, especially with providers that heavily incentivize prefix reuse.

Ablations and Algorithm Performance:

• Greedy Heuristic Efficiency: The computational cost of the reordering algorithm itself was found to be negligible compared to the LLM inference time. For the largest dataset (15,000 rows, 57 columns), the greedy reordering algorithm took approximately 15 seconds. In contrast, a brute-force or optimal search algorithm for the same problem would require 5 to 6 hours, underscoring the efficiency and practicality of the greedy approach.
• Greedy vs. Optimal Hit Rate: Empirically, the greedy heuristic achieved cache hit rates within 1-2% of the theoretical optimal solution across the evaluated datasets. This demonstrates that the significant speedup in the reordering computation does not come at a substantial cost to the effectiveness of cache utilization.
• Subset Application: The algorithm is flexible and can be applied to subsets of a table (e.g., after a SELECT or WHERE clause), allowing for dynamic optimization based on the specific data being queried by the LLM operator.

These results unequivocally demonstrate that intelligently reordering relational data inputs for LLMs is a highly effective strategy for drastically reducing both query latency and operational costs, making LLM-powered analytics on structured data far more practical and economically feasible.

Practical Implications

▶ Watch: Advanced solution: Dynamically reorder columns for each request (7:40)

The findings from this research have profound practical implications for a wide array of stakeholders involved in building, deploying, and utilizing LLM-integrated systems, particularly within data analytics contexts.

For Practitioners and Data Scientists:

• Cost-Effective LLM Analytics: The most direct benefit is the ability to perform complex analytical queries over large relational text datasets using LLMs at a fraction of the current cost. With up to 79% cost savings, tasks that were previously prohibitively expensive (e.g., automated consistency checks across millions of product reviews, sentiment analysis on customer feedback databases) become economically viable.
• Faster Insights: The up to 3.4x speedup means that analytical workflows can complete significantly faster, enabling quicker iteration cycles for data scientists and more timely business insights. This directly impacts decision-making processes, moving from hours or days to minutes or a few hours.
• Expanded LLM Use Cases: By making LLM queries cheaper and faster, this work broadens the scope of applications where LLMs can be integrated into traditional data systems. LLMs can now be more easily leveraged as powerful, flexible operators within SQL-like queries, enriching data analysis beyond numerical or categorical data.

For Infrastructure Teams and ML Engineers:

• Optimized LLM Serving Infrastructure: This research provides a clear directive for designing and configuring LLM serving infrastructures. Beyond optimizing the inference engine itself (e.g., through quantization, batching, GPU utilization), attention must be paid to the data preparation layer. Implementing intelligent reordering mechanisms upstream of the LLM serving stack can significantly reduce the load on GPUs and the overall computational budget.
• Data-Aware Caching Strategies: It highlights the need for data-aware caching strategies that go beyond naive prefix matching. Infrastructure teams can develop or integrate tools that analyze incoming relational data patterns and dynamically reorder prompts to maximize cache hits, potentially even integrating with database metadata systems (like functional dependencies).
• Resource Allocation: By drastically reducing the computational resources required per query, infra teams can serve more LLM queries with the same hardware, or achieve the same throughput with fewer resources, leading to better resource utilization and lower operational expenditures.

For Model Builders and Deployers:

• Holistic Optimization: The work emphasizes a holistic view of LLM system optimization. While improving model architectures and inference algorithms is vital, the way data is prepared and presented to the LLM is equally, if not more, critical for end-to-end performance and cost. Model deployers should consider incorporating such data preprocessing steps into their deployment pipelines.
• Standardized Input Formats: The assumption of a natural language question followed by a JSON-like object for column values suggests a potential for standardizing LLM input formats for analytical workloads, which could simplify integration and enable widespread adoption of such optimization techniques.

Tradeoffs and Limitations:

• Computational Overhead for Reordering: While the greedy heuristic is orders of magnitude faster than brute-force (15 seconds vs. 5-6 hours for large datasets), there is still a small, non-zero computational cost associated with the reordering algorithm itself. For very small, infrequent queries, this overhead might be comparatively higher, though still likely negligible against LLM inference time.
• Input Format Dependency: The effectiveness of the reordering depends on the LLM input being structured in a way that allows for column manipulation (e.g., a JSON-like structure where column order can be changed). Different LLM interaction patterns (e.g., purely conversational, highly unstructured inputs) might not benefit from this specific optimization.
• Theoretical Guarantees: While the greedy algorithm performs empirically well (within 1-2% of optimal), the authors note that providing strong theoretical guarantees for its performance remains future work. This means that in some edge cases or specific data distributions, the greedy approach might deviate further from the true optimum.
• Complexity of Integration: Integrating this sophisticated reordering logic into existing complex data pipelines and LLM serving systems might require engineering effort. However, the demonstrated benefits likely outweigh this integration cost for large-scale deployments.

In summary, this research provides a powerful, practical solution for making LLM-powered relational data analytics efficient and affordable. It shifts the focus towards intelligent data preparation at the application layer as a critical lever for optimizing LLM performance and cost, complementing ongoing efforts in backend inference optimization.

Key Takeaways

• LLM queries on relational data are inherently slow and expensive, posing a significant barrier to widespread adoption in analytical workloads.
• Intelligent column reordering for subsets of rows is a highly effective strategy to maximize LLM prefix cache hits, drastically improving performance and reducing costs.
• A greedy heuristic algorithm can find near-optimal column orderings (within 1-2% of optimal hit rate) in orders of magnitude less time (e.g., 15 seconds vs. 5-6 hours) compared to brute-force methods.
• This approach delivers substantial benefits: up to 3.4x speedup in query execution and up to 79% cost savings (with Anthropic pricing) or 39% cost savings (with OpenAI pricing).
• Leveraging database metadata like functional dependencies and data statistics (cardinality, value length) further enhances the effectiveness of the reordering strategy.
• Optimizing application-level data patterns is as crucial as backend LLM inference optimizations for achieving overall efficiency and cost-effectiveness in LLM-integrated systems.

About the Speaker(s)

The lead speaker for this presentation was Shu Liu, a PhD student from UC Berkeley, whose research focuses on optimizing LLM queries within relational data analytics. The work is a collaborative effort involving researchers from both UC Berkeley and Stanford University. The distinguished list of co-authors includes Asim Biswal, Amog Kamsetty, Ion Stoica, Joseph E. Gonzalez, and Matei Zaharia, all prominent figures in the fields of distributed systems, databases, and machine learning, particularly known for their contributions to big data frameworks like Apache Spark. Their collective expertise underpins the depth and impact of this research.