Hierarchical Graph Learners for Cardinality Estimation

Authors: Zixuan Yi, Sami Abu-El-Haija, Yawen Wang, Yannis Chronis, Yu Gan, Michael Burrows, Carsten Binnig, Bryan Perozzi, Fatma Ozcan
Primary area: learning on graphs and other geometries & topologies
Keywords: Cardinality Estimation, Many small models, Graph Hash, Group-by-template, Fast Learning

Abstract:
Cardinality estimation -- the task of estimating the number of records that a database query will return -- is core to performance optimization in  modern database systems. Traditional optimizers used in commercial systems use heuristics that can lead to large errors. Recently, neural network based models have been proposed that outperform the traditional optimizers. These neural network based estimators perform well if they are trained with large amounts of query samples. In this work, we observe that data warehouse workloads contain highly repetitive queries, and propose a hierarchy of localized on-line models to target these repetitive queries. At the core, these models use an extension of Merkle-Trees to hash query plans which are directed acyclic graphs. The hash values can divisively partition a large set of graphs into many sets, each containing few (whole) graphs. We learn an online model for each partition of the hierarchy. No upfront training is needed; on-line models learn as the queries are executed. When a new query comes, we check the partitions it is hashed to and if no such local model was sufficiently confident along the hierarchy, we fall-back onto a default model at the root.  Our experimental results show that not only our hierarchical on-line models perform better than the traditional optimizers, they also outperform neural models, with robust errors rates at the tail.

Decision: reject
Reviewer scores: 6, 3, 5

Reviews and discussion:
<thread>
creation date:
1730472053356

thread_type:
official_review

<thread_object>
creator: reviewer_2nam

<content>
summary:
To address the issue of repeated queries in cardinality estimation, this paper proposes an on-line cardinality estimation method. Unlike traditional cardinality estimation approaches that rely on a single model, this study introduces a hierarchical cardinality estimation framework. Queries are categorized into three levels, with different structural classifications applied at each level. For each level, distinct estimator models are trained based on various classification templates, and evaluations are conducted hierarchically. Additionally, these models utilize an extension of Merkle-Trees to hash directed acyclic graph (DAG) query plans. Finally, an ensemble learning method is used to statistically aggregate the results and produce the final cardinality estimates. Compared to traditional cardinality estimators and the query-based cost estimation method MSCN, this approach achieves superior results.

strengths:
S1. Hierarchical cardinality estimation methods have significant advantages for cardinality estimation methods in the presence of a large number of repeated queries. They allow for the training of separate cardinality estimators for each query type, thereby saving training costs and improving the accuracy of cardinality estimation.
S2. The method presented in this paper demonstrates strong cardinality estimation performance, and it also exhibits good convergence stability through hierarchical training.
S3. Compared to traditional cardinality estimators, the method proposed in this paper achieves faster convergence speed with lower overhead, making it suitable for practical industrial applications.

weaknesses:
W1. This paper employs only the Q-Error as an evaluation metric, which can assess the stability of the cardinality estimator but does not provide an intuitive measure of its accuracy. The addition of mean absolute error (MAE) and relative prediction error (RPE) would allow for a more comprehensive evaluation of the accuracy of different cardinality estimators.
W2. This paper compares only with two relatively outdated query-based cardinality estimation methods, MSCN and MSCN+. It should include a broader variety and greater number of baseline methods by introducing more advanced cardinality estimation approaches. Adding comparisons with data-driven cardinality estimation methods or experiments against paradigmatic methods like QueryFormer would enhance the analysis.
W3. The experimental workload in this paper lacks clarification regarding query redundancy. It should include comparative experiments under different workloads. Additionally, experiments on cardinality estimation with lower query redundancy should be added to provide a more comprehensive evaluation.

questions:
Q1. The addition of mean absolute error (MAE) and relative prediction error (RPE) would allow for a more comprehensive evaluation of the accuracy of different cardinality estimators.
Q2. It should include a broader variety and greater number of baseline methods by introducing more advanced cardinality estimation approaches. Adding comparisons with data-driven cardinality estimation methods or experiments against paradigmatic methods like QueryFormer would enhance the analysis.
Q3. It should include comparative experiments under different workloads. Additionally, experiments on cardinality estimation with lower query redundancy should be added to provide a more comprehensive evaluation.
Q4. Could you clarify what specific models are used at each level of cardinality estimation in this paper? This detail is not adequately explained in the manuscript.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730591520721

thread_type:
official_review

<thread_object>
creator: reviewer_5civ

<content>
summary:
The authors propose a supervised cardinality estimation method that enhances accuracy for workloads with repetitive queries (i.e., queries repeated in templates with only the constant parameters changed) by leveraging hierarchical, online localized models. This approach transforms each SQL query into a Directed Acyclic Graph (DAG) representation, groups isomorphic DAGs into the same partition, and trains an online model for each partition as queries are executed. Grouping is conducted hierarchically at multiple levels of granularity, ranging from fine-grained (i.e., queries varying only in constant terms are placed in the same partition) to coarse-grained (e.g., queries varying only in constants, operator types, and column names are placed in the same partition). During runtime, given a query, the method begins with the fine-grained model and moves to coarser-grained models until it finds a confident model for the query. If no suitable model exists, it defaults to a learned or traditional model. Using the CardBench benchmark, the authors demonstrate that this method yields more accurate cardinality estimates compared to competitors such as PostgreSQL and MSCN.

