{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,17]],"date-time":"2026-10-17T16:18:14Z","timestamp":1792253894383,"version":"4.4.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2020,11,13]]},"abstract":"<jats:p>Logic bugs in Database Management Systems (DBMSs) are bugs that cause an incorrect result for a given query, for example, by omitting a row that should be fetched. These bugs are critical, since they are likely to go unnoticed by users. We propose Query Partitioning, a general and effective approach for finding logic bugs in DBMSs. The core idea of Query Partitioning is to, starting from a given original query, derive multiple, more complex queries (called partitioning queries), each of which computes a partition of the result. The individual partitions are then composed to compute a result set that must be equivalent to the original query's result set. A bug in the DBMS is detected when these result sets differ. Our intuition is that due to the increased complexity, the partitioning queries are more likely to stress the DBMS and trigger a logic bug than the original query. As a concrete instance of a partitioning strategy, we propose Ternary Logic Partitioning (TLP), which is based on the observation that a boolean predicate p can either evaluate to TRUE, FALSE, or NULL. Accordingly, a query can be decomposed into three partitioning queries, each of which computes its result on rows or intermediate results for which p, NOT p, and p IS NULL hold. This technique is versatile, and can be used to test WHERE, GROUP BY, as well as HAVING clauses, aggregate functions, and DISTINCT queries. As part of an extensive testing campaign, we found 175 bugs in widely-used DBMSs such as MySQL, TiDB, SQLite, and CockroachDB, 125 of which have been fixed. Notably, 77 of these were logic bugs, while the remaining were error and crash bugs. We expect that the effectiveness and wide applicability of Query Partitioning will lead to its broad adoption in practice, and the formulation of additional partitioning strategies.<\/jats:p>","DOI":"10.1145\/3428279","type":"journal-article","created":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T18:36:06Z","timestamp":1606242966000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":125,"title":["Finding bugs in database systems via query partitioning"],"prefix":"10.1145","volume":"4","author":[{"given":"Manuel","family":"Rigger","sequence":"first","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhendong","family":"Su","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1858996.1859063"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/320455.320457"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases (Vienna, Austria) ( VLDB '07). VLDB Endowment, 1243-1251","author":"Bati Hardik","year":"2007","unstructured":"Hardik Bati , Leo Giakoumakis , Steve Herbert , and Aleksandras Surna . 2007 . A Genetic Approach for Random Testing of Database Systems . In Proceedings of the 33rd International Conference on Very Large Data Bases (Vienna, Austria) ( VLDB '07). VLDB Endowment, 1243-1251 . Hardik Bati, Leo Giakoumakis, Steve Herbert, and Aleksandras Surna. 2007. A Genetic Approach for Random Testing of Database Systems. In Proceedings of the 33rd International Conference on Very Large Data Bases (Vienna, Austria) ( VLDB '07). VLDB Endowment, 1243-1251."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367896"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247520"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1670412.1670413"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083719"},{"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.1145\/275487.275492"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3143561"},{"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\/362384.362685"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142480"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2337223.2337313"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133917"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000028"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/191843.191886"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2304510.2304525"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151113.3151116"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66962"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3377811.3380339"},{"key":"e_1_2_2_24_1","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases (Seoul, Korea) ( VLDB '06). VLDB Endowment, 1243-1246","author":"Houkjaer Kenneth","year":"2006","unstructured":"Kenneth Houkjaer , Kristian Torp , and Rico Wind . 2006 . Simple and Realistic Data Generation . In Proceedings of the 32nd International Conference on Very Large Data Bases (Seoul, Korea) ( VLDB '06). VLDB Endowment, 1243-1246 . Kenneth Houkjaer, Kristian Torp, and Rico Wind. 2006. Simple and Realistic Data Generation. In Proceedings of the 32nd International Conference on Very Large Data Bases (Seoul, Korea) ( VLDB '06). VLDB Endowment, 1243-1246."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415535"},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","unstructured":"P. Jesus C. Baquero and P. S. Almeida. 2015. A Survey of Distributed Data Aggregation Algorithms. IEEE Communications Surveys Tutorials 17 1 ( 2015 ) 381-404. P. Jesus C. Baquero and P. S. Almeida. 2015. A Survey of Distributed Data Aggregation Algorithms. IEEE Communications Surveys Tutorials 17 1 ( 2015 ) 381-404.","DOI":"10.1109\/COMST.2014.2354398"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3357377.3357382"},{"key":"e_1_2_2_28_1","first-page":"590","volume-title":"Proceedings of the 32Nd IEEE\/ACM International Conference on Automated Software Engineering (Urbana-Champaign, IL, USA) ( ASE 2017). IEEE Press","author":"Kapus Timotej","year":"2017","unstructured":"Timotej Kapus and Cristian Cadar . 2017 . Automatic Testing of Symbolic Execution Engines via Program Generation and Diferential Testing . In Proceedings of the 32Nd IEEE\/ACM International Conference on Automated Software Engineering (Urbana-Champaign, IL, USA) ( ASE 2017). IEEE Press , Piscataway, NJ, USA , 590 - 600 . Timotej Kapus and Cristian Cadar. 2017. Automatic Testing of Symbolic Execution Engines via Program Generation and Diferential Testing. In Proceedings of the 32Nd IEEE\/ACM International Conference on Automated Software Engineering (Urbana-Champaign, IL, USA) ( ASE 2017). IEEE Press, Piscataway, NJ, USA, 590-600."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2008.34"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594334"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0157-y"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360581"},{"key":"e_1_2_2_33_1","article-title":"Diferential testing for software","volume":"10","author":"McKeeman William M","year":"1998","unstructured":"William M McKeeman . 1998 . Diferential testing for software . Digital Technical Journal 10 , 1 ( 1998 ), 100-107. William M McKeeman. 1998. Diferential testing for software. Digital Technical Journal 10, 1 ( 1998 ), 100-107.","journal-title":"Digital Technical Journal"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376668"},{"key":"e_1_2_2_35_1","unstructured":"MySQL. 2020. MySQL Homepage. https:\/\/www.mysql.com\/ MySQL. 2020. MySQL Homepage. https:\/\/www.mysql.com\/"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01232186"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003674"},{"key":"e_1_2_2_38_1","volume-title":"Proceedings of the hTirtieth International Conference on Very Large Data Bases-Volume 30 (Toronto, Canada) ( VLDB '04). VLDB Endowment, 1045-1053","author":"Poess Meikel","unstructured":"Meikel Poess and John M. Stephens . 2004. Generating Thousand Benchmark Queries in Seconds . In Proceedings of the hTirtieth International Conference on Very Large Data Bases-Volume 30 (Toronto, Canada) ( VLDB '04). VLDB Endowment, 1045-1053 . Meikel Poess and John M. Stephens. 2004. Generating Thousand Benchmark Queries in Seconds. In Proceedings of the hTirtieth International Conference on Very Large Data Bases-Volume 30 (Toronto, Canada) ( VLDB '04). VLDB Endowment, 1045-1053."},{"key":"e_1_2_2_39_1","unstructured":"PostgreSQL. 2020. PostgreSQL Homepage. https:\/\/www.postgresql.org\/ PostgreSQL. 2020. PostgreSQL Homepage. https:\/\/www.postgresql.org\/"},{"key":"e_1_2_2_40_1","unstructured":"Mark Raasveldt and Hannes M\u00fchleisen. 2020. Data Management for Data Science-Towards Embedded Analytics. In CIDR. Mark Raasveldt and Hannes M\u00fchleisen. 2020. Data Management for Data Science-Towards Embedded Analytics. In CIDR."},{"key":"e_1_2_2_41_1","unstructured":"John Regehr. 2010. A Guide to Undefined Behavior in C and C++. https:\/\/blog.regehr.org\/archives\/213 John Regehr. 2010. A Guide to Undefined Behavior in C and C++. https:\/\/blog.regehr.org\/archives\/213"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254104"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368089.3409710"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.4032401"},{"key":"e_1_2_2_45_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 . 2020 c. Testing Database Engines via Pivoted Query Synthesis . In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20) . USENIX Association, Banf, Alberta. https:\/\/www.usenix. org\/conference\/osdi20\/presentation\/rigger 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, Banf, Alberta. https:\/\/www.usenix. org\/conference\/osdi20\/presentation\/rigger"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183440.3183468"},{"key":"e_1_2_2_47_1","doi-asserted-by":"crossref","unstructured":"Andreas Seltenreich. 2019. SQLSmith. https:\/\/github.com\/anse1\/sqlsmith Andreas Seltenreich. 2019. SQLSmith. https:\/\/github.com\/anse1\/sqlsmith","DOI":"10.14712\/2464689X.2019.15"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29860-8_9"},{"key":"e_1_2_2_49_1","first-page":"618","article-title":"Massive stochastic testing of SQL","volume":"98","author":"Slutz Donald R","year":"1998","unstructured":"Donald R Slutz . 1998 . Massive stochastic testing of SQL . In VLDB , Vol. 98. 618 - 622 . Donald R Slutz. 1998. Massive stochastic testing of SQL. In VLDB, Vol. 98. 618-622.","journal-title":"VLDB"},{"key":"e_1_2_2_50_1","unstructured":"SQLite. 2020. SQLite Homepage. https:\/\/www.sqlite.org\/ SQLite. 2020. SQLite Homepage. https:\/\/www.sqlite.org\/"},{"key":"e_1_2_2_51_1","volume-title":"Proceedings of the 13th Annual IEEE\/ACM International Symposium on Code Generation and Optimization (San Francisco, California) ( CGO '15). IEEE Computer Society, USA, 46-55","author":"Stepanov Evgeniy","year":"2015","unstructured":"Evgeniy Stepanov and Konstantin Serebryany . 2015 . MemorySanitizer: Fast Detector of Uninitialized Memory Use in C++ . In Proceedings of the 13th Annual IEEE\/ACM International Symposium on Code Generation and Optimization (San Francisco, California) ( CGO '15). IEEE Computer Society, USA, 46-55 . Evgeniy Stepanov and Konstantin Serebryany. 2015. MemorySanitizer: Fast Detector of Uninitialized Memory Use in C++. In Proceedings of the 13th Annual IEEE\/ACM International Symposium on Code Generation and Optimization (San Francisco, California) ( CGO '15). IEEE Computer Society, USA, 46-55."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386134"},{"key":"e_1_2_2_53_1","volume-title":"QED: Out-of-the-Box Datasets for SPARQL Query Evaluation. In hTe Semantic Web, Pascal Hitzler, Miriam Fern\u00e1ndez, Krzysztof Janowicz, Amrapali Zaveri, Alasdair J","author":"Thost Veronika","year":"2019","unstructured":"Veronika Thost and Julian Dolby . 2019 . QED: Out-of-the-Box Datasets for SPARQL Query Evaluation. In hTe Semantic Web, Pascal Hitzler, Miriam Fern\u00e1ndez, Krzysztof Janowicz, Amrapali Zaveri, Alasdair J .G. Gray, Vanessa Lopez, Armin Haller, and Karl Hammar (Eds.). Springer International Publishing , Cham , 491-506. Veronika Thost and Julian Dolby. 2019. QED: Out-of-the-Box Datasets for SPARQL Query Evaluation. In hTe Semantic Web, Pascal Hitzler, Miriam Fern\u00e1ndez, Krzysztof Janowicz, Amrapali Zaveri, Alasdair J.G. Gray, Vanessa Lopez, Armin Haller, and Karl Hammar (Eds.). Springer International Publishing, Cham, 491-506."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807323"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385985"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993532"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629600"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417260"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428279","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428279","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:02:57Z","timestamp":1750183377000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428279"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":57,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2020,11,13]]}},"alternative-id":["10.1145\/3428279"],"URL":"https:\/\/doi.org\/10.1145\/3428279","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,13]]},"assertion":[{"value":"2020-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}