{"id":"71f7a5ff-fa1a-4f8f-bab4-56fe79c0ae55","arxiv_id":"1908.07723","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Learned containment rates between query pairs, combined with a queries pool of known cardinalities, substantially improve cardinality estimates on multi-join queries.","lead":"This paper introduces containment rate estimation between pairs of SQL queries on a specific database, using a neural network called CRN, and uses these rates to estimate query result cardinalities. The method, aided by a pool of previously executed queries with known cardinalities, reports major q-error reductions on multi-join IMDb queries.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The headline 5-join improvement is only demonstrated in-distribution; the cross-generator workload stops at 4 joins, so the x1650/x120 claim is not yet supported.","rationale":"The paper's core mathematical transformation, Cnt2Crd, is sound: given exact containment rates and a matching old query with nonzero y_rate, it yields the exact cardinality. The same-generator results on crd_test2 are genuinely strong and the scale experiment provides some cross-generator evidence at 3 and 4 joins. My concern is narrower and more specific than the reader's weakest assumption: the headline 5-join numbers, which are the most striking and most cited part of the abstract, are supported only by a workload sharing the training generator and a queries pool engineered to cover all test FROM clauses. The scale workload, which is the paper's own attempt at a different-distribution test, has no 5-join queries at all, so the generalization to 5 joins under distribution shift is untested. This does not invalidate the method, but it means the central claim is conditional on favorable pool construction and in-distribution query shapes. A single real-workload 5-join evaluation with a naturally accumulated pool would resolve whether the claimed improvement transfers to realistic settings. The reader's conditional verdict is therefore appropriate; I do not see a reason to move it to accept or reject on the present evidence.","tokens_in":19434,"tokens_out":8512,"duration_ms":96305,"concrete_test":"Run Cnt2Crd(CRN) on a real or independently generated 5-join IMDb workload, e.g., queries derived from the Join Order Benchmark templates or a held-out MSCN-style generator different from the training generator, while keeping CRN trained only on 0-2 join pairs. Build QP from a naturally accumulated query log (or from a generator not designed to cover the test FROM clauses), and recompute the mean q-error for 5-join queries. If the per-join improvement over PostgreSQL and MSCN at 5 joins does not remain large (e.g., within the same order of magnitude as Table 9), the headline x1650/x120 claim should be restricted to in-distribution settings.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Table 9's headline ratios (x150/x175 for 4 joins, x1650/x120 for 5 joins) are computed entirely on crd_test2, a workload generated by the same query generator used to create the CRN training set and the queries pool QP. The only cross-generator evaluation, the scale workload in Section 6.6, contains zero 5-join queries (Table 5: 115/115/107/88/75/0 for 0-5 joins). Thus the most dramatic part of the central claim, that containment-rate-based cardinality estimation improves state-of-the-art methods on 5-join queries, has not been tested under any form of distribution shift. The gap is compounded by the construction of QP: Section 6.2 states that QP is generated to cover all FROM clauses used in the test workloads, which guarantees the availability of at least one matching old query with nonzero y_rate. A naturally accumulated queries pool in a real DBMS provides no such guarantee, and Section 5.2's fallback to a base estimator means the practical improvement depends precisely on the conditions the experiments deliberately ensure. The 3- and 4-join improvements on scale are encouraging, but they do not establish the 5-join claim, which is the strongest numerical assertion in the abstract.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the problem of estimating containment rates between SQL queries over a fixed database and proposes a deep learning model, CRN, that represents each query as sets of tables, joins, and predicates and learns to predict the containment rate of a query pair. The authors then use containment-rate estimates together with a pool of previously executed queries whose cardinalities are known to estimate the cardinality of a new query, via the identity |Qnew| = (Qold in Qnew containment rate) / (Qnew in Qold containment rate) * |Qold|. The central empirical claim is that this Cnt2Crd approach improves cardinality estimation relative to PostgreSQL and MSCN, with particularly large reported gains on 4- and 5-join queries, e.g., x150/x175 and x1650/x120 in mean q-error on the crd_test2 workload.","tokens_in":19684,"tokens_out":5338,"duration_ms":97755,"significance":"The idea of estimating cardinalities through containment rates and a query pool is novel, and the Cnt2Crd transformation is an exact identity when containment rates are known, which gives the approach a clean conceptual basis and distinguishes it from black-box cardinality estimation. The experimental section is extensive, comparing against PostgreSQL and MSCN on the IMDb dataset and including a cross-generator workload (scale); the reported 3- and 4-join improvements on the cross-generator workload are substantial and encouraging. However, the strongest 5-join numbers are demonstrated only on a workload generated by the same generator as the training data, and the experimental design guarantees that the query pool covers the test workloads' FROM clauses. The practical generality of the method, and especially of the 5-join claim, is therefore not yet established.","major_comments":[{"comment":"The headline 5-join improvement (x1650/x120 vs. PostgreSQL/MSCN) is computed solely on crd_test2, which is generated by the same query generator used to create the CRN training set (Section 6.1), while the queries pool QP is built to cover all FROM clauses used in the test workloads (Section 6.2). The only cross-generator workload, scale, contains zero 5-join queries (Table 5). Thus the most dramatic part of the abstract's claim has not been tested under any distribution shift, and it has not been tested without the guarantee of a matching old query. The 3- and 4-join gains on scale are encouraging but do not support the 5-join statement. Please either add a cross-generator 5-join evaluation or restrict the claim to the conditions actually tested.","section":"§6.5, Table 9; §6.6, Table 5"},{"comment":"The algorithm in Figure 8 skips every pool query whose y_rate is at or below epsilon and never defines the result when no pool query matches; Section 5.2's fallback to a base cardinality estimator is neither implemented in the pseudocode nor exercised in the experiments, because QP is constructed to cover all test FROM clauses (Section 6.2). In a real DBMS, an accumulated query pool provides no such coverage guarantee, so the practical improvement depends precisely on the condition the experiments deliberately ensure. Please specify the behavior for an empty results list and evaluate the method on pools with incomplete FROM-clause coverage, for example by ablating the pool size and coverage.","section":"§5.3, Figure 8; §5.2"},{"comment":"The containment-rate evaluation shows that CRN has mean q-error 111 on cnt_test1, about 6.5 times worse than Crd2Cnt(MSCN) (17.08), and has a very heavy tail (max 51,873), even though CRN is better at the 50th and 75th percentiles. Since the cardinality method aggregates many pool estimates with the median, it is plausible that CRN's bad tails are mitigated; but the paper should state this explicitly. As written, Section 4 can mislead readers about which component is responsible for the cardinality gains, and the relationship between containment-error distribution and cardinality-error distribution is left unexplained.","section":"§4.3, Table 3"},{"comment":"The method cannot handle zero-cardinality queries. By the definition in Section 2, if |Qnew| is zero then y_rate = Qnew⊂% Qold = 0, so every matching pool query is skipped by the epsilon test and the results list is empty; the paper does not specify a special rule for this case. The manuscript should state how empty results are treated, since real workloads can contain queries whose result is empty.","section":"§5.1.1; §2"}],"minor_comments":[{"comment":"The column headers '0 1 3 3 4 5' should be '0 1 2 3 4 5'.","section":"Tables 2 and 5"},{"comment":"The caption contains the typo 'Archeticture'; it should be 'Architecture'.","section":"Figure 1 caption"},{"comment":"The improvement factors x150/x175 and x1650/x120 are rounded; Table 9 gives approximate ratios of about x145/x178 for 4 joins and x1633/x115 for 5 joins. Please state explicitly that these are approximate.","section":"Abstract and Section 1"},{"comment":"'contaminate rate' should be 'containment rate'.","section":"§3.2.4"},{"comment":"The formula |Qnew| = x_rate / y_rate * |Qold| assumes containment rates are expressed as fractions; since the definition in Section 2 uses percentages, the text should make the unit convention explicit to avoid an off-by-100 error.","section":"§5.1.1"},{"comment":"The text says that the QP query pool was not changed for the scale workload, but it does not report how many of the scale workload's FROM clauses are actually covered by QP; please quantify this coverage, since Figure 8 only uses pool queries with the same FROM clause.","section":"§6.6"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a preprint formatted with PVLDB placeholders and does not mention the release of code, the query generator, or trained models; for a deep-learning-based method, reproducibility would be greatly improved by providing these artifacts. The related work discussion is adequate, and the exact Cnt2Crd identity is a genuine strength. The main unresolved issue is the gap between the strong in-distribution 5-join claim and the cross-generator evaluation, which only reaches 4 joins."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The containment-rate framing is the real novelty here. Estimating how much of one query's result sits inside another on a specific database is a sensible problem, and CRN is a reasonable architecture for it. The Cnt2Crd transformation is also genuinely neat: an exact algebraic identity, not a fitted proxy. Showing that you can wrap PostgreSQL or MSCN in this containment-based pipeline and improve their estimates is a useful trick, and the experiments on IMDb are extensive, with baselines, ablation of pool size, and timing data. The scale workload, generated by a different query generator, showing gains on 3- and 4-join queries, is the most convincing part of the empirical story.\n\nThe soft spots are real but not fatal. The abstract's headline numbers — x150/x175 for 4 joins, x1650/x120 for 5 joins — come entirely from crd_test2, which is generated by the same query generator used for training. The only cross-generator workload, scale, contains zero 5-join queries (Table 5), so the 5-join claim has not been tested under any distribution shift. The queries pool QP is explicitly constructed to cover all FROM clauses in the test workloads, guaranteeing a matching old query. In a real DBMS, a naturally accumulated pool offers no such guarantee; the method falls back to the base estimator, and the improvement evaporates. The paper acknowledges this in Section 5.2 but does not evaluate a realistic pool. Lack of released code or data also makes the results hard to verify.\n\nThese limitations are in proportion: the core identity is correct, the 3-4 join out-of-distribution results are encouraging, and the fallback behavior is at least honestly described. The paper deserves a serious referee, not a desk reject. The main requests should be: (1) a cross-generator workload that actually includes 5-join queries, (2) an evaluation with a queries pool that is not guaranteed to cover every test FROM clause, and (3) code or data to check the trained models and pool construction. I would send it to peer review and ask for those revisions.","headline":"The containment-rate idea is new and the Cnt2Crd identity is clean, but the headline 5-join improvements are only tested in-distribution; the cross-generator workload stops at 4 joins, so the strongest claims remain unproven outside the training generator.","tokens_in":20207,"tokens_out":2669,"would_cite":true,"duration_ms":67123,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Cardinality estimation can be recast as estimating containment rates between a new query and previously executed queries, and on join-heavy IMDb workloads this cuts mean q-error by factors of 150 to 1650 relative to PostgreSQL and MSCN.","keywords":["cardinality estimation","query containment rate","deep learning","queries pool","query optimization","IMDb","q-error","SQL query featurization"],"falsifier":"Measure mean q-error on the IMDb database using a queries pool built only from queries actually posed before the test queries, without any generator guarantee that every FROM clause is covered; if errors on four- and five-join queries revert to PostgreSQL or MSCN levels whenever a matching pool query is missing, the reported gains depend on the generator-built pool rather than on the containment-rate identity.","tokens_in":19221,"feed_emoji":"📊","tokens_out":12023,"duration_ms":532988,"temperature":0.7,"pith_summary":"Most cardinality estimators look at a query in isolation and predict its result size directly; the authors instead propose to estimate how much a new query overlaps, in result rows, with queries that have already been executed. The containment rate of $Q_1$ in $Q_2$ on a fixed database is the share of $Q_1$'s result rows that also appear in $Q_2$'s result. They train a deep network, CRN, to predict these rates for pairs of SQL queries, and they show that if a pool of past queries with known cardinalities is available, the new query's cardinality follows from two containment rates and one known cardinality. On the IMDb database, the resulting estimator, Cnt2Crd(CRN), keeps mean q-error--the ratio between predicted and true cardinality or its inverse--at 30.51 on four-join queries where PostgreSQL is at 4430 and MSCN at 5427, and at 129 on five-join queries where the baselines' errors are far larger. The same wrapping technique improves existing estimators without modifying them.","feed_headline":"Containment rates cut 5-join cardinality errors 1,650-fold","feed_subtitle":"Estimating how much queries overlap, via a neural net and a pool of past queries, sharpens the optimizer's weakest estimates.","key_machinery":"The load-bearing object is the Cnt2Crd transformation: from two estimated containment rates, $x_{rate} = Q_{old} \\subset\\% Q_{new}$ and $y_{rate} = Q_{new} \\subset\\% Q_{old}$, together with the known cardinality $|Q_{old}|$ from the queries pool, the estimate is $(x_{rate} / y_{rate}) \\times |Q_{old}|$, aggregated by the median over all matching pool queries. The containment rates themselves come from CRN, a network that featurizes each query as three sets--tables, joins, and predicates--with each element encoded as a fixed-length vector made of one-hot segments plus a normalized value, averages per-element learned embeddings into a single query vector, and feeds the pair through an output network that sees the two vectors, their absolute difference, and their dot product. CRN is trained to minimize mean q-error, the ratio between predicted and true containment rate or its inverse, which matches the evaluation metric and keeps the model focused on large relative mistakes.","core_discovery":"The paper's central claim is that the containment rate between two queries on a particular database is learnable, and that cardinality estimation should be done indirectly through containment rates rather than directly. For a new query $Q_{new}$ and an old query $Q_{old}$ with the same FROM clause and known cardinality $|Q_{old}|$, the identity $|Q_{new}| = \\frac{Q_{old} \\subset\\% Q_{new}}{Q_{new} \\subset\\% Q_{old}} \\times |Q_{old}|$ holds exactly when the two containment rates are exact, because both rates share the same intersection size in their numerators. The paper argues that a queries pool storing previously executed queries and their actual cardinalities is a realistic database component, that CRN can estimate the two rates in a single forward pass, and that applying the same containment-rate transformation to PostgreSQL and MSCN lowers their mean q-error by factors of about 7 and 122 on the five-join workload. The main experimental demonstration is that the error growth with the number of joins, the weakest point of existing estimators, is much flatter under the containment-rate approach even though CRN was trained only on queries with zero to two joins.","pith_inferences":["Because the Cnt2Crd formula is algebraically exact when the two containment rates are exact, all residual error in Cnt2Crd(CRN) is attributable to containment-rate error; an exact containment oracle for pool queries, such as cached result summaries, would yield exact cardinalities for any query whose FROM clause the pool covers.","The method's practical ceiling depends on pool coverage: the paper's pool was generated to cover every FROM clause used in the test workloads, so a deployment should track which FROM clauses occur and maintain pool entries for them, a question the paper does not study.","The same pairwise-overlap idea could be extended to other query relations, such as similarity between a new query and stored templates, to improve plan selection or cache reuse; the paper notes applications but does not explore these uses experimentally."],"forward_implications":["Any existing cardinality estimator can be wrapped unchanged as Cnt2Crd(Crd2Cnt(M)); on the five-join workload this lowers PostgreSQL's mean q-error from 35,169 to 5,081 and MSCN's from 3,402 to 27.78.","The improvement widens as joins increase: for four-join queries Cnt2Crd(CRN) has mean q-error 30.51 versus 4,430 for PostgreSQL and 5,427 for MSCN, and for five-join queries 129 versus 210,657 and 14,895.","A model trained only on queries with zero to two joins generalizes to five joins, with CRN's mean q-error on zero-to-five-join containment test pairs about eight times lower than the baseline transformations.","Cardinality prediction with CRN and a 300-query pool takes about 16 ms per query, comparable to sampling-based estimators and far below the cost of executing the queries, with prediction time growing linearly with pool size.","The containment-rate estimation problem is new, and solving it supports additional applications beyond cardinality, including database-specific query equivalence, query clustering, and query recommendation."],"supporting_citations":[{"why":"MSCN supplies the deep-learning cardinality baseline that Cnt2Crd(CRN) is compared against, and CRN adapts its table, join, and predicate featurization.","marker":"[24]"},{"why":"This study establishes IMDb as a join-correlated workload that is challenging for cardinality estimators, motivating the paper's focus on multi-join queries.","marker":"[29]"},{"why":"PostgreSQL's cardinality estimator is the traditional database-profiling baseline used throughout the containment and cardinality experiments.","marker":"[1]"},{"why":"Index-based join sampling is the sampling baseline whose reported limitations justify the need for learned estimators and frame the comparison set.","marker":"[30]"},{"why":"This reference defines the q-error metric that the paper uses both as CRN's training loss and as the evaluation measure for all estimators.","marker":"[37]"}],"fun_headline_variants":["Containment learning cuts 5-join estimate errors 1650x","Neural net on query overlap fixes weak cardinality guesses","Overlap rates sharpen cardinality estimates for joins","Past queries + containment: 5-join errors down 1650-fold","Learn overlap, predict size: containment cardinality"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For each new query, the queries pool must contain at least one previously executed query with the same FROM clause whose containment in the new query is estimated to be above zero; when no such pool query exists, the method falls back to the base estimator and the claimed improvement disappears.","fun_headline_variants_meta":{"raw":{"variants":["Containment learning cuts 5-join estimate errors 1650x","Neural net on query overlap fixes weak cardinality guesses","Overlap rates sharpen cardinality estimates for joins","Past queries + containment: 5-join errors down 1650-fold","Learn overlap, predict size: containment cardinality"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000433,"raw_usage":{"total_tokens":2201,"prompt_tokens":931,"completion_tokens":1270,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":547,"completion_tokens_details":{"reasoning_tokens":1185}},"tokens_in":547,"tokens_out":1270,"duration_ms":138792,"temperature":1.0,"reasoning_tokens":1185,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:58:41.488023+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure mean q-error on the IMDb database using a queries pool built only from queries actually posed before the test queries, without any generator guarantee that every FROM clause is covered; if errors on four- and five-join queries revert to PostgreSQL or MSCN levels whenever a matching pool query is missing, the reported gains depend on the generator-built pool rather than on the containment-rate identity.","supporting_citations":[{"cited_title":"That is, had we trained the MSCN model for its main purpose, with ”independent” queries, we might have ended up with worse results for MSCN","cited_arxiv_id":null,"evidence_quote":"MSCN supplies the deep-learning cardinality baseline that Cnt2Crd(CRN) is compared against, and CRN adapts its table, join, and predicate featurization."},{"cited_title":"Clifford and R","cited_arxiv_id":null,"evidence_quote":"This study establishes IMDb as a join-correlated workload that is challenging for cardinality estimators, motivating the paper's focus on multi-join queries."},{"cited_title":"Improved Cardinality Estimation by Learning Queries Containment Rates","cited_arxiv_id":"1908.07723","evidence_quote":"PostgreSQL's cardinality estimator is the traditional database-profiling baseline used throughout the containment and cardinality experiments."},{"cited_title":"Eirinaki, S","cited_arxiv_id":null,"evidence_quote":"Index-based join sampling is the sampling baseline whose reported limitations justify the need for learned estimators and frame the comparison set."}],"review_version":1}