DBRepro: Automated Database Synthesis via a Hybrid Constraint-Solving Approach for Reproducing Slow Queries

arXiv:2608.27822v1 [cs.DB] 28 Aug 2026

DBRepro: Automated Database Synthesis via a Hybrid Constraint-Solving Approach for Reproducing Slow Queries Zhaoyang Zhang

Shuang Liu✉

Dengfeng Xu

Renmin University of China Beijing, China zhaoyangzhang@ruc.edu.cn

Renmin University of China Beijing, China Shuang.Liu@ruc.edu.cn

China Electronics Technology Kingbase (Beijing) Technologies Inc. Beijing, China xudengfeng@kingbase.com.cn

Wei Lu

Jianquan Leng

Sheng Du

Renmin University of China Beijing, China lu-wei@ruc.edu.cn

China Electronics Technology Kingbase (Beijing) Technologies Inc. Beijing, China jqleng@kingbase.com.cn

China Electronics Technology Kingbase (Beijing) Technologies Inc. Beijing, China dusheng@kingbase.com.cn

Xiaoyong Du Renmin University of China Beijing, China duyong@ruc.edu.cn

Abstract

reproducing the execution performance of complex slow queries with high fidelity.

Slow queries frequently cause severe performance bottlenecks in Database Management Systems (DBMSs). Due to the severe risk of exacerbating online resource contention, diagnosing their root causes online is usually infeasible; offline diagnosis has thus become the de facto approach. However, strict data privacy regulations prohibit accessing original user data. Therefore, synthesizing a proxy database, one that induces the query optimizer to generate identical physical execution plans as in production, from non-intrusive metadata, is critical for reproducing and diagnosing slow queries offline. Achieving high-fidelity reproduction demands satisfying both global statistical distributions and exact local cardinality constraints. Existing works fundamentally fail to achieve both simultaneously: data-driven approaches cannot enforce strict local cardinalities, whereas workload-aware approaches severely distort the overall data distribution, misleading the optimizer into divergent execution plans. To bridge this gap, we introduce DBRepro, an automated endto-end database synthesis framework that synergistically integrates data-driven and workload-aware methodologies. DBRepro formulates database generation as a constrained distribution synthesis problem. It initializes a global data distribution from lightweight column statistics, extracts execution constraints from the target queries, and progressively adjusts the distribution to satisfy these constraints, ensuring the global distribution is maximally preserved while exact local cardinalities are strictly enforced. Extensive evaluations on the TPC-H and SSB benchmarks demonstrate that DBRepro outperforms state-of-the-art baselines across comprehensive fidelity metrics. Compared to the data-driven baseline, it reduces cardinality error by up to 20.3% while maintaining identical plan consistency. Against a workload-aware baseline, it reproduces 15% more consistent execution plans and lowers the latency proportion error by 21.5%. Furthermore, we validate its industrial practicality on a nearly 1 TB real-world dataset from a specific industrial sector, managed by KingbaseES, successfully

CCS Concepts • Information systems → Database performance evaluation.

Keywords database synthesis, slow query reproduction, constraint solving

1

Introduction

In modern enterprise Database Management Systems (DBMSs), slow queries represent a pervasive and critical challenge. Unlike lightweight transactional workloads, analytical queries typically involve complex multi-table joins, massive aggregations, and fullscale data scans. For example, in an enterprise data warehouse, a complex analytical query generating a large-scale operational report might suddenly degrade, taking hours instead of seconds to execute. Such performance anomalies monopolize critical CPU, memory, and I/O resources, causing severe contention that can precipitate a dramatic decline in overall system throughput or even service unavailability [30]. Furthermore, they compromise the timeliness of data analytics, directly impeding an enterprise’s capability for real-time decision-making. When a slow query anomaly occurs, it must be promptly diagnosed and optimized (e.g., via index tuning or SQL rewriting). However, debugging the root causes of these anomalies directly on the live production instance is usually infeasible due to the severe risk of exacerbating online resource contention. Consequently, offline diagnosis has become the de facto approach. Yet, strict data privacy regulations prohibit DBAs from copying original user data to test environments. Therefore, synthesizing a proxy database via non-intrusive metadata is a critical step for diagnosing slow queries in an offline environment. In modern DBMSs, a SQL query is compiled by the query optimizer into a physical execution plan—a 1

Zhaoyang Zhang, Shuang Liu, Dengfeng Xu, Wei Lu, Jianquan Leng, Sheng Du, and Xiaoyong Du

(b) Database Statistics

(a) Database Schema size: 15 Primary Key

size: 15 Primary Key

Integer

Double

Varchar

Double

Integer

Foreign Key

Attr Null 0 20% 0 0 0 0

Integer

MCV

MCF

[70, 50, 10, 30] [A, B, C, D, E] [1, 2, 3, 4, 5] [75] ---

(c) SQL Queries

[0.4, 0.3, 0.2, 0.1] [0.2, 0.2, 0.2, 0.2] [0.33, 0.26, 0.20, 0.13, 0.06] [0.2] ---

Histogram

---[0,30)[30,60)[60,90] [0,20)[20,22.5)[22.5,24.5] --

(d) Physical Execution Plans

: select count(*) from

where

;

: select count(*) from

where

;

: select count(*) from and ;

where and

: select count(*) from and and ;

where

⋈

σ

:

σ

:

R

T

R

σ

and

4 5 5 13 13 13

Domain [10,70] -[1,5] [0,90] [0,24.5] [1,12]

(e) Cardinality Constraint

⋈

:

:

:

NDV

σ

:

T

R

:

σ

σ

:

T

Figure 1: Input example of database synthesis: database schema 𝐻 and statistics 𝑆, queries 𝑄 and physical execution plans 𝑃. sequence of physical operations that dictates the query’s performance. Consequently, the ultimate goal of database synthesis is to induce the query optimizer to yield physical execution plans identical to those in production. Evaluating a successful reproduction requires strict alignment in three dimensions: query plan structure, operator cardinalities, and execution times. Existing database synthesis techniques fall into two categories: data-driven and workload-aware approaches. Data-driven methods [5–7, 20, 21, 32, 37, 40, 45, 46, 50, 58] reconstruct databases by learning column statistics or sampling production data. While they generally preserve the query plan structure, they fundamentally struggle to capture complex cross-column correlations and intricate multi-table join semantics. This limitation prevents them from enforcing strict local cardinalities. As a result, the simulated execution bottlenecks diverge significantly from the production environment, making it impossible to accurately preserve operator cardinalities and execution times. Conversely, workload-aware methods [2, 3, 26, 29, 41, 43, 54–56] formulate data generation as a constraint satisfaction problem derived from query plans. Although these methods enforce specific intermediate result sizes—thereby achieving strict cardinality consistency—they severely distort the global data distribution to satisfy these local constraints. Such distortion invariably misleads the optimizer’s global cost model into selecting divergent physical execution plans. Ultimately, this approach fails to preserve the holistic query plan structure and the overall execution performance. Achieving high-fidelity reproduction by satisfying both global statistics and local cardinalities presents three major challenges. First, reconciling the multivariate and heterogeneous inputs is difficult: database statistics dictate probabilistic data distributions, while workload cardinalities impose deterministic size constraints. Bridging this semantic gap to guide unified data generation remains an open problem. Second, reconciling potential conflicts between these inputs is non-trivial: global statistics are derived from database sampling, introducing approximation errors that

may contradict the rigid intermediate cardinalities demanded by the execution plan. Resolving this conflict requires adjusting the data distributions without destroying the global statistical baseline. Third, slow queries in industrial workloads frequently involve non-PK-FK joins (e.g., on non-unique columns or composite keys). These joins trigger severe cardinality explosions—known as the fan-out effect—which significantly complicate constraint modeling and solving. To overcome these challenges, we introduce DBRepro, an automated end-to-end framework that formulates database synthesis as a constrained distribution synthesis problem, harmonizing the multivariate and heterogeneous inputs by synergistically integrating data-driven and workload-aware methods. Specifically, DBRepro employs a novel hybrid constraint-solving approach to progressively adjust an initial statistics-based distribution, deriving a final distribution that satisfies all query constraints without compromising global characteristics. The hybrid constraint-solving approach adopts different constraint satisfiability solving methods for different types of constraints. It utilizes heuristic probabilistic inference combined with a distribution fusion algorithm to seamlessly integrate the Selection Cardinality Constraints (SCCs) into the global distribution, while resolving the potential conflicts. For Join Cardinality Constraints (JCCs), it tackles the fan-out problem in JCCs by embedding a Scaling Factor mechanism into a Constraint Programming (CP) model, preventing cardinality explosions during non-PK-FK joins. In summary, our main contributions are as follows: ⊲ We propose DBRepro, an end-to-end automated framework that non-intrusively captures production telemetry and synthesizes test databases for high-fidelity slow query reproduction, enabling practical and reliable offline performance diagnostics. ⊲ We design a novel hybrid constraint-solving approach to adjust the data distributions progressively. It utilizes heuristic inference and distribution fusion to reconcile statistical and cardinality

2

DBRepro: Automated Database Synthesis via a Hybrid Constraint-Solving Approach for Reproducing Slow Queries

conflicts, and introduces a Scaling Factor-enhanced constraint programming model to accurately resolve non-PK-FK joins. ⊲ We conduct extensive evaluations on the TPC-H and SSB benchmarks, as well as a nearly 1 TB real-world industrial dataset. DBRepro significantly outperforms state-of-the-art baselines by achieving superior high-fidelity reproduction and demonstrating robust practicality in a commercial DBMS.

2

threshold parameters based on the generated data. The resulting query plan can precisely reconstruct the three elements: query plan structure, intermediate operator cardinalities, and execution time, required for slow query reproduction in the simulated environment. Cardinality Constraints (CCs) are extracted from these AQPs to define the required output size of a physical operator. We represent the output of each query operator as a query operator view (𝑉 ). Based on 𝑄 3 in Figure 1d, we derive the following CCs in Figure 1(e): |𝑉3 | : |𝜎𝑟 2 =𝑝 3 (𝑅)| = 3, |𝑉4 | : |𝜎𝑡1 +𝑡2 ≤𝑝 4 (𝑇 )| = 6, and |𝑉5 | : |𝑉3 ⊲⊳𝑅.𝑟 0 =𝑇 .𝑡3 𝑉4 | = 4. We divide CCs into two categories: Selection Cardinality Constraints (SCCs) are imposed by selection operators (𝜎) and introduce joint data distribution requirements among non-key columns. As shown in Figure 1(e), following [55], we categorize them into Unary Cardinality Constraints (UCCs) for single-column predicates (e.g., 𝑉3 ), Arithmetic Cardinality Constraints (ACCs) for multi-column operations (e.g., 𝑉4 ), and Logical Cardinality Constraints (LCCs) for predicates connected by logical operators (e.g., 𝑉7 ). Join Cardinality Constraints (JCCs) are imposed by cross-table join operators (⊲⊳), requiring specific joint distributions between the join keys. Figure 1(e) formulates the JCC for 𝑉8 as |𝑉6 ⊲⊳𝑅.𝑟 3 =𝑇 .𝑡4 𝑉7 | = 9. This constraint requires that performing an equi-join on the specific keys (𝑅.𝑟 3 and 𝑇 .𝑡 4 ) between the two query operator views (𝑉6 and 𝑉7 ) must yield exactly 9 matching rows.

