Pith. sign in

REVIEW 4 major objections 6 minor 63 references

Improved Cardinality Estimation by Learning Queries Containment Rates

T0 review · 4 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 1908.07723 v1 pith:EYDU36QD submitted 2019-08-21 cs.DB cs.LG

Rojeh Hayek , Oded Shmueli This is my paper · ORCID
classification cs.DBcs.LG
keywords cardinalityestimationquerycontainmentratedeeplearningqueriespooloptimizationIMDbq-errorSQLfeaturization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

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.

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 (4)
  1. [§6.5, Table 9; §6.6, Table 5] 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.
  2. [§5.3, Figure 8; §5.2] 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.
  3. [§4.3, Table 3] 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.
  4. [§5.1.1; §2] 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.
minor comments (6)
  1. [Tables 2 and 5] The column headers '0 1 3 3 4 5' should be '0 1 2 3 4 5'.
  2. [Figure 1 caption] The caption contains the typo 'Archeticture'; it should be 'Architecture'.
  3. [Abstract and Section 1] 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.
  4. [§3.2.4] 'contaminate rate' should be 'containment rate'.
  5. [§5.1.1] 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.
  6. [§6.6] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

The Cnt2Crd formula is an exact algebraic identity, but its inputs are learned containment-rate estimates evaluated on unseen pairs; no derivation step is equivalent to its own input.

full rationale

The claimed derivation chain is: (i) CRN is trained to map query pairs to containment rates using labels computed from executed results; (ii) Cnt2Crd uses the algebraic identity x_rate/y_rate * |Qold| = (|Qnew∩Qold|/|Qold|) / (|Qnew∩Qold|/|Qnew|) * |Qold| = |Qnew|; (iii) the estimated rates are evaluated on unseen pairs, and the resulting cardinalities are compared with PostgreSQL and MSCN on held-out workloads. The identity is exact when the rates are exact, but the pipeline inputs are CRN's learned estimates, which are not constructed from the target cardinality labels of the test queries; the test cardinalities are never fitted. The 'Improved' models also do not collapse: Cnt2Crd(Crd2Cnt(M)) equals M(Qnew) * (actual |Qold| / M(Qold)), which is an observed-calibration correction rather than a renaming of M(Qnew). The only self-citation found, reference [7] (an aiDM proceedings entry edited by one of the authors), appears in a related-work enumeration and carries no load in the derivation. The paper's own limitations are generalization and experimental-validity concerns, not circularity: Section 5.2 says 'In such cases we can always rely on the known basic cardinality estimation models' when no matching pool query exists; Section 6.2 states that 'QP, covers all the possible FROM clauses that are used in the tests workloads'; and Section 6.6's scale workload contains no 5-join queries, so the 5-join claim is not tested under that cross-generator workload. None of these facts shows an equation defining an input in terms of the target prediction, and no load-bearing claim is justified solely by a self-citation. Verdict: no significant circularity.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical or conceptual entities; CRN is a neural network model and the queries pool is a database component. The main burdens are the same-FROM restriction and the requirement that the pool contains matching queries.

free parameters (3)
  • H (CRN hidden layer size) = 512
    Chosen by validation-set hyperparameter search (Section 3.4) and shared across all MLP layers.
  • epsilon (minimum y_rate) = not reported
    Queries with Qnew-in-Qold containment rate at or below epsilon are skipped in EstimateCardinality (Figure 8); the value is not given in the paper.
  • queries pool size = 300
    QP size used in all main cardinality experiments (Section 6.2); Table 14 shows results vary with pool size.
