{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:20:57Z","timestamp":1773886857733,"version":"3.50.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2016,5]]},"abstract":"<jats:p>Data processing systems offer an ever increasing degree of parallelism on the levels of cores, CPUs, and processing nodes. Query optimization must exploit high degrees of parallelism in order not to gradually become the bottleneck of query evaluation. We show how to parallelize query optimization at a massive scale.<\/jats:p>\n          <jats:p>We present algorithms for parallel query optimization in left-deep and bushy plan spaces. At optimization start, we divide the plan space for a given query into partitions of equal size that are explored in parallel by worker nodes. At the end of optimization, each worker returns the optimal plan in its partition to the master which determines the globally optimal plan from the partition-optimal plans. No synchronization or data exchange is required during the actual optimization phase. The amount of data sent over the network, at the start and at the end of optimization, as well as the complexity of serial steps within our algorithms increase only linearly in the number of workers and in the query size. The time and space complexity of optimization within one partition decreases uniformly in the number of workers. We parallelize single- and multi-objective query optimization over a cluster with 100 nodes in our experiments, using more than 250 concurrent worker threads (Spark executors). Despite high network latency and task assignment overheads, parallelization yields speedups of up to one order of magnitude for large queries whose optimization takes minutes on a single node.<\/jats:p>","DOI":"10.14778\/2947618.2947622","type":"journal-article","created":{"date-parts":[[2016,7,26]],"date-time":"2016-07-26T13:28:39Z","timestamp":1469539719000},"page":"660-671","source":"Crossref","is-referenced-by-count":10,"title":["Parallelizing query optimization on shared-nothing architectures"],"prefix":"10.14778","volume":"9","author":[{"given":"Immanuel","family":"Trummer","sequence":"first","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne"}]},{"given":"Christoph","family":"Koch","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne"}]}],"member":"320","published-online":{"date-parts":[[2016,5]]},"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.1109\/ICDE.2010.5447916"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543650"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.212471"},{"issue":"3","key":"e_1_2_1_5_1","first-page":"935","article-title":"Graceful Degradation for Top-Down Join Enumeration via similar sub-queries measure on Chip Multi-Processor","volume":"941","author":"Chen Y.","year":"2012","unstructured":"Y. Chen and C. Yin . Graceful Degradation for Top-Down Join Enumeration via similar sub-queries measure on Chip Multi-Processor . Applied Mathematics and Information Sciences , 941 ( 3 ): 935 -- 941 , 2012 . Y. Chen and C. Yin. Graceful Degradation for Top-Down Join Enumeration via similar sub-queries measure on Chip Multi-Processor. Applied Mathematics and Information Sciences, 941(3):935--941, 2012.","journal-title":"Applied Mathematics and Information Sciences"},{"key":"e_1_2_1_6_1","volume-title":"RDF Database Systems: Triples Storage and SPARQL Query Processing","author":"Cure O.","year":"2014","unstructured":"O. Cure and G. Blin . RDF Database Systems: Triples Storage and SPARQL Query Processing . 2014 . O. Cure and G. Blin. RDF Database Systems: Triples Storage and SPARQL Query Processing. 2014."},{"key":"e_1_2_1_7_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_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/645478.757691"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453882"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559853"},{"key":"e_1_2_1_11_1","first-page":"766","volume-title":"VLDB","author":"Hulgeri A.","year":"2003","unstructured":"A. Hulgeri and S. Sudarshan . AniPQO: almost non-intrusive parametric query optimization for nonlinear cost functions . In VLDB , pages 766 -- 777 , 2003 . A. Hulgeri and S. Sudarshan. AniPQO: almost non-intrusive parametric query optimization for nonlinear cost functions. In VLDB, pages 766--777, 2003."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98740"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050037"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989355"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.1998.658762"},{"key":"e_1_2_1_16_1","first-page":"314","volume-title":"VLDB","author":"Ono K.","year":"1990","unstructured":"K. Ono and G. Lohman . Measuring the complexity of join enumeration in query optimization . In VLDB , pages 314 -- 325 , 1990 . K. Ono and G. Lohman. Measuring the complexity of join enumeration in query optimization. In VLDB, pages 314--325, 1990."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2595637"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050040"},{"issue":"1","key":"e_1_2_1_20_1","first-page":"4","article-title":"The Case for Shared Nothing","volume":"9","author":"Stonebraker M.","year":"1986","unstructured":"M. Stonebraker . The Case for Shared Nothing . IEEE Database Engineering Bulletin , 9 ( 1 ): 4 -- 9 , 1986 . M. Stonebraker. The Case for Shared Nothing. IEEE Database Engineering Bulletin, 9(1):4--9, 1986.","journal-title":"IEEE Database Engineering Bulletin"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66961"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610527"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746484"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735512"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233317"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559938"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4304\/jcp.6.10.2004-2012"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2947618.2947622","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:33:16Z","timestamp":1672219996000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2947618.2947622"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5]]},"references-count":27,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["10.14778\/2947618.2947622"],"URL":"https:\/\/doi.org\/10.14778\/2947618.2947622","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2016,5]]}}}