{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:19:46Z","timestamp":1773886786434,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T00:00:00Z","timestamp":1672444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>Database query processing requires algorithms for duplicate removal, grouping, and aggregation. Three algorithms exist: in-stream aggregation is most efficient by far but requires sorted input; sort-based aggregation relies on external merge sort; and hash aggregation relies on an in-memory hash table plus hash partitioning to temporary storage. Cost-based query optimization chooses which algorithm to use based on several factors, including the sort order of the input, input and output sizes, and the need for sorted output. For example, hash-based aggregation is ideal for output smaller than the available memory (e.g., Query\u00a01 of TPC-H), whereas sorting the entire input and aggregating after sorting are preferable when both aggregation input and output are large and the output needs to be sorted for a subsequent operation such as a merge join.<\/jats:p>\n          <jats:p>Unfortunately, the size information required for a sound choice is often inaccurate or unavailable during query optimization, leading to sub-optimal algorithm choices. In response, this article introduces a new algorithm for sort-based duplicate removal, grouping, and aggregation. The new algorithm always performs at least as well as both traditional hash-based and traditional sort-based algorithms. It can serve as a system\u2019s only aggregation algorithm for unsorted inputs, thus preventing erroneous algorithm choices. Furthermore, the new algorithm produces sorted output that can speed up subsequent operations. Google\u2019s F1\u00a0Query uses the new algorithm in production workloads that aggregate petabytes of data every day.<\/jats:p>","DOI":"10.1145\/3568027","type":"journal-article","created":{"date-parts":[[2022,11,10]],"date-time":"2022-11-10T09:57:09Z","timestamp":1668074229000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Efficient Sorting, Duplicate Removal, Grouping, and Aggregation"],"prefix":"10.1145","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9893-5725","authenticated-orcid":false,"given":"Thanh","family":"Do","sequence":"first","affiliation":[{"name":"Celonis Inc., New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0194-6466","authenticated-orcid":false,"given":"Goetz","family":"Graefe","sequence":"additional","affiliation":[{"name":"Google Inc., Madison, WI, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3710-8096","authenticated-orcid":false,"given":"Jeffrey","family":"Naughton","sequence":"additional","affiliation":[{"name":"Celonis Inc., New York, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,1,6]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"TPC. 2021. TPC-H benchmark. Retrieved from http:\/\/www.tpc.org\/tpch\/."},{"key":"e_1_3_2_3_2","doi-asserted-by":"crossref","first-page":"2986","DOI":"10.14778\/3476311.3476377","article-title":"Napa: Powering scalable data warehousing with robust query performance at Google","volume":"14","author":"Agiwal Ankur","year":"2021","unstructured":"Ankur Agiwal, Kevin Lai, Gokul Nath Babu Manoharan, Indrajit Roy, Jagan Sankaranarayanan, Hao Zhang, Tao Zou, Min Chen, Jim Chen, Ming Dai, Thanh Do, Haoyu Gao, Haoyan Geng, Raman Grover, Bo Huang, Yanlai Huang, Adam Li, Jianyi Liang, Tao Lin, Li Liu, Yao Liu, Xi Mao, Maya Meng, Prashant Mishra, Jay Patel, Rajesh S R, Vijayshankar Raman, Sourashis Roy, Mayank Singh Shishodia, Tianhang Sun, Justin Tang, Junichi Tatemura, Sagar Trehan, Ramkumar Vadali, Prasanna Venkatasubramanian, Joey Zhang, Kefei Zhang, Yupu Zhang, Zeleng Zhuang, Goetz Graefe, Divyakanth Agrawal, Jeff Naughton, Sujata Sunil Kosalge, and Hakan Hac\u0131g\u00fcm\u00fc\u015f. 2021. Napa: Powering scalable data warehousing with robust query performance at Google. Proc. VLDB Endow. 14, 12 (2021), 2986\u20132998.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/319983.319987"},{"key":"e_1_3_2_6_2","first-page":"61","volume-title":"Proceedings of the 5th TPC Technology Conference on Performance Characterization and Benchmarking, Volume 8391","author":"Boncz Peter","year":"2013","unstructured":"Peter Boncz, Thomas Neumann, and Orri Erling. 2013. TPC-H analyzed: Hidden messages and lessons learned from an influential benchmark. In Proceedings of the 5th TPC Technology Conference on Performance Characterization and Benchmarking, Volume 8391. Springer-Verlag, Berlin, 61\u201376. DOI:10.1007\/978-3-319-04936-6_5"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_3_2_8_2","volume-title":"IBM Technical Disclosure Bulletin","author":"Conner W. M.","year":"1977","unstructured":"W. M. Conner. 1977. Offset-value coding. In IBM Technical Disclosure Bulletin."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_11_2","first-page":"134","volume-title":"Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS\u201903)","author":"Dittrich Jens-Peter","year":"2003","unstructured":"Jens-Peter Dittrich, Bernhard Seeger, David Scot Taylor, and Peter Widmayer. 2003. On producing join results early. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS\u201903). 134\u2013142. DOI:10.1145\/773153.773167"},{"key":"e_1_3_2_12_2","volume-title":"University of California at Berkeley, UCB\/ERL Memorandum M79\/8","author":"Epstein Robert","year":"1979","unstructured":"Robert Epstein. 1979. Techniques for processing of aggregates in relational database systems. In University of California at Berkeley, UCB\/ERL Memorandum M79\/8."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/363067.363102"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/366552.366556"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/69.273032"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132960.1132964"},{"key":"e_1_3_2_18_2","first-page":"267","volume-title":"Datenbanksysteme f\u00fcr Business, Technologie und Web (BTW\u201911), 14. Fachtagung des GI-Fachbereichs Datenbanken und Informationssysteme (DBIS\u201911) (LNI)","author":"Graefe Goetz","year":"2011","unstructured":"Goetz Graefe. 2011. A generalized join algorithm. In Datenbanksysteme f\u00fcr Business, Technologie und Web (BTW\u201911), 14. Fachtagung des GI-Fachbereichs Datenbanken und Informationssysteme (DBIS\u201911) (LNI), Theo H\u00e4rder, Wolfgang Lehner, Bernhard Mitschang, Harald Sch\u00f6ning, and Holger Schwarz (Eds.), Vol. P-180. GI, 267\u2013286. https:\/\/dl.gi.de\/20.500.12116\/19583"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1561\/1900000028"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00450-011-0186-9"},{"key":"e_1_3_2_21_2","first-page":"86","volume-title":"Proceedings of 21st International Conference on Very Large Data Bases (VLDB\u201998)","author":"Graefe Goetz","year":"1998","unstructured":"Goetz Graefe, Ross Bunker, and Shaun Cooper. 1998. Hash joins and hash teams in Microsoft SQL server. In Proceedings of 21st International Conference on Very Large Data Bases (VLDB\u201998). 86\u201397."},{"issue":"2","key":"e_1_3_2_22_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-031-01857-2","article-title":"Instant recovery with write-ahead logging: Page repair, system restart, media restore, and system failover","volume":"8","author":"Graefe Goetz","year":"2016","unstructured":"Goetz Graefe, Wey Guy, and Caetano Sauer. 2016. Instant recovery with write-ahead logging: Page repair, system restart, media restore, and system failover. Synth. Lect. Data Manage. 8, 2 (2016), 1\u2013113.","journal-title":"Synth. Lect. Data Manage."},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/3-540-08755-9_9","volume-title":"Operating Systems: An Advanced Course","author":"Gray Jim","year":"1978","unstructured":"Jim Gray. 1978. Notes on database operating systems. In Operating Systems: An Advanced Course. Springer-Verlag, Berlin, 393\u2013481."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2936722"},{"key":"e_1_3_2_25_2","first-page":"236","volume-title":"Proceedings of 21st International Conference on Very Large Data Bases (VLDB\u201977)","author":"H\u00e4rder Theo","year":"1977","unstructured":"Theo H\u00e4rder. 1977. A scan-driven sort facility for a relational database system. In Proceedings of 21st International Conference on Very Large Data Bases (VLDB\u201977). 236\u2013244."},{"key":"e_1_3_2_26_2","first-page":"423","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD\u201996)","author":"Hellerstein Joseph M.","year":"1996","unstructured":"Joseph M. Hellerstein and Jeffrey F. Naughton. 1996. Query execution techniques for caching expensive methods. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD\u201996). 423\u2013434. 10.1145\/233269.233359"},{"key":"e_1_3_2_27_2","volume-title":"Proceedings of the International Conference on Management of Data (COMAD\u201905)","author":"Iyer Bala R.","year":"2005","unstructured":"Bala R. Iyer. 2005. Hardware assisted sorting in IBM\u2019s DB2 DBMS. In Proceedings of the International Conference on Management of Data (COMAD\u201905)."},{"key":"e_1_3_2_28_2","first-page":"16","volume-title":"Proceedings of 21st International Conference on Very Large Data Bases (VLDB\u201997)","author":"Jagadish H. V.","unstructured":"H. V. Jagadish, P. P. S. Narayan, S. Seshadri, S. Sudarshan, and Rama Kanneganti. Incremental organization for data recording and warehousing. In Proceedings of 21st International Conference on Very Large Data Bases (VLDB\u201997). 16\u201325."},{"key":"e_1_3_2_29_2","volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"Knuth Donald E.","year":"1998","unstructured":"Donald E. Knuth. 1998. The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed. Addison Wesley Longman Publishing, Boston, MA."},{"key":"e_1_3_2_30_2","volume-title":"The Optimization of Queries in Relational Databases","author":"Kooi Robert Philip","year":"1980","unstructured":"Robert Philip Kooi. 1980. The Optimization of Queries in Relational Databases. Ph.D. Dissertation, Case Western Reserve University, Cleveland, OH."},{"key":"e_1_3_2_31_2","doi-asserted-by":"crossref","first-page":"1123","DOI":"10.1145\/2723372.2747644","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD\u201915)","author":"M\u00fcller Ingo","year":"2015","unstructured":"Ingo M\u00fcller, Peter Sanders, Arnaud Lacurie, Wolfgang Lehner, and Franz F\u00e4rber. 2015. Cache-efficient aggregation: hashing is sorting. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD\u201915). 1123\u20131136. DOI:10.1145\/2723372.2747644"},{"key":"e_1_3_2_32_2","first-page":"960","volume-title":"Proceedings of 21st International Conference on Very Large Data Bases (VLDB\u201904)","author":"Neumann Thomas","year":"2004","unstructured":"Thomas Neumann and Guido Moerkotte. 2004. A combined framework for grouping and order optimization. In Proceedings of 21st International Conference on Very Large Data Bases (VLDB\u201904). 960\u2013971."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_3_2_34_2","first-page":"618","volume-title":"Proceedings of the 19th International Conference on Very Large Data Bases (VLDB\u201993)","author":"Pang HweeHwa","year":"1993","unstructured":"HweeHwa Pang, Michael J. Carey, and Miron Livny. 1993. Memory-adaptive external sorting. In Proceedings of the 19th International Conference on Very Large Data Bases (VLDB\u201993), Rakesh Agrawal, Se\u00e1n Baker, and David A. Bell (Eds.). Morgan Kaufmann, 618\u2013629."},{"key":"e_1_3_2_35_2","first-page":"1835","volume-title":"Proceedings of 21st International Conference on Very Large Data Bases (VLDB\u201918)","author":"Samwel Bart","year":"2018","unstructured":"Bart Samwel, John Cieslewicz, Ben Handy, Jason Govig, Petros Venetis, Chanjun Yang, Keith Peters, Jeff Shute, Daniel Tenedorio, Himani Apte, Felix Weigel, David Wilhite, Jiacheng Yang, Jun Xu, Jiexing Li, Zhan Yuan, Craig Chasseur, Qiang Zeng, Ian Rae, Anurag Biyani, Andrew Harn, Yang Xia, Andrey Gubichev, Amr El-Helw, Orri Erling, Zhepeng Yan, Mohan Yang, Yiqun Wei, Thanh Do, Colin Zheng, Goetz Graefe, Somayeh Sardashti, Ahmed M. Aly, Divy Agrawal, Ashish Gupta, and Shiv Venkataraman. 2018. F1 query: Declarative querying at scale. In Proceedings of 21st International Conference on Very Large Data Bases (VLDB\u201918). 1835\u20131848. 10.14778\/3229863.3229871"},{"key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/582095.582099","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD\u201979)","author":"Selinger P. Griffiths","year":"1979","unstructured":"P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. 1979. Access path selection in a relational database management system. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD\u201979). 23\u201334. DOI:10.1145\/582095.582099"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/6314.6315"},{"key":"e_1_3_2_38_2","first-page":"1068","volume-title":"Proceedings of 21st International Conference on Very Large Data Bases (VLDB\u201913)","author":"Shute Jeff","year":"2013","unstructured":"Jeff Shute, Radek Vingralek, Bart Samwel, Ben Handy, Chad Whipkey, Eric Rollins, Mircea Oancea, Kyle Littlefield, David Menestrina, Stephan Ellner, John Cieslewicz, Ian Rae, Traian Stancescu, and Himani Apte. 2013. F1: A distributed SQL database that scales. In Proceedings of 21st International Conference on Very Large Data Bases (VLDB\u201913). 1068\u20131079. DOI:10.14778\/2536222.2536232"},{"key":"e_1_3_2_39_2","first-page":"57","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD\u201996)","author":"Simmen David","year":"1996","unstructured":"David Simmen, Eugene Shekita, and Timothy Malkemus. 1996. Fundamental techniques for order optimization. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD\u201996). 57\u201367. DOI:10.1145\/233269.233320"},{"key":"e_1_3_2_40_2","first-page":"68","volume-title":"Proceedings of the 1st International Conference on Parallel and Distributed Information Systems (PDIS\u201991)","author":"Wilschut Annita N.","year":"1991","unstructured":"Annita N. Wilschut and Peter M. G. Apers. 1991. Dataflow query execution in a parallel main-memory environment. In Proceedings of the 1st International Conference on Parallel and Distributed Information Systems (PDIS\u201991). 68\u201377."},{"key":"e_1_3_2_41_2","first-page":"345","volume-title":"Proceedings of the 21st International Conference on Very Large Data Bases (VLDB\u201995)","author":"Yan Weipeng P.","year":"1995","unstructured":"Weipeng P. Yan and Per-\u00c5ke Larson. 1995. Eager aggregation and lazy aggregation. In Proceedings of the 21st International Conference on Very Large Data Bases (VLDB\u201995), Umeshwar Dayal, Peter M. D. Gray, and Shojiro Nishio (Eds.). Morgan Kaufmann, 345\u2013357. Retrieved from http:\/\/www.vldb.org\/conf\/1995\/P345.PDF."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3568027","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3568027","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:26:14Z","timestamp":1750281974000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3568027"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,31]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3568027"],"URL":"https:\/\/doi.org\/10.1145\/3568027","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,31]]},"assertion":[{"value":"2021-10-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-18","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}