Hierarchical Graph Learners for Cardinality Estimation

W1+Q1: We added Absolute Error and Relative Error in Table 2 and Table 3. We added absolute error and relative error to the paper (see metrics, at start of Section 4, and also experiment Tables 2 and 3) -- thanks a ton! Indeed, this makes the experiments more thorough.

W2+Q2: We are adding DeepDB instead of QueryFormer (see results on top), as it is data-driven approach and complimentary to MSCN. Nonetheless, as discussed in Motivation in main comment to all reviewers (above), we think it is orthogonal to our method to compare it with baselines as our method needs a baseline, at the root node, to fall back on, for novel queries.

W3+Q3: We improved the wording in the paper. Real workloads (e.g., per Redshift paper) have repetitions in query patterns. Nonetheless, your proposed experiments makes absolute sense.

We add more details in Datasets of the experiments section and ablation studies. Our difference from the Cardbench dataset is that we modified the workload generator to allow the query predicates have more constants to choose from. All multijoin datasets we created fixed the constant sample size at 10, resulting in a repetition rate near 90% (the number reported in the Redshift paper). Additionally, we have conducted a small sweep on the sample size (ie. [1, 3, 10]) for multijoin-stackoverflow. See Fig 4 in the ablation studies. It shows that accuracy generally improves when we introduce more repetition rate. And even when the repetition rate is low, our history-based learner still shows promising results.

Q4: In the ablation studies section, we showed results on different models. We found that Gradient-Boosted Decision Trees (GBDT) are consistently strong and used this type of model at each level of the hierachy.

W1

• We are adding baseline based on reviews. We went with data-driven-approach DeepDB. However, we added [1] to the related work section.

• Unfairness of eval: Due to this, we re-designed our experimental setup, as discussed in the common Comment above.

• We plan to add P-error (we already started working on it!) which gives some quantification of the improvement of the end-to-end time.

• The time for our methods to run: Pop-out features from query graph, hash it, lookup model and run it, is fast -- each feature pop + graph hash averages 2.3 milliseconds. Each inference step involves 3 hashes (one per templatization strategy) [i.e., total hash time, per graph = 7 milliseconds on avg]. The inference time is negligable (e.g., microseconds) and the cost to train is model-dependent. For example, we can train 15000 linear regression models in under 5 seconds -- thanks to fast implementation of numpy pinv. For decision forests, we use xgboost -- it takes around half-a-second to do training (slow!). However, we will be moving to TensorFlow Decision Forests (TFDF) as we heard they are orders of magnitude faster. We will have the exact time numbers onto the main paper, by the paper camera ready (if paper gets accepted), as we would like to invoke the fingerprint in C++ to yield further advantages, and also test the speed of TFDF. This speed makes us name our method as "online".

• Fig4: now moved to appendix and became Fig 5. We improved it. It used to be: Q-error percentile (at y-axis) measured at history size equal to x-axis. That plot was very noisy. For instance, for large history size (e.g., >100), there may be one (or a couple of) template(s) with that many and therefore the Q-error estimate would come from one (or a couple of) observation(s). Now it became a cumulative plot: it measures q-error for the amount of history up-to the x-axis value (e.g., Curve(10) = Q-error when there are <= 10 examples). Curve looks less noisy. However, for coarser templatization, it does not clearly converge with more observations (due to multimodality e.g. query predicate on different columns can group to same bucket) -- Thanks for the constructive feedback.

• We now offer more details in Experiment Datasets section and Repetition Rate section in Ablation Studies. In short, we modified the workload generator to allow the query predicates have more constants to choose from. In this way, the repetition rate is close to 90% across different datasets (ie. the repetition rate number reported in [4]). We also show in the ablation studies section that the accuracy generally improve when we introduce more repetition.

W2

• We added it in the main response.

• Importantly, our online learning setup avoids the need for a complex training data pipeline, which is the biggest barrier for practical ML-based cardinality estimation techniques. While NN models, whether workload-driven or data-driven, often perform well, they can still produce significant errors (q-errors > 3), which can have severe consequences. By focusing on frequently occurring query patterns, we can significantly reduce their q-error to below 2.

W3

• We use a logical query plan to create the query graph (or DAG). We used CardBench to generate the logical query plans, which does not apply any transformations to the query plan, but our methods would work with any optimizer. For the same exact SQL string we will produce the same logical query plan. A join (B join C) and (A join B) join C will be result in two different logical query plans, and hence will not produce the same DAG. However, your review (and another reviewer) is making us think about canonicalizing the graph (e.g., making super node that absorbs all join nodes). Nonetheless, as-is, our method has some false negatives (i.e., one equivalent query might be partitioned onto multiple graphs), and this could be hurting the performance. In the final version, we will either fix this in code or mention it in the paper (we will try to go for fixing the implementation, first).

• We added text (in blue): where $d_{\psi} \in \mathbb{Z}_+$ is dimensionality of extracted feature -- thank you.

