{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T06:52:12Z","timestamp":1777013532936,"version":"3.51.4"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>\n            Many commercial RDBMSs employ cost-based query optimization exploiting dynamic programming (DP) to efficiently generate the optimal query execution plan. However, optimization time increases rapidly for queries joining more than 10 tables. Randomized or heuristic search algorithms reduce query optimization time for large join queries by considering fewer plans, sacrificing plan optimality. Though commercial systems executing query plans in parallel have existed for over a decade, the optimization of such plans still occurs serially. While modern microprocessors employ multiple cores to accelerate computations, parallelizing query optimization to exploit multi-core parallelism is not as straightforward as it may seem. The DP used in join enumeration belongs to the challenging\n            <jats:italic>nonserial polyadic<\/jats:italic>\n            DP class because of its non-uniform data dependencies. In this paper, we propose a comprehensive and practical solution for parallelizing query optimization in the multi-core processor architecture, including a parallel join enumeration algorithm and several alternative ways to allocate work to threads to balance their load. We also introduce a novel data structure called\n            <jats:italic>skip vector array<\/jats:italic>\n            to significantly reduce the generation of join partitions that are infeasible. This solution has been prototyped in PostgreSQL. Extensive experiments using various query graph topologies confirm that our algorithms allocate the work evenly, thereby achieving almost linear speed-up. Our parallel join enumeration algorithm enhanced with our skip vector array outperforms the conventional generate-and-filter DP algorithm by up to two orders of magnitude for star queries-linear speedup due to parallelism and an order of magnitude performance improvement due to the skip vector array.\n          <\/jats:p>","DOI":"10.14778\/1453856.1453882","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"188-200","source":"Crossref","is-referenced-by-count":28,"title":["Parallelizing query optimization"],"prefix":"10.14778","volume":"1","author":[{"given":"Wook-Shin","family":"Han","sequence":"first","affiliation":[{"name":"Kyungpook National University, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wooseong","family":"Kwak","sequence":"additional","affiliation":[{"name":"Kyungpook National University, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinsoo","family":"Lee","sequence":"additional","affiliation":[{"name":"Kyungpook National University, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy M.","family":"Lohman","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center, San Jose, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Volker","family":"Markl","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center, San Jose, California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.466632"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/564870.564916"},{"key":"e_1_2_1_3_1","volume-title":"ICGA","author":"Bennett K. P.","year":"1991","unstructured":"K. P. Bennett , A genetic algorithm for database query optimization . In ICGA , 1991 . K. P. Bennett, et al. A genetic algorithm for database query optimization. In ICGA, 1991."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247567"},{"key":"e_1_2_1_5_1","volume-title":"PDP","author":"Elkihel M.","year":"2006","unstructured":"M. Elkihel and D. E. Baz . Load balancing in a parallel dynamic programming multi-method applied to the 0--1 knapsack problem . In PDP , 2006 . M. Elkihel and D. E. Baz. Load balancing in a parallel dynamic programming multi-method applied to the 0--1 knapsack problem. In PDP, 2006."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/219713.219760"},{"key":"e_1_2_1_7_1","volume-title":"Multicore and gpus: One tool, two processors. Dr. Dobb's Journal","author":"Erickson J.","year":"2007","unstructured":"J. Erickson . Multicore and gpus: One tool, two processors. Dr. Dobb's Journal , 2007 . J. Erickson. Multicore and gpus: One tool, two processors. Dr. Dobb's Journal, 2007."},{"key":"e_1_2_1_8_1","volume-title":"Introduction to Parallel Computing","author":"Grama A.","year":"2003","unstructured":"A. Grama Introduction to Parallel Computing . Addison Wesley , 2 nd edition, 2003 . A. Grama et al. Introduction to Parallel Computing. Addison Wesley, 2nd edition, 2003.","edition":"2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1099554.1099587"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247569"},{"key":"e_1_2_1_11_1","volume-title":"Parallel dynamic programming","author":"Huang S.-H. S.","year":"1994","unstructured":"S.-H. S. Huang Parallel dynamic programming . IEEE TPDS , 5(3), 1994 . S.-H. S. Huang et al. Parallel dynamic programming. IEEE TPDS, 5(3), 1994."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872803"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98740"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/582250.582278"},{"key":"e_1_2_1_15_1","volume-title":"VLDB","author":"Klots B.","year":"1996","unstructured":"B. Klots . Cache coherency in oracle parallel server . In VLDB , 1996 . B. Klots. Cache coherency in oracle parallel server. In VLDB, 1996."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.277773"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/50202.50204"},{"key":"e_1_2_1_18_1","unstructured":"G. M. Lohman. Is (your) database research having impact? In DASFAA (Keynote speech) 2007.   G. M. Lohman. Is (your) database research having impact? In DASFAA (Keynote speech) 2007."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872778"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007642"},{"key":"e_1_2_1_21_1","volume-title":"VLDB","author":"Moerkotte G.","year":"2006","unstructured":"G. Moerkotte and T. Neumann . Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products . In VLDB , 2006 . G. Moerkotte and T. Neumann. Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products. In VLDB, 2006."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376672"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/188573.188623"},{"key":"e_1_2_1_24_1","volume-title":"VLDB","author":"Ono K.","year":"1990","unstructured":"K. Ono and G. M. Lohman . Measuring the complexity of join enumeration in query optimization . In VLDB , 1990 . K. Ono and G. M. Lohman. Measuring the complexity of join enumeration in query optimization. In VLDB, 1990."},{"key":"e_1_2_1_25_1","unstructured":"Postgresql version 8.3. http:\/\/www.postgresql.org.  Postgresql version 8.3. http:\/\/www.postgresql.org."},{"key":"e_1_2_1_26_1","volume-title":"Database Management Systems","author":"Ramakrishnan R.","year":"2003","unstructured":"R. Ramakrishnan and J. Gehrke . Database Management Systems . Addison Wesley , 2 nd edition, 2003 . R. Ramakrishnan and J. Gehrke. Database Management Systems. Addison Wesley, 2nd edition, 2003.","edition":"2"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2002.1003856"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007652"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_30_1","volume-title":"VLDB","author":"Shatdal A.","year":"1994","unstructured":"A. Shatdal Cache conscious algorithms for relational query processing . In VLDB , 1994 . A. Shatdal et al. Cache conscious algorithms for relational query processing. In VLDB, 1994."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.506710"},{"key":"e_1_2_1_32_1","volume-title":"IPDPS","author":"Multi-Core P.","year":"2007","unstructured":"P. Stenstr\u00f6m Is the Multi-Core Roadmap going to Live Up to its Promises ? In IPDPS , 2007 . P. Stenstr\u00f6m Is the Multi-Core Roadmap going to Live Up to its Promises? In IPDPS, 2007."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/50202.50203"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1188455.1188538"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248399"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1453856.1453882","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:12:37Z","timestamp":1672225957000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1453856.1453882"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.14778\/1453856.1453882"],"URL":"https:\/\/doi.org\/10.14778\/1453856.1453882","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}