Testing Database Engines via Query Plan Guidance

• URL: http://arxiv.org/abs/2312.17510v1
• Date: Fri, 29 Dec 2023 08:09:47 GMT
• Title: Testing Database Engines via Query Plan Guidance
• Authors: Jinsheng Ba, Manuel Rigger
• Abstract summary: We propose the concept of Query Plan Guidance (QPG) for guiding automated testing towards "interesting" test cases. We apply our method to three mature, widely-used, and diverse database systems-DBite, TiDB, and Cockroach-and found 53 unique, previously unknown bugs.
• Score: 6.789710498230718
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Database systems are widely used to store and query data. Test oracles have been proposed to find logic bugs in such systems, that is, bugs that cause the database system to compute an incorrect result. To realize a fully automated testing approach, such test oracles are paired with a test case generation technique; a test case refers to a database state and a query on which the test oracle can be applied. In this work, we propose the concept of Query Plan Guidance (QPG) for guiding automated testing towards "interesting" test cases. SQL and other query languages are declarative. Thus, to execute a query, the database system translates every operator in the source language to one of potentially many so-called physical operators that can be executed; the tree of physical operators is referred to as the query plan. Our intuition is that by steering testing towards exploring diverse query plans, we also explore more interesting behaviors-some of which are potentially incorrect. To this end, we propose a mutation technique that gradually applies promising mutations to the database state, causing the DBMS to create diverse query plans for subsequent queries. We applied our method to three mature, widely-used, and extensively-tested database systems-SQLite, TiDB, and CockroachDB-and found 53 unique, previously unknown bugs. Our method exercises 4.85-408.48X more unique query plans than a naive random generation method and 7.46X more than a code coverage guidance method. Since most database systems-including commercial ones-expose query plans to the user, we consider QPG a generally applicable, black-box approach and believe that the core idea could also be applied in other contexts (e.g., to measure the quality of a test suite).

Related papers

• Text2SQL is Not Enough: Unifying AI and Databases with TAG [47.45480855418987]
  Table-Augmented Generation (TAG) is a paradigm for answering natural language questions over databases. We develop benchmarks to study the TAG problem and find that standard methods answer no more than 20% of queries correctly.
  arXiv  Detail & Related papers  (2024-08-27T00:50:14Z)
• An Exploratory Case Study of Query Plan Representations [5.747331236875253]
  In database systems, a query plan is a series of concrete internal steps to execute a query. Multiple testing approaches utilize query plans for finding bugs. We envision that a unified query plan representation can facilitate the implementation of these approaches.
  arXiv  Detail & Related papers  (2024-08-14T23:56:37Z)
• UQE: A Query Engine for Unstructured Databases [71.49289088592842]
  We investigate the potential of Large Language Models to enable unstructured data analytics. We propose a new Universal Query Engine (UQE) that directly interrogates and draws insights from unstructured data collections.
  arXiv  Detail & Related papers  (2024-06-23T06:58:55Z)
• Detecting DBMS Bugs with Context-Sensitive Instantiation and Multi-Plan Execution [11.18715154222032]
  This paper aims to solve the two challenges, including how to generate semantically correctsql queries in a test case, and how to propose effective oracles to capture logic bugs. We have implemented a prototype system called Kangaroo and applied three widely used and well-tested semantic codes. The comparison between our system with the state-of-the-art systems shows that our system outperforms them in terms of the number of generated semantically valid queries, the explored code paths during testing, and the detected bugs.
  arXiv  Detail & Related papers  (2023-12-08T10:15:56Z)
• 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)
• UNITE: A Unified Benchmark for Text-to-SQL Evaluation [72.72040379293718]
  We introduce a UNIfied benchmark for Text-to-domain systems. It is composed of publicly available text-to-domain datasets and 29K databases. Compared to the widely used Spider benchmark, we introduce a threefold increase in SQL patterns.
  arXiv  Detail & Related papers  (2023-05-25T17:19:52Z)
• QUADRo: Dataset and Models for QUestion-Answer Database Retrieval [97.84448420852854]
  Given a database (DB) of question/answer (q/a) pairs, it is possible to answer a target question by scanning the DB for similar questions. We build a large scale DB of 6.3M q/a pairs, using public questions, and design a new system based on neural IR and a q/a pair reranker. We show that our DB-based approach is competitive with Web-based methods, i.e., a QA system built on top the BING search engine.
  arXiv  Detail & Related papers  (2023-03-30T00:42:07Z)
• Searching for Better Database Queries in the Outputs of Semantic Parsers [16.221439565760058]
  In this paper, we consider the case when, at the test time, the system has access to an external criterion that evaluates the generated queries. The criterion can vary from checking that a query executes without errors to verifying the query on a set of tests. We apply our approach to the state-of-the-art semantics and report that it allows us to find many queries passing all the tests on different datasets.
  arXiv  Detail & Related papers  (2022-10-13T17:20:45Z)
• "What makes my queries slow?": Subgroup Discovery for SQL Workload Analysis [1.3124513975412255]
  We introduce an original approach rooted on Subgroup Discovery. We show how to instantiate and develop this generic data-mining framework. We also provide a visualization tool for interactive knowledge discovery.
  arXiv  Detail & Related papers  (2021-08-09T09:44:13Z)
• Dual Reader-Parser on Hybrid Textual and Tabular Evidence for Open Domain Question Answering [78.9863753810787]
  A large amount of world's knowledge is stored in structured databases. query languages can answer questions that require complex reasoning, as well as offering full explainability.
  arXiv  Detail & Related papers  (2021-08-05T22:04:13Z)
• Photon: A Robust Cross-Domain Text-to-SQL System [189.1405317853752]
  We present Photon, a robust, modular, cross-domain NLIDB that can flag natural language input to which a mapping cannot be immediately determined. The proposed method effectively improves the robustness of text-to-native system against untranslatable user input.
  arXiv  Detail & Related papers  (2020-07-30T07:44:48Z)

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.