Preliminaries

Due to strict privacy regulations, data extracted from production databases is typically limited to aggregated statistics and workload artifacts. This section formalizes these non-intrusive inputs. Figure 1 shows a minimal example with two tables, 𝑅 and 𝑇 , and four queries, which we use throughout this paper. Database Schema (𝐻 ) defines tables, attributes, data types, primary keys (PKs), and foreign keys (FKs). In Figure 1a, 𝑅 has a PK 𝑟 0 , and 𝑇 has an FK 𝑡 3 referencing 𝑅.𝑟 0 . The synthetic proxy database must satisfy these structural and referential integrity constraints. Database Statistics (𝑆) captures the global data distributions from the production catalog. In database systems, queries are executed according to physical execution plans compiled by the query optimizer. The prevailing Cost-Based Optimizers (CBOs) heavily rely on statistics as the foundational baseline to estimate execution costs and select the optimal physical operators and join orders [10, 24, 44]. They typically include: ⊲ Null Fraction: The proportion of tuples containing NULL values. ⊲ Number of Distinct Values (NDV): The cardinality of an attribute’s active domain. ⊲ Most Common Values (MCVs) & Frequencies (MCFs): A set of the most frequent values coupled with their probabilities. ⊲ Histograms: A set of buckets (equi-depth or equi-width) summarizing the continuous data distribution. In Figure 1b, 𝑅.𝑟 1 has an NDV of 4 and an MCV set {70, 50, 10, 30} with corresponding MCF {0.4, 0.3, 0.2, 0.1}, while 𝑇 .𝑡 1 uses three equi-depth histogram buckets ([0, 30), [30, 60), and [60, 90]). These statistics serve as the foundational data distribution. Reproducing them ensures the optimizer selects the same join orders and physical operators, while distorting them produces divergent plans. Queries (𝑄) denote a set of 𝑛 slow queries, 𝑄 1, . . . , 𝑄𝑛 , which are the original SQL statements executed in production. Physical Execution Plans (𝑃) are generated by the optimizer to dictate the exact sequence of physical operations for a query. Each query 𝑄𝑖 is accompanied by a physical plan from the production environment, which inherently comprises three critical dimensions: query plan structure (join order and physical operator type), intermediate operator cardinalities, and execution time. Therefore, faithfully reproducing a slow query necessitates the precise reconstruction of these three elements in the simulated environment. ˆ are converted from the physAnnotated Query Plans (AQPs 𝑃) ical plans by parameterizing the constants in the predicates. For example, in Figure 1d, the predicate 𝑡 1 + 𝑡 2 ≤ 55 in 𝑄 3 is parameterized into 𝑡 1 + 𝑡 2 ≤ 𝑝 4 , and its output 𝑉4 is labeled with a cardinality of 6. This parameterization significantly reduces the computational complexity. It avoids relying on computationally expensive models to synthesize exact tuples satisfying hardcoded constants [2, 43] and grants the solver the flexibility to straightforwardly infer new

3

Problem Formulation

In this section, we formalize the high-fidelity database synthesis problem for slow query reproduction. To achieve this, the synthesis process must strictly satisfy the cardinality constraints while maximally preserving the global statistical distributions defined by the database statistics. Definition 3.1 (High-Fidelity Database Synthesis). Given the target database schema 𝐻 , statistics 𝑆, and a set of slow queries 𝑄 ˆ the synthetic proxy with corresponding annotated query plans 𝑃, database 𝐷˜ is expected to satisfy the following fidelity properties: 1) Schema Consistency: 𝐷˜ strictly conforms to the structural and integrity constraints defined in 𝐻 . 2) Statistical Consistency: The single-column statistics of 𝐷˜ (de˜ closely match the production statistics (𝑆˜ ≈ 𝑆), preservnoted 𝑆) ing the optimizer’s global cost baseline. 3) Plan Structural Consistency: For each slow query 𝑄𝑖 ∈ 𝑄, the generated physical plan 𝑃˜𝑖 is topologically identical to 𝑃ˆ𝑖 , preserving join orders and operator types. 4) Cardinality Consistency: For each slow query 𝑄𝑖 , we evaluate the relative error between expected (𝐶 𝑗 ) and actual (𝐶˜ 𝑗 ) outputs Í

across its operators 𝑂𝑄𝑖 : RE𝑐𝑎𝑟𝑑 (𝑄𝑖 ) =

|𝐶 𝑗 −𝐶˜ 𝑗 | 𝑖 𝑗 ∈𝑂𝑄 𝐶 𝑗 𝑖

𝑗 ∈𝑂𝑄

Í

.

5) Latency Proportion Consistency: Directly comparing absolute execution times is unreliable due to potential differences in hardware and system configurations in the production and simulation environments. Therefore, we evaluate the latency of each operator relative to the overall query latency to reliably reproduce the true performance bottlenecks. For query 𝑄𝑖 , we evaluate the relative error between expected (𝐿 𝑗 ) and actual (𝐿˜ 𝑗 ) 3

Zhaoyang Zhang, Shuang Liu, Dengfeng Xu, Wei Lu, Jianquan Leng, Sheng Du, and Xiaoyong Du

Slow Query Listener

Application Workload

Detect Slow Queries { , , } ,

DBMS

,

Runtime Context Capturer Context

+ SQLs (Q) Plans (P) Database Statistics (S) Capture Json Log Files Schema, Index (H)

Business Database D

Runtime Context Analyzer

Production Environment

Simulation Environment Data Distribution Manager Cols' Stas

PK & Non-key PK & Non-key All Cols cols distro1 Dinit cols distro2 D fused distro3 D final

SCC Solver

SCCs AQPs

Heuristic Inference

Distro Fusion

Conflicts

Tuple Generator

JCC Solver CP-SAT CP Problem Constructor Solver

JCCs

Constraint Manager

Synthetic Workload Database

Data Tables Statistics Indexes

SQL Queries

Scale factor

Predicate Parameters

Query Instantiator

Figure 2: Design overview of DBRepro.

4.2

latency proportions across key operators 𝐾𝑄𝑖 : RE𝑙𝑎𝑡𝑒𝑛𝑐𝑦 (𝑄𝑖 ) = Í

|𝐿 𝑗 −𝐿˜ 𝑗 | Í 𝑖 𝑗 ∈𝐾𝑄 𝐿 𝑗 𝑖

𝑗 ∈𝐾𝑄

Runtime Context Capture and Analysis

DBRepro begins with lightweight monitoring in the production environment, aiming to extract the necessary runtime context accurately while minimizing performance overhead. When the Slow Query Listener detects slow queries, it triggers the Runtime Context Capturer. Without accessing the underlying raw data, it extracts the necessary runtime context with minimal overhead. This context includes the database schema (𝐻 ), column-level statistics (𝑆), and the physical execution plans (𝑃) annotated with operator cardinalities and execution latencies. Production DBMS catalogs (like pg_stats in PostgreSQL) rely on periodic sampling and lack exact global aggregations like precise distinct counts or min/max bounds. For instance, min/max bounds can be accurately estimated from the outermost buckets of the equi-depth histograms, which typically contain hundreds of fine-grained intervals. When cardinality constraints involve these inferred bounds, the subsequent SCC Solver strictly adjusts the data distribution to satisfy exact cardinalities, absorbing any initial boundary inaccuracies. The Slow Query Listener relies on native DBMS slow-query monitoring facilities. For example, PostgreSQL uses duration thresholds to log completed slow statements, while auto_explain, when configured to log analyzed plans, records their physical execution plans. Upon detecting such records, DBRepro performs post-execution collection: it obtains the logged queries and plans, identifies the referenced tables and columns, and retrieves their schema and column-level statistics from the system catalogs. This process neither re-executes the slow queries nor scans their base tables. Consequently, its cost is independent of the stored data volume and instead depends on the aggregate size of the recorded slow-query execution plans and the numbers of involved tables and columns, minimizing additional overhead on the production system. The Runtime Context Analyzer processes these extracted artifacts within the production environment. To simplify data generation, it applies relational algebra to push down selection operators to the bottom of the query tree [55]. This decouples the generation of non-key columns from PK-FK relationships, allowing DBRepro to independently solve SCCs for non-key columns before resolving complex JCCs. It then transforms the raw physical plans (𝑃) into AQPs by replacing hardcoded predicate constants with parameters (e.g., 𝑟 1 > 35 becomes 𝑟 1 > 𝑝 1 ). Finally, it extracts the cardinality constraints from these AQPs and categorizes them into formalized

.

6) Generalizability: For unseen queries from the same application scenario, 𝐷˜ continues to maintain Properties 3, 4, and 5.

4 Methodology 4.1 Overview In this section, we present the design of DBRepro. The core idea is to synthesize a high-fidelity proxy database that accurately reproduces the performance bottlenecks of slow queries without requiring access to sensitive production data. To achieve this, DBRepro must handle multivariate inputs extracted from the production environment: catalog statistics and physical execution plans. In the isolated simulation environment, DBRepro first uses the extracted statistics to model an initial global data distribution. It then employs a Hybrid Constraint-Solving Approach to systematically adjust this initial distribution, ensuring it strictly satisfies the exact cardinality constraints imposed by the queries. This refined final data distribution directly drives the synthetic proxy database generation. Figure 2 shows the workflow. First, the Runtime Context Capturer extracts runtime artifacts from the production servers: the database schema (𝐻 ), column-level statistics (𝑆), the queries (𝑄), and physical execution plans (𝑃). The Analyzer then transforms the raw physical plans into AQPs and extracts cardinality constraints. Based on these artifacts, the Data Distribution Manager builds a global initial distribution (PK & Non-key column distro1 D 𝑖𝑛𝑖𝑡 ) from the column statistics. Concurrently, the Constraint Manager solves the SCCs and JCCs. To resolve conflicts between the cardinality constraints and this initial distribution, the SCC Solver uses heuristic probabilistic inference combined with Iterative Proportional Fitting (IPF) to create a fusion distribution (PK & Non-key column distro2 D 𝑓 𝑢𝑠𝑒𝑑 ). Then, the JCC Solver uses this fusion distribution and the JCCs to construct a Constraint Programming (CP) model. For non-PK-FK joins, it uses a scaling factor-enhanced mechanism. Subsequently, the CP-SAT solver solves this problem to obtain the foreign key distributions, which constitute the complete final distribution (All Cols distro3 D 𝑓 𝑖𝑛𝑎𝑙 ). Finally, the Tuple Generator uses this distribution to physically generate the synthetic proxy database. 4

