Jeffrey F. Naughton
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Interests
Jeffrey F. Naughton has a total of 27 co-authors. Here are the top co-authors by number of shared publications:
- Anja Gruenheid
Microsoft Gray Systems Lab, Madison, USA
1 shared publication Biswadeep Nag
Computer Sciences Department, University of Wisconsin-Madison
1 shared publication- Chander Kant
NIT Agartala Tripura
1 shared publication Curt Ellmann
Computer Sciences Department, University of Wisconsin-Madison
1 shared publicationDavid De Witt
Computer Sciences Department, University of Wisconsin-Madison
1 shared publication- David J. DeWitt
MIT CSAIL, Cambridge, MA, USA
1 shared publication
Latest Publications
- Open Access
- 31 December 2022
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 47 (4) , 1-35
Efficient Sorting, Duplicate Removal, Grouping, and Aggregation
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.
- 31 December 2022
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 47 (4) , 1-35
Open AccessEfficient Sorting, Duplicate Removal, Grouping, and Aggregation
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.
- 17 November 2022
- Published by Springer Nature in Datenbank-Spektrum
- Vol. 22 (3) , 249-256
Comprehensive and Efficient Workload Summarization
- 17 November 2022
- Published by Springer Nature in Datenbank-Spektrum
- Vol. 22 (3) , 249-256
Comprehensive and Efficient Workload Summarization
- Open Access
- 2 June 2016
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 45 (1) , 23
Technical Perspective
- 2 June 2016
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 45 (1) , 23
Open AccessTechnical Perspective
- Open Access
- 17 June 2004
- Published by Association for Computing Machinery (ACM)
- p. 49-54
Unraveling the duplicate-elimination problem in XML-to-SQL query translation
- 17 June 2004
- Published by Association for Computing Machinery (ACM)
- p. 49-54
Open AccessUnraveling the duplicate-elimination problem in XML-to-SQL query translation
- Open Access
- 1 June 1997
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 26 (2) , 336-347
Building a scaleable geo-spatial DBMS
This paper presents a number of new techniques for parallelizing geo-spatial database systems and discusses their implementation in the Paradise object-relational database system. The effectiveness of these techniques is demonstrated using a variety of complex geo-spatial queries over a 120 GB global geo-spatial data set.
- 1 June 1997
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 26 (2) , 336-347
Open AccessBuilding a scaleable geo-spatial DBMS
This paper presents a number of new techniques for parallelizing geo-spatial database systems and discusses their implementation in the Paradise object-relational database system. The effectiveness of these techniques is demonstrated using a variety of complex geo-spatial queries over a 120 GB global geo-spatial data set.
- Open Access
- 1 October 1994
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 29 (10) , 414-426
A status report on the OO7 OODBMS benchmarking effort
The OO7 Benchmark was first published in 1993, and has since found a home in the marketing literature of various object-oriented database management system (OODBMS) vendors. The OO7 Benchmark (as published) was the initial result of an ongoing OODBMS performance evaluation effort at the University of Wisconsin. This paper provides an update on the status of the effort on two fronts: single-user and multi-user. On the single-user front, we review and critique the design of the initial OO7 Benchmark. We discuss some of its faults, the reasons for those faults, and things that might be done to correct them. On the multi-user front, we describe our current work on the development of a multi-user benchmark for OODBMSs. This effort includes changes and extensions to the OO7 database and the design of a family of interesting multi-user workloads.
- 1 October 1994
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 29 (10) , 414-426
Open AccessA status report on the OO7 OODBMS benchmarking effort
The OO7 Benchmark was first published in 1993, and has since found a home in the marketing literature of various object-oriented database management system (OODBMS) vendors. The OO7 Benchmark (as published) was the initial result of an ongoing OODBMS performance evaluation effort at the University of Wisconsin. This paper provides an update on the status of the effort on two fronts: single-user and multi-user. On the single-user front, we review and critique the design of the initial OO7 Benchmark. We discuss some of its faults, the reasons for those faults, and things that might be done to correct them. On the multi-user front, we describe our current work on the development of a multi-user benchmark for OODBMSs. This effort includes changes and extensions to the OO7 database and the design of a family of interesting multi-user workloads.
- 1 March 1993
- Published by Springer Nature in Algorithmica
- Vol. 9 (3) , 239-252
Clocked adversaries for hashing
- 1 March 1993
- Published by Springer Nature in Algorithmica
- Vol. 9 (3) , 239-252
Clocked adversaries for hashing
- Open Access
- 1 April 1991
- Published by Association for Computing Machinery (ACM)
- p. 268-279
On the expected size of recursive Datalog queries
- 1 April 1991
- Published by Association for Computing Machinery (ACM)
- p. 268-279
Open AccessOn the expected size of recursive Datalog queries