{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:29Z","timestamp":1750220669755,"version":"3.41.0"},"reference-count":41,"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>Optimizing the physical data storage and retrieval of data are two key database management problems. In this paper, we propose a language that can express both a relational query and the layout of its data. Our language can express a wide range of physical database layouts, going well beyond the row- and column-based methods that are widely used in database management systems. We use deductive program synthesis to turn a high-level relational representation of a database query into a highly optimized low-level implementation which operates on a specialized layout of the dataset. We build an optimizing compiler for this language and conduct experiments using a popular database benchmark, which shows that the performance of our specialized queries is better than a state-of-the-art in memory compiled database system while achieving an order-of-magnitude reduction in memory use.<\/jats:p>","DOI":"10.1145\/3428238","type":"journal-article","created":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T23:40:14Z","timestamp":1606261214000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Deductive optimization of relational data storage"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8577-1784","authenticated-orcid":false,"given":"John","family":"Feser","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sam","family":"Madden","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nan","family":"Tang","sequence":"additional","affiliation":[{"name":"QCRI HBKU, Qatar"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Armando","family":"Solar-Lezama","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"169","volume-title":"Weaving Relations for Cache Performance. In VLDB 2001, Proceedings of 27th International Conference on Very Large Data Bases","author":"Ailamaki Anastassia","year":"2001","unstructured":"Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , and Marios Skounakis . 2001 . Weaving Relations for Cache Performance. In VLDB 2001, Proceedings of 27th International Conference on Very Large Data Bases , September 11-14, 2001, Roma, Italy, Peter M. G. Apers, Paolo Atzeni, Stefano Ceri, Stefano Paraboschi, Kotagiri Ramamohanarao, and Richard T. Snodgrass (Eds.). Morgan Kaufmann , 169 - 180 . http:\/\/www.vldb.org\/conf\/2001\/P169.pdf Anastassia Ailamaki, David J. DeWitt, Mark D. Hill, and Marios Skounakis. 2001. Weaving Relations for Cache Performance. In VLDB 2001, Proceedings of 27th International Conference on Very Large Data Bases, September 11-14, 2001, Roma, Italy, Peter M. G. Apers, Paolo Atzeni, Stefano Ceri, Stefano Paraboschi, Kotagiri Ramamohanarao, and Richard T. Snodgrass (Eds.). Morgan Kaufmann, 169-180. http:\/\/www.vldb.org\/conf\/2001\/P169.pdf"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.1998.732672"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050076"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73951-7_13"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066184"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275492"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462180"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44957-4_66"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1734714.1734718"},{"key":"e_1_2_2_11_1","unstructured":"Transaction Processing Performance Council. 2008. TPC-H Benchmark Specification. 21 ( 2008 ) 592-603.  Transaction Processing Performance Council. 2008. TPC-H Benchmark Specification. 21 ( 2008 ) 592-603."},{"key":"e_1_2_2_12_1","volume-title":"Declarative Storage System. In CIDR","author":"Cudr\u00e9-Mauroux Philippe","year":"2009","unstructured":"Philippe Cudr\u00e9-Mauroux , Eugene Wu , and Samuel Madden . 2009. The Case for RodentStore: An Adaptive , Declarative Storage System. In CIDR 2009 , Fourth Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 4-7, 2009, Online Proceedings . www.cidrdb.org. http:\/\/www-db.cs.wisc.edu\/cidr\/cidr2009\/Paper_97.pdf Philippe Cudr\u00e9-Mauroux, Eugene Wu, and Samuel Madden. 2009. The Case for RodentStore: An Adaptive, Declarative Storage System. In CIDR 2009, Fourth Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 4-7, 2009, Online Proceedings. www.cidrdb.org. http:\/\/www-db.cs.wisc.edu\/cidr\/cidr2009\/Paper_97.pdf"},{"key":"e_1_2_2_13_1","volume-title":"Fabiano Cupertino Botelho, and Nivio Ziviani","author":"de Castro Reis Davi","year":"2011","unstructured":"Davi de Castro Reis , Djamel Belazzougui , Fabiano Cupertino Botelho, and Nivio Ziviani . 2011 . CMPH : C Minimal Perfect Hashing Library . http:\/\/cmph.sourceforge.net Davi de Castro Reis, Djamel Belazzougui, Fabiano Cupertino Botelho, and Nivio Ziviani. 2011. CMPH: C Minimal Perfect Hashing Library. http:\/\/cmph.sourceforge.net"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2677006"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90014-7"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.273032"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1997.581755"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2007.53"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100054"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17164-2_15"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993504"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/356924.356928"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732959"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180211"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908122"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_2_2_27_1","first-page":"383","volume-title":"Proceedings (LNI), Thomas Seidl, Norbert Ritter, Harald Sch\u00f6ning, Kai-Uwe Sattler, Theo H\u00e4rder, Stefen Friedrich, and Wolfram Wingerath (Eds.)","volume":"241","author":"Neumann Thomas","year":"2015","unstructured":"Thomas Neumann and Alfons Kemper . 2015 . Unnesting Arbitrary Queries. In Datenbanksysteme f\u00fcr Business, Technologie und Web (BTW), 16. Fachtagung des GI-Fachbereichs \"Datenbanken und Informationssysteme\" (DBIS), 4.-6.3.2015 in Hamburg , Germany. Proceedings (LNI), Thomas Seidl, Norbert Ritter, Harald Sch\u00f6ning, Kai-Uwe Sattler, Theo H\u00e4rder, Stefen Friedrich, and Wolfram Wingerath (Eds.) , Vol. P- 241 . GI, 383 - 402 . https:\/\/dl.gi. de\/20.500.12116\/2418 Thomas Neumann and Alfons Kemper. 2015. Unnesting Arbitrary Queries. In Datenbanksysteme f\u00fcr Business, Technologie und Web (BTW), 16. Fachtagung des GI-Fachbereichs \"Datenbanken und Informationssysteme\" (DBIS), 4.-6.3.2015 in Hamburg, Germany. Proceedings (LNI), Thomas Seidl, Norbert Ritter, Harald Sch\u00f6ning, Kai-Uwe Sattler, Theo H\u00e4rder, Stefen Friedrich, and Wolfram Wingerath (Eds.), Vol. P-241. GI, 383-402. https:\/\/dl.gi. de\/20.500.12116\/2418"},{"key":"e_1_2_2_28_1","first-page":"484","volume-title":"VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases","author":"Pottinger Rachel","year":"2000","unstructured":"Rachel Pottinger and Alon Y. Levy . 2000. A Scalable Algorithm for Answering Queries Using Views . In VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases , September 10-14, 2000 , Cairo, Egypt, Amr El Abbadi, Michael L. Brodie, Sharma Chakravarthy, Umeshwar Dayal, Nabil Kamel, Gunter Schlageter, and Kyu-Young Whang (Eds.). Morgan Kaufmann , 484 - 495 . http:\/\/www.vldb.org\/conf\/2000\/P484.pdf Rachel Pottinger and Alon Y. Levy. 2000. A Scalable Algorithm for Answering Queries Using Views. In VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10-14, 2000, Cairo, Egypt, Amr El Abbadi, Michael L. Brodie, Sharma Chakravarthy, Umeshwar Dayal, Nabil Kamel, Gunter Schlageter, and Kyu-Young Whang (Eds.). Morgan Kaufmann, 484-495. http:\/\/www.vldb.org\/conf\/2000\/P484.pdf"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2004.840306"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462176"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2784731.2784760"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915244"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00976642"},{"key":"e_1_2_2_34_1","article-title":"SciDB: An Open-Source DBMS for Scientific Data","volume":"2012","author":"Stonebraker Michael","year":"2012","unstructured":"Michael Stonebraker . 2012 . SciDB: An Open-Source DBMS for Scientific Data . ERCIM News 2012 , 89 ( 2012 ). http:\/\/ercimnews.ercim.eu\/en89\/special\/scidb-an-open-source-dbms-for-scientific-data Michael Stonebraker. 2012. SciDB: An Open-Source DBMS for Scientific Data. ERCIM News 2012, 89 ( 2012 ). http:\/\/ercimnews.ercim.eu\/en89\/special\/scidb-an-open-source-dbms-for-scientific-data","journal-title":"ERCIM News"},{"key":"e_1_2_2_35_1","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases","author":"Stonebraker Michael","year":"2005","unstructured":"Michael Stonebraker , Daniel J. Abadi , Adam Batkin , Xuedong Chen , Mitch Cherniack , Miguel Ferreira , Edmond Lau , Amerson Lin , Samuel Madden , Elizabeth J. O'Neil , Patrick E. O'Neil , Alex Rasin , Nga Tran , and Stanley B. Zdonik . 2005. C-Store: A Column-oriented DBMS . In Proceedings of the 31st International Conference on Very Large Data Bases , Trondheim, Norway, August 30- September 2, 2005 , Klemens B\u00f6hm, Christian S. Jensen, Laura M. Haas, Martin L. Kersten, Per-\u00c5ke Larson, and Beng Chin Ooi (Eds.). ACM, 553-564. http:\/\/www.vldb.org\/archives\/website\/2005\/program\/paper\/thu\/p553-stonebraker.pdf Michael Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Samuel Madden, Elizabeth J. O'Neil, Patrick E. O'Neil, Alex Rasin, Nga Tran, and Stanley B. Zdonik. 2005. C-Store: A Column-oriented DBMS. In Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30-September 2, 2005, Klemens B\u00f6hm, Christian S. Jensen, Laura M. Haas, Martin L. Kersten, Per-\u00c5ke Larson, and Beng Chin Ooi (Eds.). ACM, 553-564. http:\/\/www.vldb.org\/archives\/website\/2005\/program\/paper\/thu\/p553-stonebraker.pdf"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2584665"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196893"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353383"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2004.12.011"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342630"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062386"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428238","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428238","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:57Z","timestamp":1750197777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428238"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":41,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2020,11,13]]}},"alternative-id":["10.1145\/3428238"],"URL":"https:\/\/doi.org\/10.1145\/3428238","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"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"}}]}}