Can the Rookies Cut the Tough Cookie? Exploring the Use of LLMs for SQL Equivalence Checking

Rajat Singh, Srikanta Bedathur · 2024

Read Can the Rookies Cut the Tough Cookie? Exploring the Use of LLMs for SQL Equivalence Checking by Rajat Singh, Srikanta Bedathur (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-05561.txt.

Introduction

Rajat Singh and Srikanta Bedathur ask whether language models can judge if two database queries mean the same thing, in a 2024 paper. Checking SQL equivalence is a hard problem that shows up in grading and in debugging query optimizers. Formal tools handle only simple queries in a small corner of the language.

The pair built a new benchmark, SQLEquiQuest, with realistic and complex query pairs. They then tested several top language models with varied prompting styles, including hints from logical query plans. Models covered all pairs, where formal tools managed only about thirty percent, and reached up to eighty-two percent accuracy on one set. A flaw stood out: models over-predict equivalence and stumble on pairs that truly differ. That bias marks a clear target for future work.

Catalog record

CREATORRajat Singh, Srikanta Bedathur
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-05561

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Can the Rookies Cut the Tough Cookie? Exploring the Use of LLMs for SQL Equivalence Checking Rajat Singh, Srikanta Bedathur Abstract Equivalence checking of SQL queries is an intractable problem often encountered in settings ranging from grading SQL submissions to debugging query optimizers. Despite recent work toward developing practical solutions, only simple queries written using a small subset of SQL are supported, leaving the equivalence checking of sophisticated SQL queries at the mercy of intensive, potentially error-prone, manual analysis. In this paper, we explore how LLMs can be used to reason with SQL queries to address this challenging problem. Towards this, we introduce a novel, realistic, and sufficiently complex benchmark called SQLEquiQuest for SQL query equivalence checking that reflects real-world settings. We establish strong baselines for SQL equivalence checking by leveraging the ability of LLMs to reason with SQL queries. We conduct a detailed evaluation of several state-of-the-art LLMs using various prompting strategies and carefully constructed in-context learning examples, including logical plans generated by SQL query processors. Our empirical evaluation shows that LLMs go well beyond the current capabilities of formal models for SQL equivalence, going from a mere 30% supported query pairs to full coverage, achieving up to 82% accuracy on Spider+DIN . However, a critical limitation of LLMs revealed by our analysis is that they exhibit a strong bias for equivalence predictions, with consistently poor performance over non-equivalent pairs, opening a new direction for potential future research. 1 Introduction Determining if two arbitrary SQL queries are equivalent – i.e., they generate the same output when executed on any database instance of the given schema – is a classical “tough cookie” to cut with well-established undecidability results ( Chandra & Merlin, 1977 ; Abiteboul et al., 1995 ; Ioannidis & Ramakrishnan, 1995 ) . However, the need to check equivalence appears in many practical scenarios, such as evaluating SQL assignment submissions in a university classroom setting ( Chandra et al., 2014 ) , verifying text-to-SQL results, and ensuring correct query rewriting rules in a query optimizer ( Jarke & Koch, 1984 ) . Current ad hoc approaches, such as executing queries on an (often small) database instance and comparing the results ( He et al., 2024 ; Yin et al., 2020 ) , or measuring the similarity between two SQL statements using an edit-distance-based method ( Yin et al., 2020 ) , tend to be highly error-prone. Consequently, significant effort has been devoted to exploring computable query equivalence for specific sub-classes of relational queries and under certain assumptions ( Chandra & Merlin, 1977 ; Zhou et al., 2022 ; Ding et al., 2023 ; Chaudhuri & Vardi, 1993 ; Wang, 2023 ; Zhou et al., 2019 ; Haynes et al., 2023 ; Wang et al., 2022 ; Chu et al., 2017 ; He et al., 2024 ; Chu et al., 2016 ; Cohen, 2006 ) . Despite the long list of technically sophisticated results & well-crafted tools, we are still far from building a model that can be reliably used in production to verify the equivalence of SQL queries of arbitrary complexity. For example, consider the two SQL queries in Figure 1 . These queries are part of an assignment in a university graduate-level course, where Query_1 and Query_2 are non-equivalent. Their non-equivalence is not immediately obvious, even to those familiar with SQL. Moreover, SQL equivalence-checking tools such as VeriEQL ( He et al., 2024 ) , SQLSolver ( Ding et al., 2023 ) , and Cosette ( Chu et al., 2017 ) either do not support this pair of queries or fail to provide an explanation for why the queries are equivalent or non-equivalent. In fact, in the novel SQLEquiQuest benchmark we present in this paper (cf. Section 3.1 ), only about 30\% pairs are supported by SQLSolver ( Zhao et al., 2023 ) and mere 2.8\% by VeriEQL ( He et al., 2024 ) – two recent SQL equivalence checkers (for details, see Section 5 ). ⬇ WITH result AS ( SELECT playerid , SUM ( COALESCE ( cs ,0)) AS total_caught_stealing FROM batting GROUP BY batting . playerid ORDER BY total_caught_stealing DESC ) SELECT result . playerid , COALESCE ( people . namefirst , ’’ ) AS firstname , COALESCE ( people . namelast , ’’ ) AS lastname , result . total_caught_stealing FROM result JOIN people ON result . playerid = people . playerid ORDER BY total_caught_stealing DESC , namefirst ASC , namelast ASC , playerid ASC LIMIT 10; I Query_1 ⬇ SELECT people . playerid , namefirst AS firstname , namelast AS lastname , cs AS total_caught_stealing FROM people JOIN batting ON people . playerid = batting . playerid ORDER BY COALESCE ( cs , 0) DESC , COALESCE ( namefirst , ’’ ) ASC , COALESCE ( namelast , ’’ ) ASC , people . playerid ASC LIMIT 10; II Query_2 Figure 1 : Example of a non-equivalent pair of SQL queries from a database assignment question ( SQLEquiQuest dataset). Large Language Models for SQL: Large language models (LLMs), among other capabilities, have demonstrated exceptional performance in tasks such as text-to-SQL ( Liu et al., 2023a ; Pourreza & Rafiei, 2023 ; Gao et al., 2023a ; Xie et al., 2022 ) , and also in generating natural language explanations of code segments – including SQL – with remarkable accuracy ( Sun et al., 2023 ; Bhattacharya et al., 2023 ; Geng et al., 2023 ; Gao et al., 2023b ) . By leveraging these capabilities of LLMs, we aim to develop a robust solution for determining the equivalence of SQL queries, potentially overcoming the limitations of existing formal methods and tools. In this work, we will treat LLMs as black-box experts – advanced artificial intelligence (AI) models – capable of understanding and generating human-like text. Given the extensive corpus used during their training, it is highly likely that these LLMs have been exposed to datasets used in existing work. Furthermore, prevailing benchmarks, such as SPIDER+DIN, primarily consist of relatively simple SQL queries that do not accurately represent the complexity and diversity of real-world SQL queries encountered in practical applications. This underscores the need for novel, diverse, and complex datasets to effectively evaluate LLMs on the task of equivalence of SQL queries. 1.1 Contributions In summary, this paper makes the following key contributions: • Presents a practical and challenging SQL equivalence benchmark called SQLEquiQuest , derived from advanced SQL assignments at a graduate-level DBMS course. We believe this novel benchmark will further spur research activity in this task. • Introduces the task of SQL query equivalence to evaluate the SQL reasoning abilities of LLMs, and establishes a strong baseline performance across a number of LLMs, using SQL logical plans in context. The experimental results achieved up to 70% coverage gains over traditional SQL equivalence checkers, with nearly 82% accuracy on Spider+DIN dataset and 61% accuracy on SQLEquiQuest dataset. Organization : The structure of this paper is as follows: Section 2 reviews related work, focusing on traditional approaches to SQL equivalence checking and recent advancements leveraging LLMs. Section 3 discusses the lack of benchmarks for SQL equivalence checking, and presents our SQLEquiQuest benchmark in addition to a recently proposed approach for synthetically generated Spider+DIN

Read the complete text