assumptions (4)
  • domain assumption Containment rate is defined only for query pairs with identical SELECT and FROM clauses.
    Section 2 states this restriction, which carries over to cardinality estimation through the FROM-clause matching in Figure 8.
  • domain assumption The training query distribution, generated with up to two joins, is representative of the test workloads, and the model generalizes to more joins.
    Section 3.1.2 limits training to 0-2 joins while tests go to 5 joins; the generalization claim is empirical, not derived.
  • domain assumption The queries pool contains at least one old query with the same FROM clause as the new query and with y_rate greater than epsilon.
    The cardinality estimate uses the ratio x_rate/y_rate, so a matching pool query is required; without one the method falls back to the base estimator.
  • domain assumption The database is static during training and evaluation.
    Section 9 discusses database updates as future work; the model encodings and containment rates are computed on an immutable snapshot.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Cardinality Estimation by Learning Queries Containment Rates." pith.science (2026). https://pith.science/paper/EYDU36QD

@misc{pith2026190807723,
  author       = {Pith},
  title        = {Pith review of: Improved Cardinality Estimation by Learning Queries Containment Rates},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EYDU36QD}},
  note         = {Machine review of arXiv:1908.07723}
}
read the original abstract

The containment rate of query Q1 in query Q2 over database D is the percentage of Q1's result tuples over D that are also in Q2's result over D. We directly estimate containment rates between pairs of queries over a specific database. For this, we use a specialized deep learning scheme, CRN, which is tailored to representing pairs of SQL queries. Result-cardinality estimation is a core component of query optimization. We describe a novel approach for estimating queries result-cardinalities using estimated containment rates among queries. This containment rate estimation may rely on CRN or embed, unchanged, known cardinality estimation methods. Experimentally, our novel approach for estimating cardinalities, using containment rates between queries, on a challenging real-world database, realizes significant improvements to state of the art cardinality estimation methods.

Figures

Figures reproduced from arXiv: 1908.07723 by the authors.

