Traditional database management systems optimize queries in isolation. When a query arrives, the optimizer parses it, generates an efficient execution plan, and executes it. This "one-at-a-time" approach works well for sporadic, independent requests. However, modern data systems—ranging from large-scale analytical warehouses to high-velocity stream processors and graph databases—frequently handle thousands of concurrent, recurring, or structurally similar queries that target the same underlying data.
Optimizing each query individually in these environments leads to massive systemic inefficiencies. Multiple queries end up scanning the same files, traversing the same indexes, and computing identical intermediate joins or aggregations.
Shared Query Execution, often studied under the umbrella of Multi-Query Optimization (MQO), shifts the paradigm from local to global optimization. Instead of asking "What is the best way to execute this query?", the system asks "What is the best way to execute this entire workload?" As noted by Anthony K. H. Tung in Letter from the Associate Editor, processing a large volume of concurrent queries as a single collective task allows systems to amortize data access and computation costs, unlocking throughput levels that are mathematically impossible under independent query optimization.
Consolidating Global Execution Plans
To share work across multiple queries, an engine must first identify where their structural logic overlaps. This is achieved by merging individual query trees into a unified global execution plan.
In a traditional setup, an optimizer selects the absolute fastest plan for an individual query. However, Qing Li et al. demonstrated in Algorithms for Materialized View Design in Data Warehousing Environment that a globally optimal system state might require choosing a slightly less efficient individual plan if that plan utilizes intermediate results that can be shared across multiple other queries. By iteratively merging individual execution trees based on common join patterns, the system minimizes total resource consumption.
Traditional (Isolated):
Query 1: Scan A ──> Filter ──> Join B ──> Output 1
Query 2: Scan A ──> Filter ──> Join C ──> Output 2
Shared (Unified Global Plan):
Scan A ──> Filter ──> Shared Intermediate ──┬──> Join B ──> Output 1
└──> Join C ──> Output 2
These global plans are typically organized into Directed Acyclic Graphs (DAGs) or specialized AND-OR graphs. For example, Garima Gaur et al. utilized AND-OR graphs in How and Why is An Answer (Still) Correct? Maintaining Provenance in Dynamic Knowledge Graphs to track query derivations in real time. By consolidating standing queries into a single global structure, their framework eliminates up to 70% of redundant intermediate computations.
Similarly, in graph databases where path enumeration is notoriously expensive, Kongzhang Hao et al. introduced a query sharing graph in Batch Hop-Constrained s-t Simple Path Query Processing in Large Graphs. This DAG organizes a batch of path queries based on their containment relationships, allowing the engine to determine an optimal, dependency-aware order for materializing and reusing common sub-structures.
Cooperative Scans and Stream Sharing
At the lowest layer of execution, the most common bottleneck is data retrieval—whether from disk, network, or high-velocity memory streams. Shared query execution addresses this by synchronizing data access across concurrent users.
This concept was pioneered for high-latency storage media by Sunita Sarawagi et al. in Reordering Query Execution in Tertiary Memory Databases. They introduced a centralized scheduler that dynamically reorders data fetching at runtime, allowing late-arriving queries to "piggyback" on ongoing scans of storage fragments. This dramatically reduces the number of times expensive media must be loaded.
In modern cloud and streaming architectures, this mechanism manifests as grouping queries that target the same inputs:
- Predictable Batch Workloads: Bingsheng He et al. showed in Wave Computing in the Cloud that recurring log-mining queries can be merged into a single execution unit. The system scans the input data exactly once for an entire series of related tasks, smoothing out cluster load imbalances.
- High-Velocity Streams: For enterprise security monitoring, Peng Gao et al. designed a master-dependent execution scheme in A Stream-based Query System for Efficiently Detecting Abnormal System Behaviors for Enterprise Security. This architecture groups semantically similar anomaly detection queries so they can evaluate a single, shared data stream simultaneously, drastically cutting down memory consumption and computational redundancy.
Sharing Intermediate Results and Sub-Joins
Beyond raw data access, queries frequently share higher-level structural components, such as multi-table relational joins or graph sub-structures.
In distributed environments, performing joins over massive datasets incurs heavy CPU and network costs. To mitigate this, InA Kim et al. developed the SAMUEL framework in SAMUEL: A Sharing-based Approach to processing Multiple SPARQL Queries with MapReduce. SAMUEL identifies overlapping subquery patterns within a global execution plan, ensuring that expensive distributed graph joins are computed once and shared across all relevant queries in the workload.
This structural sharing is also highly effective for resolving semantic ambiguity. When translating natural language questions into structured database queries (like SPARQL), systems often generate multiple candidate interpretations. Jie Jiao et al. demonstrated in Multi-Query Optimization in RDF Q/A System that this ambiguity can be treated as a structural optimization problem. By identifying the common structural "backbone" across all ambiguous interpretations, the system processes the shared components once rather than repeating execution for every potential variation.
Furthermore, in relational keyword searches where multiple candidate join sequences must be evaluated to find relevant connections, Jeffrey Xu Yu et al. highlighted in Keyword Search in Relational Databases: A Survey that shared operator structures can identify and cache common sub-joins across different potential answer sets, minimizing redundant database operations.
Amortizing Index and Network Overhead
When queries span complex multi-dimensional indexes or distributed networks, the fixed overhead of query instantiation, authentication, and index traversal becomes a major bottleneck. Shared execution amortizes these costs by bundling requests.
For distributed internet applications where data fields are fetched on-demand via hyperlinks, Alfons Kemper et al. showed in Hyperqueries: Dynamic Distributed Query Processing on the Internet that aggregating multiple virtual attribute requests destined for the same remote source into a single combined request significantly reduces network latency and fixed connection overheads.
In spatial-temporal applications, such as location-based social networks, processing queries concurrently allows for shared index traversals. Jianzhong Qi et al. demonstrated in K-Nearest Neighbor Temporal Aggregate Queries that batching spatial-temporal requests allows a system to traverse index trees collectively, lowering the computational cost per query and stabilizing system performance during peak traffic.
Index Traversal:
Query A Node Path: Root ──> Node 1 ──> Leaf X
Query B Node Path: Root ──> Node 1 ──> Leaf Y
Shared Traversal:
Shared Path: Root ──> Node 1 ──┬──> Leaf X (Query A)
└──> Leaf Y (Query B)
For massive analytical workloads requiring thousands of distinct views, Maximilian Schleich et al. introduced the LMFAO engine in A Layered Aggregate Engine for Analytics Workloads. By utilizing multi-root traversals over trie-like structures, the engine computes thousands of distinct aggregates simultaneously in a single pass over the data, sharing identical sub-computations directly over relational joins.
Open Frontiers in Shared Execution
While the benefits of shared query execution are clear, extending these techniques to highly dynamic, heterogeneous, or serverless environments remains an active area of research.
In streaming dataflows, Magdalena Balazinska et al. emphasize in Front Matter that inter-query resource sharing is essential for real-time throughput. When scaling to millions of concurrent stream queries over virtual actors, Philip A. Bernstein et al. argue in Serverless Event-Stream Processing over Virtual Actors that advanced multi-query optimization is a strict architectural necessity; without it, the resource overhead of independent query execution becomes entirely prohibitive.
A major open challenge lies in sharing state across queries with different parameters, such as varying sliding window sizes or slide intervals. Chuan Lei noted in Redoop: Supporting Recurring Queries in Hadoop that traditional window-aware caching mechanisms optimize for single query types in isolation. Similarly, Reza Akbarinia et al. pointed out in Efficient Incremental Computation of Aggregations over Sliding Windows that future research must address how internal buffers can be shared across diverse, overlapping aggregation tasks to maximize global efficiency.
Finally, as modern systems tackle specialized domains like localized data mining and massive graph matching, authors such as Abhishek Mukherji et al. in COLARM: Cost-based Optimization for Localized Association Rule Mining and Xin Wang et al. in Efficient Subgraph Matching on Large RDF Graphs Using MapReduce highlight a significant paradigm shift: moving away from single-query cost models toward comprehensive multi-query optimization strategies that can handle massive batches of heterogeneous requests simultaneously.
Key Foundational Work
Multiple Query Optimization with Depth-First Branch-and-Bound and Dynamic Query Ordering (1995) — contributed 1 concept elements to this direction.
Reordering Query Execution in Tertiary Memory Databases (1996) — contributed 1 concept elements to this direction.