論文の概要: A Set-Theoretic Approach to Detecting Logic Bugs in DBMS Inner Join Optimizations

• arxiv url: http://arxiv.org/abs/2606.23294v1
• Date: Mon, 22 Jun 2026 13:09:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-24 22:45:41.777699
• Title: A Set-Theoretic Approach to Detecting Logic Bugs in DBMS Inner Join Optimizations
• Title（参考訳）: DBMS内結合最適化における論理バグ検出のための集合論的アプローチ
• Authors: Ce Lyu, Changzheng Wei, Yanhao Wang, Jie Liang, Li Lin, Hanghang Wu, Minghao Zhao, Ying Yan, Aoying Zho,
• Abstract要約: 我々は,INNER JOIN最適化に関連するバグを,セット理論のレンズを用いて検出するテスト手法を提案する。 私たちはこの設計を、オラクルテストエグゼキュータとして機能するJoinEquivで実装しています。
• 参考スコア（独自算出の注目度）: 11.483939409020637
• 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.
• Abstract（参考訳）: クエリオプティマイザは、データベース管理システムの基本コンポーネントであり、代替クエリ計画を評価することで、与えられたクエリに対して最も効率的な実行戦略を決定する。 マルチテーブルクエリにおけるジョインの順序が実行パフォーマンスに大きく影響する可能性があるため、そのタスクの中でジョイン最適化が中心的な役割を果たす。 しかし、結合最適化の本質的な複雑さのため、論理的なバグは避けられず、しばしば検出するのが困難である。 既存のファジィツールは、クラッシュやパフォーマンス関連のエラーの発見に顕著な成功を示しているが、論理的なバグを効果的に識別する — システムが不正なクエリ結果を生成する場合 — は、ほとんど未解決のままである。 本稿では,INNER JOIN最適化に関連するDBMSバグを,セット理論のレンズを通して検出するメタモルフィックテスト手法を提案する。 各テストケースに対して、基本集合演算(交叉)に基づいて等価なクエリを生成し、対称結合変換、非対称差分変換、対称差分変換という3つのセマンティクス保存変換規則を導入する。 これらのルールは単純なNATURAL/INNER JOINクエリを、より複雑だが意味論的に等価な形式に書き換える。 我々はこの設計をJoinEquivで実装し、DBMSクエリ処理における論理的不整合を、元のクエリと変換されたクエリの結果を比較して体系的に発見する、テストのオラクルとして機能する。 JoinEquivを使って、メインストリームDBMS(MySQL、TiDB、DuckDB、Percona)で29の既知の問題を発見し、そのうち27が正式に確認されました。 JoinEquivはDBMSオプティマイザとエグゼキュータの深い論理的欠陥を明らかにし、DBMSの堅牢性向上の価値を強調している。

関連論文リスト

• ASTRA: Adaptive Semantic Tree Reasoning Architecture for Complex Table Question Answering [55.55968342644846]
  テーブルのシリアライゼーションは、複雑なテーブル質問応答において、LLM(Large Language Models)にとって重要なボトルネックであり続けている。 既存のシリアライゼーションメソッドは明示的な階層をキャプチャできず、スキーマの柔軟性が欠如している。 本稿では,AdaSTRとDuTRの2つの主要モジュールを含むASTRA(Adaptive Semantic Tree Reasoning Architecture)を提案する。 複雑なテーブルベンチマーク実験により,本手法がSOTA(State-of-the-art)性能を実現することを示す。
  論文  参考訳（メタデータ） (2026-04-10T06:09:41Z)
• Effective Instruction Parsing Plugin for Complex Logical Query Answering on Knowledge Graphs [51.33342412699939]
  知識グラフクエリ埋め込み(KGQE)は、不完全なKGに対する複雑な推論のために、低次元KG空間に一階論理(FOL)クエリを埋め込むことを目的としている。 近年の研究では、FOLクエリの論理的セマンティクスをよりよく捉えるために、さまざまな外部情報(エンティティタイプや関係コンテキストなど)を統合している。 コードのようなクエリ命令から遅延クエリパターンをキャプチャする効果的なクエリ命令解析(QIPP)を提案する。
  論文  参考訳（メタデータ） (2024-10-27T03:18:52Z)
• DAC: Decomposed Automation Correction for Text-to-SQL [51.48239006107272]
  De Automation Correction (DAC)を導入し、エンティティリンクとスケルトン解析を分解することでテキストから合成を補正する。 また,本手法では,ベースライン法と比較して,スパイダー,バード,カグルDBQAの平均値が平均3.7%向上することを示した。
  論文  参考訳（メタデータ） (2024-08-16T14:43:15Z)
• JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning [58.71541261221863]
  結合順序選択(JOS)は、クエリの実行コストを最小化するために結合操作を順序付けする問題である。 木質強化学習(RL)のためのクエリ最適化環境JoinGymを提案する。 JoinGymは内部で、事前計算されたデータセットから中間結果の濃度を調べることで、クエリプランのコストをシミュレートする。
  論文  参考訳（メタデータ） (2023-07-21T17:00:06Z)
• CERT: Finding Performance Issues in Database Systems Through the Lens of Cardinality Estimation [6.789710498230718]
  本稿では,CERT(Cardinality Restriction Testing)を提案する。 CERTテストでは、クエリ最適化の最も重要な部分であることが示されている。
  論文  参考訳（メタデータ） (2023-06-01T05:21:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。