---
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.'
author:
- |
    Rojeh Hayek\
    \
    \
    Oded Shmueli\
    \
    \
bibliography:
- 'main.bib'
nocite: '[@*]'
title: 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 