Multi-Query Optimization through Shared Intermediate Results

This direction is merged into another direction: dynamic graph maintenance. Its last version stays readable and citable here.

Version 1 of 116 papers20 conceptsfrozen 2026-10-04

In traditional database systems, query optimizers treat every incoming request as an isolated island. The goal is to find the most efficient execution plan for that specific query in a vacuum. However, as systems scale to handle millions of concurrent requests—particularly in complex domains like graph processing and event streams—this "one-at-a-time" philosophy becomes a bottleneck.

The core insight of Multi-Query Optimization (MQO) is that concurrent queries are rarely unique. They often share structural overlaps, such as common sub-joins, identical path segments, or redundant filtering criteria. By identifying and sharing these intermediate computations, systems can achieve massive gains in throughput that individual query optimization could never provide.

The Global Optimization Paradox

A fundamental tension exists between local and global efficiency. As Qing Li and Kamalakar Karlapalem observed in Algorithms for Materialized View Design in Data Warehousing Environment, the most efficient plan for an individual query might actually be detrimental to the system as a whole.

Imagine two queries: one asks for "Engineers in New York" and another for "Engineers in San Francisco." A local optimizer might choose different indices for each. However, a global optimizer might realize that both queries first need to filter the entire database for "Engineers." By executing that filter once and sharing the result, the system saves significant CPU cycles, even if the subsequent city-specific filtering is slightly less "optimal" than a dedicated index scan.

Consolidating Plans into Unified Structures

To move from theory to implementation, researchers have developed ways to merge thousands of independent query plans into a single, unified execution structure.

In the context of dynamic Knowledge Graphs, Garima Gaur and Srikanta Bedathur proposed the HUKA framework in How and Why is An Answer (Still) Correct? Maintaining Provenance in Dynamic Knowledge Graphs. HUKA uses AND-OR graphs to represent multiple standing queries. This unified structure acts as a shared infrastructure where overlapping intermediate results are cached and reused. This approach can eliminate up to 70% of the redundant work required to maintain query results as the underlying data changes.

Similarly, in relational keyword searches, Jeffrey Xu Yu and Lu Qin highlight the use of shared operator structures in Keyword Search in Relational Databases: A Survey. By identifying common sub-joins across different potential answer sets, the system avoids re-evaluating the same join sequences multiple times for a single keyword query.

Structural Decomposition and Indexing

When dealing with graph data, the "overlap" between queries is often structural. Two different subgraph matching queries might both contain the same three-node triangle or a specific linear path.

The TRIC (TRIe-based Clustering) algorithm, detailed by Lefteris Zervakis and Katja Hose in Efficient Continuous Multi-Query Processing over Graph Streams, exploits this by decomposing queries into paths and indexing them in a trie. This allows the system to:

  1. Identify common prefixes across thousands of queries.
  2. Compute the match for a prefix exactly once.
  3. Distribute that result to all queries that require it.

This mechanism effectively decouples the computational cost from the number of queries. As noted in their follow-up work in EDBT 2020, systems using shared indexing can maintain near-constant processing time even as the volume of concurrent queries grows, because they focus on the total number of unique structural components rather than the raw query count.

Batching for Path Enumeration and Storage

Beyond continuous streams, MQO is also being applied to batch processing in massive, billion-scale graphs. In Batch Hop-Constrained s-t Simple Path Query Processing in Large Graphs, Kongzhang Hao and Long Yuan introduced BatchEnum. This framework identifies common sub-structures across a batch of path queries, caching these results to achieve up to a 7.7x speedup over sequential execution.

This "strength in numbers" approach even extends to the physical storage layer. Dor Elimelech and Moshe Schwartz demonstrate in The Generalized Covering Radii of Linear Codes that processing a batch of queries together can significantly reduce the total number of database items that need to be accessed. By exploiting the overlap in query requirements, the system minimizes aggregate access complexity, proving that multi-query optimization is a powerful tool from the high-level execution plan down to the low-level data retrieval.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_multi_query_optimization_through_shared__89d121e5,
  title = {Multi-Query Optimization through Shared Intermediate Results},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-query-optimization-through-shared-intermediate-results/rdr_89d121e5198f40ce8dbaaded4173c853},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_multi_query_optimization_through_shared__89d121e5_v1,
  title = {Multi-Query Optimization through Shared Intermediate Results},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-query-optimization-through-shared-intermediate-results/rdr_89d121e5198f40ce8dbaaded4173c853/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}