A database replay system (DRS) captures workloads on a production system and then replays them in a test system to test various system changes, avoiding any risk before realizing them in production. The dependency graph generation in a DRS is crucial in preserving output determinism while maximizing concurrency. The state-of-the-art dependency graph generation algorithm deployed in a commercial DBMS uses a generate-and-prune strategy. It first generates a dependency graph by performing backward scans for each request in a workload. It then prunes all redundant edges using an expensive, transitive reduction algorithm. However, we notice that this generates a large dependency graph that contains many redundant edges and its worst-case time complexity is quadratic to the number of requests in a workload. In order to solve these challenging problems, we formally propose four classes of dependency graphs for DRSs. We then present a stateful single forward scan algorithm, SSFS, to generate any class of dependency graphs by performing a single scan over all requests while succinctly maintaining states. Here, states refer to information that is stored and maintained for efficient dependency graph generation. We also propose the parallel SSFS to utilize the computation power with multi-core CPUs while balancing the loads. We implemented our DRS in a leading commercial DBMS. Extensive experiments using the TPC-C, SD benchmarks, and a real-world customer workload show that our DRS significantly improves the dependency graph generation time by up to two orders of magnitude, compared to the state-of-the-art.

A Database Replay System (DRS) captures workloads from a production system and subsequently replays them in a testing environment to verify correctness and performance. Prior to the replay process, DRS initially generates a dependency graph from the workload to ensure output determinism and to maximize replay concurrency in the testing system. However, the state-of-the-art inefficiently generates unnecessarily larger dependency graphs, creating a major bottleneck in the end-to-end pipeline. DoppelGanger++ is a new DRS supporting fast dependency graph generation. This demonstration illustrates how it captures and replays workloads, with a focus on efficiently generating compact dependency graphs. Specifically, we showcase the end-to-end database replay workflow using the complete database replay workload, accompanied by a web tool developed for our demo which can animate the dependency graph generation process and visualize important internal data structures.

We propose a new method for estimating the number of answers OUT of a small join query Q in a large database D, and for uniform sampling over joins. Our method is the first to satisfy all the following statements.