strengths:
S1. The authors tackle an important issue in analytical databases: cardinality estimation for repetitive queries.

S2. The authors propose a cardinality estimator, which leverages hierarchical localized models that are trained online.

weaknesses:
W1. The Experiments section needs to be improved.
- The authors should compare their method with state-of-the-art (SOTA) data-driven cardinality estimation methods such as [1]. Currently, the comparison is limited to MSCN, a query-driven method proposed in 2019 [2], and PostgreSQL, a traditional estimator.
- The “Imperfect Admission Experiments” in Section 4 seems unfair, as the q-error percentiles of each method are reported on different query subsets: PostgreSQL is evaluated on the entire query set, MSCN on a subset excluding disjunctions, while the proposed method seems to be evaluated on a subset of simple queries (e.g., repetitive queries varying only in constant terms).
- The authors should report end-to-end time (including both planning and query execution time), as shown in [1,3], along with its breakdown for further clarity.
- Reporting training time and model size would provide further insights into the method’s practical feasibility.
- The authors should clarify why the q-error is higher in certain intervals with larger training sample sizes in Figure 4.
- The experimental setup requires a more thorough explanation, particularly regarding how query repetitiveness was generated and its extent.


W2. Motivation is inadequate.
- The authors should explain why existing learned estimators struggle with repetitive workloads to highlight the necessity for their proposed method.
- The authors should clarify why a hierarchical model structure is effective in improving the accuracy of cardinality estimation.

W3. The presentation needs to be improved.
- The process of generating a DAG from a query needs further explanation. If the DAG refers to a query plan, the authors should specify which query plan is used, as multiple plans can exist for a single query.
- There are some undefined terms, such as d_{\psi} in Section 2.
- There are inconsistent notations throughout the paper. For instance, “query graph” and “query plan” are used interchangeably.
- Numerous typos appear throughout the paper, such as “geoping” and “hases” in Section 5.

W4. There are some misstatements regarding existing work
- The authors seem to overstate the limitations of existing methods. They claim that “NN-based estimators perform well if they are trained with large amounts of query samples,” which is true specifically for query-driven learned estimators, not all NN-based methods.
- The authors state that “50% of the real world clusters have more than 90% queries repeated in templates (only changing the constant parameters),” citing [4]. However, according to [4], the correct value is 80%, not 90%.

[1] Kim, Kyoungmin, et al. "Asm: Harmonizing autoregressive model, sampling, and multi-dimensional statistics merging for cardinality estimation." Proceedings of the ACM on Management of Data 2.1 (2024): 1-27.
[2] Kipf, Andreas, et al. “Learned cardinalities: Estimating correlated joins with deep learning.” In Biennial Conference on Innovative Data Systems Research, 2019.
[3] Wu, Ziniu, et al. "FactorJoin: a new cardinality estimation framework for join queries." Proceedings of the ACM on Management of Data 1.1 (2023): 1-27.
[4] van Renen, Alexander, et al. "Why tpc is not enough: An analysis of the amazon redshift fleet." Proceedings of the VLDB Endowment 17.11 (2024): 3694-3706.

questions:
Please refer to W1-W4.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730674654717

thread_type:
official_review

<thread_object>
creator: reviewer_3tiu

<content>
summary:
This paper proposes a workload-driven approach for cardinality estimation aiming at workloads containig repetative queries. The proposal utilizes multiple templatizer to derive hierarchical cardinality estimation models, taking a query plan tree as input and obtaining data with different granularity. It employs general predictors like PostgreSQL to perform cardinality estimation at the lowest level.

strengths:
- S1: The evaluation experiments used six types of workloads, including up to five-table join queries, and achieved a higher Q-error than MSCN (CIDR2019). It was confirmed that the fine-grained model, H1, achieved the fastest convergence in training and the highest accuracy.

- S2: Since machine learning-based methods often underperform in high-percentile cases, the fallback mechanism is beneficial in practice. As shown in Table 4, the deeper hierarchical fallback mechanism achieves a higher Q-error.

- S3: As a query-driven approach, the featurizer’s ability to characterize predicates is useful.

weaknesses:
- W1: In addition to Q-error, P-error should be also evaluated, which is becoming a standard metric.

- W2: As shown in Table 3, H1 demonstrates the highest performance, so a structure of H1 -> PostgreSQL seems optimal, making the multiple hierarchy setup (in Equation 15) unnecessary. The authors should clarify the benefit of using multiple hierarchy levels. 

- W3: Although the proposal adopts a workload-driven approach, recent trends favor data-driven or hybrid approaches. Notably, data-driven approaches have the advantage of robustness for unknown queries. Combining a workload-driven approach with data-driven methods could enhance accuracy in cases where prediction errors are large. While a workload-driven approach has the advantage of faster inference time, it is not obvious workload-driven approach alone is useful. 