DBRepro: Automated Database Synthesis via a Hybrid Constraint-Solving Approach for Reproducing Slow Queries

= =

=

=

= = Probability derived from UCCs

= = Parameters = =

:

split with 75

Fusion Module (based on IPF)

(a) Example of unified CDF modeling from diverse statistics.

1 0 0 0 2 6 15 21 3 12 20 32 4 18 20.5 38.5 5 24 21 45 6 30 21.5 51.5 7 36 22 58 8 42 22.5 64.5

=

9 48 23 71 10 54 23.5 77.5 11 60 24 84 12 90 24.5 114.5 13 75 10 85 14 75 10 85 15 75 10 85

(b) Example of UCCs parameter inference and conflict resolution. (c) Example of resolving ACCs and LCCs.

Figure 3: Examples of the statistical constraints modeling and selection cardinality constraints resolution algorithms. SCCs and JCCs. DBRepro then transmits these processed artifacts to the simulation environment, routing the statistics (𝑆) to the Data Distribution Manager to initialize the data distribution, and the constraints to the Constraint Manager for targeted solving.

4.3

Algorithm 1: Heuristic Inference and Distribution Fusion Input: C: UCCs with target probs {(𝑜𝑝, 𝑝𝑖 , 𝑣𝑜𝑟𝑖𝑔 , 𝜏)}; D 𝑖𝑛𝑖𝑡 : Distro1 (includes CDF F and MCV set S𝑚𝑐𝑣 ) Output: M: Parameter instantiations {𝑝𝑖 → 𝑣 }; D 𝑓 𝑢𝑠𝑒𝑑 : PK & Non-key column distro2 1 S𝑢𝑠𝑒𝑑 ← ∅, M ← ∅, A ← ∅ 2 Sort C in descending order of target probability 𝜏 3 Merge constraints in C with Δ𝜏 ≤ 𝜖 sharing parameters 4 foreach constraint 𝑐 = (𝑜𝑝, 𝑝𝑖 , 𝑣 𝑜𝑟𝑖𝑔 , 𝜏) ∈ C do 5 if 𝑜𝑝 is ‘=’ then // Handle equality predicates via MCVs 6 𝑉𝑐𝑎𝑛𝑑 ← S𝑚𝑐𝑣 \ S𝑢𝑠𝑒𝑑 7 if 𝑉𝑐𝑎𝑛𝑑 ≠ ∅ then // Find closest MCV frequency 8 𝑣𝑏𝑒𝑠𝑡 ← arg min𝑣 ∈𝑉𝑐𝑎𝑛𝑑 |𝑓 𝑟𝑒𝑞(𝑣) − 𝜏 | 9 S𝑢𝑠𝑒𝑑 ← S𝑢𝑠𝑒𝑑 ∪ {𝑣𝑏𝑒𝑠𝑡 } 10 M [𝑝𝑖 ] ← 𝑣𝑏𝑒𝑠𝑡 11 if 𝑓 𝑟𝑒𝑞(𝑣𝑏𝑒𝑠𝑡 ) ≠ 𝜏 then // Record mismatch conflict 12 A.add(UPDATE_MCV(𝑣𝑏𝑒𝑠𝑡 , 𝜏))

Distribution and Constraint Modeling

In DBRepro, database statistics establish the initial data distribution to anchor the optimizer’s cost baseline, while query cardinalities serve as hard local constraints that dictate exact intermediate sizes to reproduce bottlenecks. To enable our hybrid constraint-solving algorithm, we must first model these heterogeneous inputs. Data Distribution Modeling. Statistics usually contain discrete MCVs and continuous histograms. To enable heuristic probabilistic inference, we merge these structures into a Cumulative Distribution Function (CDF). If an MCV overlaps with a histogram bucket, we split the bucket at the MCV and proportionally allocate the remaining probability to the new sub-ranges based on their lengths (Figure 3a). For attributes with only MCVs (𝑟 1 ) or histograms (𝑡 2 ), the CDF directly maps values to probabilities. For attributes with both statistic types like 𝑡 1 , the MCV 75 (20% frequency) falls inside the bucket [60, 90] (33.3% frequency). We split the bucket at 75 and allocate the remaining 13.3% evenly to the new sub-ranges [60, 75) and (75, 90] (6.67% each). To support efficient downstream tuple generation, we map this CDF into an array of memory-efficient buckets: (𝑙𝑜𝑤, ℎ𝑖𝑔ℎ, 𝑓 𝑟𝑒𝑞𝑢𝑒𝑛𝑐𝑦, 𝑛𝐷𝑖𝑠𝑡𝑖𝑛𝑐𝑡). This array serves as the initial data distribution for all PK and non-key columns, denoted as PK & Non-key column distro1 D 𝑖𝑛𝑖𝑡 , and is maintained by the Data Distribution Manager. FK columns are excluded from this initialization because they are populated later to satisfy JCCs. Cardinality Constraints Modeling. The extracted SCCs and JCCs provide hard cardinality constraints in the form of absolute row counts (e.g., |𝜎𝑟 1 >𝑝 1 (𝑅)|=9). However, the hybrid constraint solvers operate on probabilities. To bridge this gap, the Analyzer normalizes these absolute cardinalities into relative target probabilities (𝜏) by dividing them by the corresponding table sizes. For example, as shown in Figure 3b, the original constraint requires 6 rows. Since table 𝑅’s size is 15 (Figure 1a), we transform this into a parameterized probability constraint: |𝜎𝑟 1 ≤𝑝 1 (𝑅)| = 0.4 (using the complement 9 1 − 15 ). This transformation into a unified probabilistic domain enables the solver to perform heuristic probabilistic inference over the data distributions to strictly satisfy the required selectivity.

4.4

13 14 15 16 17 18 19 20 21 22

else // Fallback to original constant 𝑣𝑜𝑟𝑖𝑔 ← original query constant S𝑢𝑠𝑒𝑑 ← S𝑢𝑠𝑒𝑑 ∪ {𝑣𝑜𝑟𝑖𝑔 } M [𝑝𝑖 ] ← 𝑣𝑜𝑟𝑖𝑔 A.add(ADD_MCV(𝑣𝑜𝑟𝑖𝑔 , 𝜏)) else if 𝑜𝑝 ∈ {<, ≤} then // Handle range predicates via CDF 𝑣 𝑝𝑟𝑒𝑑 ← F −1 (𝜏) // Inverse CDF lookup M [𝑝𝑖 ] ← 𝑣 𝑝𝑟𝑒𝑑 if 𝑃 (𝑋 op 𝑣 𝑝𝑟𝑒𝑑 ) ≠ 𝜏 then // Record mismatch conflict A.add(UPDATE_RANGE(𝑣 𝑝𝑟𝑒𝑑 , 𝜏, 𝑜𝑝))

if A ≠ ∅ then // Apply IPF algorithm to reconcile conflicts D 𝑓 𝑢𝑠𝑒𝑑 ← IPF_Distribution_Fusion(A, D 𝑖𝑛𝑖𝑡 ) 25 else 26 D 𝑓 𝑢𝑠𝑒𝑑 ← D 𝑖𝑛𝑖𝑡 23

24

27

return M, D 𝑓 𝑢𝑠𝑒𝑑

from the initial distribution D 𝑖𝑛𝑖𝑡 to the final distribution D 𝑓 𝑖𝑛𝑎𝑙 . This adjustment harmoniously satisfies both the probabilistic global statistics and the deterministic workload cardinalities. To achieve this balance, we employ the Iterative Proportional Fitting (IPF) algorithm. IPF is mathematically proven to converge on a new joint distribution that strictly satisfies new marginal constraints (the deterministic workload cardinalities) while minimizing the deviation

Hybrid Constraint Solving for DB Synthesis

This phase is the computational core of DBRepro, bridging the Data Distribution Manager and the Constraint Manager. By systematically solving SCCs and JCCs, it progressively adjusts the distribution 5

Zhaoyang Zhang, Shuang Liu, Dengfeng Xu, Wei Lu, Jianquan Leng, Sheng Du, and Xiaoyong Du +

(e.g., KL divergence) from the initial distribution (the probabilistic global statistics) [23].

10 A 1 10 A 1 10 A 1 4 10 B 1 ··· ··· ··· ···

4.4.1 Solving Selection Cardinality Constraints. To accurately satisfy filter conditions without violating the underlying data distribution, we process SCCs progressively by complexity. We first resolve single-column UCCs through heuristic probabilistic inference and Distribution Fusion mechanism, followed by satisfying LCCs via data binding and addressing ACCs through post-generation sampling. Resolving UCCs. As shown in Algorithm 1, the solver takes the initial probabilistic distribution (D 𝑖𝑛𝑖𝑡 ) and the extracted SCCs as inputs. It first normalizes greater-than predicates into less-than counterparts using the complement of their target probabilities (1 −𝜏). It then sorts UCCs in descending order of target probabilities and merges constraints with nearly identical probabilities (within a threshold 𝜖) to share the same inferred parameter (Lines 2-3), thereby reducing solving overhead. The solver then employs operator-specific heuristic inference to satisfy these target probabilities. For equality predicates (Lines 5-17), the solver heuristically searches the MCV set for the bestmatching frequency, using an exclusion set S𝑢𝑠𝑒𝑑 to prevent mapping multiple parameters to the same MCV. If the MCV candidates are exhausted, it falls back to the original query constant. For range predicates (Lines 18-22), it performs an inverse lookup on the CDF F −1 (𝜏) to locate the exact boundary threshold. If the chosen parameter’s inherent statistical frequency does not perfectly match the required probability 𝜏, the solver records an adjustment action (e.g., UPDATE_MCV or UPDATE_RANGE) into an action list A. The inferred parameters (M) are routed to the Query Instantiator, while the action list A is forwarded to Distribution Fusion. Distribution Fusion. When the action list A indicates conflicts between the query-required probabilities and the initial statistical distribution (D 𝑖𝑛𝑖𝑡 ), Distribution Fusion intervenes (Lines 23-24). While database statistics establish the optimizer’s foundational cost baseline, they are inherently approximate due to periodic sampling. Therefore, instead of treating them as rigid, immutable constraints, we strategically adjust these global distributions only when necessary—specifically, when they conflict with the exact marginal constraints dictated by the SCCs (A ≠ ∅). This ensures that the synthetic proxy database exactly reproduces local execution bottlenecks. Guided by the IPF algorithm, we adjust the specific attribute distributions to strictly satisfy the new marginal constraints while mathematically minimizing the deviation from D 𝑖𝑛𝑖𝑡 . As illustrated in Figure 3b, suppose the solver receives two parameterized SCCs requiring 𝑃 (𝑟 1 ≤ 𝑝 1 ) = 40% and 𝑃 (𝑟 1 = 𝑝 5 ) = 40%. By searching D 𝑖𝑛𝑖𝑡 , it infers 𝑝 1 = 30 and 𝑝 5 = 70. However, the initial distribution indicates 𝑃 (𝑟 1 ≤ 30) is only 30%, triggering a conflict. Through IPF, the distribution of 𝑟 1 is adjusted to {26.67%, 13.33%, 20%, 40%}. This new fusion distribution—denoted as PK & Non-key column distribution2 D 𝑓 𝑢𝑠𝑒𝑑 —strictly satisfies the local 40% cardinality requirement while preserving the global relative proportions. Resolving ACCs and LCCs. As shown in Figure 3c, arithmetic constraints (e.g., |𝜎𝑡1 +𝑡2 ≤𝑝 4 (𝑇 )| = 6) and logical constraints (e.g., |𝜎𝑡1 =75∧𝑡2 =10 (𝑇 )| = 3) involve multi-column dependencies that cannot be directly inferred from 1D marginal distributions. Building upon the decoupling principles established in prior work [55], we apply a post-generation approach to resolve these dependencies

