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: hd12bd9aaaf3cd06f
Venue: VLDB
Year: 2023
Pagerank: 5.1402577e-05
Overall Rank: 9,689 | 34.88%
DOI: 10.14778/3611540.3611541
PDF: Download (CC BY-NC-ND 4.0)

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 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,567	Counting Is All You Need for Instant Tuple Discovery: Enabling Real-Time HTAP in Standalone DBMSs	2026	SIGMOD	4.9769913e-05
10,939	Seron: Smart Query Router for Multi-Primary Cloud-Native Databases with Shared Storage	2026	VLDB	4.9769913e-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
48	Weaving Relations for Cache Performance	2001	VLDB	0.00043795812
123	Schism: a Workload-Driven Approach to Database Replication and Partitioning	2010	VLDB	0.00030749898
187	DB2 Design Advisor: Integrated Automatic Physical Database Design	2004	VLDB	0.00025914764
195	Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design	2004	SIGMOD	0.00025619089
243	Automating Physical Database Design in a Parallel Database	2002	SIGMOD	0.00023349603
252	Database Cracking	2007	CIDR	0.00023101361
473	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD	0.00017684278
657	An Overview of The System Software of A Parallel Relational Database Machine GRACE	1986	VLDB	0.0001506334
1,837	Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	9.5315292e-05
1,884	Automated Partitioning Design in Parallel Database Systems	2011	SIGMOD	9.4349703e-05
2,384	The Uncracked Pieces in Database Cracking	2014	VLDB	8.5401256e-05
2,476	Learning a Partitioning Advisor for Cloud Databases	2020	SIGMOD	8.407183e-05
2,916	F1 Query: Declarative Querying at Scale	2018	VLDB	7.8581972e-05
3,838	Design Considerations for Data-flow Database Machines	1980	SIGMOD	6.9898164e-05
3,879	Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores	2012	VLDB	6.9481594e-05
4,107	Napa: Powering Scalable Data Warehousing with Robust Query Performance at Google	2021	VLDB	6.8020956e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,488	A Partitioning Framework for Aggressive Data Skipping	2014	VLDB
2	3,083	Skipping-oriented Partitioning for Columnar Layouts	2017	VLDB
3	3,641	Efficient Bulk Insertion into a Distributed Ordered Table	2008	SIGMOD
4	7,712	Query Centric Partitioning and Allocation for Partially Replicated Database Systems	2017	SIGMOD
5	7,202	Optimizing Queries over Partitioned Tables in MPP Systems	2014	SIGMOD
6	3,241	Locality-aware Partitioning in Parallel Database Systems	2015	SIGMOD
7	1,884	Automated Partitioning Design in Parallel Database Systems	2011	SIGMOD
8	7,360	Parallelism-Optimizing Data Placement for Faster Data-Parallel Computations	2023	VLDB
9	473	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD
10	4,107	Napa: Powering Scalable Data Warehousing with Robust Query Performance at Google	2021	VLDB