{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:50:23Z","timestamp":1773481823090,"version":"3.50.1"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,6,2]],"date-time":"2016-06-02T00:00:00Z","timestamp":1464825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2016,6,2]]},"abstract":"<jats:p>We propose a generalization of the classical database query optimization problem: multi-objective parametric query optimization (MPQ). MPQ compares alternative processing plans according to multiple execution cost metrics. It also models missing pieces of information on which plan costs depend upon as parameters. Both features are crucial to model query processing on modern data processing platforms. MPQ generalizes previously proposed query optimization variants such as multi-objective query optimization, parametric query optimization, and traditional query optimization. We show however that the MPQ problem has different properties than prior variants and solving it requires novel methods. We present an algorithm that solves the MPQ problem and finds for a given query the set of all relevant query plans. This set contains all plans that realize optimal execution cost tradeoffs for any combination of parameter values. Our algorithm is based on dynamic programming and recursively constructs relevant query plans by combining relevant plans for query parts. We assume that all plan execution cost functions are piecewise-linear in the parameters. We use linear programming to compare alternative plans and to identify plans that are not relevant. We present a complexity analysis of our algorithm and experimentally evaluate its performance.<\/jats:p>","DOI":"10.1145\/2949741.2949748","type":"journal-article","created":{"date-parts":[[2016,6,3]],"date-time":"2016-06-03T12:14:26Z","timestamp":1464956066000},"page":"24-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Multi-Objective Parametric Query Optimization"],"prefix":"10.1145","volume":"45","author":[{"given":"Immanuel","family":"Trummer","sequence":"first","affiliation":[{"name":"Ecole Polytechnique F\u00e9d\u00e9rale de Lausanne"}]},{"given":"Christoph","family":"Koch","sequence":"additional","affiliation":[{"name":"Ecole Polytechnique F\u00e9d\u00e9rale de Lausanne"}]}],"member":"320","published-online":{"date-parts":[[2016,6,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367533"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00004-9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.160"},{"key":"e_1_2_1_4_1","volume-title":"PVLDB","author":"Darera P.","year":"2007","unstructured":"P. Darera and J. Haritsa . On the production of anorexic plan diagrams . PVLDB , 2007 . P. Darera and J. Haritsa. On the production of anorexic plan diagrams. PVLDB, 2007."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454173"},{"key":"e_1_2_1_6_1","first-page":"228","volume-title":"VLDB","author":"Ganguly S.","year":"1998","unstructured":"S. Ganguly . Design and analysis of parametric query optimization algorithms . In VLDB , pages 228 -- 238 , 1998 . S. Ganguly. Design and analysis of parametric query optimization algorithms. In VLDB, pages 228--238, 1998."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130291"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287385"},{"key":"e_1_2_1_9_1","first-page":"766","volume-title":"PVLDB","author":"Hulgeri A.","year":"2003","unstructured":"A. Hulgeri and S. Sudarshan . AniPQO: almost non-intrusive parametric query optimization for nonlinear cost functions . In PVLDB , pages 766 -- 777 , 2003 . A. Hulgeri and S. Sudarshan. AniPQO: almost non-intrusive parametric query optimization for nonlinear cost functions. In PVLDB, pages 766--777, 2003."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050037"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375560"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536207"},{"key":"e_1_2_1_13_1","first-page":"1228","volume-title":"VLDB","author":"Reddy N.","year":"2005","unstructured":"N. Reddy and J. Haritsa . Analyzing plan diagrams of database query optimizers . VLDB , pages 1228 -- 1239 , 2005 . N. Reddy and J. Haritsa. Analyzing plan diagrams of database query optimizers. VLDB, pages 1228--1239, 2005."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050040"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610527"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746484"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367546"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2949741.2949748","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2949741.2949748","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:00Z","timestamp":1750222560000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2949741.2949748"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,2]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,6,2]]}},"alternative-id":["10.1145\/2949741.2949748"],"URL":"https:\/\/doi.org\/10.1145\/2949741.2949748","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2016,6,2]]},"assertion":[{"value":"2016-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}