Hierarchical Graph Learners for Cardinality Estimation
Cardinality Estimation;Many small models;Graph Hash;Group-by-template;Fast Learning
Yes
No ethics review needed.
- 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?
- 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.
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.
- 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.
Yes
No ethics review needed.
Please refer to W1-W4.
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.
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.
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.
Yes
NA
No ethics review needed.
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.
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.
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.
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.
Given many labeled graphs, each representing database query, where graph label is cardinality, we group graphs by graph-structure and learn simple model per group (within group, feature dimension is constant).
@inproceedings{
anonymous2024hierarchical,
title={Hierarchical Graph Learners for Cardinality Estimation},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=0zmHFyZwkA},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Cardinality Estimation Many small models Graph Hash Group-by-template Fast Learning
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/a797ce27036a1f3593a57a960711d98c47e24fbc.pdf
learning on graphs and other geometries & topologies
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Hierarchical Graph Learners for Cardinality Estimation
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission