Modern data systems increasingly face a "cost explosion" problem. As we move from simple SQL lookups to complex tasks—like asking a Large Language Model (LLM) to summarize a thousand reviews, running a deep learning model on hours of video, or querying an encrypted blockchain—the computational cost per record skyrockets.
The emerging research direction across these domains is a shift toward multi-stage, cost-aware query optimization. The core intuition is simple: instead of applying an expensive operator to every data point, use cheap, highly selective "hints" or filters to prune the search space first. By ordering operations based on their selectivity-to-cost ratio, systems can achieve orders-of-magnitude speedups without sacrificing accuracy.
The Selectivity-Cost Heuristic
The fundamental challenge in hybrid systems is that not all filters are created equal. A traditional database filter (e.g., WHERE price < 20) is nearly free, while a semantic filter (e.g., "Is this restaurant review positive?") requires an expensive LLM call.
Lei Cao and colleagues in the SEED project formalize this as a priority heuristic. They argue that processing modules should be ordered by the ratio of the data they filter out to their execution cost. This ensures that the most "efficient" filters—those that discard the most junk for the least effort—run first.
This principle is echoed in VIVA, an interactive video analytics system by Daniel Kang and Matei Zaharia. VIVA uses "relational hints"—cheap, structured metadata like transcripts—to avoid running heavy neural networks on every frame of video. By prioritizing these cheap, noisy signals, the system can prune up to 80x of the unnecessary computation.
Two-Stage Execution for Hybrid Data
When queries span both structured databases and unstructured text, the most effective strategy is a two-stage "narrowing" process.
Shicheng Liu and Monica S. Lam demonstrate this in SUQL. To handle conversational search over restaurants and reviews, SUQL first uses dense retrieval to identify a small subset of candidate rows. Only then does it apply expensive LLM-based semantic functions to that tiny subset.
This "win-win loop," as described by Sihem Amer-Yahia and Lei Chen in their 2023 discussion, allows the database to act as a "grounding" mechanism. The database provides deterministic reliability and filtering, ensuring the LLM only operates on the most relevant data, which simultaneously reduces costs and minimizes hallucinations.
Historical Roots in Logic and Graphs
While the application to LLMs is new, the underlying logic of "pruning via selectivity" has deep roots in database theory.
As early as 1986, Donald Cohen introduced AP5, which optimized logical conjunctions by estimating the cost of different execution sequences. The goal was the same: prioritize the most restrictive filters to keep intermediate result sets small. Similarly, in the world of RDF and graph processing, Louis Jachiet and others developed SPARQLGX, which reorders joins based on the statistical selectivity of triple patterns to reduce network shuffles in distributed environments.
This logic even extends to specialized domains like blockchain auditing. Shuaicheng Ma and Li Xiong found that by filtering for the most selective attribute first, they could drastically reduce the number of expensive blockchain API calls, performing the rest of the query logic in-memory.
Pruning Beyond Tables
The most advanced versions of this idea move away from coarse-grained table optimizations toward fine-grained, tuple-level pruning.
Beng Chin Ooi and Meihui Zhang argue in their 2017 position paper that representing data as a unified graph allows systems to prune specific data paths that are unlikely to contribute to a result. This shift from table-level to tuple-level optimization can reduce computational costs by over 75% in complex data science workflows.
Whether the "expensive" part of a query is a Lisp program (AP5), a procedural simulation (Magnaguagno & Meneguzzi), or a modern LLM, the winning strategy remains the same: use the structure of the data to prove what doesn't need to be computed as early as possible.