{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T10:24:41Z","timestamp":1777631081769,"version":"3.51.4"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,8]]},"abstract":"<jats:p>\n            Intra-query parallelism is a key for database software to offer acceptable responsiveness for data-intensive queries. Many researchers have studied how to achieve greater execution parallelism for database queries.\n            <jats:italic toggle=\"yes\">Partitioning<\/jats:italic>\n            is a representative approach, which divides a query into multiple sub-tasks and executes them in parallel. However, given a new query, optimal division is not necessarily obvious. Database software utilizes heuristic rules or statistical information to decide how to divide the query before execution. As yet another approach to achieve execution parallelism, this paper presents\n            <jats:italic toggle=\"yes\">out-of-order database execution<\/jats:italic>\n            (OoODE), a massively-parallel query execution method to offer significant speedup for database queries consistently. OoODE dynamically decomposes query work by making the best use of the exact knowledge of the potential execution parallelism for each operation ready to be performed during query execution. With OoODE, the database software is allowed to automatically squeeze out the execution parallelism that the query inherently holds. Hence, for a wide spectrum of queries, OoODE performs significantly faster than the serial (non-parallelized) execution, while it performs better than or comparably with alternative parallelizing methods without the need for dividing the query before execution. This paper presents the experiments that we conducted using the prototyped database software and demonstrates that OoODE is two to three orders of magnitude faster than the serial execution, whereas it is substantially (up to 2.07 times) faster than the best achievable case of partitioning. Besides, OoODE performs two to four orders of magnitude faster than major DBMSs.\n          <\/jats:p>","DOI":"10.14778\/3415478.3415571","type":"journal-article","created":{"date-parts":[[2020,9,14]],"date-time":"2020-09-14T18:46:40Z","timestamp":1600109200000},"page":"3489-3501","source":"Crossref","is-referenced-by-count":12,"title":["Out-of-order execution of database queries"],"prefix":"10.14778","volume":"13","author":[{"given":"Kazuo","family":"Goda","sequence":"first","affiliation":[{"name":"The University of Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuto","family":"Hayamizu","sequence":"additional","affiliation":[{"name":"The University of Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroyuki","family":"Yamada","sequence":"additional","affiliation":[{"name":"The University of Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masaru","family":"Kitsuregawa","sequence":"additional","affiliation":[{"name":"The University of Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,8]]},"reference":[{"issue":"10","key":"e_1_2_1_1_1","first-page":"1064","volume":"5","author":"Albutiu M.-C.","year":"2012","unstructured":"M.-C. Albutiu, A. Kemper, and T. Neumann. Massively Parallel Sort-merge Joins in Main Memory Multi-core Database Systems. PVLDB, 5(10):1064--1075, 2012.","journal-title":"PVLDB"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1993.344026"},{"issue":"2","key":"e_1_2_1_3_1","first-page":"42","volume":"15","author":"Arvind A.","year":"1982","unstructured":"A. Arvind and K. P. Gostelow. The U-Interpreter. Computer, 15(2):42--49, 1982.","journal-title":"The U-Interpreter. Computer"},{"issue":"2","key":"e_1_2_1_4_1","first-page":"3","article-title":"Born To Be Parallel Why Parallel Origins Give Teradata an Enduring Performance Edge","volume":"20","author":"Ballinger C.","year":"1997","unstructured":"C. Ballinger and R. Fryer. Born To Be Parallel Why Parallel Origins Give Teradata an Enduring Performance Edge. IEEE Data Eng. Bull., 20(2):3--12, 1997.","journal-title":"IEEE Data Eng. Bull."},{"issue":"11","key":"e_1_2_1_5_1","first-page":"1102","volume":"6","author":"Bellamkonda S.","year":"2013","unstructured":"S. Bellamkonda, H. Li, U. Jagtap, Y. Zhu, V. Liang, and T. Cruanes. Adaptive and Big Data Scale Parallel Execution in Oracle. PVLDB, 6(11):1102--1113, 2013.","journal-title":"PVLDB"},{"key":"e_1_2_1_6_1","volume-title":"Proc. Biennial Conf. on Innovative Data Systems Research","author":"Boncz P.","year":"2005","unstructured":"P. Boncz, M. Zukowski, and N. Nes. MonetDB\/X100: Hyper-Pipelining Query Execution. In Proc. Biennial Conf. on Innovative Data Systems Research, 2005."},{"issue":"2","key":"e_1_2_1_7_1","first-page":"1648","article-title":"Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct","volume":"2","author":"Boncz P. A.","year":"2009","unstructured":"P. A. Boncz, S. M., and M. L. Kersten. Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct. PVLDB, 2(2):1648--1653, 2009.","journal-title":"PVLDB"},{"key":"e_1_2_1_8_1","first-page":"746","volume-title":"Proc. Annual ACM\/IEEE Design Automation Conf.","author":"Borkar S.","year":"2007","unstructured":"S. Borkar. Thousand core chips - a technology perspective. In Proc. Annual ACM\/IEEE Design Automation Conf., pages 746--749, 2007."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767921"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61695-0_9"},{"key":"e_1_2_1_11_1","first-page":"15","volume-title":"Proc. Int'l Conf. on Very Large Data Bases","author":"Chen M.-S.","year":"1992","unstructured":"M.-S. Chen, M.-L. Lo, P. S. Yu, and H. C. Young. Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins. In Proc. Int'l Conf. on Very Large Data Bases, pages 15--26, 1992."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303760"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1140402.1140408"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191872"},{"key":"e_1_2_1_15_1","first-page":"210","volume-title":"Proc. Int'l Symp. on Computer Archiecture","author":"Davis A. L.","year":"1978","unstructured":"A. L. Davis. The Architecture and System Method of DDMI: A Recursively Structured Data Driven Machine. In Proc. Int'l Symp. on Computer Archiecture, pages 210--215, 1978."},{"key":"e_1_2_1_16_1","first-page":"137","volume-title":"Proc. USENIX Symp. on Opearting Systems Design Implementation","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. In Proc. USENIX Symp. on Opearting Systems Design Implementation, pages 137--150, 2004."},{"key":"e_1_2_1_17_1","volume-title":"A Highly Parallel Processor Using a Data Flow Machine Language. Technical report","author":"Dennis J. B.","year":"1977","unstructured":"J. B. Dennis, C. K. Leung, and D. P. Misunas. A Highly Parallel Processor Using a Data Flow Machine Language. Technical report, Massachusetts Institute of Technology, 1977."},{"key":"e_1_2_1_18_1","first-page":"228","volume-title":"Proc. Int'l Conf. on Very Large Data Bases","author":"DeWitt D. J.","year":"1986","unstructured":"D. J. DeWitt, R. H. Gerber, G. Graefe, M. L. Heytens, K. B. Kumar, and M. Muralikrishna. GAMMA - A High Performance Dataflow Database Machine. In Proc. Int'l Conf. on Very Large Data Bases, pages 228--237, 1986."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/645791.668131"},{"issue":"2","key":"e_1_2_1_20_1","first-page":"35","volume":"20","author":"Ding E.","year":"1997","unstructured":"E. Ding, L. A. Dimino, G. Gopal, and T. K. Rengarajan. Parallel Processing Capabilities of Sybase Adaptive Server Enterprise 11.5. IEEE Data Eng. Bull., 20(2):35--43, 1997.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_21_1","volume-title":"Benjamin\/Cummings","author":"Elmasri R.","year":"1989","unstructured":"R. Elmasri and S. B. Navathe. Fundamentals of Database Systems. Benjamin\/Cummings, 1989."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1982.1653942"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130291"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1980.1675474"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.273032"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66960"},{"key":"e_1_2_1_27_1","first-page":"623","volume-title":"Proc. National Computer Conf.","author":"Gurd J.","year":"1979","unstructured":"J. Gurd and I. Watson. A prototype data flow computer with token labelling. In Proc. National Computer Conf., pages 623--628, 1979."},{"key":"e_1_2_1_28_1","unstructured":"Hitachi Ltd. Hitachi's Database Product Based on Achievement of Collaborative Research by Institute of Industrial Science the University of Tokyo and Hitachi Obtains the World's First Performance Record for the Largest-Scale Class in the Industry-Standard TPC-H Database Benchmark. https:\/\/www.hitachi.com\/New\/cnews\/131021a.html 2013."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/PDIS.1991.183106"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273005"},{"issue":"2","key":"e_1_2_1_31_1","first-page":"111","volume":"16","author":"Jarke M.","year":"1984","unstructured":"M. Jarke and J. Koch. Query Optimization in Database Systems. ACM Comput. Surv., 16(2):111--152, 1984.","journal-title":"Query Optimization in Database Systems. ACM Comput. Surv."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276315"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687564"},{"issue":"1","key":"e_1_2_1_34_1","first-page":"131","article-title":"Vision and Preliminary Experiments for Out-of-Order Database Engine (OoODE) (Japanese)","volume":"8","author":"Kitsuregawa M.","year":"2009","unstructured":"M. Kitsuregawa and K. Goda. Vision and Preliminary Experiments for Out-of-Order Database Engine (OoODE) (Japanese). DBSJ Journal, 8(1):131--136, 2009.","journal-title":"DBSJ Journal"},{"key":"e_1_2_1_35_1","volume-title":"U.S. Patent 7,827,167","author":"Kitsuregawa M.","year":"2010","unstructured":"M. Kitsuregawa and K. Goda. Database Management System and Method. Japan Patent 4,611,830, U.S. Patent 7,827,167, 2010."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2010.73"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610507"},{"key":"e_1_2_1_38_1","volume-title":"Multithreaded Programming With PThreads","author":"Lewis B.","year":"1997","unstructured":"B. Lewis and D. J. Berg. Multithreaded Programming With PThreads. Prentice Hall, 1997."},{"key":"e_1_2_1_39_1","first-page":"178","volume-title":"Proc. Int'l Symp. on Cooperative Database Systems for Advanced Applications","author":"Li J.","year":"2001","unstructured":"J. Li, W. Sun, and Y. Li. Parallel Join Algorithms based on Parallel B+-trees. In Proc. Int'l Symp. on Cooperative Database Systems for Advanced Applications, pages 178--185, 2001."},{"key":"e_1_2_1_40_1","first-page":"829","volume-title":"Proc. Int'l Conf. Very Large Data Bases","author":"Liu B.","year":"2005","unstructured":"B. Liu and E. A. Rundensteiner. Revisiting Pipelined Parallelism in Multi-Join Query Processing. In Proc. Int'l Conf. Very Large Data Bases, pages 829--840, 2005."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1987816.1987832"},{"key":"e_1_2_1_42_1","volume-title":"MariaDB: One of the most popular database servers","author":"Foundation DB","year":"2009","unstructured":"MariaDB Foundation. MariaDB: One of the most popular database servers, 2009."},{"issue":"1","key":"e_1_2_1_43_1","first-page":"1","volume":"6","author":"Marr D. T.","year":"2003","unstructured":"D. T. Marr, F. Binns, D. L. Hill, G. Hinton, D. A. Koufaty, J. A. Miller, and M. Upton. Hyper-Threading Technology Architecture and Microarchitecture. Intel Technology J., 6(1):1--12, 2003.","journal-title":"Hyper-Threading Technology Architecture and Microarchitecture. Intel Technology J."},{"issue":"1","key":"e_1_2_1_44_1","first-page":"330","article-title":"Dremel","volume":"3","author":"Melnik S.","year":"2010","unstructured":"S. Melnik, A. Gubarev, J. J. Long, G. Romer, S. Shivakumar, M. Tolton, and T. Vassilakis. Dremel: Interactive Analysis of Web-scale Datasets. PVLDB, 3(1):330--339, 2010.","journal-title":"Interactive Analysis of Web-scale Datasets. PVLDB"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_2_1_46_1","volume-title":"MySQL: The world's most popular open source database","author":"Oracle Corp.","year":"2020","unstructured":"Oracle Corp. MySQL: The world's most popular open source database, 2020."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132766"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2001.914871"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915224"},{"key":"e_1_2_1_50_1","volume-title":"PostgreSQL: The world's most advanced open source relational database","author":"PostgreSQL Global Development Group","year":"2020","unstructured":"PostgreSQL Global Development Group. PostgreSQL: The world's most advanced open source relational database, 2020."},{"issue":"12","key":"e_1_2_1_51_1","first-page":"1442","volume":"8","author":"Psaroudakis I.","year":"2015","unstructured":"I. Psaroudakis, T. Scheuer, N. May, A. Sellami, and A. Ailamaki. Scaling Up Concurrent Main-memory Column-store Scans: Towards Adaptive NUMA-aware Data and Task Placement. PVLDB, 8(12):1442--1453, 2015.","journal-title":"PVLDB"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465292"},{"key":"e_1_2_1_53_1","first-page":"469","volume-title":"Proc. Int'l Conf. on Very Large Data Bases","author":"Schneider D. A.","year":"1990","unstructured":"D. A. Schneider and D.J. DeWitt. Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines. In Proc. Int'l Conf. on Very Large Data Bases, pages 469--480, 1990."},{"key":"e_1_2_1_54_1","volume-title":"Operating system concepts","author":"Silberschatz A.","year":"2013","unstructured":"A. Silberschatz, B. Galvin, and G. Gagne. Operating system concepts. Wiley, 2013."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/361020.361025"},{"key":"e_1_2_1_56_1","volume-title":"TPC-H is a Decision Support Benchmark","author":"Transaction Processing Performance Council","year":"2020","unstructured":"Transaction Processing Performance Council. TPC-H is a Decision Support Benchmark, 2020."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/641865.641867"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/27633.28055"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882904"},{"key":"e_1_2_1_60_1","first-page":"686","volume-title":"Query Parallelism: Staging and Implementation. In Proc. Int'l Conf. on Very Large Data Bases","author":"Wang Y.","year":"1995","unstructured":"Y. Wang. DB2 Query Parallelism: Staging and Implementation. In Proc. Int'l Conf. on Very Large Data Bases, pages 686--691, 1995."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/320473.320479"},{"key":"e_1_2_1_62_1","first-page":"15","volume-title":"Proc. USENIX Conf. on Networked Systems Design and Implementation","author":"Zaharia M.","year":"2012","unstructured":"M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. J. Franklin, S. Shenker, and I. Stoica. Resilient Distributed Datasets: A Fault-tolerant Abstraction for In-memory Cluster Computing. In Proc. USENIX Conf. on Networked Systems Design and Implementation, pages 15--28, 2012."},{"issue":"3","key":"e_1_2_1_63_1","first-page":"277","volume":"2","author":"Ziane M.","year":"1993","unstructured":"M. Ziane, M. Za\u00eft, and P. Borla-Salamet. Parallel Query Processing with Zigzag Trees. The VLDB Journal, 2(3):277--302, 1993.","journal-title":"Parallel Query Processing with Zigzag Trees. The VLDB Journal"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3415478.3415571","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T02:18:36Z","timestamp":1758075516000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3415478.3415571"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8]]},"references-count":63,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["10.14778\/3415478.3415571"],"URL":"https:\/\/doi.org\/10.14778\/3415478.3415571","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,8]]}}}