{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T11:34:51Z","timestamp":1791459291004,"version":"4.3.4"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>Query optimizers perform various optimizations, many of which have been proposed to optimize joins. It is pivotal that these optimizations are correct, meaning that they should be extensively tested. Besides manually written tests, automated testing approaches have gained broad adoption. Such approaches semi-randomly generate databases and queries. More importantly, they provide a so-called test oracle that can deduce whether the system's result is correct. Recently, researchers have proposed a novel testing approach called Transformed Query Synthesis (TQS) specifically designed to find logic bugs in join optimizations. TQS is a sophisticated approach that splits a given input table into several sub-tables and validates the results of the queries that join these sub-tables by retrieving the given table. We studied TQS's bug reports, and found that 14 of 15 unique bugs were reported by showing discrepancies in executing the same query with different query plans. Therefore, in this work, we propose a simple alternative approach to TQS. Our approach enforces different query plans for the same query and validates that the results are consistent. We refer to this approach as Differential Query Plan (DQP) testing. DQP can reproduce 14 of the 15 unique bugs found by TQS, and found 26 previously unknown and unique bugs. These results demonstrate that a simple approach with limited novelty can be as effective as a complex, conceptually appealing approach. Additionally, DQP is complementary to other testing approaches for finding logic bugs. 81% of the logic bugs found by DQP cannot be found by NoREC and TLP, whereas DQP overlooked 86% of the bugs found by NoREC and TLP. We hope that the practicality of our approach---we implemented in less than 100 lines of code per system---will lead to its wide adoption.<\/jats:p>","DOI":"10.1145\/3654991","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-26","source":"Crossref","is-referenced-by-count":30,"title":["Keep It Simple: Testing Databases via Differential Query Plans"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4008-9225","authenticated-orcid":false,"given":"Jinsheng","family":"Ba","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8303-2099","authenticated-orcid":false,"given":"Manuel","family":"Rigger","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1858996.1859063"},{"key":"e_1_2_2_2_1","volume-title":"In Popl","volume":"2","author":"Andoni Alexandr","year":"2003","unstructured":"Alexandr Andoni, Dumitru Daniliuc, Sarfraz Khurshid, and Darko Marinov. 2003. Evaluating the ?small scope hypothesis\". In In Popl, Vol. 2."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE48619.2023.00174"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597503.3639076"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325993"},{"key":"e_1_2_2_6_1","volume-title":"2007 IEEE 23rd International Conference on Data Engineering. IEEE, 506--515","author":"Binnig Carsten","year":"2006","unstructured":"Carsten Binnig, Donald Kossmann, and Eric Lo. 2006. Reverse query processing. In 2007 IEEE 23rd International Conference on Data Engineering. IEEE, 506--515."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247520"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.190"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.190"},{"key":"e_1_2_2_10_1","volume-title":"Metamorphic Testing: A New Approach for Generating Next Test Cases. CoRR","author":"Chen Tsong Yueh","year":"2020","unstructured":"Tsong Yueh Chen, S. C. Cheung, and Siu-Ming Yiu. 2020. Metamorphic Testing: A New Approach for Generating Next Test Cases. CoRR, Vol. abs\/2002.12543 (2020). showeprint[arXiv]2002.12543 https:\/\/arxiv.org\/abs\/2002.12543"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3143561","article-title":"Metamorphic testing: A review of challenges and opportunities","volume":"51","author":"Chen Tsong Yueh","year":"2018","unstructured":"Tsong Yueh Chen, Fei-Ching Kuo, Huai Liu, Pak-Lok Poon, Dave Towey, TH Tse, and Zhi Quan Zhou. 2018. Metamorphic testing: A review of challenges and opportunities. ACM Computing Surveys (CSUR), Vol. 51, 1 (2018), 1--27.","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462173"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247598"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556565"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.27"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3551349.3560431"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3106237.3106256"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191886"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2304510.2304525"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320211"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597503.3623307"},{"key":"e_1_2_2_22_1","volume-title":"DynSQL: Stateful Fuzzing for Database Management Systems with Complex and Valid SQL Query Generation. (Aug","author":"Jiang Zu-Ming","year":"2023","unstructured":"Zu-Ming Jiang, Jia-Ju Bai, and Zhendong Su. 2023. DynSQL: Stateful Fuzzing for Database Management Systems with Complex and Valid SQL Query Generation. (Aug. 2023)."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3357377.3357382"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243804"},{"key":"e_1_2_2_25_1","volume-title":"Detecting Logical Bugs of DBMS with Coverage-based Guidance. In 31st USENIX Security Symposium (USENIX Security 22)","author":"Liang Yu","year":"2022","unstructured":"Yu Liang, Song Liu, and Hong Hu. 2022. Detecting Logical Bugs of DBMS with Coverage-based Guidance. In 31st USENIX Security Symposium (USENIX Security 22). USENIX Association."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3510003.3510093"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360581"},{"key":"e_1_2_2_28_1","first-page":"100","article-title":"Differential testing for software","volume":"10","author":"McKeeman William M","year":"1998","unstructured":"William M McKeeman. 1998. Differential testing for software. Digital Technical Journal, Vol. 10, 1 (1998), 100--107.","journal-title":"Digital Technical Journal"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376668"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376668"},{"key":"e_1_2_2_31_1","volume-title":"Finding Crash-Consistency Bugs with Bounded Black-Box Crash Testing. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)","author":"Mohan Jayashree","year":"2018","unstructured":"Jayashree Mohan, Ashlie Martinez, Soujanya Ponnapalli, Pandian Raju, and Vijay Chidambaram. 2018. Finding Crash-Consistency Bugs with Bounded Black-Box Crash Testing. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18). 33--50."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--36727--4_1"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559889"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3031843.3031849"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611540.3611568"},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of the Thirtieth International Conference on Very Large Data Bases -","volume":"30","author":"Poess Meikel","unstructured":"Meikel Poess and John M. Stephens, Jr. 2004. Generating Thousand Benchmark Queries in Seconds. In Proceedings of the Thirtieth International Conference on Very Large Data Bases - Volume 30 (Toronto, Canada) (VLDB '04). VLDB Endowment, 1045--1053."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2771783.2771791"},{"key":"e_1_2_2_38_1","first-page":"46","article-title":"Pattern matching: The gestalt approach","volume":"13","author":"Ratcliff John W","year":"1988","unstructured":"John W Ratcliff, David Metzener, et al. 1988. Pattern matching: The gestalt approach. Dr. Dobb's Journal, Vol. 13, 7 (1988), 46.","journal-title":"Dr. Dobb's Journal"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254104"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368089.3409710"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428279"},{"key":"e_1_2_2_42_1","volume-title":"14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)","author":"Rigger Manuel","year":"2020","unstructured":"Manuel Rigger and Zhendong Su. 2020c. Testing Database Engines via Pivoted Query Synthesis. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). USENIX Association, Banff, Alberta."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386134"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588909"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611540.3611584"},{"key":"e_1_2_2_47_1","unstructured":"Website. 1988. TPC-DS Benchmark. https:\/\/www.tpc.org\/tpcds\/. Accessed: 2022--11--15."},{"key":"e_1_2_2_48_1","volume-title":"American Fuzzy Lop (AFL) Fuzzer","unstructured":"Website. 2013. American Fuzzy Lop (AFL) Fuzzer. http:\/\/lcamtuf.coredump.cx\/afl\/technical_details.txt. Accessed: 2022-06-08."},{"key":"e_1_2_2_49_1","unstructured":"Website. 2015. SQLsmith. https:\/\/github.com\/anse1\/sqlsmith. Accessed: 2022-06-08."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209950.3209958"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417260"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654991","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654991","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:41:05Z","timestamp":1755787265000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654991"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654991"],"URL":"https:\/\/doi.org\/10.1145\/3654991","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}