{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T08:22:13Z","timestamp":1782289333672,"version":"3.54.5"},"reference-count":94,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,3,31]],"date-time":"2018-03-31T00:00:00Z","timestamp":1522454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Google Ph.D. Fellowship, NCCR MARVEL, and ERC","award":["279804"],"award-info":[{"award-number":["279804"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>Abstraction without regret refers to the vision of using high-level programming languages for systems development without experiencing a negative impact on performance. A database system designed according to this vision offers both increased productivity and high performance instead of sacrificing the former for the latter as is the case with existing, monolithic implementations that are hard to maintain and extend.<\/jats:p>\n          <jats:p>\n            In this article, we realize this vision in the domain of analytical query processing. We present LegoBase, a query engine written in the\n            <jats:italic>high-level<\/jats:italic>\n            programming language Scala. The key technique to regain efficiency is to apply\n            <jats:italic>generative<\/jats:italic>\n            programming: LegoBase performs source-to-source compilation and optimizes database systems code by converting the high-level Scala code to specialized, low-level C code. We show how generative programming allows to\n            <jats:italic>easily<\/jats:italic>\n            implement a wide spectrum of optimizations, such as introducing data partitioning or switching from a row to a column data layout, which are difficult to achieve with existing low-level query compilers that handle\n            <jats:italic>only<\/jats:italic>\n            queries. We demonstrate that sufficiently powerful abstractions are essential for dealing with the complexity of the optimization effort, shielding developers from compiler internals and decoupling individual optimizations from each other.\n          <\/jats:p>\n          <jats:p>We evaluate our approach with the TPC-H benchmark and show that (a) with all optimizations enabled, our architecture significantly outperforms a commercial in-memory database as well as an existing query compiler. (b) Programmers need to provide just a few hundred lines of high-level code for implementing the optimizations, instead of complicated low-level code that is required by existing query compilation approaches. (c) These optimizations may potentially come at the cost of using more system memory for improved performance. (d) The compilation overhead is low compared to the overall execution time, thus making our approach usable in practice for compiling query engines.<\/jats:p>","DOI":"10.1145\/3183653","type":"journal-article","created":{"date-parts":[[2018,4,11]],"date-time":"2018-04-11T12:31:03Z","timestamp":1523449863000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["Building Efficient Query Engines in a High-Level Language"],"prefix":"10.1145","volume":"43","author":[{"given":"Amir","family":"Shaikhha","sequence":"first","affiliation":[{"name":"EPFL, Lausanne, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yannis","family":"Klonatos","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christoph","family":"Koch","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,4,11]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376712"},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the International Workshop on End-to-end Management of Big Data (BigData\u201912)","author":"Ackermann Stefan","year":"2012"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687592"},{"key":"e_1_2_2_4_1","unstructured":"Alfred V. Aho Ravi Sethi and Jeffrey D. Ullman. 2007. Compilers: Principles Techniques and Tools. Vol. 2. Addison-Wesley Reading MA.   Alfred V. Aho Ravi Sethi and Jeffrey D. Ullman. 2007. Compilers: Principles Techniques and Tools. Vol. 2. Addison-Wesley Reading MA."},{"key":"e_1_2_2_5_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB\u201901)","author":"Ailamaki Anastassia","year":"2001"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742797"},{"key":"e_1_2_2_7_1","unstructured":"Peter Bailis. 2015. Coordination Avoidance in Distributed Databases. Ph.D. Dissertation. University of California Berkeley.  Peter Bailis. 2015. Coordination Avoidance in Distributed Databases. Ph.D. Dissertation. University of California Berkeley."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04936-6_5"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/358769.358784"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767870"},{"key":"e_1_2_2_11_1","volume-title":"Conference on Innovative Data Systems Research (CIDR\u201913)","author":"Cheung Alvin"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350262"},{"key":"e_1_2_2_13_1","first-page":"48","article-title":"Using program analysis to improve database applications","volume":"37","author":"Cheung Alvin","year":"2014","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462180"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824045"},{"key":"e_1_2_2_16_1","volume-title":"Tupleware: Redefining modern analytics. CoRR abs\/1406.6667","author":"Crotty Andrew","year":"2014"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375634.1375649"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544838"},{"key":"e_1_2_2_19_1","unstructured":"F. E. Allen and J. Cocke. 1971. A Catalogue of Optimizing Transformations.  F. E. Allen and J. Cocke. 1971. A Catalogue of Optimizing Transformations."},{"key":"e_1_2_2_20_1","volume-title":"Proceedings of the 1997 Conference on Domain-Specific Languages (DSL\u201997)","author":"Faith Rickard E."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2094114.2094126"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010095604496"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/165180.165214"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824069"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.273032"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304242"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559982"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453975"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB\u201906)","author":"Harizopoulos Stavros","year":"2006"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/242224.242477"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2658761.2658776"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243418.1243424"},{"key":"e_1_2_2_33_1","unstructured":"Neil D. Jones Carsten K. Gomard and Peter Sestoft. 1993. Partial Evaluation and Automatic Program Generation. Peter Sestoft.   Neil D. Jones Carsten K. Gomard and Peter Sestoft. 1993. Partial Evaluation and Automatic Program Generation. Peter Sestoft."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2658761.2658771"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454211"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2004.840447"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732959"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465334"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807100"},{"key":"e_1_2_2_40_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201913)","author":"Koch Christoph","year":"2013"},{"key":"e_1_2_2_41_1","first-page":"70","article-title":"Abstraction without regret in database systems building: A manifesto","volume":"37","author":"Koch Christoph","year":"2014","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0348-4"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447892"},{"key":"e_1_2_2_44_1","first-page":"34","article-title":"The hekaton memory-optimized OLTP engine","volume":"36","author":"Larson Per-\u00c5ke","year":"2013","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/977395.977673"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2011.68"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687618"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.194"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/362875.362879"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142552"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151113.3151114"},{"key":"e_1_2_2_52_1","doi-asserted-by":"crossref","first-page":"843","DOI":"10.14778\/3402707.3402723","article-title":"Accelerating queries with group-by and join by groupjoin","volume":"4","author":"Moerkotte Guido","year":"2011","journal-title":"Proc. VLDB"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993513"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732984"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094815"},{"key":"e_1_2_2_57_1","unstructured":"Oracle Corporation. 2006. \u00a0\u00a0\u00a0TimesTen\u00a0\u00a0\u00a0 In-Memory\u00a0\u00a0\u00a0 Database\u00a0\u00a0\u00a0 Architectural\u00a0\u00a0\u00a0 Overview. Retrieved from http:\/\/download.oracle.com\/otn_hosted_doc\/timesten\/603\/TimesTen-Documentation\/arch.pdf.  Oracle Corporation. 2006. \u00a0\u00a0\u00a0TimesTen\u00a0\u00a0\u00a0 In-Memory\u00a0\u00a0\u00a0 Database\u00a0\u00a0\u00a0 Architectural\u00a0\u00a0\u00a0 Overview. Retrieved from http:\/\/download.oracle.com\/otn_hosted_doc\/timesten\/603\/TimesTen-Documentation\/arch.pdf."},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656552"},{"key":"e_1_2_2_59_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201917)","author":"Palkar Shoumik","year":"2017"},{"key":"e_1_2_2_60_1","volume-title":"Conference on Innovative Data Systems Research (CIDR\u201917)","author":"Pavlo Andrew","year":"2017"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213852"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497414"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.40"},{"key":"e_1_2_2_64_1","volume-title":"International Workshop on Languages and Compilers for Parallel Computing. Springer, 300--314","author":"Kristian F."},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818180"},{"key":"e_1_2_2_66_1","unstructured":"Tiark Rompf. 2012. Lightweight Modular Staging and Embedded Compilers: Abstraction Without Regret for High-Level High-Performance Programming. Technical Report. EPFL Ph.D. thesis 5456.  Tiark Rompf. 2012. Lightweight Modular Staging and Embedded Compilers: Abstraction Without Regret for High-Level High-Performance Programming. Technical Report. EPFL Ph.D. thesis 5456."},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868294.1868314"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429128"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723720"},{"key":"e_1_2_2_70_1","doi-asserted-by":"crossref","unstructured":"Amir Shaikhha Mohammad Dashti and Christoph Koch. 2018. Push vs. pull-based loop fusion in query engines. J. Funct. Program. 28 (2018).  Amir Shaikhha Mohammad Dashti and Christoph Koch. 2018. Push vs. pull-based loop fusion in query engines. J. Funct. Program. 28 (2018).","DOI":"10.1017\/S0956796818000102"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915244"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610492"},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/1995441.1995446"},{"key":"e_1_2_2_74_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB\u201905)","author":"Stonebraker Mike","year":"2005"},{"key":"e_1_2_2_75_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB\u201907)","author":"Stonebraker Michael","year":"2007"},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517208.2517220"},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012984529382"},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159876.1159884"},{"key":"e_1_2_2_79_1","volume-title":"Domain-Specific Program Generation","author":"Taha Walid"},{"key":"e_1_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00053-0"},{"key":"e_1_2_2_81_1","unstructured":"The GNOME Project. 2013. GLib: Library Package for Low-Level Data Structures in C\u2014The Reference Manual. Retrieved from https:\/\/developer.gnome.org\/glib\/2.38\/.  The GNOME Project. 2013. GLib: Library Package for Low-Level Data Structures in C\u2014The Reference Manual. Retrieved from https:\/\/developer.gnome.org\/glib\/2.38\/."},{"key":"e_1_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3079079.3079099"},{"key":"e_1_2_2_83_1","unstructured":"Transaction Processing Performance Council. 1999. TPC-H an Ad-Hoc Decision Support Benchmark. Retrieved from http:\/\/www.tpc.org\/tpch.  Transaction Processing Performance Council. 1999. TPC-H an Ad-Hoc Decision Support Benchmark. Retrieved from http:\/\/www.tpc.org\/tpch."},{"key":"e_1_2_2_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/352029.352035"},{"key":"e_1_2_2_85_1","first-page":"12","article-title":"Processing declarative queries through generating imperative code in managed runtimes","volume":"37","author":"Viglas Stratis","year":"2014","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190216.1190248"},{"key":"e_1_2_2_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/1449764.1449767"},{"key":"e_1_2_2_88_1","unstructured":"Michael Joseph Wolfe. 1978. Techniques for Improving the Inherent Parallelism in Programs. Ph.D. Dissertation. Department of Computer Science University of Illinois at Urbana--Champaign.  Michael Joseph Wolfe. 1978. Techniques for Improving the Inherent Parallelism in Programs. Ph.D. Dissertation. Department of Computer Science University of Illinois at Urbana--Champaign."},{"key":"e_1_2_2_89_1","unstructured":"Yuan Yu Michael Isard Dennis Fetterly Mihai Budiu \u00dalfar Erlingsson Pradeep Kumar Gunda and Jon Currey. 2008. DryadLINQ: A system for general-purpose \u00a0distributed data-parallel computing using a high-level language. (OSDI\u201908). USENIX Association Berkeley CA 1--14.   Yuan Yu Michael Isard Dennis Fetterly Mihai Budiu \u00dalfar Erlingsson Pradeep Kumar Gunda and Jon Currey. 2008. DryadLINQ: A system for general-purpose \u00a0distributed data-parallel computing using a high-level language. (OSDI\u201908). USENIX Association Berkeley CA 1--14."},{"key":"e_1_2_2_90_1","unstructured":"Matei Zaharia Mosharaf Chowdhury Michael J. Franklin Scott Shenker and Ion Stoica. 2010. Spark: cluster computing with working sets. In \u00a0Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing (HotCloud\u201910). USENIX Association Berkeley CA.   Matei Zaharia Mosharaf Chowdhury Michael J. Franklin Scott Shenker and Ion Stoica. 2010. Spark: cluster computing with working sets. In \u00a0Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing (HotCloud\u201910). USENIX Association Berkeley CA."},{"key":"e_1_2_2_91_1","first-page":"011","article-title":"Optimized SQL code generation. Patent No. 7430549 B2","volume":"10","author":"Zane Barry M.","year":"2008","journal-title":"WO Patent App. US"},{"key":"e_1_2_2_92_1","doi-asserted-by":"publisher","DOI":"10.1145\/2259016.2259025"},{"key":"e_1_2_2_93_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.110"},{"key":"e_1_2_2_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290520.1290522"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3183653","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3183653","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:32Z","timestamp":1750213592000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3183653"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,31]]},"references-count":94,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3183653"],"URL":"https:\/\/doi.org\/10.1145\/3183653","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,31]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}