Prefix-Cache-Aware Data Reordering for LLM-Augmented Database Analytics

LLM-augmented database analytics face a major bottleneck in the costly prefill phase. Although relational tables inherently contain repeated attribute values, standard row-by-row processing produces fragmented prompt layouts that obscure shared prefixes, thereby minimizing opportunities for prefix KV cache reuse and constraining system efficiency. Existing solutions typically employ heuristic or exhaustive search methods to reorder prompt layouts, but these approaches can be inefficient and may not leverage the structural properties of relational tables. We address this challenge by formulating prefix-cache-aware prompt layout optimization as a problem rooted in the isomorphism between prefix-cache reuse and the radix tree topology induced by the relational data distribution. Building on this perspective, we introduce a practical greedy tree-shaping algorithm that efficiently selects row and column orderings to maximize prefix overlap. Our approach, SOLO, improves prefill throughput by up to 90.3\% under fixed prefix-cache budget. Moreover, it reduces planning overhead by up to 242$\times$ compared to state-of-the-art baselines.

Modern databases increasingly use large language models (LLMs) as built-in "smart" operators to clean messy data, match records across sources, or filter tables based on natural-language criteria. But this is expensive: each row in the table becomes a separate request to the LLM, and the time the model spends reading each prompt (rather than generating an answer) dominates the cost. We notice that real database tables are full of repetition—many people live in the same city, many products share the same category, many forms repeat the same labels. When two consecutive requests to an LLM start with exactly the same text, modern serving systems can reuse the computation from the previous request and skip the shared beginning. By default, however, the order in which rows are sent to the model, and the order in which their attributes appear inside each prompt, rarely line up to take advantage of this. Our method, SOLO, automatically rearranges both the row order and the attribute order so that consecutive prompts share as much common opening text as possible. We show that this rearrangement problem has a clean mathematical structure: it corresponds to building a tree of shared prefixes and choosing how to walk through its leaves. Using this view, we design a fast algorithm with provable guarantees on how close to optimal it gets. On real-world datasets, SOLO speeds up the LLM processing phase by up to 90%, while the planning itself takes only seconds—up to 242× faster than the previous best planners. The reordering doesn't change what the LLM is being asked or which answers it produces; it only changes the order, letting database systems use LLMs at substantially lower cost and higher throughput.