- W4: In Section 2.5, the statement "All graphs whose templates are isomorphic share the same model" is based on graph isomorphism as defined in Definition 1, relying on edge information only. The templatizer, H1, thus does not use graph attribute information. However, Section 3.1 states, "Hence, query graphs found in the same H1 template differ only by the constant values," which appears contradictory.

- W5: Section 3.3 includes a calculation for the hash size, such as s(#T1), but according to Equation 6, the hash length is fixed at h, so the case distinction in Equation 10 does not seem valid.

- W6: Although Cardbench is used as the evaluation benchmark, it is proposed in an arXiv paper and is not yet a standard benchmark. It would be better to use the widely accepted join order benchmark or explain the strong justification for using Cardbench.

questions:
- It is unclear how the plan tree is constructed. For example, is it correct to interpret that (A ? B) ? C and A ? (B ? C) are non-isomorphic plans?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731994267715

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Thank you for your reviews!

comment:
Dear reviewers,


We took our time to craft the response, as your feedback pushed us to re-do our experimental setup, fix typos in paper, and discuss some more related work. We uploaded the new rebuttal PDF. We highlight significant changes in blue.

Our response here addresses common concerns. Additionally, we respond to each reviewer, often referencing this very response.

Given your feedbacks, we have done the following:

## Re-design Experiments

1. We run another data-driven baseline: DeepDB[1]. We run the code of authors of DeepDB (we only transform the input format) and show the comparisons on two datasets. DeepDB outperforms our method on **multijoin-accidents** dataset but underperforms on **multijoin-stackoverflow** dataset (numbers are at the end of this comment).
2. Remove "imperfect admission" experiments since reviewers eluded that they are not fair (each method potentially evaluated on different set of queries). Instead, we evaluate all methods on the intersection of queries they are all able to process in Table 3 of the revised PDF. This shows that: when query pattern is known, our methods outperform the baselines. This then motivates the hierarchy experiments (use our models for repetive queries) -- Table 2 of the revised PDF. In most practical scenarios, only Postgres estimator can always compute (as it can handle arbitrary queries and does not require training), that's why we use it at the root in our experiments.
3. We are now reporting two additional metrics (Absolute error and Relative error) -- Unfortunately, integration with P-Error requires more work, because it needs to invoke cardinality estimator at each subquery, and additionally invoke Postgres query-planner and cost-estimator during eval. We are working on it, and we plan to have the numbers in our final version.
4. We add the ablation study on different repetition in Fig 4 of the revised PDF.
5. We replaced experiment figure (now Fig #5 in Appendix) with ``cumulative plot'' i.e. the errors when using this-many-prior-observations-or-less (versus the old one: using this-many-observations) as the old one was noisy: at high example count, the number would come from one (or a couple) of predictions.

## Motivation

We want to emphasize that our contribution learns from queries (online) by grouping similar ones. **Our work must sit on-top** of another cardinality estimator (may it be deep net or heuristic-based). The familiar queries can be intercepted by our hierarchy and the unseen queries can fall back onto more-general estimator. Since Postgres can always process any query, and that it gives decent results [given no training!], we use it as a default fall-back. Since our method does **not** stand on its own [needs a fallback for novel templates], it is somewhat orthogonal to compare it against many baselines.

## DeepDB Comparison

We report Q-Errors (at 50th and 90th percentile) and also median absolute and relative errors, for two multijoin datasets. We train on 100,000 sample rows per table -- training takes several hours, per dataset. We are queueing runs for the remainder of the datasets, and we should have all numbers reported by camera ready (if paper gets accepted).


|               |                | Postgres | MSCN+  | DeepDB    | Ours      |
|---------------|----------------|----------|--------|-----------|-----------|
| multijoin-stackoverflow | Q-error @50    | 3.8      | 2.0    | 3.9       | **1.05**  |
|               | Q-error @90    | 149      | 10.99  | 1.9e4     | **2.19**  |
|               | Relative Error | 0.74     | 0.50   | 0.74      | **0.05**  |
|               | Absolute Error | 4.2e4    | 9.7e3  | 2.7e5     | **30.3**  |
| multijoin-accidents     | Q-Error @50    | 1.73     | 2.2    | **1.02**  | 1.09      |
|               | Q-error @90    | 11.04    | 8.31   | **1.17**  | 3.31      |
|               | Relative Error | 0.42     | 0.54   | **0.02**  | 0.08      |
|               | Absolute Error | 6.0e7    | 3.1e7  | **1.4e6** | 4.0e6     |


[1] Hilprecht, Benjamin, et al. "DeepDB: Learn from Data, not from Queries!", VLDB 2020.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a workload-driven approach for cardinality estimation for workloads containing repetitive queries. The reviewers agree the problem is important and that the hierarchical cardinality estimation methods are effective. However, there are also concerns on the motivation, related work, experiments, and presentation. While some of the comments were addressed during the discussion period, others seem to be only partially addressed with ongoing experiments. Overall, I think the paper can be improved and should go through another round of reviewing.