A Benchmark Harness for Query Execution Correctness Verification and Query Optimizer Evaluation of Database Systems

Abstract

Query engines are the cornerstone of any relational databases, including query optimizers and query executors. It is imperative for database developers to be equipped with a tool to detect the query execution bug and evaluate the query optimizer quality during rapid iterative development phases. We propose a testing framework for query (especially join) execution verification, cardinality estimation benchmarking, and join order selection evaluation. Our core components are a data and schema generator, a complex and effective join query generator, as well as an exact cardinality and join oracle generator. In the data and schema generator, we propose a PK-driven deterministic data generation mechanism which not only compresses the entire database in a memory-saving way via mathematical relationships but also enables our tool to be aware of data and orchestrate data meaningfully. We can generate large-scale data with customizable skewness and a complex schema with rich joinable key sets, providing an ample search space for diverse join generation. For the join query generation, we implement a complex join template generator which covers intricate join graphs including chain join, star join, tree join, cycle query, and other complex join graphs. The biggest obstacle preventing existing database fuzzers from generating massive joins is to ensure their meaningfulness. To address it, we propose a synergy-aware and result-guided query parameter inference method to quantify and infer the sample spaces for query parameters, guaranteeing the effectiveness of complex join queries. In terms of the exact cardinality and join oracle generation, we formulate the Join Query Processing as the Constraint Satisfaction Problem (CSP) and build a true cardinality and join oracle generator on top of SMT solvers, providing a formal, provable, and highly reliable solution for generating exact cardinality and join ground-truth results in a self-inferable way. Our tool has been collaborating with many famous database vendors such as OceanBase, demonstrating its effectiveness by evaluating it on many open-sourced databases regarding cardinality estimation benchmarking, join order performance diagnostics, and logic bug detection.