Efficient Sorting, Duplicate Removal, Grouping, and Aggregation

ACM Transactions on Database Systems - Tập 47 Số 4 - Trang 1-35 - 2022
Thanh Do1, Goetz Graefe2, Jeffrey F. Naughton1
1Celonis Inc., New York, NY, USA
2Google Inc., Madison, WI, USA

Tóm tắt

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 1 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. 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’s 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’s F1 Query uses the new algorithm in production workloads that aggregate petabytes of data every day.

Từ khóa


Tài liệu tham khảo

TPC. 2021. TPC-H benchmark. Retrieved from http://www.tpc.org/tpch/.

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ıgümüş. 2021. Napa: Powering scalable data warehousing with robust query performance at Google. Proc. VLDB Endow. 14, 12 (2021), 2986–2998.

10.1007/BF00288683

10.1145/319983.319987

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–76. DOI:10.1007/978-3-319-04936-6_5

10.1145/1365815.1365816

W. M. Conner. 1977. Offset-value coding. In IBM Technical Disclosure Bulletin.

10.1145/2491245

10.1145/1327452.1327492

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’03). 134–142. DOI:10.1145/773153.773167

Robert Epstein. 1979. Techniques for processing of aggregates in relational database systems. In University of California at Berkeley, UCB/ERL Memorandum M79/8.

10.1145/363067.363102

10.1145/366552.366556

10.1145/152610.152611

10.1109/69.273032

10.1145/1132960.1132964

Goetz Graefe. 2011. A generalized join algorithm. In Datenbanksysteme für Business, Technologie und Web (BTW’11), 14. Fachtagung des GI-Fachbereichs Datenbanken und Informationssysteme (DBIS’11) (LNI), Theo Härder, Wolfgang Lehner, Bernhard Mitschang, Harald Schöning, and Holger Schwarz (Eds.), Vol. P-180. GI, 267–286. https://dl.gi.de/20.500.12116/19583

10.1561/1900000028

10.1007/s00450-011-0186-9

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’98). 86–97.

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–113.

Jim Gray. 1978. Notes on database operating systems. In Operating Systems: An Advanced Course. Springer-Verlag, Berlin, 393–481.

10.1145/2936722

Theo Härder. 1977. A scan-driven sort facility for a relational database system. In Proceedings of 21st International Conference on Very Large Data Bases (VLDB’77). 236–244.

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’96). 423–434. 10.1145/233269.233359

Bala R. Iyer. 2005. Hardware assisted sorting in IBM’s DB2 DBMS. In Proceedings of the International Conference on Management of Data (COMAD’05).

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’97). 16–25.

Donald E. Knuth. 1998. The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed. Addison Wesley Longman Publishing, Boston, MA.

Robert Philip Kooi. 1980. The Optimization of Queries in Relational Databases. Ph.D. Dissertation, Case Western Reserve University, Cleveland, OH.

Ingo Müller, Peter Sanders, Arnaud Lacurie, Wolfgang Lehner, and Franz Färber. 2015. Cache-efficient aggregation: hashing is sorting. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD’15). 1123–1136. DOI:10.1145/2723372.2747644

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’04). 960–971.

10.1007/s002360050048

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’93), Rakesh Agrawal, Seán Baker, and David A. Bell (Eds.). Morgan Kaufmann, 618–629.

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’18). 1835–1848. 10.14778/3229863.3229871

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’79). 23–34. DOI:10.1145/582095.582099

10.1145/6314.6315

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’13). 1068–1079. DOI:10.14778/2536222.2536232

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’96). 57–67. DOI:10.1145/233269.233320

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’91). 68–77.

Weipeng P. Yan and Per-Åke Larson. 1995. Eager aggregation and lazy aggregation. In Proceedings of the 21st International Conference on Very Large Data Bases (VLDB’95), Umeshwar Dayal, Peter M. D. Gray, and Shojiro Nishio (Eds.). Morgan Kaufmann, 345–357. Retrieved from http://www.vldb.org/conf/1995/P345.PDF.

Thông tin
Thông tin xuất bản

ACM Transactions on Database Systems

Tập 47 Số 4

1-35

Thông tin tác giả