1 0 0 2 6 15 3 12 20 4 18 20.5 5 24 21 7 6 30 21.5 8 7 36 22 15 ... ... ... ...

(a) PK-FK JCC.

1 0 2 21 3 32 4 38.5 5 45 6 51.5 7 58 ... ...

+ ··· ··· ··· ··· 10 70 D 11 70 D 12 70 D 13 70 null 4 14 70 null 4 15 70 null 5

... ... 13 75 14 75 15 75

... 10 10 10

... 9 8 7

...

... 85 85 85

(b) Non-PK-FK JCC.

Figure 4: Resolution of Join Cardinality Constraints (JCCs). based on D 𝑓 𝑢𝑠𝑒𝑑 . For ACCs (left part of Figure 3c), we sample a batch of these generated tuples to compute their arithmetic expressions, ensuring a bounded approximation error [19]. Evaluating these samples allows us to accurately infer the required parameters (e.g., 𝑝 4 = 51.5) to fulfill the ACCs. For LCCs (right part of Figure 3c), the Tuple Generator physically generates the non-key columns, explicitly binding values required by LCCs to the same rows to guarantee their co-occurrence. 4.4.2 Solving Join Cardinality Constraints. After deriving D 𝑓 𝑢𝑠𝑒𝑑 , DBRepro must resolve the inter-table cardinality dependencies imposed by JCCs to derive the complete final distribution (All Cols distro3 D 𝑓 𝑖𝑛𝑎𝑙 ). This requires accurately populating foreign keys. Resolving PK-FK JCCs. For standard PK-FK joins, existing methods [55] formalize foreign key population based on a known set of primary keys. Given a join operation between the left view 𝑉𝑙 (typically the build side) and the right view 𝑉𝑟 (the probe side) with a target cardinality 𝑛 𝑗𝑐𝑐 , two fundamental Populating FK rules (𝑃𝐹 ) are derived. Rule (1) ensures that selecting PKs from 𝑉𝑙 to populate FKs in 𝑉𝑟 yields exactly 𝑛 𝑗𝑐𝑐 matched rows. Rule (2) guarantees that the remaining rows in 𝑉𝑟 are populated using PKs absent from 𝑉𝑙 to prevent unintended join outputs: (1) 𝑃𝐹𝑉𝑙 →𝑉𝑟 = 𝑛 𝑗𝑐𝑐 , (2) 𝑃𝐹𝑉𝑙 →𝑉𝑟 = |𝑉𝑟 | − 𝑛 𝑗𝑐𝑐 . In Figure 4a (representing the PK-FK join in 𝑄 3 ), the target cardinality is 4. 𝑉𝑙 provides 3 available PKs (highlighted in yellow), and 𝑉𝑟 has 6 rows satisfying the ACCs. Because 𝑅.𝑟 0 is a unique primary key, we select 3 PKs (e.g., 1, 2, 3) from 𝑉𝑙 to populate 4 FKs in 𝑉𝑟 , and fill the remaining 2 FKs with absent keys (e.g., 7, 8). This allocation perfectly meets the target cardinality of 4. Resolving Non-PK-FK JCCs. In industrial scenarios, queries frequently involve joins on a subset of composite primary keys or between two non-key columns. This violates the stringent prerequisite of PK uniqueness required by traditional 𝑃𝐹 rules. If the join column in 𝑉𝑙 contains duplicate values, treating it as a unique key and blindly applying the standard 𝑃𝐹 rules inevitably triggers a Cartesian product explosion (fan-out effect). The physical cardinality will diverge unpredictably, misleading the execution plan. To overcome this limitation, we introduce a Scaling Factor (𝑤) mechanism. Unlike existing solvers that strictly assume primary key uniqueness and inevitably fail on complex analytical joins, our scaling factor explicitly models the empirical fan-out effect. Specifically, DBRepro builds a pseudo-PK column for 𝑉𝑙 based on its distribution and uses the frequency of each key value 𝑘 within 6

DBRepro: Automated Database Synthesis via a Hybrid Constraint-Solving Approach for Reproducing Slow Queries

Table 1: Plan structural consistency on the TPC-H and SSB. The first number in the Consistent column accumulates strictly identical and topologically consistent cases, with the parenthetical value being the topologically consistent ones. The Inconsistent column tallies category (iii).

𝑉𝑙 as its scaling factor 𝑤𝑘 . This transforms the rigid 𝑃𝐹 rules into weighted constraint equations: ∑︁ (3) (𝑤𝑘 × 𝑃𝐹𝑘→𝑉𝑟 ) = 𝑛 𝑗𝑐𝑐 , 𝑘 ∈𝑉𝑙

(4)

∑︁

𝑃𝐹𝑘→𝑉𝑟 = |𝑉𝑟 | −

𝑘∉𝑉𝑙

∑︁

Generation

𝑃𝐹𝑘→𝑉𝑟 .

𝑘 ∈𝑉𝑙

Methods Hydra Touchstone Mirage RSGen DBRepro

where 𝑃𝐹𝑘→𝑉𝑟 is the number of times key 𝑘 is populated into the right view 𝑉𝑟 ’s FK column. Figure 4b shows the non-PK-FK join 𝑟 3 = 𝑡 4 in 𝑄 4 , where 𝑛 𝑗𝑐𝑐 =9. In Figure 1d, 𝑉𝑟 has 3 rows satisfying the LCC. While the base column 𝑟 3 contains duplicates, the filtered view 𝑉𝑙 retains only keys {3, 4, 5} with local frequencies 𝑤={3, 2, 1} (bottom-right in Figure 4b). Previous algorithms would fail here: if they blindly selected distinct values from 𝑟 3 to populate 𝑡 4 , causing the join output to explode due to duplicates. Instead, DBRepro uses the scaling factors 𝑤𝑘 to form the weighted equation: 3 · 𝑃𝐹 3→𝑡4 + 2 · 𝑃𝐹 4→𝑡4 + 1 · 𝑃𝐹 5→𝑡4 = 9. The solver can easily find a feasible solution, like selecting key 3 to populate all 3 rows in 𝑉𝑟 yields exactly 3 × 3 = 9 matches. If 𝑉7 had more rows that need to be mismatched, they would be safely populated with absent keys from column 𝑟 3 (e.g., 𝑘 ∉ 𝑉6 , like 𝑘 = 1, 2) to strictly meet the cardinality without explosion. When queries contain multiple join constraints across several tables, the 𝑃𝐹 rules and weighted equations combine into a comprehensive Constraint Programming (CP) model. This allows DBRepro to solve both strict PK-FK and non-PK-FK joins within a unified framework using CP-SAT solvers like OR-Tools [36]. For acceleration when absolute precision is less critical, the system can dynamically estimate a uniform scaling factor using either sampling methods or the n_distinct statistic to approximate the degree of uniqueness. Ultimately, we compute the valid FK distributions, which completes the evolution into the final D 𝑓 𝑖𝑛𝑎𝑙 . Through the systematic resolution of SCCs and JCCs, DBRepro computes the valid data distributions for all attributes. This completes the entire data distribution evolution from the initial statisticsbased D 𝑖𝑛𝑖𝑡 to the final constraint-compliant D 𝑓 𝑖𝑛𝑎𝑙 . Through this progressive evolution, DBRepro satisfies both the probabilistic global statistics and the deterministic local cardinalities. The resulting D 𝑓 𝑖𝑛𝑎𝑙 serves as the definitive blueprint, directly driving the Tuple Generator to physically synthesize the high-fidelity proxy database required for reproducing queries.

5

SSB (13 Queries)

Consistent Inconsistent Consistent Inconsistent 3 (0) 9 (1) 15 (6) 18 (4) 18 (4)

19 13 7 4 4

7 (4) 10 (8) 12 (3) 13 (4) 13 (4)

6 3 1 0 0

cardinality-constraint formulations are DBMS-independent, PostgreSQL provides a widely used open-source CBO platform for these experiments. For the industrial-scale practicality evaluation in RQ3, we deployed DBRepro on a server with dual HiSilicon Kunpeng-920 processors (128 cores) and 1 TB RAM using KingbaseES V8R6C9B14, a proprietary commercial RDBMS managing the terabyte-scale data. Together, the two systems represent open-source and commercial CBO-based DBMSs. 5.1.2 Baseline Methods. We compare DBRepro against state-of-theart data-driven and workload-aware baseline methods: • RSGen [45]: A data-driven generator that reverses columnlevel statistics to reproduce the original data distribution. It is entirely workload-independent and does not enforce any query-specific cardinality constraints. • Hydra [43]: A workload-aware regenerator that models plan cardinalities through linear programming. It requires schema anonymization at the client side, which causes semantic loss, and its LP formulation supports only a restricted set of filter and equi-join operators. • Touchstone [26]: A workload-aware generator that decomposes query plan trees into constraint chains to satisfy cardinality constraints and support scalable parallel generation. It does not support complex logical predicates. • Mirage [55]: A recent state-of-the-art workload-aware approach tailored for complex analytical workloads. It strictly bounds cardinality deviations through a multi-phase generation strategy and offers the broadest operator support among existing workload-aware methods.