• We now consistently use "query graph" -- thank you! We feel this is better aligned with ICLR audience. However, if this paper gets rejected, we will consider renaming to "query plan" then submit to database venue (especially that DB folks we talk to, are all thrilled by this work).

• We fixed a lot of typos. We will give the paper more thorough reads, before we post it anywhere (e.g., camera ready or arxiv). Thank you!!

W4

• We now compare with data-driven neural methods. It seems that we outperform in one case and they outperform in another (for 2 datasets). However, training takes hours (using code open-sourced by authors of DeepDB).

• We acknowledge that [4] reports that "50% of database clusters have 80% of queries as 1-to-1 repetitions." However, this statistic refers to exact query repetition, where the entire query string is identical to a previous query. In our work, we focus on a broader notion of query repetition, leveraging query templates. As highlighted in Figure 5(c) of [4], 50% of clusters exhibit more than 90% query repetition within templates over a one-week period. This indicates a high degree of structural similarity among queries, even if they differ in parameter values.

• W1: We looked into P-error. It quantifies the impact of cardinality estimation on the real metric (cost of query execution). However, its implementation requires some time. It seems we have to invoke Postgres query-planner twice, once using cardinality hints (of subgraphs) from a model, and once again feeding the ground-truth, giving two plans $P(C^E)$ and $P(C^T)$. We should then run Postgres query plan cost-estimator twice, once on $(P(C^E), C^T)$ and another on $(P(C^T), C^T)$ and compute the ratio of the two -- crucially feeding ground-truth cardinalities $C^T$ to both cost-estimator invocations. This makes sense, as it shows the bottom-line metric, i.e., quantifying the slowness introduced by inaccurate cardinality estimates, as compared to the optimal [achievable by the query-planner].

Implementing P-error implies we have to integrate with the (1) Postgres query-planner and plan cost-estimator and (2) annotate cardinalities at subqueries (as you mention, this can be retrieved during execution, and our online learner can absorb that info). Alternatively, we can integrate with https://github.com/Nathaniel-Han/End-to-End-CardEst-Benchmark which we found upon searching per your review. We will do our best to implement this by the camera read deadline, as it can greatly improve our paper.

• W2: While $H_1$ are indeed the best hierarchy, it only captures 45%-75% of the queries [as many queries differ only in their constant parameter value] and $H_2$, $H_3$, ..., are designed to capture the remaining ones [e.g., query on same table though different column predicate], as much as possible, though we cannot capture more than 26% with any $H_i$ on the datasets.

In addition to the experiments comparing $H_1 \rightarrow H_2 \rightarrow H_3 \rightarrow Postgres$ VS $H_2 \rightarrow H_3 \rightarrow P$ VS $H_3 \rightarrow P$, we have additional experiments now also comparing $H_1 \rightarrow P$, $H_1 \rightarrow H_2 \rightarrow P$. Generally, $H_1 \rightarrow H_2 \rightarrow H_3 \rightarrow P$ seems to be the strongest. See updated Table 2.

• 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.

we understand that our approach does not cover unseen queries. Our goal is to improve the error rate of frequently run queries (which is about ~80% of workloads). That is why we fall back to a general model as the default. In our experiments we used postgres, but this model can be any of the learned cardinality models as well (query- or data-driven). Specifically, one possible future work is to replace the root model by a data-learned model (e.g., GNN), which we elude to, in the fifth-line in the Conclusion. This could combine the advantages of both worlds (no restriction on input query, yet ability to specialize per workload).

• W4: We sincerely apologize. Our Definition also associates node features. We had a typo in the definition $f^{(v)} = z^{(\pi_v)}$ that is now corrected to $f^{(v)} = f^{(\pi_v)}$ [we somehow missed that earlier, during a rename exercise $z \rightarrow f$]. We checked: the Appendix hashing algorithm uses the correct symbol $f$.

• W5: We sincerely apologize (again!). We (mistakenly) omitted notation $s(.)$ in the submitted version. We fixed it now by adding:

where the history size $s(Ti)$ equals the number of observations that hash to ${T_i}$, i.e., the height of matrices $\mathbf{X}_i^{[T_i]}$ and $\mathbf{Y}_i^{[T_i]}$.

(it is marked in blue)

• W6: We use CardBench due to practical advantages. First, they open-source their query generator (with instructions on how to re-generate the data). We modified their query generator to repeat patterns (but we remove duplicate queries) to represent common workloads where queries repeat.

JOB benchmark uses IMDB, which has a license not compatible with our corporate policies. But our workload generator follows similar patterns as JOB.

Q: It is unclear how the plan tree is constructed.

Excellent point. We have been relying on the query parser of CardBench to convert SQL statement into query graph. While CardBench is consistent (graph is determined by order of join conditions), we may be splitting identical graphs onto different buckets. We think the graph can be canonicalized (e.g., super-node can absorb all join nodes). Worst-comes-worse, it is OK to have equivalent query into different buckets [potentially this can cause degradation of metrics]. We will do our best to have this aspect reflected into the paper and into our final implementation, by camera ready, if our paper is accepted.