III: Small: Pessimistic Cardinality Estimation using Information Theory

Modern computer programs often use a large amount of resources and energy. Before running a complex program it is important to anticipate how many resources the program needs, to best provision these resources in order to avoid any waste, while at the same time ensuring that the program executes successfully. Database management systems often have multiple alternatives ways available on how to run a program, and the system needs to choose that alternative that uses the small amount of resources. This project develops novel techniques for estimating the amount of data produced by a program, which in turn can be used either to provision how many resources the program needs, or to chose between alternative ways to execute the program. The project develops a cardinality estimation system, which is "pessimistic", in the sense that it offers a one-sided theoretical guarantee that output cardinality of a query will never exceed that estimate. To compute this estimate, the project builds on information theory and computes a tight upper bound on the output cardinality. The estimate is computed from simple statistics on the input data, which can be collected offline, and which are already available in many current systems, such as cardinalities of base tables, number of distinct values in various columns, maximum degrees, or Lp-norms of degree sequences for various values of p. During the offline phase, the system can further refine these statistics by dividing the input data into buckets, then computing these statistics separately in each bucket, similar to how histograms are computed today by database management systems. What is novel about this project is that it uses all available statistics and computes an upper bound on the output size of a query, which is guaranteed to be the tightest upper bound possible given these statistics. The project studies new efficient ways to compute this bound, explores the potential use of Lp-sketches for computing the statistics offline and maintaining them incrementally, and extends the framework to group-by queries, for which traditional cardinality estimation methods are known to perform very poorly. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.