Evaluation

We structure our evaluation around three research questions: RQ1: How does DBRepro compare to existing generation methods in high-fidelity slow query reproduction and end-to-end efficiency? RQ2: How well does DBRepro generalize to unseen queries on the same benchmark schema? RQ3: How does DBRepro perform on commercial DBMSs in realworld industrial scenarios?

5.1

TPC-H (22 Queries)

5.2

RQ1: Reproduction Fidelity

To answer RQ1, we evaluate the end-to-end reproduction fidelity of DBRepro against baselines on the TPC-H [52] and SSB [34] benchmarks. We use scale factor SF=1 to assess reproduction fidelity and SF=200 to evaluate synthesis efficiency. The synthesis quality is measured based on the properties defined in Definition 3.1. Specifically, we report the plan structural match rate (Property 3), the mean relative error of cardinality (RE𝑐𝑎𝑟𝑑 , Property 4), and the mean relative error of latency proportion (RE𝑙𝑎𝑡𝑒𝑛𝑐𝑦 , Property 5). We also measure the end-to-end efficiency via metadata extraction and data generation time. As detailed below, DBRepro achieves the strongest overall fidelity across all metrics among the tested methods.

Experimental Setup

5.1.1 Environment and DBMS. For RQ1 and RQ2, we ran experiments on a server with an Intel Xeon Gold 5220 CPU @ 2.20 GHz (36 cores) and 156 GB RAM using PostgreSQL 14.11. Since the 7

Zhaoyang Zhang, Shuang Liu, Dengfeng Xu, Wei Lu, Jianquan Leng, Sheng Du, and Xiaoyong Du

Touchstone

0.01

All Queries

(d) Avg SCCs RE𝑐𝑎𝑟𝑑

Average RE (%)

80

40

0

DBRepro 100

50

0

All Queries

Valid Queries

All Queries

(e) Avg JCCs RE𝑐𝑎𝑟𝑑

Valid Queries

All Queries

(c) Avg RE𝑙𝑎𝑡𝑒𝑛𝑐𝑦 Average RE (%)

0.01

Valid Queries

Valid Queries

(b) Avg JCCs RE𝑐𝑎𝑟𝑑 Average RE (%)

35 0.01

Average RE (%)

0

All Queries

70

0

50

0.01

Valid Queries

RSGen

0.01

0

(a) Avg SCCs RE𝑐𝑎𝑟𝑑

Mirage

100

0.00

Average RE (%)

40 0.18

Average RE (%)

Hydra 80

0.01

5.2.1 Plan Structural Consistency. To provide a granular analysis of structural fidelity, we classify plan consistency into three categories: (i) Strictly Identical: the synthetic plan perfectly matches the production plan in join order and physical operator types; (ii) Topologically Consistent: the join order matches, but some physical operator types differ (e.g., hash join vs. merge join); and (iii) Inconsistent: join orders diverge, or the baseline fails to support the query’s operators, rendering subsequent operator-level comparisons invalid. As shown in Table 1, DBRepro and the data-driven method RSGen achieve the highest structural consistency. The workload-aware methods ignore global statistics and distort the cost model’s baseline by enforcing cardinality constraints, which mislead the optimizer into selecting divergent join orders. Conversely, data-driven methods preserve these macroscopic distributions. DBRepro harmonizes these paradigms by solving local constraints within the bounds of the global statistical baseline, maintaining structural consistency.

60

30

0

Valid Queries

All Queries

(f) Avg RE𝑙𝑎𝑡𝑒𝑛𝑐𝑦

Figure 5: Comparison of average relative error of cardinality (RE𝑐𝑎𝑟𝑑 ) for SCCs and JCCs, and latency proportion (RE𝑙𝑎𝑡𝑒𝑛𝑐𝑦 ) on TPC-H (top row) and SSB (bottom row). Touchstone

Mirage

RSGen

sf=50

sf=100

dbgen

sf=150

(a) TPC-H

sf=200

0

sf=50

sf=100

sf=150

0.36

0.34

30 0.24

Time (min)

0.80

0.76

0.70

100

0

DBRepro

60

0.60

Time (min)

200

0.31

5.2.2 Relative Error of Cardinality. To comprehensively evaluate downstream fidelity across both the cardinality analysis in this section and the latency evaluation in Section 5.2.3, we employ two distinct metrics inspired by prior works [22, 55]: (1) ValidQueries Mean, which calculates the error exclusively for queries with consistent execution plans to assess the underlying constraint satisfaction accuracy; and (2) All-Queries Mean, which evaluates the overall effectiveness across the benchmark by assigning a 100% error to structurally inconsistent or unsupported queries. Figure 5 shows the average relative cardinality error (RE𝑐𝑎𝑟𝑑 ) for selection and join operators. Data-driven methods (RSGen) assume column independence and thus fail to capture complex multicolumn or cross-table correlations. This causes intermediate cardinalities to exhibit unbounded growth, averaging a 12.4% error for selection operators and exceeding 25.6% for join operators on valid-queries. Workload-aware methods (Hydra, Touchstone), conversely, successfully achieve lower valid-queries errors by explicitly modeling intermediate cardinality constraints. However, their performance severely deteriorates on all-queries due to two limitations. First, mathematically modeling diverse and complex operators is inherently challenging, strictly limiting their applicability to a narrow subset of queries. Second, as shown in Section 5.2.1, their distorted global distributions induce inconsistent plans. Consequently, their successfully satisfied local constraints become entirely ineffective during actual execution, increasing their all-queries mean error. By driving data generation through progressive distribution evolution, DBRepro explicitly models exact cardinality constraints while preserving the vast majority of non-constrained data in line with authentic statistics. This dual-guarantee allows DBRepro to achieve a remarkably low cardinality error on valid-queries, while delivering the lowest all-queries mean error across all benchmarks, reducing the error by 20.3% compared to data-driven baselines.

sf=200

(b) SSB

Figure 6: Overall extraction (upper hatched) and generation (lower solid) efficiency. This misleads the optimizer into selecting divergent physical operators (e.g., swapping a Hash Join for a Nested Loop Join), altering execution time complexity. Second, methods like Hydra and Touchstone neglect data distribution metrics such as NDV, inducing data skew and thus triggering severe hash collisions and unintended disk spilling. Data-driven methods (RSGen) successfully preserve operator types, enabling a low 5% latency proportion error on the simpler SSB. However, on complex workloads like TPC-H, their inability to enforce cross-column constraints triggers cascading intermediate data explosions. This overestimation increases memory consumption and physical costs for downstream operators, raising their comprehensive all-queries latency proportion error to 27%. DBRepro addresses the limitations of both approaches. By providing the optimizer with accurate statistics, it preserves operator types and plan structures. Concurrently, its exact cardinality control prevents unintended memory spilling and physical overheads. As a result, DBRepro achieves the lowest mean latency proportion error on valid-queries (3.29% on TPC-H and 1.06% on SSB), reducing the error by 21.5% compared to workload-aware methods. 5.2.4 Extraction and Generation Efficiency. To evaluate end-to-end efficiency, we measure the total execution time across varying scale factors and decompose it into online context extraction and offline data generation. As shown in Figure 6, the hatched and solid bars represent these two stages, respectively. Touchstone reports only its generation time because the constraint formulation must be manually constructed from the target workload. This human effort does not constitute an automated extraction stage and is not included in its reported runtime; consequently, its end-to-end cost

5.2.3 Relative Error of Latency Proportion. Achieving latency fidelity (Figure 5 (c) and Figure 5 (f)) is drastically more complex than satisfying cardinalities, as execution time is sensitive to physical overheads like data skew, CPU hash collisions, and I/O spilling. Workload-aware methods struggle with latency reproduction due to two inherent limitations. First, by ignoring global statistics, they disrupt the Cost-Based Optimization (CBO) mechanism [24]. 8

DBRepro: Automated Database Synthesis via a Hybrid Constraint-Solving Approach for Reproducing Slow Queries

Table 2: Plan structural consistency on LLM-synthesized unseen queries across different complexity levels.

Touchstone Mirage RSGen DBRepro

SSB (10 Queries)

Low(3) Med(4) High(3) Low(3) Med(4) High(3) 2 3 3 3

1 2 4 4

0 0 1 1

3 3 3 3

2 3 4 4

0 0 2 3

Mirage

50

0

RSGen

Average RE (%)

Methods

TPC-H (10 Queries)

Average RE (%)

Generation

Touchstone

100

TPC-H

SSB

(a) Average RE𝑐𝑎𝑟𝑑

DBRepro

100

50

0

TPC-H

SSB

(b) Average RE𝑙𝑎𝑡𝑒𝑛𝑐𝑦

Figure 7: Average relative error of cardinality and latency proportion on LLM-synthesized unseen queries.

5.3

Hydra

Touchstone Histogram RE (%)

NDV RE (%)

100 50 0

sf=1

sf=10

Mirage

RSGen

100 50 0

DBRepro MCV RE (%)

is not directly comparable with those of automated methods. In contrast, dbgen generates standard benchmark data directly from predefined specifications and therefore requires no productioncontext extraction. During data generation, DBRepro is approximately 2× slower than Mirage. This is an anticipated trade-off: DBRepro’s hybrid algorithm must initially synthesize baseline data to satisfy global statistics before constructing and solving the CP problem for JCCs. However, because this generation occurs entirely offline in the simulation environment, it is highly insensitive to time overhead. Conversely, the extraction phase executes directly on the resourcecritical production database, making the minimization of intrusion paramount. As illustrated, DBRepro extracts existing slow-query execution plans and catalog metadata without full-table scans. Its extraction time is therefore independent of the underlying data volume and instead depends on the aggregate size of the recorded slow-query execution plans and the numbers of their referenced tables and columns. In contrast, RSGen and Mirage require expensive full-table aggregation queries to derive precise global bounds, causing their extraction times to scale linearly with data volume. This reduction in online extraction overhead compensates for the offline generation cost, allowing DBRepro to achieve roughly 1.5× and 3× the overall efficiency of RSGen and Mirage respectively.

sf=1

50 0

sf=10

Postgres

100

sf=1

sf=10

(a) Relative errors of statistics for TPC-H (NDV, Histogram, MCV)

50 0

sf=1

sf=10

100

MCV RE (%)

Histogram RE (%)

NDV RE (%)

100

50 0

sf=1

sf=10

100 50 0

sf=1

sf=10

(b) Relative errors of statistics for SSB (NDV, Histogram, MCV)

