{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,10]],"date-time":"2025-05-10T23:01:16Z","timestamp":1746918076034},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:p>Just-in-time (JIT) query compilation is a technique to improve analytical query performance in database management systems (DBMSs). But the cost of compiling each query can be significant relative to its execution time. This overhead prohibits the DBMS from employing well-known adaptive query processing (AQP) methods to generate a new plan for a query if data distributions do not match the optimizer's estimations. The optimizer could eagerly generate multiple sub-plans for a query, but it can only include a few alternatives as each addition increases the compilation time.<\/jats:p>\n          <jats:p>We present a method, called Permutable Compiled Queries (PCQ), that bridges the gap between JIT compilation and AQP. It allows the DBMS to modify compiled queries without needing to recompile or including all possible variations before the query starts. With PCQ, the DBMS structures a query's code with indirection layers that enable the DBMS to change the plan even while it is running. We implement PCQ in an in-memory DBMS and compare it against non-adaptive plans in a microbenchmark and against state-of-the-art analytic DBMSs. Our evaluation shows that PCQ outperforms static plans by more than 4X and yields better performance on an analytical benchmark by more than 2X against other DBMSs.<\/jats:p>","DOI":"10.14778\/3425879.3425882","type":"journal-article","created":{"date-parts":[[2020,11,25]],"date-time":"2020-11-25T02:45:23Z","timestamp":1606272323000},"page":"101-113","source":"Crossref","is-referenced-by-count":17,"title":["Permutable compiled queries"],"prefix":"10.14778","volume":"14","author":[{"given":"Prashanth","family":"Menon","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amadou","family":"Ngom","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lin","family":"Ma","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Todd C.","family":"Mowry","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Pavlo","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,11,16]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Actian Vector. http:\/\/esd.actian.com\/product\/Vector.  [n.d.]. Actian Vector. http:\/\/esd.actian.com\/product\/Vector."},{"key":"e_1_2_1_2_1","unstructured":"[n.d.]. Google Benchmark. https:\/\/github.com\/google\/benchmark.  [n.d.]. Google Benchmark. https:\/\/github.com\/google\/benchmark."},{"key":"e_1_2_1_3_1","unstructured":"[n.d.]. HyPer. https:\/\/hyper-db.de.  [n.d.]. HyPer. https:\/\/hyper-db.de."},{"key":"e_1_2_1_4_1","unstructured":"[n.d.]. NoisePage. https:\/\/noise.page.  [n.d.]. NoisePage. https:\/\/noise.page."},{"key":"e_1_2_1_5_1","unstructured":"[n.d.]. Skewed TPC-H. https:\/\/www.microsoft.com\/en-us\/download\/details.aspx?id=52430.  [n.d.]. Skewed TPC-H. https:\/\/www.microsoft.com\/en-us\/download\/details.aspx?id=52430."},{"key":"e_1_2_1_6_1","unstructured":"Shivnath Babu and Pedro Bizarro. 2005. Adaptive Query Processing in the Looking Glass. In CIDR. 238--249.  Shivnath Babu and Pedro Bizarro. 2005. Adaptive Query Processing in the Looking Glass. In CIDR. 238--249."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066171"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04936-6_5"},{"key":"e_1_2_1_9_1","unstructured":"Peter Boncz Marcin Zukowski and Niels Nes. 2005. MonetDB\/X100: Hyper-pipelining query execution. In CIDR.  Peter Boncz Marcin Zukowski and Niels Nes. 2005. MonetDB\/X100: Hyper-pipelining query execution. In CIDR."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/358769.358784"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/191843.191872"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1331939.1331940"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389138"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588566"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66960"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389739"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/170036.170078"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732959"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Andr\u00e9 Kohn Viktor Leis and Thomas Neumann. 2018. Adaptive Execution of Compiled Queries. In ICDE. 197--208.  Andr\u00e9 Kohn Viktor Leis and Thomas Neumann. 2018. Adaptive Execution of Compiled Queries. In ICDE. 197--208.","DOI":"10.1109\/ICDE.2018.00027"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447892"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610507"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367848"},{"key":"e_1_2_1_25_1","volume-title":"Mainlining Databases: Supporting Fast Transactional Workloads on Universal Columnar Data File Formats. Under Submission.","author":"Li Tianyu","year":"2019","unstructured":"Tianyu Li , Matthew Butrovich , Amadou Ngom , Wes McKinney , and Andrew Pavlo . 2019 . Mainlining Databases: Supporting Fast Transactional Workloads on Universal Columnar Data File Formats. Under Submission. Tianyu Li, Matthew Butrovich, Amadou Ngom, Wes McKinney, and Andrew Pavlo. 2019. Mainlining Databases: Supporting Fast Transactional Workloads on Universal Columnar Data File Formats. Under Submission."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007642"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151113.3151114"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749436"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10424-4_17"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735499"},{"key":"e_1_2_1_32_1","volume-title":"Code Generation: The Inner Sanctum of Database Performance","author":"Paroski Drew","year":"2016","unstructured":"Drew Paroski . 2016 . Code Generation: The Inner Sanctum of Database Performance . http:\/\/highscalability.com\/blog\/2016\/9\/7\/code-generation-the-inner-sanctum-of-database-performance.html. Drew Paroski. 2016. Code Generation: The Inner Sanctum of Database Performance. http:\/\/highscalability.com\/blog\/2016\/9\/7\/code-generation-the-inner-sanctum-of-database-performance.html."},{"key":"e_1_2_1_33_1","volume-title":"2019 IEEE 35th International Conference on Data Engineering (ICDE).","author":"Perron M.","unstructured":"M. Perron , Z. Shang , T. Kraska , and M. Stonebraker . 2019. How I Learned to Stop Worrying and Love Re-optimization . In 2019 IEEE 35th International Conference on Data Engineering (ICDE). M. Perron, Z. Shang, T. Kraska, and M. Stonebraker. 2019. How I Learned to Stop Worrying and Love Re-optimization. In 2019 IEEE 35th International Conference on Data Engineering (ICDE)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465292"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377382"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/645927.672349"},{"key":"e_1_2_1_37_1","unstructured":"The Transaction Processing Council. 2013. TPC-H Benchmark (Revision 2.16.0). http:\/\/www.tpc.org\/tpch\/.  The Transaction Processing Council. 2013. TPC-H Benchmark (Revision 2.16.0). http:\/\/www.tpc.org\/tpch\/."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300088"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536254"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3090163.3090167"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3425879.3425882","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:06:17Z","timestamp":1672225577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3425879.3425882"}},"subtitle":["dynamically adapting compiled queries without recompiling"],"short-title":[],"issued":{"date-parts":[[2020,10]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["10.14778\/3425879.3425882"],"URL":"https:\/\/doi.org\/10.14778\/3425879.3425882","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,10]]}}}