Cardinality learning under practical constraints principled theory and empirical design Peizhi Wu

Format:

Book

Thesis/Dissertation

Author/Creator:

Wu, Peizhi, author.

Contributor:

University of Pennsylvania. Computer and Information Science., degree granting institution.

Language:

English

Subjects (All):

Computer science.

Engineering.

Information technology.

0984.

0800.

0489.

0537.

Local Subjects:

Computer science.

Engineering.

Information technology.

0984.

0800.

0489.

0537.

Genre:

Academic theses

Physical Description:

1 online resource (190 pages)

Contained In:

Dissertations Abstracts International 87-12B

Place of Publication:

Ann Arbor : ProQuest Dissertations and Theses, 2026

Language Note:

English

Summary:

Cardinality/selectivity estimation - predicting the output size of database queries - is a core component of effective query optimization and has remained one of the most important problems in database management systems (DBMSes) since the 1980s. Early approaches relied on basic statistics, such as histograms, together with uniformity and independence assumptions. Although widely adopted in real DBMSes because of their simplicity, these approaches are prone to large estimation errors. More recently, cardinality estimation has been formulated as a query-driven machine learning (ML) problem, in which the system learns from observed queries and their cardinalities to make predictions for future queries. Such methods have shown strong potential because they can better capture data correlations and skewness.Despite the potential, existing research in learned cardinality estimation has three major limitations when applying to real-world settings. First, existing approaches implicitly assume that training and test workloads are drawn from the same distribution. However, real-world workloads are rarely static; they often evolve over time. Second, due to the vast query space, it is crucial to accurately characterize the generalization ability of the models, specifically how they perform on queries that were not seen during training. Yet, there is limited theoretical analysis of the generalizability of these query-driven models. Third, existing work overlooks systematic analysis of enterprise scenarios and workloads, leaving a gap in understanding the practical constraints and challenges faced by these models in enterprise settings.For workload shifts, we propose ShiftHandler using the notion of replay buffer. ShiftHandler allows rapid adaptation and retraining of learned cardinality estimation models when facing workload shifts by learning a concise yet representative model of the workload distribution. While ShiftHandler reduces the need for extensive training queries, it still requires model retraining under workload shifts. To enable a theoretical understanding of how these models behave when testing on unseen queries without retraining, we develop a new theory of generalization for learned cardinality estimation, based on the Probably Approximately Correct (PAC) learning framework and measure theory. The new theory quantifies both the in-distribution and out-of-distribution (OOD) generalization error bounds for learned cardinality estimation models and guides the design of two strategies to improve OOD performance for these models. To understand the practical constraints of real-world enterprise settings, the dissertation then introduces the challenges of deploying learned cardinality estimation in ByteDance's cloud-native query services. First, data access may not be allowed due to privacy concerns. While query workloads can be instrumented as a less privacy-sensitive alternative, they are often imperfect - featuring incomplete and imbalanced join templates that hinder existing models. To overcome this, we propose GRASP, a data-agnostic cardinality estimation system that generalizes to unseen and imbalanced join templates without seeing the data. GRASP combines compositional model design with novel learned count sketch models, enabling robust performance under imperfect query workloads.Although GRASP learns generalizable cardinality estimates using only query workloads, cloud database users may still be reluctant to share either their data or their workloads. The dissertation therefore concludes by studying scalable foundation models for cardinality estimation. Existing work in this area largely follows a query-driven paradigm, but we argue that this is inherently inefficient: queries are far more diverse than the underlying data, and such models often still require data-derived features. The final chapter instead explores a model pretrained directly on a large corpus of tabular data without relying on synthetic queries. Once pretrained, the model aims to estimate query cardinalities - including for join queries - from schema-level signals and lightweight catalog metadata on a new database instance

Notes:

Source: Dissertations Abstracts International, Volume: 87-12, Section: B.

Advisors: Ives, Zachary G.; Marcus, Ryan Committee members: Loo, Boon Thau; Naik, Mayur; Roth, Dan; Kipf, Andreas

Ph.D. University of Pennsylvania 2026

Vendor supplied data

Local Notes:

School code: 0175

ISBN:

9798247973621

Access Restriction:

Restricted for use by site license