Exploiting Structural Overlap in Concurrent Queries

53 concepts49 papers1 proposal

In modern data systems, performance is often limited not by the raw complexity of a single task, but by the inefficiency of executing many similar tasks in isolation. When a system processes a batch of queries—whether they are SQL aggregations, graph pattern searches, or machine learning inferences—it frequently encounters "computational redundancy." This occurs when independent tasks perform identical operations on the same data, such as scanning the same disk blocks, performing the same joins, or verifying the same structural patterns.

The research direction of Multi-Query Optimization (MQO) and shared execution aims to identify these overlapping requirements and consolidate them into a single, unified workflow. By treating a workload as a coordinated set of operations rather than a sequence of isolated requests, systems can achieve orders-of-magnitude speedups.

The Cost of Isolation

Traditional query engines are designed to optimize a single query at a time. While effective for simple lookups, this approach fails in data-intensive environments where queries are naturally related. As Agarwal et al. observed in their foundational work on Data Cubes, executing related aggregation queries independently results in massive I/O bottlenecks because the system repeatedly scans the same underlying records.

This redundancy appears across diverse domains:

  • Bioinformatics: Baras et al. demonstrate in miRge that standard workflows waste time by repeatedly aligning identical RNA sequences found across different samples.
  • Security: Gao et al. note that concurrent security monitoring tasks often perform redundant processing on the same system log streams in SAQL.
  • Machine Learning: The authors of MEME point out that training unique proxy models for every search task creates significant overhead compared to task-agnostic indexing.

Identifying Shared Structural Backbones

The core challenge of shared execution is identifying what can be shared. In graph processing, this involves finding structural overlaps between different pattern queries. Vinay Setty proposes a trie-based clustering algorithm in TRIC to identify shared "backbones" across thousands of simultaneous graph queries. By computing these common sub-patterns once, the system amortizes the cost across the entire workload.

Similarly, in distributed RDF environments, Peng et al. introduce the Local Partial Match Equivalence Class (LEC) to group matches that are structurally identical, reducing both computation and network traffic. For path enumeration, Hao et al. developed BatchEnum, which caches common sub-structures across a batch of path queries to avoid traversing the same intermediate vertices multiple times.

Amortizing I/O through Batching

Beyond sharing CPU cycles, systems can eliminate redundant data movement by batching I/O operations. Xiao Yan demonstrates this in DiskJoin, where shifting from a "query-based" search to a "batch-based" orchestration strategy prevents the same disk blocks from being fetched repeatedly for different vectors.

In the context of large-scale log analysis, He et al. propose the Wave computing model, which groups recurring batch computations into "query series." This allows the system to predict workloads and eliminate I/O redundancies by reading massive datasets once and passing them through a pipeline of concurrent analytics.

Intelligent Caching of Intermediate Results

When queries cannot be perfectly batched, systems rely on caching intermediate results. However, not all data is equally worth storing. Yang et al. developed an automated system for Apache Spark that analyzes computation graphs to identify the most "valuable" intermediate datasets to cache. Carra et al. further refined this by framing cache admission as a Multiple-Choice Knapsack Problem, maximizing the reduction in execution time for a given memory budget.

For complex graph queries, Wang et al. introduced GraphCache, which leverages semantic relationships between queries. Instead of looking for exact matches, it recognizes when a new query is a subgraph or supergraph of a previously computed result, allowing the system to bypass expensive isomorphism tests.

Pruning Redundancy in Logic and Preprocessing

Redundancy also exists within the logic of a single complex query or a data pipeline. Kim et al. address this in Tagged Execution, where semantic tags are attached to data records to track which parts of a disjunctive (OR) predicate they satisfy. This prevents the engine from materializing the same record multiple times for different branches of the query.

Finally, the trend extends to data preparation. Tae et al. argue in MLClean that executing cleaning, fairness, and sanitization tasks as a sequential pipeline is redundant. By integrating these tasks, systems can leverage shared structural patterns, while Rafiei et al. suggest that one-time tabular normalization can eliminate the need for repetitive cleaning across multiple downstream reasoning tasks.

Key Foundational Work

On the Computation of Multidimensional Aggregates (1996) — contributed 1 concept elements to this direction.
Cooperating Brokers to Support Cooperative Work (1994) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_redundant_query_execution_de57daaf,
  title = {redundant query execution},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/redundant-query-execution/rdr_de57daaf9d9b4993940bdbc4f6c87dfd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_redundant_query_execution_de57daaf_v1,
  title = {redundant query execution},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/redundant-query-execution/rdr_de57daaf9d9b4993940bdbc4f6c87dfd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake