A Set-Theoretic Approach to Detecting Logic Bugs in DBMS Inner Join Optimizations

• URL: http://arxiv.org/abs/2606.23294v2
• Date: Thu, 25 Jun 2026 05:44:57 GMT
• Title: A Set-Theoretic Approach to Detecting Logic Bugs in DBMS Inner Join Optimizations
• Abstract summary: We propose a testing approach to detect bugs related to INNER JOIN optimization through the lens of set theory.<n>We implement this design in JoinEquiv, which serves as an oracle testing executor.
• Score: 15.757749995343715
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The query optimizer is a fundamental component of database management systems that determines the most efficient execution strategy for a given query by evaluating alternative query plans. Among its tasks, join optimization plays a central role, as the order of joins in multi-table queries can significantly affect execution performance. However, due to the inherent complexity of join optimization, logical bugs are inevitable and often difficult to detect. While existing fuzzing tools have shown notable success in uncovering crash- and performance-related errors, effectively identifying logical bugs -- cases in which the system produces incorrect query results -- remains largely unresolved. In this paper, we propose a metamorphic testing approach to detect DBMS bugs related to INNER JOIN optimization through the lens of set theory. For each testing case, equivalent queries are generated based on a basic set operation -- intersection -- and three semantics-preserving transformation rules, i.e., symmetric join transformation, asymmetric difference transformation, and symmetric difference transformation, are introduced. These rules rewrite a simple NATURAL/INNER JOIN query into a more complex, yet semantically equivalent, form. We implement this design in JoinEquiv, which serves as a testing oracle to systematically uncover logical inconsistencies in DBMS query processing by comparing the results of original and transformed queries. Using JoinEquiv, we uncovered 29 previously unknown issues in mainstream DBMSs (MySQL, TiDB, DuckDB, and Percona), and 27 of them were officially confirmed. JoinEquiv reveals deep logical flaws in DBMS optimizers and executors, underscoring its value in enhancing DBMS robustness.

Related papers

• Detecting DBMS Bugs by Constructing Equivalent Representations of Intermediate Query Results [4.984008334354563]
  We propose ERIQ, a novel testing approach for detecting logic bugs.<n>In total, ERIQ detected 64 bugs, 63 of which were confirmed by developers, and two have been fixed.
  arXiv  Detail & Related papers  (2026-08-31T07:41:09Z)
• When RAG Meets Query Planning: Logical Query Trees for Resolving Exploratory Reasoning Problems [56.24850338895714]
  RAG struggles with textbfexploratory reasoning problems (ERPs) that are the complex queries involving high uncertainty and ambiguity.<n>We introduce emphPlanRAG, an RAG framework that modelsERPs of natural language as textbflogical query trees (LQTs).<n>PlanRAG outperforms state-of-the-art iteration-based and graph-based RAG systems on our newly constructed dataset, textbfWikiWeb-ERP.
  arXiv  Detail & Related papers  (2026-07-01T06:43:55Z)
• ASTRA: Adaptive Semantic Tree Reasoning Architecture for Complex Table Question Answering [55.55968342644846]
  Table serialization remains a critical bottleneck for Large Language Models (LLMs) in complex table question answering.<n>Existing serialization methods fail to capture explicit hierarchies and lack schema flexibility.<n>We propose ASTRA (Adaptive Semantic Tree Reasoning Architecture) including two main modules, AdaSTR and DuTR.<n> Experiments on complex table benchmarks demonstrate that our method achieves state-of-the-art (SOTA) performance.
  arXiv  Detail & Related papers  (2026-04-10T06:09:41Z)
• NGDB-Zoo: Towards Efficient and Scalable Neural Graph Databases Training [55.35217340229661]
  We present NGDB-Zoo, a unified framework that resolves bottlenecks by synergizing operator-level training with semantic augmentation.<n>We demonstrate that NGDB-Zoo maintains high GPU utilization across diverse logical patterns and significantly mitigates friction in hybrid neuro-symbolic reasoning.
  arXiv  Detail & Related papers  (2026-02-25T05:46:42Z)
• Fine-tuned LLM-based Code Migration Framework [0.0]
  The study presents the outcomes of research and experimental validation in the domain of automated sampling migration.<n>The proposed method for migration essentially appears as a framework that leverages the best aspects of traditional software engineering techniques.
  arXiv  Detail & Related papers  (2025-12-15T16:42:51Z)
• Effective Instruction Parsing Plugin for Complex Logical Query Answering on Knowledge Graphs [51.33342412699939]
  Knowledge Graph Query Embedding (KGQE) aims to embed First-Order Logic (FOL) queries in a low-dimensional KG space for complex reasoning over incomplete KGs. Recent studies integrate various external information (such as entity types and relation context) to better capture the logical semantics of FOL queries. We propose an effective Query Instruction Parsing (QIPP) that captures latent query patterns from code-like query instructions.
  arXiv  Detail & Related papers  (2024-10-27T03:18:52Z)
• DAC: Decomposed Automation Correction for Text-to-SQL [51.48239006107272]
  We introduce De Automation Correction (DAC), which corrects text-to-composed by decomposing entity linking and skeleton parsing. We show that our method improves performance by $3.7%$ on average of Spider, Bird, and KaggleDBQA compared with the baseline method.
  arXiv  Detail & Related papers  (2024-08-16T14:43:15Z)
• Hydro: Adaptive Query Processing of ML Queries [7.317548344184541]
  We present Hydro, an adaptive query processing (AQP) for efficiently processing machine learning (ML) queries. We demonstrate Hydro's efficacy through four illustrative use cases, delivering up to 11.52x speedup over a baseline system.
  arXiv  Detail & Related papers  (2024-03-22T01:17:07Z)
• JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning [58.71541261221863]
  Join order selection (JOS) is the problem of ordering join operations to minimize total query execution cost. We present JoinGym, a query optimization environment for bushy reinforcement learning (RL) Under the hood, JoinGym simulates a query plan's cost by looking up intermediate result cardinalities from a pre-computed dataset.
  arXiv  Detail & Related papers  (2023-07-21T17:00:06Z)
• CERT: Finding Performance Issues in Database Systems Through the Lens of Cardinality Estimation [6.789710498230718]
  We propose Cardinality Restriction Testing (CERT), a technique that finds performance issues through the lens of cardinality estimation. CERT tests cardinality estimation specifically, because they were shown to be the most important part for query optimization.
  arXiv  Detail & Related papers  (2023-06-01T05:21:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.