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: 12419
Venue: VLDB
Year: 2020
Pagerank: 5.1523392e-05
Overall Rank: 10,096 | 30.74%
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
7,915	Krypton: Real-time Serving and Analytical SQL Engine at ByteDance	2023	VLDB	5.5181056e-05
10,690	Dynamic Pruning for Recursive Joins	2025	SIGMOD	5.093636e-05
10,704	anagodb: Offering Massive Parallelism for Database Engine	2025	SIGMOD	5.093636e-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.0006312782
23	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00054886415
51	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.0004291425
52	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00041107291
151	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00029161879
209	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024932174
241	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00023654664
289	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD	0.00022278876
423	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00018725853
434	Query Optimization for Parallel Execution	1992	SIGMOD	0.00018531826
474	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00017894953
519	Optimizing the Performance of a Relational Algebra Database Interface	1975	SIGMOD	0.00017144967
721	Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct	2009	VLDB	0.00014631814
904	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00013319798
1,720	Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins	1992	VLDB	9.9265634e-05
1,977	HetExchange: Encapsulating heterogeneous CPU-GPU parallelism in JIT compiled engines	2019	VLDB	9.3641101e-05
2,664	Adaptive and Big Data Scale Parallel Execution in Oracle	2013	VLDB	8.2816537e-05
2,848	GPL: A GPU-based Pipelined Query Processing Engine	2016	SIGMOD	8.0538815e-05
3,195	Micro Adaptivity in Vectorwise	2013	SIGMOD	7.6481177e-05
4,001	Scaling Up Concurrent Main-Memory Column-Store Scans: Towards Adaptive NUMA-aware Data and Task Placement	2015	VLDB	6.9663191e-05
6,255	Elastic Pipelining in an In-Memory Database Cluster	2016	SIGMOD	5.9399698e-05
6,515	Revisiting Pipelined Parallelism in Multi-Join Query Processing	2005	VLDB	5.8550491e-05
6,898	DB2 Query Parallelism: Staging and Implementation	1995	VLDB	5.7440021e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	246	Automating Physical Database Design in a Parallel Database	2002	SIGMOD
2	3,726	Parallelizing Query Optimization	2008	VLDB
3	3,036	On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS	1998	SIGMOD
4	7,822	Resource Bricolage for Parallel Database Systems	2015	VLDB
5	2,131	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB
6	7,984	Parallelism and Concurrency Control Performance in Distributed Database Machines	1989	SIGMOD
7	434	Query Optimization for Parallel Execution	1992	SIGMOD
8	1,291	Managing Intra-operator Parallelism in Parallel Database Systems	1995	VLDB
9	471	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD
10	10,704	anagodb: Offering Massive Parallelism for Database Engine	2025	SIGMOD