Progressive Partitioning for Parallelized Query Execution in Google’s Napa

Summary: Napa uses progressive, query-specific partitioning for skewed multi-key lookups, trading exact balance for low overhead and sub-second SLOs. B-tree key-distribution statistics support both lookup and partitioning, enabling robust service at billions of queries per day. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13368
Venue: VLDB
Year: 2023
Pagerank: 5.1664022e-05
Overall Rank: 10,059 | 30.99%
DOI: 10.14778/3611540.3611541

Incoming Non-self Citations Over Time

Authors

1. Junichi Tatemura (Google)
2. Tao Zou (Google)
3. Jagan Sankaranarayanan (Google)
4. Yanlai Huang (Google)
5. Jim Chen (Google)
6. Yupu Zhang (Google)
7. Kevin Lai (Google)
8. Hao Zhang (Google)
9. Gokul Nath Babu Manoharan (Google)
10. Goetz Graefe (Google)
11. Divyakant Agrawal (Google)
12. Brad Adelberg (Google)
13. Shilpa Kolhar (Google)
14. Indrajit Roy (Google)

BibTeX Citation

@article{tatemura_vldb23,
        title = {{Progressive Partitioning for Parallelized Query Execution in Google’s Napa}},
        author = {Tatemura, Junichi and Zou, Tao and Sankaranarayanan, Jagan and Huang, Yanlai and Chen, Jim and Zhang, Yupu and Lai, Kevin and Zhang, Hao and Manoharan, Gokul Nath Babu and Graefe, Goetz and Agrawal, Divyakant and Adelberg, Brad and Kolhar, Shilpa and Roy, Indrajit},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {12},
        pages = {3475--3487},
        doi = {10.14778/3611540.3611541},
        url = {https://doi.org/10.14778/3611540.3611541},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,355	Counting Is All You Need for Instant Tuple Discovery: Enabling Real-Time HTAP in Standalone DBMSs	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
49	Weaving Relations for Cache Performance	2001	VLDB	0.00043781096
126	Schism: a Workload-Driven Approach to Database Replication and Partitioning	2010	VLDB	0.00030779127
184	DB2 Design Advisor: Integrated Automatic Physical Database Design	2004	VLDB	0.00026256101
199	Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design	2004	SIGMOD	0.00025612088
246	Automating Physical Database Design in a Parallel Database	2002	SIGMOD	0.00023457421
259	Database Cracking	2007	CIDR	0.00023119313
471	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD	0.0001793564
652	An Overview of The System Software of A Parallel Relational Database Machine GRACE	1986	VLDB	0.00015304915
1,811	Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	9.698026e-05
1,852	Automated Partitioning Design in Parallel Database Systems	2011	SIGMOD	9.6134443e-05
2,378	The Uncracked Pieces in Database Cracking	2014	VLDB	8.6682285e-05
2,499	Learning a Partitioning Advisor for Cloud Databases	2020	SIGMOD	8.4993549e-05
2,889	F1 Query: Declarative Querying at Scale	2018	VLDB	7.9935046e-05
3,770	Design Considerations for Data-flow Database Machines	1980	SIGMOD	7.1392128e-05
3,830	Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores	2012	VLDB	7.0877801e-05
4,017	Napa: Powering Scalable Data Warehousing with Robust Query Performance at Google	2021	VLDB	6.9525581e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,410	A Holistic View of Stream Partitioning Costs	2017	VLDB
2	3,106	Skipping-oriented Partitioning for Columnar Layouts	2017	VLDB
3	3,566	Efficient Bulk Insertion into a Distributed Ordered Table	2008	SIGMOD
4	7,585	Query Centric Partitioning and Allocation for Partially Replicated Database Systems	2017	SIGMOD
5	7,090	Optimizing Queries over Partitioned Tables in MPP Systems	2014	SIGMOD
6	3,200	Locality-aware Partitioning in Parallel Database Systems	2015	SIGMOD
7	1,852	Automated Partitioning Design in Parallel Database Systems	2011	SIGMOD
8	8,091	Parallelism-Optimizing Data Placement for Faster Data-Parallel Computations	2023	VLDB
9	471	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD
10	4,017	Napa: Powering Scalable Data Warehousing with Robust Query Performance at Google	2021	VLDB