{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T01:04:50Z","timestamp":1789434290908,"version":"build-2803163510"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,8]]},"abstract":"<jats:p>Robust query optimization becomes illusory in the presence of correlated predicates or user-defined functions. Occasionally, the query optimizer will choose join orders whose execution time is by many orders of magnitude higher than necessary. We present SkinnerDB, a novel database management system that is designed from the ground up for reliable optimization and robust performance.<\/jats:p>\n          <jats:p>SkinnerDB implements several adaptive query processing strategies based on reinforcement learning. We divide the execution of a query into small time periods in which different join orders are executed. Thereby, we converge to optimal join orders with regret bounds, meaning that the expected difference between actual execution time and time for an optimal join order is bounded. To the best of our knowledge, our execution strategies are the first to provide comparable formal guarantees. SkinnerDB can be used as a layer on top of any existing database management system. We use optimizer hints to force existing systems to try out different join orders, carefully restricting execution time per join order and data batch via timeouts. We choose timeouts according to an iterative scheme that balances execution time over different timeouts to guarantee bounded regret. Alternatively, SkinnerDB can be used as a standalone, featuring an execution engine that is tailored to the requirements of join order learning. In particular, we use a specialized multi-way join algorithm and a concise tuple representation to facilitate fast switches between join orders. In our demonstration, we let participants experiment with different query types and databases. We visualize the learning process and compare against baselines.<\/jats:p>","DOI":"10.14778\/3229863.3236263","type":"journal-article","created":{"date-parts":[[2018,9,10]],"date-time":"2018-09-10T12:12:28Z","timestamp":1536581548000},"page":"2074-2077","source":"Crossref","is-referenced-by-count":25,"title":["SkinnerDB"],"prefix":"10.14778","volume":"11","author":[{"given":"Immanuel","family":"Trummer","sequence":"first","affiliation":[{"name":"Cornell University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Samuel","family":"Moseley","sequence":"additional","affiliation":[{"name":"Cornell University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Deepak","family":"Maram","sequence":"additional","affiliation":[{"name":"Cornell University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saehan","family":"Jo","sequence":"additional","affiliation":[{"name":"Cornell University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph","family":"Antonakakis","sequence":"additional","affiliation":[{"name":"Cornell University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316788"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.64"},{"key":"e_1_2_1_3_1","unstructured":"K. H. Alyoubi. Database query optimisation based on measures of regret. PhD thesis 2016.  K. H. Alyoubi. Database query optimisation based on measures of regret. PhD thesis 2016."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806446"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/335191.335420"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066172"},{"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.1145\/1409360.1409380"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564722"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.908978"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453976"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/974121.974129"},{"issue":"1","key":"e_1_2_1_13_1","first-page":"1","volume":"1","author":"Deshpande A.","year":"2006","journal-title":"Adaptive Query Processing. Foundations and Trends\u00ae in"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989359"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733036"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588566"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687556"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"S. Ewen M. Ortega-Binderberger and V. Markl. A learning optimizer for a federated database management system. Informatik - Forschung und Entwicklung 20(3):138--151 2005.  S. Ewen M. Ortega-Binderberger and V. Markl. A learning optimizer for a federated database management system. Informatik - Forschung und Entwicklung 20(3):138--151 2005.","DOI":"10.1007\/s00450-005-0206-8"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.130"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2093548.2093574"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_22_1","first-page":"522","volume-title":"ICDE","author":"Haas P.","year":"2011"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/141484.130335"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622737.1622748"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610531"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11871842_29"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350269"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/93605.93611"},{"key":"e_1_2_1_29_1","first-page":"56","volume-title":"CIDR","author":"Malik T.","year":"2007"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1188455.1188562"},{"key":"e_1_2_1_31_1","first-page":"73","volume-title":"BTW","author":"Neumann T.","year":"2013"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_1_33_1","volume-title":"CIDR","author":"Pavlo A.","year":"2017"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556553"},{"key":"e_1_2_1_35_1","unstructured":"PostgreSQL Global Development Group. PostgreSQL. https:\/\/www.postgresql.org\/ 2017.  PostgreSQL Global Development Group. PostgreSQL. https:\/\/www.postgresql.org\/ 2017."},{"key":"e_1_2_1_36_1","first-page":"26","volume-title":"ICDE","author":"Quanzhong L.","year":"2007"},{"key":"e_1_2_1_37_1","first-page":"353","volume-title":"ICDE","author":"Raman V. R. V.","year":"2003"},{"key":"e_1_2_1_38_1","first-page":"19","volume-title":"PVLDB","author":"Stillger M.","year":"2001"},{"key":"e_1_2_1_39_1","unstructured":"TPC. TPC-H Benchmark 2013.  TPC. TPC-H Benchmark 2013."},{"key":"e_1_2_1_40_1","unstructured":"K. Tzoumas T. Sellis and C. S. Jensen. A reinforcement learning approach for adaptive query processing. Technical report 2008.  K. Tzoumas T. Sellis and C. S. Jensen. A reinforcement learning approach for adaptive query processing. Technical report 2008."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315477"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882914"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3229863.3236263","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:13:51Z","timestamp":1672222431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3229863.3236263"}},"subtitle":["regret-bounded query evaluation via reinforcement learning"],"short-title":[],"issued":{"date-parts":[[2018,8]]},"references-count":42,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["10.14778\/3229863.3236263"],"URL":"https:\/\/doi.org\/10.14778\/3229863.3236263","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,8]]}}}