Detecting Logic Bugs of Join Optimizations in DBMS

Citations Over TimeTop 10% of 2023 papers

Abstract

Generation-based testing techniques have shown their effectiveness in detecting logic bugs of DBMS, which are often caused by improper implementation of query optimizers. Nonetheless, existing generation-based debug tools are limited to single-table queries and there is a substantial research gap regarding multi-table queries with join operators. In this paper, we propose TQS, a novel testing framework targeted at detecting logic bugs derived by queries involving multi-table joins. Given a target DBMS, TQS achieves the goal with two key components: Data-guided Schema and Query Generation (DSG) and Knowledge-guided Query Space Exploration (KQE). DSG addresses the key challenge of multi-table query debugging: how to generate ground-truth (query, result) pairs for verification. It adopts the database normalization technique to generate a testing schema and maintains a bitmap index for result tracking. To improve debug efficiency, DSG also artificially inserts some noises into the generated data. To avoid repetitive query space search, KQE forms the problem as isomorphic graph set discovery and combines the graph embedding and weighted random walk for query generation. We evaluated TQS on four popular DBMSs: MySQL, MariaDB, TiDB and PolarDB. Experimental results show that TQS is effective in finding logic bugs of join optimization in database management systems. It successfully detected 115 bugs within 24 hours, including 31 bugs in MySQL, 30 in MariaDB, 31 in TiDB, and 23 in PolarDB respectively.

Related Papers

• → Application of Filters to Multiway Joins in MapReduce(2014)6 cited
• → A comparative evaluation of techniques for N-way joins in wireless sensors networks(2020)3 cited
• → Faster joins, self-joins and multi-way joins using join indices(1998)15 cited
• The Network Joins Each Other and Joins Installation to Use Dwelling(2007)
• USING SEMI-JOINS TO REALIZE JOINS AND MIXED-SEMI(?)JOINS(1987)