Cheriton students Jeremy Chen, Yuqing Huang and Mushi Wang and Professors Semih Salihoğlu and Ken Salem have received a 2022 ACM SIGMOD Research Highlight Award for their paper “Accurate summary-based cardinality estimation through the lens of cardinality estimation graphs.” No stranger to scholarly recognition, this research earlier received the Best Experiment, Analysis and Benchmark Award at VLDB 2022, the 48th International Conference on Very Large Databases, where it was presented originally.
“The SIGMOD Research Highlight Award aims to showcase a set of research projects that exemplify core database research,” wrote Wim Martens, chair of the SIGMOD award selection committee in his letter to Professor Salihoğlu. “These projects address an important problem, represent a definitive milestone in solving the problem, and have the potential of significant impact. The initiative of the SIGMOD Research Highlights also aims to make the selected works widely known in the database community, to our industry partners, and potentially to the broader ACM community.”
L to R: Ken Salem, Mushi Wang and Semih Salihoğlu. Co-authors Jeremy Chen and Yuqing Huang have graduated and were unavailable for the photo.
Ken Salem is a Professor at the Cheriton School of Computer Science and a member of the Data Systems Group. His research interests are in data systems, especially synchronization, transactions and fault tolerance, and in distributed systems and cloud computing.
Mushi Wang is a master’s candidate at the Cheriton School of Computer Science, advised by Professor Salihoğlu. His research interests are in the integration of graph neural networks into graph database management systems.
Semih Salihoğlu is an Associate Professor at the Cheriton School of Computer Science and a member of the Data Systems Group. He conducts both systems and theoretical research in data management and processing. His systems work focuses on developing systems for managing, querying, or doing analytics on graph-structured data.
Jeremy Chen is a software engineer at Snowflake. He is fascinated by distributed systems, large-scale data processing, and databases.
Yuqing Huang is currently a master’s candidate in computer science at ETH Zurich. At Waterloo, she was an undergraduate student double majoring in computer science and combinatorics and optimization.
About this award-winning research
Software applications use database management systems (DBMSs) to store and query data, often organized as tables of records. A core feature of DBMSs is to support high-level declarative query languages, which allow application developers to describe what they want to retrieve from the database, without worrying about how to retrieve it. For example, in the most widely adopted query language called SQL, the query “SELECT name FROM Employee WHERE age < 20” asks the DBMS to return the names of all employees in the employee table who are less than 20 years old, without specifying how the employee table should be searched to identify them. A DBMS can choose to compute the result of even this simple query in many ways. A key feature of DBMSs is that they automatically generate and put together programs, which are called query plans, that correctly answer such high-level queries. DBMSs do this by first finding a set of correct plans for a query, then assign each plan an estimated cost, which is expected to correlate with how long the plan would take, and then selecting the plan with the minimum cost.
The most challenging part of assigning accurate cost estimates to plans is to estimate the number of records they would process. This is called the problem of cardinality estimation. The most common techniques for cardinality estimation are summary-based techniques, which store statistics about the tables and then put these statistics together to come up with an estimate.
In their paper, the research team examined two types of summary-based cardinality estimators — optimistic estimators that make uniformity and conditional independence assumptions and can both under-estimate and over-estimate actual cardinalities, and pessimistic estimators that use information theoretic linear programs that are guaranteed to never underestimate. They showed, surprisingly, that these two classes of estimators are connected and can be seen as instantiations of a more generic estimator, called a cardinality estimation graph (CEG)-based estimator. This discovery had interesting scientific implications, e.g., that the estimates made by the linear program-based pessimistic estimators could be solved using combinatorial algorithms that solve optimistic estimators.
The paper also made an important observation about optimistic estimators. Specifically, the paper showed that when making optimistic estimates, there is often more than one way — corresponding to paths in CEGs — to put the stored statistics together and no obvious technique to decide which one is better. They outlined and empirically evaluated a space of heuristics and showed that the heuristic that leads generally to most accurate estimates depends on the structure of the query and proposed specific estimators to use different classes of queries.
“An important life lesson to draw from the story of this paper is to not give up on a good paper you love,” noted Professor Salihoğlu anecdotally. “Keep stubbornly polishing its writing and positioning. Before winning a VLDB Best Paper Award and now a SIGMOD Research Highlight Award, this paper was rejected three times from SIGMOD and VLDB. It was painful. We knew it was a very strong paper with a clear contribution, but we could not figure out the right way to position it. After three rejections, we finally got it right.”
To learn more about the award-winning research on which this article is based, please see Jeremy Chen, Yuqing Huang, Mushi Wang, Semih Salihoglu, and Ken Salem. Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs. PVLDB, 15(8): 1533–1545, 2022. doi:10.14778/3529337.3529339
