Data-Agnostic Cardinality Learning from Imperfect Workloads

Peizhi Wu, Rong Kang, Tieying Zhang, Jianjun Chen, Ryan Marcus, Zachary G. Ives · 2025

Read Data-Agnostic Cardinality Learning from Imperfect Workloads by Peizhi Wu, Rong Kang, Tieying Zhang, Jianjun Chen, Ryan Marcus, Zachary G. Ives (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-16007.txt.

Introduction

Peizhi Wu, Rong Kang, Tieying Zhang, Jianjun Chen, Ryan Marcus, and Zachary Ives present GRASP, a tool that guesses query result sizes in two thousand twenty-five. Database engines need those guesses to plan fast queries. Rules or privacy law can bar direct access to the data, so the tool learns from past queries alone.

Real query logs are messy: join patterns are patchy and skewed, which breaks older learners. GRASP is built to stretch to join patterns it has never seen and to stay steady under skew. A per-table model handles shifts in value spread, and a sketch model catches links across tables. On three databases it beat past query-driven tools and matched data-based ones.

Catalog record

CREATORPeizhi Wu, Rong Kang, Tieying Zhang, Jianjun Chen, Ryan Marcus, Zachary G. Ives
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE78 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-16007

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Data-Agnostic Cardinality Learning from Imperfect Workloads Peizhi Wu, Rong Kang, Tieying Zhang, Jianjun Chen, Ryan Marcus, Zachary G. Ives Abstract . Cardinality estimation (CardEst) is a critical aspect of query optimization. Traditionally, it leverages statistics built directly over the data. However, organizational policies (e.g., regulatory compliance) may restrict global data access. Fortunately, query-driven cardinality estimation can learn CardEst models using query workloads. However, existing query-driven models often require access to data or summaries for best performance, and they assume perfect training workloads with complete and balanced join templates (or join graphs). Such assumptions rarely hold in real-world scenarios, in which join templates are incomplete and imbalanced. We present GRASP, a data-agnostic cardinality learning system designed to work under these real-world constraints. GRASP’s compositional design generalizes to unseen join templates and is robust to join template imbalance. It also introduces a new per-table CardEst model that handles value distribution shifts for range predicates, and a novel learned count sketch model that captures join correlations across base relations. Across three database instances, we demonstrate that GRASP consistently outperforms existing query-driven models on imperfect workloads, both in terms of estimation accuracy and query latency. Remarkably, GRASP achieves performance comparable to, or even surpassing, traditional approaches built over the underlying data on the complex CEB-IMDb-full benchmark — despite operating without any data access and using only 10% of all possible join templates. † † authors: . PVLDB Reference Format: PVLDB, 18(8): XXX-XXX, 2025. doi:XX.XX/XXX.XX † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 18, No. 8 ISSN 2150-8097. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/shoupzwu/GRASP . 1. Introduction At enterprise scale and beyond, data management and access may be compartmentalized , due to (1) organizational structure and implementation (e.g., different groups adopt incompatible database platforms or access control mechanisms), (2) limited-access agreements between groups (e.g., one organization only grants access through restricted query APIs), and/or (3) regulatory policy and the principle of least privilege (e.g., due to HIPAA or FERPA, certain data fields may be protected). In such settings, query optimization remains essential for performance, despite the fact some data is kept private 1 1 1 Note that by “privacy”, we refer to constraints on what data can be seen by other users or systems. The restrictions do not guarantee differential privacy ( dwork2006differential ) . : the organization may need to execute federated queries ( giannakouris2022building ) , provide a service that abstracts over alternative DBMS platforms ( gadepally2016bigdawg ) , or even develop query optimization-as-a-service ( jindal2022query ) . Consider our motivating use case involving two real-world scenarios at ByteDance. First, within the organization, numerous internal business units require query optimization services to enhance performance. However, these units often handle sensitive data, such as TikTok user profiles and e-commerce transactions, which are subject to strict data privacy constraints. Consequently, sharing this data across departments is restricted. Additionally, ByteDance’s cloud-native services provide query services, but many users are hesitant to allow access to their personal data. Traditional query optimization relies on cardinality estimation (CardEst) that leverages statistics built directly over base relations. A potentially promising alternative is to instrument query workloads and their cardinality results, which typically raise fewer privacy concerns than direct data access, and are often shared more readily by users with database vendors for optimizing query performance. Importantly, pairs of SQL queries and their resultant cardinalities can be collected with minimal impact on system performance. This facilitates the feasibility of developing learned query-driven CardEst models based primarily on query workloads, circumventing the need for direct access to underlying data. Recent studies ( negi2023robust ; wu2024practical ) also demonstrate that machine learning (ML)-based query-driven approaches, which learn a regression model that predicts the cardinality for an input query, have the potential to consistently outperform traditional histogram-based methods. This is because traditional methods make assumptions like independence and uniformity of data distributions, whereas learning-based techniques can model data correlations and skewness. These lessons motivate us to adopt query-driven CardEst techniques, which do not access the underlying data while enhancing estimation accuracy. Limitations of existing approaches. However, it is challenging to apply existing ML-based query-driven CardEst methods to our real-world settings for three main reasons . First, most of them ( kipf2019learned ; dutt2020efficiently ) are not purely query-driven as they still require data-derived metadata ( e.g., samples and histogram estimates) for better generalization performance. Table 1 . Problem settings for query-driven cardinality estimation in the literature versus production environments. Problem Data Coverage of Distribution of Distribution of Setting Access Join Templates Join Templates Predicate Values in the literature Yes Complete Balanced Static in production No Incomplete Imbalanced Shifting A B A\Join B A B A\Join B LW-NN: Separate Model for Each A B A\Join B One Model For All MSCN: One Model for All A B A A\Join B B A B GRASP : Compositional Model Design Join template CardEst model LCS model Figure 1 . Join handling in existing query-driven methods Second, they assume perfect training workloads in which the join templates ( i.e., join graphs that connect base tables 2 2 2 Join templates and join graphs are interchangeable throughout this paper. ) are complete and balanced. As demonstrated in § 2.2 , these assumptions may not hold in real-world environments. Specifically, apart from data inaccessibility, as shown in Table 1 , production workloads are inherently imperfect , characterized by incomplete and imbalanced join templates . This issue is especially problematic in business workloads, which may introduce new join templates over time (Figure 2(c) ). Even if join templates remain constant, for a query from seen join templates, cost models must estimate cardinalities for all possible subqueries --- including those with join templates not seen in the workload 3 3 3 In real-world workloads, such as those collected at Bytedance, we only observe the ultimate cardinality of each query without access to the cardinalities of its subqueries. — to make accurate cost predictions. Unfortunately, existing query-driven models suffer in these scenarios. Specifically, for join template incompleteness , as shown in Figure 1 , they handle joins by either encoding each join in the query encoding individually ( kipf2019learned ) or by training separate models for each join template ( dutt2020efficiently ) . However, neither approach generalizes well to unseen join templates. While join bitmaps ( negi2023robust ) improve their generalizability to unseen join templates, constructing join bitmaps requires data access. Furthermore, for join template imbalance , the lack of consistency across join templates in existing methods means that knowledge learned from the “majority” join templates (with more training queries) cannot be transferred to the “minority” join templates (with very few training queries). Third, even for the same query templates (with fixed join graph and queried columns), production workloads often experience shifts (Figure 2(d) ) in value/literal distributions (aka., value distribution shifts ). However, existing query-driven approaches rely heavily on data information (

Read the complete text