Figure 8: Comparison of relative statistics errors between the synthetic and original databases. contrast, both RSGen and DBRepro preserve macroscopic execution structures across the three complexity levels, with DBRepro improving overall fidelity by approximately 10% over RSGen. RSGen’s inability to model multi-column distributions can cause cascading cardinality underestimation on unseen queries with crosscolumn predicates. DBRepro’s advantage stems from two factors. First, the historical workloads used during synthesis cover diverse business scenarios, improving estimates for unseen queries that share similar predicates or join keys. Second, satisfying complex constraint chains during generation implicitly embeds business semantics and joint distributions into the physical data. Consequently, the optimizer encounters more faithful physical correlations even for complex unseen queries, supporting DBRepro’s generalization beyond the synthesis workload.

RQ2: Generalization and Statistical Fidelity

To answer RQ2, we conduct two interconnected evaluations. First, we test generalizability using 20 unseen queries (10 per benchmark, spanning three complexity levels) synthesized by GPT-4o. The queries were generated from the benchmark schemas and workloads and manually verified for syntactic correctness and successful execution. Second, to explain the statistical basis of this generalization capability, we assess statistical consistency by directly measuring the recovery accuracy of the underlying database statistics and data densities across value ranges.

5.3.2 Fidelity on Synthesized Databases’ Statistics. To examine the statistical basis of DBRepro’s generalization and structural consistency, we evaluate the fidelity of the underlying data distributions. We measure relative errors in three core statistical components extracted from each proxy database: NDV, equi-width histograms, and MCV frequencies. We also use native PostgreSQL statistics collected from the original database as a reference. Because ANALYZE constructs statistics through sampling rather than exact counting, this reference captures the system’s intrinsic estimation error and provides a practical baseline for evaluating synthesized data. Figure 8 shows that workload-aware methods substantially distort the base distributions. Enforcing isolated query constraints without a global statistical anchor changes the distributions on which the optimizer’s estimates depend. In contrast, RSGen and

5.3.1 Performance on LLM-Synthesized Unseen Workloads. We compare the reproduction fidelity of proxy databases generated by each method. Hydra is excluded because its forced schema anonymization and redundant data generation make this generalization test inapplicable. As shown in Table 2 and Figure 7, workload-aware methods struggle with high-complexity unseen queries. Novel queries introduce different predicate combinations and join topologies; without a global distribution foundation, the optimizer is easily driven toward divergent plans, substantially increasing their all-queries errors. In 9

Zhaoyang Zhang, Shuang Liu, Dengfeng Xu, Wei Lu, Jianquan Leng, Sheng Du, and Xiaoyong Du

Touchstone

Mirage

RSGen

80 60 40 20 0

1%

5%

10%

20%

50%

Rows:202 Repro:202 InitPlan 1(return $0)

80 60

Index Only Scan

40

on schema2.table5 using s2_t5_colpk_idx

0

5%

10%

20%

#Tbl.

#Scan

Q1 Q2 Q3 Q4 Q5 Q6

80 140 207 91 47 142

1 6 5 6 6 4

2 6 5 8 6 4

Avg.

117.8

4.67

5.17

#Join

Hash Left Join

Rows:9,141,228

SCCs RE𝑐𝑎𝑟𝑑

JCCs

Latency

RE𝑐𝑎𝑟𝑑

RE𝑙𝑎𝑡𝑒𝑛𝑐𝑦

0 5 3 3 5 3

175.6 45.7 234.0 10.8 84.5 62.1

0.00 0.00 0.00 0.64 0.00 0.00

0.00 3.43 0.00 0.00 0.00 16.20

7.07 0.72 1.91 3.34 1.43 13.80

3.17

102.1

0.11

3.27

4.71

#5

Repro:630,289

Seq Scan

#225

on schema1.table2 Timing: 26s8ms Repro:26s Proportion: 11% Repro:10.5%

Index Only Scan #224

on schema1.table1.pk = schema2.table0.fk #2 by Optimizer] [Join Elimination

Reproduction error Time (s)

Rows:630,271

Rows:9,141,228

Table 3: Industrial workload and reproduction errors (%). Tbl.: distinct base tables; Scan/Join: logical operators before optimizer elimination (partition scans grouped). Workload characteristics

#4

on schema2.table1.pk = schema2.table0.fk [Join Elimination by Optimizer]

Figure 9: Average relative cardinality errors of range queries.

#3

on schema1.table2.nonkey1 = schema2.table0.fk Timing:18s57ms Repro:18s7ms Proportion:8.1% Repro:7.3%

Hash Left Join

50%

Repro: 9,141,228

Hash Left Join

Rows:9,141,228 1%

(b) SSB

DB (GB)

Rows: 9,141,228

#2

20

(a) TPC-H

Q

Repro Total Time: 4m7s

SimpleAggregate #1

100

Average RE (%)

Average RE (%)

100

Total Timing: 3m54s

DBRepro

Repro: 9,141,228

#6

Append

Index Only Scan #223 on schema1.table1

Timing: 705ms | 0.3% Rows:0

Rows:459,266

Seq Scan

#7 Seq Scan

on schema2. table0_ppmin

on schema2.table1

Rows:1,377,431

#8

Rows:0

Seq Scan #221 Seq Scan #222

on schema2. ··· ··· on schema2. on schema2. table0_p5140100 200+ table0_p5151721 table0_ppmax partitions

All partitions filter used: t1col1 <> '987654321' AND t1col2 = ANY(ARRAY[$0]) Total Seq Scan Timing: 3m9s | 80.5%

Repro:3m13s | 79.9%

DBRepro approach the PostgreSQL sampling reference. They perform comparably on NDV and histograms, while DBRepro’s MCV error is 5% higher on average. This deviation is an expected trade-off: to satisfy exact SCCs, Distribution Fusion explicitly adjusts selected MCV frequencies when they conflict with the initial statistics. Unlike a purely data-driven reconstruction that cannot enforce these local cardinalities, this targeted adjustment preserves the distribution as closely as possible while satisfying the workload constraints. Figure 9 further evaluates the reconstructed data density using range queries with selectivities from 1% to 50%. These queries directly probe histogram fidelity and the allocation of probability mass across value ranges. Consistent with the statistical metrics, DBRepro and RSGen outperform workload-aware methods at every selectivity level. The results confirm that DBRepro retains sufficient global distribution fidelity to support optimizer decisions on unseen queries while enforcing the cardinalities required by the workload.

Figure 10: Original physical execution plan of industrial slow query Q3, annotated with reproduction results.

5.4