Figure 1
Figure 1. CRN Model Archeticture. 3.2.1 First Stage, from (Q1, Q2) to (V 1, V 2) In the same way as MSCN model [24], we represent each query Q as a collection of three sets (T, J, P). T is the set of all the tables in Q’s FROM clause. J is the set of all the joins (i.e., join clauses) in Q’s WHERE clause. P is the set of all the (column) predicates in Q’s WHERE clause. Using sets T, J, and P, we obtain a set of vectors V repr… view at source ↗
Figure 2
Figure 2. Query featurization as sets of feature vectors obtained from sets [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. The mean q-error on the validation set with [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: Convergence of the mean q-error on the vali [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]
Figure 5
Figure 5. Figure 5: Estimation errors on the cnt test1 workload. In all the similar plots presented in this paper, the box boundaries are at the 25th/75th percentiles and the hor￾izontal lines mark the 5th/95th percentiles. Hence, 50% of the tests results are located within the box bound￾…
Figure 6
Figure 6. Figure 6: Estimation errors on the cnt test2 workload. 5. CARDINALITY ESTIMATION USING CONTAINMENT RATES In this section we consider one application of the proposed containment rate estimation model: cardinality estimation. We introduce a novel approach for estimating cardinalit…
Figure 7
Figure 7. Figure 7: A novel approach, from cardinality estimation to containment rate estimation, and back to cardinality [PITH_FULL_IMAGE:figures/full_fig_p007_7.png]
Figure 8
Figure 8. Figure 8: Cardinality Estimation Technique. Estimating cardinality considers all the matching queries whose FROM clauses are identical to Qnew’s FROM clause. For each matching query, we estimate Qnew’s cardinality using the Cnt2Crd transformation and save the estimated result in…
Figure 9
Figure 9. Figure 9: depicts the q-error of the Cnt2Crd(CRN) model as compared to MSCN and PostgreSQL on the crd test1 workload. While PostgreSQL’s errors are more skewed to￾wards the positive spectrum, MSCN is competitive with Cnt2Crd(CRN) in all the described values. As can be seen in […
Figure 11
Figure 11. Figure 11: Q-error medians for each number of joins. [PITH_FULL_IMAGE:figures/full_fig_p009_11.png]
Figure 10
Figure 10. Figure 10: Estimation errors on the crd test2 workload. As depicted in [PITH_FULL_IMAGE:figures/full_fig_p009_10.png]
Figure 12
Figure 12. Figure 12: Estimation errors on the scale workload. [PITH_FULL_IMAGE:figures/full_fig_p009_12.png]
Figure 13
Figure 13. Figure 13: Estimation errors on the crd test2 workload, compared with all models. We make the test easier for MSCN1000 model by training the MSCN1000 model with a training set that was created with the same queries generator that was used for generat￾ing the scale workload. As d…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

63 extracted references · 58 canonical work pages

  1. [1]

    Improved Cardinality Estimation by Learning Queries Containment Rates

    INTRODUCTION Query Q1 is contained in (resp. equivalent to), query Q2, analytically, if for all the database states D, Q1’s result over D is contained in (resp., equals) Q2’s result over D. Query containment is a well-known concept that has applications in query optimization. It has been extensively researched in database theory, and many algorithms were ...

    work page Pith review arXiv 1997

  2. [2]

    Query Q1 is x%-contained in query Q2 on database D if precisely x% of Q1’s execution result rows on database D are also in Q2’s execution result on database D

    CONTAINMENT RA TE DEFINITION We define the containment rate between two queries Q1, and Q2 on a specific database D. Query Q1 is x%-contained in query Q2 on database D if precisely x% of Q1’s execution result rows on database D are also in Q2’s execution result on database D. The containment rate is formally a function from QxQxD to R, where Q is the set of...

    work page

  3. [3]

    LEARNED CONTAINMENT RA TES From a high-level perspective, applying machine learn- ing to the containment rate estimation problem is straight- forward. Following the training of the CRN model with pairs of queries ( Q1, Q2) and the actual containment rates Q1⊂% Q2, the model is used as an estimator for other, unseen pairs of queries. There are, however, se...

    work page

  4. [4]

    Since to the best of our knowledge, the problem of determining containment rate has not been addressed till now, we used a transformation as described in Section 4.1 below

    CONTAINMENT EV ALUA TION In this section we describe how we compared the CRN model to other (baseline) methods. Since to the best of our knowledge, the problem of determining containment rate has not been addressed till now, we used a transformation as described in Section 4.1 below. 4.1 From Cardinality to Containment To our knowledge, this is the first w...

    work page

  5. [5]

    CARDINALITY ESTIMA TION USING CONTAINMENT RA TES In this section we consider one application of the proposed containment rate estimation model: cardinality estimation. We introduce a novel approach for estimating cardinalities using query containment rates, and we show that using the proposed approach, we improve cardinality estimations sig- nificantly, es...

    work page

  6. [6]

    We compare our cardinality estimates with those of the PostgreSQL version 11 cardinality estimation component [1], and the MSCN model [24]

    CARDINALITY EV ALUA TION We evaluate our proposed technique for estimating cardi- nality, with different test sets, while using the CRN model as defined in Section 3.2 for estimating containment rates. We compare our cardinality estimates with those of the PostgreSQL version 11 cardinality estimation component [1], and the MSCN model [24]. We train both the...

    work page

  7. [7]

    IMPROVING EXISTING CARDINALITY ESTIMA TION MODELS In this section we describe how existing cardinality esti- mation models can be improved using the idea underlining our proposed technique. The proposed technique for im- proving existing cardinality estimation models relies on the same technique for predicting cardinalities using a contain- ment rate esti...

    work page

  8. [8]

    Conjunctive queries constitute a broad class of frequently used queries

    RELA TED WORK Over the past five decades, conjunctive queries have been studied in the contexts of database theory and database systems. Conjunctive queries constitute a broad class of frequently used queries. Their expressive power is roughly equivalent to that of the Select-Join-Project queries of rela- tional algebra. Therefore, several problems and alg...

    work page

Show all 63 references
  1. [9]

    CONCLUSIONS AND FUTURE WORK We introduced a new problem, that of estimating contain- ment rates between queries over a specific database, and in- troduced the CRN model, a new deep learning model for solving it. We trained CRN with generated queries, uni- formly distributed wit...

  2. [10]

    Brownlee

    J. Brownlee. When to use mlp, cnn, and rnn neural networks. https://machinelearningmastery.com/when- to-use-mlp-cnn-and-rnn-neural-networks/, 2018

    2018

  3. [11]

    A. Cal` ı. Containment the conjunctive queries over conceptual schemata. In Proceedings the Database Systems for Advanced Applications conference,DASFAA, pages 628–643, 2006

    2006

  4. [12]

    E. P. F. Chan. Containment and minimization of positive conjunctive queries in oodb’s. In Proceedings the Eleventh ACM SIGACT-SIGMOD-SIGART , pages 202–211, 1992

    1992

  5. [13]

    https://www.postgresql.org/

    Postgresql, the world’s most advanced open source relational database. https://www.postgresql.org/

  6. [14]

    Abadi, P

    M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, M. Kudlur, J. Levenberg, R. Monga, S. Moore, D. G. Murray, B. Steiner, P. Tucker, V. Vasudevan, P. Warden, M. Wicke, Y. Yu, and X. Zheng. Tensorflow: A system for large-scale m...

    2016

  7. [15]

    In addition to the mentioned cases, there are many other tractable cases [44, 11, 12, 19]

    it was proved that for every k≥ 1, conjunctive query containment could be solved in polynomial time, if Q2 has querywidth smaller than k+1. In addition to the mentioned cases, there are many other tractable cases [44, 11, 12, 19]. Such cases are obtained by imposing syntactic ...

  8. [16]

    Abiteboul, R

    S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995

    1995

  9. [17]

    A. V. Aho, Y. Sagiv, and J. D. Ullman. Equivalences among relational expressions. SIAM J. Comput. , 8(2):218–246, 1979

    1979

  10. [18]

    Aurelien

    G. Aurelien. Hands-on machine learning with Scikit-Learn and TensorFlow : concepts, tools, and techniques to build intelligent systems . O’Reilly Media, 2017

    2017

  11. [19]

    Bogdanova, C

    D. Bogdanova, C. N. dos Santos, L. Barbosa, and B. Zadrozny. Detecting semantically equivalent questions in online user forums. In Proceedings the 19th Conference on Computational Natural Language Learning, CoNLL, pages 123–131, 2015

    2015

  12. [20]

    Bordawekar and O

    R. Bordawekar and O. Shmueli, editors. Proceedings of the Second International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM@SIGMOD. ACM, 2019

    2019

  13. [21]

    S. R. Bowman, J. Gauthier, A. Rastogi, R. Gupta, C. D. Manning, and C. Potts. A fast unified model for parsing and sentence understanding. CoRR, abs/1603.06021, 2016

    2016 arXiv

  14. [22]

    Bressan, E

    M. Bressan, E. Peserico, and L. Pretto. Simple set cardinality estimation through random sampling. CoRR, abs/1512.07901, 2015

    2015 arXiv

  15. [23]

    D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In Proceedings the 3rd International Conference on Learning Representations, ICLR, 2015

    2015

  16. [24]

    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

    is estimating cardinalities. 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. To provide a fuller picture, we also show the percentiles, maximum, and mean q-errors. As depicted in Table...

  17. [25]

    A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing , pages 77–90, 1977

    1977

  18. [26]

    Chatzopoulou, M

    G. Chatzopoulou, M. Eirinaki, and N. Polyzotis. Query recommendations for interactive database exploration. In Scientific and Statistical Database Management, 21st International Conference, SSDBM , pages 3–18, 2009

    2009

  19. [27]

    Chekuri and A

    C. Chekuri and A. Rajaraman. Conjunctive query containment revisited. Theor. Comput. Sci. , 239(2):211–229, 2000

    2000

  20. [28]

    Chung, C ¸

    J. Chung, C ¸ . G¨ ul¸ cehre, K. Cho, and Y. Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. CoRR, abs/1412.3555, 2014

    2014 arXiv

  21. [29]

    Clifford and R

    J. Clifford and R. King, editors. Proceedings the 1991 ACM SIGMOD International Conference on Management of Data . ACM Press, 1991

    1991

  22. [30]

    Eirinaki, S

    M. Eirinaki, S. Abraham, N. Polyzotis, and N. Shaikh. Querie: Collaborative database exploration. IEEE Trans. Knowl. Data Eng. , 26(7):1778–1790, 2014

    2014

  23. [31]

    Farr´ e, W

    C. Farr´ e, W. Nutt, E. Teniente, and T. Urp´ ı. Containment of conjunctive queries over databases with null values. In Proceedings ICDT, pages 389–403, 2007

    2007

  24. [32]

    Ganapathi, H

    A. Ganapathi, H. A. Kuno, U. Dayal, J. L. Wiener, A. Fox, M. I. Jordan, and D. A. Patterson. Predicting multiple metrics for queries: Better decisions enabled by machine learning. In Proceedings ICDE, pages 592–603, 2009

    2009

  25. [33]

    I. J. Goodfellow, Y. Bengio, and A. C. Courville. Deep Learning. Adaptive computation and machine learning. MIT Press, 2016

    2016

  26. [34]

    D. S. Johnson and A. C. Klug. Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci. , 28(1):167–189, 1984

    1984

  27. [35]

    Marcus and O

    R. Marcus and O. Papaemmanouil. Deep reinforcement learning for join order enumeration. In Proceedings the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM@SIGMOD, TX, USA, June 10, 2018, pages 3:1–3:4, 2018

    2018

  28. [36]

    A. Kipf, T. Kipf, B. Radke, V. Leis, P. A. Boncz, and A. Kemper. Learned cardinalities: Estimating correlated joins with deep learning. In Proceedings CIDR, 2019

    2019

  29. [37]

    Kirkpatrick, R

    J. Kirkpatrick, R. Pascanu, N. C. Rabinowitz, J. Veness, G. Desjardins, A. A. Rusu, K. Milan, J. Quan, T. Ramalho, A. Grabska-Barwinska, D. Hassabis, C. Clopath, D. Kumaran, and R. Hadsell. Overcoming catastrophic forgetting in neural networks. CoRR, abs/1612.00796, 2016

    2016 arXiv

  30. [38]

    Kraska, A

    T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis. The case for learned index structures. In Proceedings SIGMOD Conference, pages 489–504, 2018

    2018

  31. [39]

    Krishnan, Z

    S. Krishnan, Z. Yang, K. Goldberg, J. M. Hellerstein, and I. Stoica. Learning to optimize join queries with deep reinforcement learning. CoRR, abs/1808.03196, 2018

    2018 arXiv

  32. [40]

    M. S. Lakshmi and S. Zhou. Selectivity estimation in extensible databases - A neural network approach. In Proceedings VLDB’98, pages 623–627, 1998

    1998

  33. [41]

    V. Leis, A. Gubichev, A. Mirchev, P. A. Boncz, A. Kemper, and T. Neumann. How good are query optimizers, really? PVLDB, 9(3):204–215, 2015

    2015

  34. [42]

    V. Leis, B. Radke, A. Gubichev, A. Kemper, and T. Neumann. Cardinality estimation done right: Index-based join sampling. In Proceedings CIDR, 2017

    2017

  35. [43]

    V. Leis, B. Radke, A. Gubichev, A. Mirchev, P. A. Boncz, A. Kemper, and T. Neumann. Query optimization through the looking glass, and what we found running the join order benchmark. VLDB J., 27(5):643–668, 2018. 13

    2018

  36. [44]

    J. Li, A. C. K¨ onig, V. R. Narasayya, and S. Chaudhuri. Robust estimation of resource consumption for SQL queries using statistical techniques. PVLDB, 5(11):1555–1566, 2012

    2012

  37. [45]

    H. Liu, M. Xu, Z. Yu, V. Corvinelli, and C. Zuzarte. Cardinality estimation using neural networks. In Proceedings the 25th Annual International Conference on Computer Science and Software Engineering, CASCON, pages 53–59, 2015

    2015

  38. [46]

    G. Lohman. Is query optimization a solved problem ? https://wp.sigmod.org/?p=1075, 2014

    2014

  39. [47]

    Y. P. Saraiya. Polynomial-time program transformations in deductive databases. In Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems , PODS ’90, pages 132–144. ACM, 1990

    1990

  40. [48]

    A. O. Mendelzon and J. Paredaens, editors. Proceedings the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems . ACM Press, 1998

    1998

  41. [49]

    Moerkotte, T

    G. Moerkotte, T. Neumann, and G. Steidl. Preventing bad plans by bounding the impact of cardinality estimation errors. PVLDB, 2(1):982–993, 2009

    2009

  42. [50]

    Nambiar and M

    R. Nambiar and M. Poess, editors. Performance Evaluation and Benchmarking for the Analytics Era - 9th TPC Technology Conference, TPCTC , volume 10661 of Lecture Notes in Computer Science . Springer, 2018

    2018

  43. [51]

    M. A. Nielsen. Neural Networks and Deep Learning . Determination Press, 2017

    2017

  44. [52]

    Nwankpa, W

    C. Nwankpa, W. Ijomah, A. Gachagan, and S. Marshall. Activation functions: Comparison of trends in practice and research for deep learning. CoRR, abs/1811.03378, 2018

    2018 arXiv

  45. [53]

    Olken and D

    F. Olken and D. Rotem. Random sampling from database files: A survey. In Proccedings the Statistical and Scientific Database Management, 5th International Conference SSDBM, pages 92–111, 1990

    1990

  46. [54]

    Ortiz, M

    J. Ortiz, M. Balazinska, J. Gehrke, and S. S. Keerthi. Learning state representations for query optimization with deep reinforcement learning. In Proceedings the Second Workshop on Data Management for End-To-End Machine Learning, DEEM@SIGMOD 2018, pages 4:1–4:4, 2018

    2018

  47. [55]

    Prechelt

    L. Prechelt. Early stopping - but when? In Neural Networks: Tricks of the Trade - Second Edition , pages 53–67. 2012

    2012

  48. [56]

    G. Rull, P. A. Bernstein, I. G. dos Santos, Y. Katsis, S. Melnik, and E. Teniente. Query containment in entity SQL. In Proceedings ACM SIGMOD, pages 1169–1172, 2013

    2013

  49. [57]

    Sagiv and M

    Y. Sagiv and M. Yannakakis. Equivalences among relational expressions with the union and difference operators. J. ACM, 27(4):633–655, 1980

    1980

  50. [58]

    Y. Saraiya. Subtree elimination algorithms in deductive databases. PhD thesis, Department of Computer Science, Stanford University. , 1991

    1991

  51. [60]

    Sirangelo

    C. Sirangelo. Positive relational algebra. In Encyclopedia of Database Systems, Second Edition . Computer Science Press, 2018

    2018

  52. [61]

    J. D. Ullman. Principles the Database and Knowledge-Base Systems, Volume II . Computer Science Press, 1989

    1989

  53. [62]

    Woltmann, C

    L. Woltmann, C. Hartmann, M. Thiele, D. Habich, and W. Lehner. Cardinality estimation with local deep learning models. In Proceedings the Second International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM@SIGMOD, pages 5:1–5:8, 2019

    2019

  54. [63]

    W. E. Zhang, Q. Z. Sheng, Y. Qin, K. Taylor, and L. Yao. Learning-based SPARQL query performance modeling and prediction. World Wide Web , 21(4):1015–1035, 2018. 14

    2018

  55. [1880]

    by 235,000 different companies with over 4M actors. 3.1.2 Generating the Development Dataset Our approach for solving the ”cold start problem” is to ob- tain an initial training corpus using a specialized queries gen- erator that randomly generates queries based on the IMDB sch...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.