{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T02:51:22Z","timestamp":1774320682492,"version":"3.50.1"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p>Napa holds Google's critical data warehouses in log-structured merge trees for real-time data ingestion and sub-second response for billions of queries per day. These queries are often multi-key look-ups in highly skewed tables and indexes.<\/jats:p>\n          <jats:p>In our production experience, only progressive query-specific partitioning can achieve Napa's strict query latency SLOs. Here we advocate good-enough partitioning that keeps the per-query partitioning time low without risking uneven work distribution. Our design combines pragmatic system choices and algorithmic innovations. For instance, B-trees are augmented with statistics of key distributions, thus serving the dual purpose of aiding lookups and partitioning. Furthermore, progressive partitioning is designed to be \"good enough\" thereby balancing partitioning time with performance. The resulting system is robust and successfully serves day-in-day-out billions of queries with very high quality of service forming a core infrastructure at Google.<\/jats:p>","DOI":"10.14778\/3611540.3611541","type":"journal-article","created":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T11:32:37Z","timestamp":1694777557000},"page":"3475-3487","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Progressive Partitioning for Parallelized Query Execution in Google's Napa"],"prefix":"10.14778","volume":"16","author":[{"given":"Junichi","family":"Tatemura","sequence":"first","affiliation":[{"name":"Google Inc"}]},{"given":"Tao","family":"Zou","sequence":"additional","affiliation":[{"name":"Google Inc"}]},{"given":"Jagan","family":"Sankaranarayanan","sequence":"additional","affiliation":[{"name":"Google Inc"}]},{"given":"Yanlai","family":"Huang","sequence":"additional","affiliation":[{"name":"Google Inc"}]},{"given":"Jim","family":"Chen","sequence":"additional","affiliation":[{"name":"Google Inc"}]},{"given":"Yupu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Google Inc"}]},{"given":"Kevin","family":"Lai","sequence":"additional","affiliation":[{"name":"Google Inc"}]},{"given":"Hao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Google Inc"}]},{"given":"Gokul Nath Babu","family":"Manoharan","sequence":"additional","affiliation":[{"name":"Google Inc"}]},{"given":"Goetz","family":"Graefe","sequence":"additional","affiliation":[{"name":"Google Inc"}]},{"given":"Divyakant","family":"Agrawal","sequence":"additional","affiliation":[{"name":"Google Inc"}]},{"given":"Brad","family":"Adelberg","sequence":"additional","affiliation":[{"name":"Google Inc"}]},{"given":"Shilpa","family":"Kolhar","sequence":"additional","affiliation":[{"name":"Google Inc"}]},{"given":"Indrajit","family":"Roy","sequence":"additional","affiliation":[{"name":"Google Inc"}]}],"member":"320","published-online":{"date-parts":[[2023,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"S. Agrawal V. R. Narasayya and B. Yang. 2004. Integrating Vertical and Horizontal Partitioning Into Automated Physical Database Design. In SIGMOD (Paris France). 359--370.","DOI":"10.1145\/1007568.1007609"},{"key":"e_1_2_1_2_1","unstructured":"A. Ailamaki D. J. DeWitt M. D. Hill and M. Skounakis. 2001. Weaving Relations for Cache Performance. In VLDB (Rome Italy). 169--180."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/319989.319991"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"H. Boral and D. J. DeWitt. 1980. Design Considerations for Data-flow Database Machines. In SIGMOD (Santa Monica CA). 94--104.","DOI":"10.1145\/582250.582266"},{"key":"e_1_2_1_5_1","first-page":"8","article-title":"Spanner: Google's Globally Distributed Database","volume":"31","author":"J. C.","year":"2013","unstructured":"J. C. Corbett et. al. 2013. Spanner: Google's Globally Distributed Database. ACM Trans. Comput. Syst. 31, 3 (2013), 8.","journal-title":"ACM Trans. Comput. Syst."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920853"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"J. Dean. 2010. Evolution and Future Directions of Large-scale Storage and Computation Systems at Google. https:\/\/research.google.com\/people\/jeff\/SOCC2010-keynote.html","DOI":"10.1145\/1807128.1807130"},{"key":"e_1_2_1_8_1","unstructured":"J. Dean and S. Ghemawat. 2004. MapReduce: Simplified Data Processing on Large Clusters. In OSDI (San Francisco CA). 137--150."},{"key":"e_1_2_1_9_1","volume-title":"Napa: Powering scalable data warehousing with robust query performance at Google. PVLDB 14 (07","author":"A.","year":"2021","unstructured":"A. Agiwal et. al. 2021. Napa: Powering scalable data warehousing with robust query performance at Google. PVLDB 14 (07 2021), 2986--2997."},{"key":"e_1_2_1_10_1","first-page":"1835","article-title":"F1 Query: Declarative Querying at Scale","volume":"11","author":"B.","year":"2018","unstructured":"B. Samwel et. al. 2018. F1 Query: Declarative Querying at Scale. PVLDB 11, 12 (2018), 1835--1848.","journal-title":"PVLDB"},{"key":"e_1_2_1_11_1","unstructured":"S. Fushimi M. Kitsuregawa and H. Tanaka. 1986. An Overview of The System Software of A Parallel Relational Database Machine GRACE. In VLDB (Kyoto Japan). 209--219."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"F. Halim S. Idreos P. Karras and R. Yap. 2012. Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores. PVLDB 5 (02 2012) 502--513.","DOI":"10.14778\/2168651.2168652"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"B. Hilprecht C. Binnig and U. R\u00f6hm. 2020. Learning a Partitioning Advisor for Cloud Databases. In SIGMOD (Portland OR USA). 143--157.","DOI":"10.1145\/3318464.3389704"},{"key":"e_1_2_1_14_1","volume-title":"Database Cracking. In CIDR 2007","author":"Idreos S.","unstructured":"S. Idreos, M. Kersten, and S. Manegold. 2007. Database Cracking. In CIDR 2007 (Asilomar, CA). 68--78."},{"key":"e_1_2_1_15_1","volume-title":"Merged: Adaptive Inexing in Main-Memory Column-Stores. PVLDB 4 (06","author":"Idreos S.","year":"2011","unstructured":"S. Idreos, S. Manegold, H. Kuno, and G. Graefe. 2011. Merging What's Cracked, Cracking What\u015b Merged: Adaptive Inexing in Main-Memory Column-Stores. PVLDB 4 (06 2011), 585--597."},{"key":"e_1_2_1_16_1","first-page":"1","article-title":"LSM-Based Storage Techniques: A Survey","volume":"29","author":"Luo C.","year":"2019","unstructured":"C. Luo and M. J. Carey. 2019. LSM-Based Storage Techniques: A Survey. The VLDB Journal 29, 1 (jul 2019), 393--418.","journal-title":"The VLDB Journal"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"R. V. Nehme and N. Bruno. 2011. Automated partitioning design in parallel database systems. In SIGMOD (Athens Greece). 1137--1148.","DOI":"10.1145\/1989323.1989444"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"A. Pavlo C. Curino and S. B. Zdonik. 2012. Skew-aware automatic database partitioning in shared-nothing parallel OLTP systems. In SIGMOD (Scottsdale AZ). 61--72.","DOI":"10.1145\/2213836.2213844"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452427"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"J. Rao C. Zhang N. Megiddo and G. Lohman. 2002. Automating physical database design in a parallel database. In SIGMOD. 558--569.","DOI":"10.1145\/564691.564757"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"F. Schuhknecht A. Jindal and J. Dittrich. 2013. The Uncracked Pieces in Database Cracking. PVLDB 7 (10 2013) 97--108.","DOI":"10.14778\/2732228.2732229"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"F. Schuhknecht A. Jindal and J. Dittrich. 2015. An experimental evaluation and analysis of Database Cracking. The VLDB Journal 25 (08 2015) 27--52.","DOI":"10.1007\/s00778-015-0397-y"},{"key":"e_1_2_1_24_1","volume-title":"ACM Symposium on Cloud Computing. 229--241","author":"Shanbhag A.","unstructured":"A. Shanbhag, A. Jindal, S. Madden, J. Quian\u00e9-Ruiz, and A. Elmore. 2017. A robust partitioning scheme for ad-hoc query workloads. In ACM Symposium on Cloud Computing. 229--241."},{"key":"e_1_2_1_25_1","volume-title":"Design Advisor: Integrated Automatic Physical Database Design. In VLDB (Toronto, Canada). 1087--1097.","author":"Zilio D. C.","year":"2004","unstructured":"D. C. Zilio, J. Rao, S. Lightstone, G. M. Lohman, A. J. Storm, C. Garcia-Arellano, and S. Fadden. 2004. DB2 Design Advisor: Integrated Automatic Physical Database Design. In VLDB (Toronto, Canada). 1087--1097."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3611540.3611541","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:37:41Z","timestamp":1757543861000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3611540.3611541"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":25,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["10.14778\/3611540.3611541"],"URL":"https:\/\/doi.org\/10.14778\/3611540.3611541","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,8]]},"assertion":[{"value":"2023-08-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}