Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints

Sungjin Im, Benjamin Moseley, Hung Q. Ngo, Kirk Pruhs · 2025

Read Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints by Sungjin Im, Benjamin Moseley, Hung Q. Ngo, Kirk Pruhs (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-02770.txt.

Introduction

Sungjin Im, Benjamin Moseley, Hung Ngo and Kirk Pruhs wrote a 2025 paper on two core database tasks. One task guesses how many rows a query will return. The other runs the query itself. A known frame gives a bound on the count from facts about the data, but computing it can be hard.

For one common class of facts, no fast method to compute the bound was known. The team gives a fast method for that class. They also give a fast way to build a proof of the bound, which speeds up query runs. They show that wider classes stay hard, which marks where the method ends.

Catalog record

CREATORSungjin Im, Benjamin Moseley, Hung Q. Ngo, Kirk Pruhs
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-02770

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints Sungjin Im, Benjamin Moseley, Hung Q. Ngo, Kirk Pruhs Abstract . Cardinality estimation and conjunctive query evaluation are two of the most fundamental problems in database query processing. Recent work proposed, studied, and implemented a robust and practical information-theoretic cardinality estimation framework. In this framework, the estimator is the cardinality upper bound of a conjunctive query subject to “degree-constraints”, which model a rich set of input data statistics. For general degree constraints, computing this bound is computationally hard. Researchers have naturally sought efficiently computable relaxed upper bounds that are as tight as possible. The polymatroid bound is the tightest among those relaxed upper bounds. While it is an open question whether the polymatroid bound can be computed in polynomial-time in general, it is known to be computable in polynomial-time for some classes of degree constraints. Our focus is on a common class of degree constraints called simple degree constraints. Researchers had not previously determined how to compute the polymatroid bound in polynomial time for this class of constraints. Our first main result is a polynomial time algorithm to compute the polymatroid bound given simple degree constraints. Our second main result is a polynomial-time algorithm to compute a “proof sequence” establishing this bound. This proof sequence can then be incorporated in the PANDA-framework to give a faster algorithm to evaluate a conjunctive query. In addition, we show computational limitations to extending our results to broader classes of degree constraints. Finally, our technique leads naturally to a new relaxed upper bound called the flow bound , which is computationally tractable. 1. Introduction 1.1. Motivations Estimating a tight upper bound on the output size of a (full) conjunctive query is an important problem in query optimization and evaluation, for many reasons. First, the bound is used to estimate whether the computation can fit within a given memory budget. Second, cardinalities of intermediate relations are the main parameters used to estimate the cost of query plans [ 23 ] , and the intermediate size bound is used as a cardinality estimator [ 27 , 10 , 9 , 18 , 17 ] . These “pessimistic” estimators are designed to be robust [ 33 ] , removing the assumptions that lead to the well-documented impediment of selectivity-based estimators [ 21 ] , where the estimates often under approximate the real intermediate sizes by orders of magnitudes. Third, the bound is used as a yardstick to measure the quality of a join algorithm [ 26 ] . The history of bounding the output size of a conjunctive query (CQ) is rich [ 6 , 24 , 8 , 4 , 12 , 11 , 30 , 14 , 3 , 2 , 26 , 15 , 5 , 19 ] . In the simplest setting where the query is a join of base tables with known cardinalities, the AGM-bound [ 5 ] is tight w.r.t. data complexity. up to a O(2^{n}) factor, where n is the number of variables in the query. Join algorithms running in asymptotically the same amount of time are “worst-case optimal” [ 28 , 31 , 29 ] . In practice, however, we know a lot more information about the inputs beyond cardinalities. Query optimizers typically make use of distinct value counts, heavy hitters, primary and and foreign keys information [ 22 , 27 ] , in addition to function predicates. Every additional piece of information is a constraint that may drastically reduce the size of the query output. For example, in a triangle query R(a,b)\wedge S(b,c)\wedge T(a,c) , if we knew a was a primary key in relation R , then the output size is bounded by \min\{|T|,|R|\cdot|S|\} , which can be asymptotically much less than the AGM-bound of \sqrt{|R|\cdot|S|\cdot|T|} . To model these common classes of input statistics and key constraints, Abo Khamis et al. [ 2 , 3 ] introduced an abstract class of constraints, called degree constraints. 1 1 1 Degree constraints are also generalized to frequency moments collected on input tables [ 19 , 27 ] . A degree constraint is a triple (X,Y,c) , where X\subseteq Y are sets of variables, and 2^{c} is positive integer. The constraint holds for a predicate or relation R if \max_{\bm{x}}|\pi_{Y}\sigma_{X=\bm{x}}R|\leq 2^{c} , where \pi and \sigma are the projection and selection operators, respectively. The intuitive meaning of the triple (X,Y,c) is that the number of possible bindings for variables in Y can attain, given a particular binding of the variables in X , is at most 2^{c} . If X=\emptyset then this is a cardinality constraint , which says |\pi_{Y}R|\leq 2^{c} ; if c=0 (i.e. 2^{c}=1 ) then this is a functional dependency from X to Y . Given a set DC of degree constraints, and a full CQ Q ; we write \bm{I}\models\text{\sf DC} to denote that a database instance \bm{I} satisfies the constraints DC . A robust cardinality estimator is \sup_{\bm{I}\models\text{\sf DC}}|Q(\bm{I})| , the upper bound on the number of output tuples of Q over all databases satisfying the constraints [ 27 , 7 , 17 ] . We will refer to this bound as the combinatorial bound . For arbitrary degree constraints, it is not clear how to even compute it. Even in the simplest case when all degree constraints are cardinality constraints, approximating the combinatorial bound better than the 2^{n} -ratio is already hard [ 5 ] , where n is the number of variables in Q . Consequently, researchers have naturally sought relaxed upper bounds to the combinatorial bound that are (efficiently) computable, and that are as tight as possible [ 5 , 14 , 3 , 26 , 13 , 27 , 33 ] . Most of these bounds are characterized by two collections: the collection \mathcal{F} of set-functions h:2^{[n]}\to\mathbb{R}_{+} we are optimizing over, and the collection DC of (degree-) constraints the functions have to satisfy. Here, n is the number of variables in the query. Abusing notations, we also use DC to denote the constraints over set-functions: h(Y)-h(X)\leq c , for every (X,Y,c)\in\text{\sf DC} . Given DC and \mathcal{F} , define (1) \displaystyle\text{\sf DC}[\mathcal{F}]:=\sup\{h([n])\ |\ h\in\mathcal{F}\cap\text{\sf DC}\}. Different classes of \mathcal{F} and DC give rise to classes of bounds with varying degrees of tightness (how close to the combinatorial bound) and computational complexities [ 3 ] . This paper focuses on the polymatroid bound [ 3 , 19 ] , obtained by setting \mathcal{F}=\Gamma_{n} , the collection of all n -dimensional polymatroid functions. The upper bound \log_{2}\sup_{\bm{I}\models\text{\sf DC}}|Q(\bm{I})|\leq\text{\sf DC}[\Gamma_{n}] is the tightest known upper bound that is plausibly computable in polynomial-time [ 27 ] . (See Section 2 for more.) More precisely, the polymatroid bound \text{\sf DC}[\Gamma_{n}] for a collection \text{\sf DC}=\{(X_{i},Y_{i},c_{i})\mid i\in[k]\} of k degree constraints over variables X_{i}\subseteq Y_{i}\subseteq[n] , can be computed by solving: (2) \begin{array}[]{rrlll}\displaystyle\max&\lx@intercol h([n])\hfil\lx@intercol\\ \textrm{s.t.}&h(Y_{i})-h(X_{i})&\leq&c_{i}&\forall i\in[k]\\ &\displaystyle h&\in&\Gamma_{n}\end{array} The optimization problem ( 2 ) is a linear program (LP, see Sec. 2 ). with an exponential number of variables and constraints. In the query processing pipeline, for every query the optimizer has to issue many cardinality estimates when searching for an optimal query plan. Hence, solving the LP ( 2 ) in polynomial

Read the complete text