5.4.2 Case Study: Execution Plan Analysis. Figure 10 shows Q3’s five-table plan: a four-table left-join tree plus a scalar InitPlan lookup, running for nearly four minutes. Reproducing this plan presents three major challenges. First, without consistent integrity constraints and global statistics, the optimizer may fail to trigger Join Elimination (Nodes #4 and #5), causing structural divergence. Second, its SCCs span vastly different scales. Even a minor error in the tiny InitPlan (#2) can alter cost estimates, whereas the Seq Scan on the 200-partition schema2.table0 must precisely filter 40 million rows to 9.1 million. This scan is the primary bottleneck, accounting for 80.5% of total latency. Third, the final Hash Left Join (#3) imposes a non-key JCC (nonkey1) requiring exactly 9.1 million output rows. Solvers designed only for PK-FK relationships cannot control the unpredictable fan-out of this join. DBRepro addresses these challenges by combining heuristic inference with Distribution Fusion, achieving 0% SCC error and exact

reproduced identical plan structures. The SCC error remains below 0.64% for every query, while the mean SCC, JCC, and latencyproportion errors are 0.11%, 3.27%, and 4.71%, respectively. Q6 is the most challenging case because most of its joins are non-PK-FK. Precisely reproducing their fan-out would require exact key-frequency distributions for the pseudo-PK columns used by the Scaling Factor model, whose collection is costly on the production system. DBRepro instead estimates scaling factors from lightweight statistics, trading some JCC accuracy for low-overhead extraction while retaining the identical plan structure. These results demonstrate consistent fidelity at both optimizer and operator levels across heterogeneous industrial workloads.

RQ3: Practicality in Commercial DBMS

To answer RQ3, we evaluate DBRepro’s performance on commercial DBMSs in real-world industrial scenarios. Specifically, we deploy DBRepro on KingbaseES to synthesize a nearly 1 TB proxy database (serving over 20 million users) that contains 5 schemas, nearly 200 base tables, and over 5,000 physical partitions. The target workload includes six complex analytical slow queries extracted from the production environment, with an average execution time exceeding 100 seconds. We evaluate the reproduction fidelity using the same plan structural, cardinality, and latency metrics applied in RQ1. Table 3 reports the anonymized workload characteristics and perquery reproduction errors. Q3 is the case study shown in Figure 10. 5.4.1 End-to-End Reproduction Fidelity. Across all six real-world slow queries, which span 47–207 GB of data, 1–6 base tables, 2–8 scans, 0–5 joins, and execution times of 10.8–234.0 seconds, DBRepro 10

DBRepro: Automated Database Synthesis via a Hybrid Constraint-Solving Approach for Reproducing Slow Queries

input cardinalities for the table scans. Its Scaling Factor mechanism further eliminates fan-out error for the non-key JCC. Consequently, the synthetic latency distribution closely matches the original: all bottleneck operators contributing over 5% of total latency remain below 1% relative error. Preserving both the optimizer’s structural decisions and the operator-level bottleneck profile demonstrates the practical value of the hybrid design for diagnosing industrial performance anomalies.

5.5

specific intermediate-result sizes [2, 3, 25, 26, 29, 33, 41–43, 55]. Coverage-based approaches automatically generate test databases and SQL inputs that satisfy query constraints and maximize objectives such as code or execution-path coverage [9, 11, 39, 48, 49, 54]. Related DBMS testing techniques also synthesize SQL inputs for semantic differential testing or derive generation strategies from empirical bug patterns [27, 28]. Learning-based approaches use supervised autoregressive models to efficiently synthesize databases from large query workloads [56].

Threats to Validity

7

Internal validity. Threats concern the implementation of DBRepro and the experimental measurements. Its analyzer produces constraint models for a comprehensive subset of relational operators, including unary, logical, and arithmetic selections as well as PK-FK and non-key joins. We used pair programming to check implementation correctness. Execution-latency measurements may also be affected by environmental noise; to reduce this error, we flushed the OS and DBMS caches before execution and reported the arithmetic mean of multiple runs. External validity. Threats arise from the database systems selected for evaluation, since two systems cannot cover all RDBMSs. We chose PostgreSQL and KingbaseES to represent widely used opensource and commercial DBMSs driven by cost-based optimizers. Although this choice does not establish generality across every optimizer architecture, DBRepro relies on standard catalog statistics used by CBOs rather than system-specific internals, supporting its applicability to other systems exposing comparable metadata.

6

Conclusion

We presented DBRepro, an automated database synthesis framework that combines data-driven and workload-aware methodologies for offline slow query reproduction. By formulating database generation as a constrained distribution synthesis problem, DBRepro progressively adjusts an initial global statistical distribution to satisfy exact local cardinality constraints. Its hybrid solver uses heuristic probabilistic inference and Distribution Fusion for SCCs, together with a Scaling Factor-enhanced CP model for non-PK-FK joins. By reusing native DBMS slow-query records and non-intrusive catalog metadata, it avoids online query re-execution and base-table scans. This enables efficient runtime-context extraction whose cost is independent of the stored data volume, without accessing or exposing sensitive raw production tuples. Extensive evaluations demonstrate high-fidelity reproduction across structural, cardinality, and latency metrics. Compared with data-driven baselines, DBRepro reduces cardinality error by up to 20.3%; compared with workload-aware methods, it lowers latencyproportion error by 21.5% while reproducing 15% more consistent execution plans. We further validated its practicality on a 1 TB realworld industrial dataset managed by KingbaseES, demonstrating its utility for offline performance diagnosis.

Related Work

Database synthesis techniques fall into three paradigms: Independent Synthesis. Independent synthesis methods construct databases from scratch without relying on existing production data. They are widely used to generate scalable datasets for standard performance benchmarks [13, 17]. For more flexible scenarios, statistical model-based tools let users specify data distributions and dependencies through configuration files [1, 4, 12, 16, 18, 38, 47], while commercial generators provide extensive user-defined generation capabilities [14, 31, 53]. Recent systems further employ LLM agents to synthesize datasets from natural-language instructions [51]. However, they cannot recover workload-specific characteristics from production. Data-driven Synthesis. Data-driven approaches synthesize instances that preserve the characteristics of an existing source database. Metadata-based methods reconstruct data by inversely mapping catalog statistics [20, 21, 37, 45, 46]. Representative sample methods expand an authentic data sample to a target volume while maintaining its macroscopic distributions [5–7, 32, 50, 58]. Additionally, probabilistic generative models with differential privacy synthesize relational data safely [8, 15, 35, 57]. This grounding yields more realistic global characteristics than independent generation. However, preserving global statistics alone does not guarantee exact intermediate cardinalities for a target workload. Workload-aware Synthesis. Workload-aware methods synthesize databases explicitly guided by query workloads and execution requirements. Constraint-based methods formulate synthesis as a constraint satisfaction problem, generating tuples that satisfy

Acknowledgments This work is supported by the National Natural Science Foundation of China under Grant Nos. 62472429, 62441230, the Fundamental Research Funds for the Central Universities, the Research Funds of Renmin University of China, Key Laboratory of Data Engineering and Knowledge Engineering MOE, and the A3 Foresight Program No. 62461146205. We gratefully acknowledge the support from the RUC Kingbase Database Collaborative Innovation Joint Laboratory.

11

Zhaoyang Zhang, Shuang Liu, Dengfeng Xu, Wei Lu, Jianquan Leng, Sheng Du, and Xiaoyong Du

Data Availability Statement

//dl.acm.org/doi/10.5555/1182635.1164254 [21] Joseph W. Hu, Ivan T. Bowman, Anisoara Nica, and Anil Goel. 2019. DistributionDriven, Embedded Synthetic Data Generation System and Tool for RDBMS. In 2019 IEEE 35th International Conference on Data Engineering Workshops (ICDEW). 113–115. doi:10.1109/ICDEW.2019.00-25 [22] Xuhua Huang, Zirui Hu, Siyang Weng, Rong Zhang, Chengcheng Yang, Xuan Zhou, Weining Qian, Chuanhui Yang, and Quanqing Xu. 2025. A Query-Aware Enormous Database Generator For System Performance Evaluation. In Companion of the 2025 International Conference on Management of Data (Berlin, Germany) (SIGMOD/PODS ’25). Association for Computing Machinery, New York, NY, USA, 131–134. doi:10.1145/3722212.3725076 [23] C Terrance Ireland and Solomon Kullback. 1968. Contingency tables with given marginals. Biometrika 55, 1 (1968), 179–188. doi:10.1093/biomet/55.1.179 [24] Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2015. How good are query optimizers, really? Proc. VLDB Endow. 9, 3 (Nov. 2015), 204–215. doi:10.14778/2850583.2850594 [25] Hao Li, Qingshuai Wang, Zirui Hu, Xuhua Huang, Lyu Ni, Rong Zhang, Peng Cai, Xuan Zhou, and Quanqing Xu. 2024. Touchstone+: Query Aware Database Generation for Match Operators. In Database Systems for Advanced Applications: 29th International Conference, DASFAA 2024, Gifu, Japan, July 2–5, 2024, Proceedings, Part I (Gifu, Japan). Springer-Verlag, Berlin, Heidelberg, 266–282. doi:10.1007/978-981-97-5552-3_18 [26] Yuming Li, Rong Zhang, Xiaoyan Yang, Zhenjie Zhang, and Aoying Zhou. 2018. Touchstone: generating enormous query-aware test databases. In Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference (Boston, MA, USA) (USENIX ATC ’18). USENIX Association, USA, 575–586. https://dl. acm.org/doi/10.5555/3277355.3277411 [27] Shuang Liu, Chenglin Tian, Jun Sun, Ruifeng Wang, Wei Lu, Yongxin Zhao, Yinxing Xue, Junjie Wang, and Xiaoyong Du. 2024. Semantic Conformance Testing of Relational DBMS. Proc. VLDB Endow. 18, 3 (Nov. 2024), 850–862. doi:10.14778/3712221.3712247 [28] Shuang Liu, Ruifeng Wang, Yuanfeng Xie, Junjie Chen, Wei Lu, Xiao Zhang, Quanqing Xu, Chuanhui Yang, and Xiaoyong Du. 2025. A Comprehensive Study of Bugs in Relational DBMS. IEEE Transactions on Software Engineering 51, 12 (2025), 3654–3668. doi:10.1109/TSE.2025.3625300 [29] Eric Lo, Nick Cheng, Wilfred W. Lin, Wing-Kai Hon, and Byron Choi. 2014. MyBenchmark: generating databases for query workloads. The VLDB Journal 23, 6 (Dec. 2014), 895–913. doi:10.1007/s00778-014-0354-1 [30] Minghua Ma, Zheng Yin, Shenglin Zhang, Sheng Wang, Christopher Zheng, Xinhao Jiang, Hanwen Hu, Cheng Luo, Yilin Li, Nengjun Qiu, Feifei Li, Changcheng Chen, and Dan Pei. 2020. Diagnosing root causes of intermittent slow queries in cloud databases. Proc. VLDB Endow. 13, 8 (April 2020), 1176–1189. doi:10.14778/ 3389133.3389136 [31] Mark Brocato. 2015. Mockaroo. Mockaroo. https://www.mockaroo.com/ [Online; accessed 2026-04-10]. [32] Zijian Ming, Chunjie Luo, Wanling Gao, Rui Han, Qiang Yang, Lei Wang, and Jianfeng Zhan. 2014. Bdgs: A scalable big data generator suite in big data benchmarking. In Advancing Big Data Benchmarks: Proceedings of the 2013 Workshop Series on Big Data Benchmarking, WBDB. cn, Xi’an, China, July16-17, 2013 and WBDB. us, San José, CA, USA, October 9-10, 2013, Revised Selected Papers 0. Springer, 138–154. doi:10.1007/978-3-319-10596-3_11 [33] Parimarjan Negi, Laurent Bindschaedler, Mohammad Alizadeh, Tim Kraska, Jyoti Leeka, Anja Gruenheid, and Matteo Interlandi. 2023. Unshackling database benchmarking from synthetic workloads. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 3659–3662. doi:10.1109/ICDE55515.2023.00292 [34] Patrick O’Neil, Elizabeth O’Neil, Xuedong Chen, and Stephen Revilak. 2009. The Star Schema Benchmark and Augmented Fact Table Indexing. Springer-Verlag, Berlin, Heidelberg, 237–252. doi:10.1007/978-3-642-10424-4_17 [35] Neha Patki, Roy Wedge, and Kalyan Veeramachaneni. 2016. The Synthetic Data Vault. In 2016 IEEE International Conference on Data Science and Advanced Analytics (DSAA). 399–410. doi:10.1109/DSAA.2016.49 [36] Laurent Perron and Vincent Furnon. 2021. OR-Tools. Google. https://developers. google.com/optimization/ [Online; accessed 2026-04-08]. [37] Tilmann Rabl, Manuel Danisch, Michael Frank, Sebastian Schindler, and HansArno Jacobsen. 2015. Just can’t get enough: Synthesizing Big Data. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (Melbourne, Victoria, Australia) (SIGMOD ’15). Association for Computing Machinery, New York, NY, USA, 1457–1462. doi:10.1145/2723372.2735378 [38] Tilmann Rabl, Michael Frank, Hatem Mousselly Sergieh, and Harald Kosch. 2010. A data generator for cloud-scale benchmarking. In Proceedings of the Second TPC Technology Conference on Performance Evaluation, Measurement and Characterization of Complex Systems (Singapore) (TPCTC’10). Springer-Verlag, Berlin, Heidelberg, 41–56. doi:10.1007/978-3-642-18206-8_4 [39] Zhilei Ren, Shaozheng Dong, Xiaochen Li, Zongzheng Chi, and He Jiang. 2020. Many-Objective Test Database Generation for SQL. In Parallel Problem Solving from Nature – PPSN XVI: 16th International Conference, PPSN 2020, Leiden, The Netherlands, September 5-9, 2020, Proceedings, Part II (Leiden, The Netherlands). Springer-Verlag, Berlin, Heidelberg, 229–242. doi:10.1007/978-3-030-58115-2_16

Our source code and benchmark datasets are publicly available [59]. The real-world industrial dataset used in Section 5.4 cannot be publicly shared due to strict corporate data privacy regulations.

References [1] Alexander Alexandrov, Kostas Tzoumas, and Volker Markl. 2012. Myriad: scalable and expressive data generation. Proc. VLDB Endow. 5, 12 (Aug. 2012), 1890–1893. doi:10.14778/2367502.2367530 [2] Arvind Arasu, Raghav Kaushik, and Jian Li. 2011. Data generation using declarative constraints. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data (Athens, Greece) (SIGMOD ’11). Association for Computing Machinery, New York, NY, USA, 685–696. doi:10.1145/1989323.1989395 [3] Carsten Binnig, Donald Kossmann, Eric Lo, and M. Tamer Özsu. 2007. QAGen: generating query-aware test databases. In Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data (Beijing, China) (SIGMOD ’07). Association for Computing Machinery, New York, NY, USA, 341–352. doi:10. 1145/1247480.1247520 [4] Nicolas Bruno and Surajit Chaudhuri. 2005. Flexible database generators. In Proceedings of the 31st International Conference on Very Large Data Bases (Trondheim, Norway) (VLDB ’05). VLDB Endowment, 1097–1107. https://dl.acm.org/ doi/10.5555/1083592.1083719 [5] Teodora Sandra Buda, Thomas Cerqueus, Cristian Grava, and John Murphy. 2017. ReX: Representative extrapolating relational databases. Information Systems 67 (2017), 83–99. doi:10.1016/j.is.2017.03.001 [6] Teodora Sandra Buda, Thomas Cerqueus, John Murphy, and Morten Kristiansen. 2013. CoDS: A representative sampling method for relational databases. In International Conference on Database and Expert Systems Applications. Springer, 342–356. doi:10.1007/978-3-642-40285-2_30 [7] Teodora Sandra Buda, Thomas Cerqueus, John Murphy, and Morten Kristiansen. 2014. VFDS: An Application to Generate Fast Sample Databases. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management (Shanghai, China) (CIKM ’14). Association for Computing Machinery, New York, NY, USA, 2048–2050. doi:10.1145/2661829.2661845 [8] Kuntai Cai, Xiaokui Xiao, and Graham Cormode. 2023. PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy. Proc. ACM Manag. Data 1, 2, Article 142 (June 2023), 25 pages. doi:10.1145/3589287 [9] Jeroen Castelein, Maurício Aniche, Mozhan Soltani, Annibale Panichella, and Arie van Deursen. 2018. Search-Based Test Data Generation for SQL Queries. In 2018 IEEE/ACM 40th International Conference on Software Engineering (ICSE). 1220–1230. doi:10.1145/3180155.3180202 [10] Surajit Chaudhuri. 1998. An overview of query optimization in relational systems. In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (Seattle, Washington, USA) (PODS ’98). Association for Computing Machinery, New York, NY, USA, 34–43. doi:10.1145/275487.275492 [11] Claudio de la Riva, María José Suárez-Cabal, and Javier Tuya. 2010. Constraintbased test database generation for SQL queries. In Proceedings of the 5th Workshop on Automation of Software Test (Cape Town, South Africa) (AST ’10). Association for Computing Machinery, New York, NY, USA, 67–74. doi:10.1145/1808266. 1808276 [12] Bailu Ding, Surajit Chaudhuri, Johannes Gehrke, and Vivek Narasayya. 2021. DSB: a decision support benchmark for workload-driven and traditional database systems. Proc. VLDB Endow. 14, 13 (Sept. 2021), 3376–3388. doi:10.14778/3484224. 3484234 [13] electrum. 2011. tpch-dbgen. GitHub. https://github.com/electrum/tpch-dbgen [Online; accessed 2026-04-10]. [14] EMS Software Development. 2026. EMS Data Generator. SQL Manager. https: //www.sqlmanager.net/products/datagenerator [Online; accessed 2026-04-10]. [15] Yunqing Ge, Jianbin Qin, Shuyuan Zheng, Yongrui Zhong, Bo Tang, Yu-Xuan Qiu, Rui Mao, Ye Yuan, Makoto Onizuka, and Chuan Xiao. 2024. Privacy-Enhanced Database Synthesis for Benchmark Publishing. Proc. VLDB Endow. 18, 2 (Oct. 2024), 413–425. doi:10.14778/3705829.3705855 [16] Jim Gray, Prakash Sundaresan, Susanne Englert, Ken Baclawski, and Peter J. Weinberger. 1994. Quickly generating billion-record synthetic databases. SIGMOD Rec. 23, 2, 243–252. doi:10.1145/191843.191886 [17] gregrahn. 2012. tpcds-kit. GitHub. https://github.com/gregrahn/tpcds-kit [Online; accessed 2026-04-10]. [18] Joseph E. Hoag and Craig W. Thompson. 2007. A parallel general-purpose synthetic data generator. SIGMOD Rec. 36, 1 (March 2007), 19–24. doi:10.1145/ 1276301.1276305 [19] Wassily Hoeffding. 1963. Probability inequalities for sums of bounded random variables. Journal of the American statistical association 58, 301 (1963), 13–30. doi:10.1080/01621459.1963.10500830 [20] Kenneth Houkjær, Kristian Torp, and Rico Wind. 2006. Simple and realistic data generation. In Proceedings of the 32nd International Conference on Very Large Data Bases (Seoul, Korea) (VLDB ’06). VLDB Endowment, 1243–1246. https: 12

DBRepro: Automated Database Synthesis via a Hybrid Constraint-Solving Approach for Reproducing Slow Queries

[40] Ashoke S. and Jayant R. Haritsa. 2015. CODD: a dataless approach to big data testing. Proc. VLDB Endow. 8, 12 (Aug. 2015), 2008–2011. doi:10.14778/2824032. 2824123 [41] Anupam Sanghi, Shadab Ahmed, and Jayant R. Haritsa. 2022. Projectioncompliant database generation. Proc. VLDB Endow. 15, 5 (Jan. 2022), 998–1010. doi:10.14778/3510397.3510398 [42] Anupam Sanghi, Raghav Sood, Jayant R. Haritsa, and Srikanta Tirthapura. 2018. Scalable and Dynamic Regeneration of Big Data Volumes. In Proceedings of the 21th International Conference on Extending Database Technology, EDBT 2018, Vienna, Austria, March 26-29, 2018. OpenProceedings.org, 301–312. doi:10.5441/ 002/edbt.2018.27 [43] Anupam Sanghi, Raghav Sood, Dharmendra Singh, Jayant R. Haritsa, and Srikanta Tirthapura. 2018. HYDRA: a dynamic big data regenerator. Proc. VLDB Endow. 11, 12 (Aug. 2018), 1974–1977. doi:10.14778/3229863.3236238 [44] P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. 1979. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data (Boston, Massachusetts) (SIGMOD ’79). Association for Computing Machinery, New York, NY, USA, 23–34. doi:10.1145/582095.582099 [45] Entong Shen and Lyublena Antova. 2013. Reversing statistics for scalable test databases generation. In Proceedings of the Sixth International Workshop on Testing Database Systems (New York, New York) (DBTest ’13). Association for Computing Machinery, New York, NY, USA, Article 7, 6 pages. doi:10.1145/2479440.2479445 [46] Ghanem Soltana, Mehrdad Sabetzadeh, and Lionel C. Briand. 2017. Synthetic data generation for statistical testing. In Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering (Urbana-Champaign, IL, USA) (ASE ’17). IEEE Press, 872–882. doi:10.1109/ASE.2017.8115698 [47] John M. Stephens and Meikel Poess. 2004. MUDD: a multi-dimensional data generator. In Proceedings of the 4th International Workshop on Software and Performance (Redwood Shores, California) (WOSP ’04). Association for Computing Machinery, New York, NY, USA, 104–109. doi:10.1145/974044.974060 [48] Maria Jose Suárez-Cabal, C De La Riva, and Javier Tuya. 2010. Populating test databases for testing SQL queries. IEEE Latin America Transactions 8, 2 (2010), 164–171. doi:10.1109/TLA.2010.5514443

[49] María José Suárez-Cabal, Claudio Riva, Javier Tuya, and Raquel Blanco. 2017. Incremental test data generation for database queries. Automated Software Engg. 24, 4 (Dec. 2017), 719–755. doi:10.1007/s10515-017-0212-7 [50] Y.C. Tay, Bing Tian Dai, Daniel T. Wang, Eldora Y. Sun, Yong Lin, and Yuting Lin. 2013. UpSizeR: Synthetically scaling an empirical relational database. Information Systems 38, 8 (2013), 1168–1183. doi:10.1016/j.is.2013.07.004 [51] Tonic.ai. 2026. Tonic Fabricate. Tonic.ai. https://www.tonic.ai/ [Online; accessed 2026-04-10]. [52] Transaction Processing Performance Council. 2006. TPC-H Benchmark V3.0. https://www.tpc.org/tpch/ [Online; accessed 2026-04-10]. [53] Upscene Productions. 2020. Advanced Data Generator. Upscene. https://www. upscene.com/advanced_data_generator/ [Online; accessed 2026-04-10]. [54] Margus Veanes, Nikolai Tillmann, and Jonathan De Halleux. 2010. Qex: Symbolic SQL query explorer. In Logic for Programming, Artificial Intelligence, and Reasoning: 16th International Conference, LPAR-16, Dakar, Senegal, April 25–May 1, 2010, Revised Selected Papers 16. Springer, 425–446. doi:10.1007/978-3-642-17511-4_24 [55] Qingshuai Wang, Hao Li, Zirui Hu, Rong Zhang, Chengcheng Yang, Peng Cai, Xuan Zhou, and Aoying Zhou. 2024. Mirage: Generating Enormous Databases for Complex Workloads. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). 3989–4001. doi:10.1109/ICDE60146.2024.00306 [56] Jingyi Yang, Peizhi Wu, Gao Cong, Tieying Zhang, and Xiao He. 2022. SAM: Database Generation from Query Workloads with Supervised Autoregressive Models. In Proceedings of the 2022 International Conference on Management of Data (Philadelphia, PA, USA) (SIGMOD ’22). Association for Computing Machinery, New York, NY, USA, 1542–1555. doi:10.1145/3514221.3526168 [57] Jun Zhang, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, and Xiaokui Xiao. 2017. PrivBayes: Private Data Release via Bayesian Networks. ACM Trans. Database Syst. 42, 4, Article 25 (Oct. 2017), 41 pages. doi:10.1145/3134428 [58] J. W. Zhang and Y. C. Tay. 2016. Dscaler: synthetically scaling a given relational database. Proc. VLDB Endow. 9, 14 (Oct. 2016), 1671–1682. doi:10.14778/3007328. 3007333 [59] Zhaoyang Zhang. 2026. DBRepro: Source Code and Datasets. Zenodo. doi:10. 5281/zenodo.21619545

13

Related documents

• Running with scissors: Fast queries on just-in-time databases#433463
• Tailwind: A Practical Framework for Query Accelerators#155427
• Logos: Certified Order-Sensitive SQL Rewrites with Mechanized Semantics and LLM Guidance#616853
• Logos: Certified Order-Sensitive SQL Rewrites with Mechanized Semantics and LLM Guidance#616353
• Logos: Certified Order-Sensitive SQL Rewrites with Mechanized Semantics and LLM Guidance#459763