Out-of-order Execution of Database Queries

Summary: OoODE enables out-of-order query execution via dynamic decomposition using known parallelism, removing pre-partitioning. Experiments show 2-3x orders-of-magnitude speedup vs serial, up to 2.07x vs optimal partitioning, and 2-4x faster than DBMSs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h3bf7c0977b08899a
Venue: VLDB
Year: 2020
Pagerank: 5.0367346e-05
Overall Rank: 10,318 | 30.63%
DOI: 10.14778/3415478.3415571

Incoming Non-self Citations Over Time

Authors

1. Kazuo Goda (University of Tokyo)
2. Yuto Hayamizu (University of Tokyo)
3. Hiroyuki Yamada (University of Tokyo)
4. Masaru Kitsuregawa (National Institute of Informatics; University of Tokyo)

BibTeX Citation

@article{goda_vldb20,
        title = {{Out-of-order Execution of Database Queries}},
        author = {Goda, Kazuo and Hayamizu, Yuto and Yamada, Hiroyuki and Kitsuregawa, Masaru},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {12},
        pages = {3489--3501},
        doi = {10.14778/3415478.3415571},
        url = {https://doi.org/10.14778/3415478.3415571},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,082	Krypton: Real-time Serving and Analytical SQL Engine at ByteDance	2023	VLDB	5.3942942e-05
11,126	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.9793485e-05
11,138	anagodb: Offering Massive Parallelism for Database Engine	2025	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 23 of 23 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
14	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.00064031282
21	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00056855599
49	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.00043160717
54	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00040499302
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028981723
210	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024851502
215	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00024598661
289	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD	0.0002196543
423	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00018491327
446	Query Optimization for Parallel Execution	1992	SIGMOD	0.00018174972
476	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00017640534
535	Optimizing the Performance of a Relational Algebra Database Interface	1975	SIGMOD	0.00016789841
702	Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct	2009	VLDB	0.00014673738
920	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00013081835
1,736	Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins	1992	VLDB	9.7507905e-05
1,747	HetExchange: Encapsulating heterogeneous CPU-GPU parallelism in JIT compiled engines	2019	VLDB	9.7335416e-05
2,530	Adaptive and Big Data Scale Parallel Execution in Oracle	2013	VLDB	8.3391175e-05
2,815	GPL: A GPU-based Pipelined Query Processing Engine	2016	SIGMOD	7.9777435e-05
3,100	Micro Adaptivity in Vectorwise	2013	SIGMOD	7.6505054e-05
4,055	Scaling Up Concurrent Main-Memory Column-Store Scans: Towards Adaptive NUMA-aware Data and Task Placement	2015	VLDB	6.8270333e-05
6,288	Elastic Pipelining in an In-Memory Database Cluster	2016	SIGMOD	5.8227911e-05
6,608	Revisiting Pipelined Parallelism in Multi-Join Query Processing	2005	VLDB	5.735991e-05
7,036	DB2 Query Parallelism: Staging and Implementation	1995	VLDB	5.6159672e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	243	Automating Physical Database Design in a Parallel Database	2002	SIGMOD
2	3,775	Parallelizing Query Optimization	2008	VLDB
3	3,084	On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS	1998	SIGMOD
4	7,967	Resource Bricolage for Parallel Database Systems	2015	VLDB
5	2,168	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB
6	8,149	Parallelism and Concurrency Control Performance in Distributed Database Machines	1989	SIGMOD
7	446	Query Optimization for Parallel Execution	1992	SIGMOD
8	1,271	Managing Intra-operator Parallelism in Parallel Database Systems	1995	VLDB
9	472	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD
10	11,138	anagodb: Offering Massive Parallelism for Database Engine	2025	SIGMOD