Source-linked AI summary
SharedDB: Killing One Thousand Queries With One Stone
Georgios Giannikis, Gustavo Alonso, Donald Kossmann
TL;DR
Traditional query-at-a-time databases provide best-effort performance, whereas modern applications require response-time guarantees under high load. SharedDB batches queries and updates for shared computation, and its TPC-W evaluation reports robust performance across dynamic workloads. The paper also identifies limits in scalability and optimizer scope.
Problem
Query-at-a-time optimization is insufficient for modern applications requiring response-time guarantees under high load.
Method
SharedDB batches queries and updates and shares computation through a global plan across concurrent workloads.
Results
SharedDB's TPC-W performance is robust across query load, hardware configuration, and query mixes, while sustaining twice the throughput of a top-of-the-line database system and almost eight times MySQL.
Takeaways & Limitations
SharedDB's advantages emerge under high loads with unpredictable mixes of heavy and light queries and updates, without special tuning, load control, or adaptive techniques.
Takeaways & Limitations
SharedDB does not always outperform query-at-a-time techniques, and its optimizer is outside the paper's scope, with more sophisticated cost-based optimization left for future work.
Abstract
from arXiv · showhide
Traditional database systems are built around the query-at-a-time model. This approach tries to optimize performance in a best-effort way. Unfortunately, best effort is not good enough for many modern applications. These applications require response time guarantees in high load situations. This paper describes the design of a new database architecture that is based on batching queries and shared computation across possibly hundreds of concurrent queries and updates. Performance experiments with the TPC-W benchmark show that the performance of our implementation, SharedDB, is indeed robust across a wide range of dynamic workloads.
1. INTRODUCTION
SharedDB replaces query-at-a-time processing with batching and shared computation to target response-time guarantees under high load. TPC-W experiments report substantially higher throughput than two traditional database systems, while related-system comparisons identify scope limitations.
- Modern applications may require SLAs that bound response time for 99 percent of queries, along with isolation or data-freshness guarantees.
- SharedDB batches queries and updates to share computation, executing multiple customer-order queries through one join and routing results to each query.
- SharedDB may perform extra work and perform poorly at low throughput, but overlapping customer and order sets make sharing valuable with hundreds of concurrent queries.
- SharedDB applies general batch-oriented sharing principles across OLTP, OLAP, and mixed workloads, unlike related systems limited to certain query classes or OLAP.
- SharedDB sustains twice the throughput of a top-of-the-line database system and almost eight times MySQL on the TPC-W benchmark.
- QPipe, CJoin, and DataPath could not be experimentally compared because they were unavailable, and their applicability to transactional workloads was unclear.
2. RELATED WORK
SharedDB builds on multi-query optimization and stream-processing ideas while extending shared computation beyond the workloads and operators supported by earlier systems. Its push-oriented model also addresses execution deadlocks associated with pull-oriented sharing.
- Multi-query optimization evaluates common subexpressions once, but its applicability is limited in many workloads and synchronization is difficult when queries arrive at different times.
- QPipe exploits sharing within a time frame and distinguishes data sharing from work sharing, but its work-sharing opportunities depend on common subexpressions and focus on OLAP.
- CJoin and DataPath share work without detecting common subexpressions, but their techniques are limited to joins and certain join methods.
- SharedDB uses standard relational operators and supports transactional, analytical, and mixed workloads, while also providing response-time guarantees.
- SharedDB adopts push-oriented processing to alleviate deadlocks that may arise from shared computation in pull-oriented query processors.
- Unlike Eddies, which targets runtime adaptivity but cannot provide response-time guarantees, SharedDB uses a static processing model.
- Related SLA-oriented techniques include indexing, materialized views, caching, query-result reuse, and data-placement optimization.
3. SYSTEM OVERVIEW
SharedDB combines a global query plan, batched execution, and shared operators to process many concurrent queries and updates with bounded, predictable performance. Its query-data model tracks interested query identifiers so joins and other operators can share computation, while the benefits depend on workload overlap and may trade against latency or extra work.
- SharedDB combines the data-query model, global query plan, batched query execution, and shared operators to provide performance and predictability across workloads.The section identifies these components as the key ideas behind SharedDB’s performance and predictability characteristics.
- Data-query model: The data-query model adds a query id attribute to intermediary relations, allowing relational operators to track which active queries may be interested in each tuple.SharedDB implements this attribute internally as a set-valued attribute to avoid duplicating tuples for every relevant query.
- Global query plan: SharedDB compiles the workload into one global query plan that can serve hundreds or thousands of concurrent queries and updates over an extended period.Queries of the same type can share operators even when their parameter settings differ; for example, hundreds of Q4 queries can share one join and sort.
- Shared operators: Shared joins merge query-specific plans into one join over the union of relevant tuples, with query id included in the join predicate to route results correctly.Indexing query id, such as with a hash join, supports scalability by turning queries into data processed through traditional query-processing techniques.
- Discussion: Batching can increase individual-query latency by up to a factor of 2, but compile-time scheduling avoids interference and supports bounded response times and concurrent updates.SharedDB’s stated advantage over QPipe and DataPath is its ability to meet SLAs and bound query response time while supporting strong consistency.
- Shared operators: Shared computation is most advantageous when many concurrent queries overlap in their required tuples, whereas low overlap can make one shared operator do extra work.For n = Σ_i n_i input tuples and o tuples needed by at least one query, shared processing can save work for suitable operator complexities; for f(n) = n*logn, the worst case o = n adds work but retains bounded computation and predictable performance.
4. IMPLEMENTATION DETAILS
SharedDB implements query processing as an always-on data flow network whose operators batch concurrent work and route query-specific paths. Its implementation also integrates shared storage access, transaction support, hardware-aware deployment, and operator replication.
- Query execution model: SharedDB uses a global plan of always-on database operators instead of individual query plans.
- Query execution model: Each query describes an acyclic path through the data flow network, with results flowing from table scans through operators to clients.
- Batched operators: Shared operators process active queries in cycles, while queries arriving after a cycle begins wait for the next cycle.
- Batched operators: Blocking operators such as SORT buffer tuples for all queries in a batch, sort the shared buffer, and emit results at end of stream.
- Hardware deployment: Operators can be assigned to separate CPU cores with processor affinity, while related operators may be placed on adjacent cores for cache and NUMA locality.
- Storage and transactions: The Crescando-based storage manager supports shared scans, index probes, updates in arrival order, consistent snapshots, and transactional isolation favoring optimistic or multiversion control.
- Replication: SharedDB can replicate storage and processing operators, allowing bottlenecked operators to partition load across replicas without changing update order.
5. PERFORMANCE EXPERIMENTS AND RESULTS
SharedDB was evaluated against MySQL and SystemX on TPC-W workloads with varying mixes, loads, cores, and query types. It generally achieved higher throughput and better robustness under heavy, dynamic workloads, while sharing helped less for point-query- and update-dominated interactions.
- Experimental Environment: TPC-W experiments compared SharedDB with MySQL and a high-end commercial database across comprehensive workloads and individual-query microbenchmarks.The benchmark models an online bookstore with web interactions subject to response-time limits ranging from 2 to 20 seconds.
- Performance under Varying Load: SharedDB achieved higher throughput in all three TPC-W workload mixes, including twice SystemX’s and eight times MySQL’s throughput in the Browsing mix.The Browsing mix contains many heavy search queries involving joins and sorts.
- Performance under Varying Load: SharedDB’s advantage was smaller in the Ordering mix, where point queries and updates dominate and sharing provides little benefit.MySQL also had recovery options disabled in this comparison, giving it an advantage over the other systems.
- Scaling with the Number of Cores: SharedDB remained the clear winner across workload mixes and was almost independent of core count, while MySQL stopped scaling beyond twelve cores.SharedDB was outperformed by MySQL only for the Ordering mix when restricted to one core; update-intensive workloads were limited by concurrency control and transaction management.
- Analysis of Individual Web Interactions: SharedDB won many individual web interactions but lost on interactions dominated by point queries or updates, where sharing reduces little work.Its sharing applies both across query types and among concurrent queries of the same type with different parameter settings.
- Load Interaction: Under mixed heavy and light-query load, SharedDB scaled better than the other systems and beat SystemX by a factor of 3 in the extreme case.Starting at about 250 “best sellers” queries per second, SharedDB also diverged from ideal throughput because parameter differences prevented perfect sharing and created per-query overhead.
6. CONCLUSION
SharedDB’s batching and shared-computation model is most effective under high, unpredictable workloads, where it delivers robust latency and throughput without special tuning. The paper also identifies optimizer development and NUMA scalability as important next steps.
- Conclusion: SharedDB is robust under high loads with unpredictable mixes of heavy and light queries and updates.Its advantages are not universal: traditional query-at-a-time techniques can still outperform it in other settings.
- Conclusion: TPC-W experiments confirmed robustness across query load, hardware configuration, and query/update diversity.
- Conclusion: SharedDB achieves greater generality than related shared-computation systems, including support for transactional workloads with many small queries and updates.
- Future work: The next step is a comprehensive query optimizer that automatically generates good global query plans using a cost model for shared execution.
- Future work: Future runtime work will target better use of NUMA machines with potentially hundreds of cores.