![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-1024x473.png\")
<\/figure>\n\n\n\nTo see this, consider a few graphs from the seminal 2015 benchmarking paper \u201cHow good are query optimizers really?\u201d. The first shows the performance of a few commercial query optimizers on the cardinality estimation problem. Even a series of battle-tested commercial optimizers consistently underestimate by orders of magnitude on this benchmark. Intuitively, this is because they all rely on some form of independence assumptions to simplify the problem. For instance, many of them assume that WHERE predicates on different columns randomly and independently filter rows. However, this assumption is almost always violated because columns are generally correlated, e.g. city and state columns.<\/p>\n\n\n\n The second figure demonstrates the performance of all possible plans for a few queries under different index configurations. For most queries, performance differs wildly between plans. A small proportion (~5%) of plans are within 10x of the optimal plan\u2019s performance, but the vast majority of plans are 2-4 orders of magnitude worse. In a perfect world, the query optimizer would simply choose the optimal plan, but this would require perfect cardinality estimates, which is impossible. Given this limitation, it makes sense to aim for an optimizer that simply avoids catastrophically bad plans. Most of these plans contain a sub-plan with a large intermediate join result which brings us to the core problem of underestimating cardinalities; A single underestimate of a large intermediate result can push the query optimizer to include that sub-plan, resulting in an overall plan that is much, much slower than the optimizer expects. For example, suppose that cardinality estimator A produces perfect cardinality estimates for 99% of intermediate results but drastically underestimates 1% of them. Despite estimator A\u2019s incredibly high average accuracy, the query optimizer will always select plans that incorporate these underestimated intermediates. On the other hand, suppose that cardinality estimator B produces perfect cardinality estimates for 99% of intermediates and drastically overestimates 1% of them. In this case, the query optimizer will simply ignore plans with bad estimates. If a single good plan is accurately estimated, then the optimizer will still produce a good query plan. In other words, systems that overestimate only need to be accurate for at least one<\/em> good plan, while systems that underestimate need to be accurate for every<\/em> bad query plan. This asymmetric risk is why recent benchmarks have shown much better performance when systems consistently produce overestimates. <\/p>\n\n\n\n Proposed methods for this problem have generally fallen into one of three categories: traditional, learned, and bound-based. Each of these angles has its own benefits and drawbacks to consider. We summarize the methods in all these categories, along with our newly proposed methods (FactorJoin and Safebound), in the following table.<\/p>\n\n\n\n The traditional cardinality estimators are the most commonly used method in DBMSes. The traditional histogram-based methods generally adopt attribute independence and join uniformity assumptions to decompose the join queries as a combination of single table estimates. They are very efficient, easy to train, update and maintain, thus perfect for system deployment. However, their simplifying assumptions can generate erroneous estimates and poor query plans.<\/p>\n\n\n\n Sampling-based methods also have a long history in the database community. There are two fundamental issues facing sampling methods: the exponential decline of sample sizes as the number of joins increases and how to handle estimates when the sample doesn\u2019t include any satisfying tuples. To illustrate the first problem, consider a simple FK-PK join where rows are sampled from R and S independently with probability p. The likelihood that a row in the sample of R joins with a row in the sample of S is 1\/p. Immediately, the sampling probability for tuples in R effectively goes from 1\/p to 1\/p^2. This becomes exponentially worse as more tables are added to the query. For the second, consider a query with a filter predicate that doesn\u2019t match any tuples in our sample of R. At this point, the estimation algorithm has some information to infer the number of tuples in R, but it has no information to estimate how the filtered subset of R would interact with other tables in the query. The most promising sampling methods, such as WanderJoin, tend to avoid this problem by using dynamic sampling rather than computing samples offline, and they achieve very robust accuracy. However, this introduces further concerns about the maintenance of indices, the latency of accessing data during optimization, and increased code complexity.<\/p>\n\n\n\n \u03a4he learned cardinality estimators use the machine learning (ML) model to relax or eliminate the simplifying assumptions made by traditional methods. Their sophisticated ML models can provide accurate estimation but are subject to expensive training\/updating costs and slow inference speed.<\/p>\n\n\n\n Query-driven ML methods learn cardinality estimates by running an example workload of queries and training a traditional ML model from the resulting (query, cardinality) pairs. These methods can achieve high accuracy on the queries which come from the same distribution as the example workload, and they are often very fast to both train and perform inference. However, running these example queries can be very time-consuming, and they often suffer significantly when faced with updates or queries that differ significantly from the example workload.<\/p>\n\n\n\n Data-driven ML methods use unsupervised approaches which attempt to learn the data distribution directly rather than training on example queries. This allows for generalization to different query workloads and can be accurate depending on the complexity of the underlying models. However, the model complexity needed for accurate estimates grows quickly due to the inherent challenge of modeling all the complicated non-linear relationships between columns both within and between tables. Because of this, they generally take a long time to train and are slow to perform inference on, and have problems scaling to complicated schemas. <\/p>\n\n\n\n The last approach is grounded in database theory and provides provable upper bounds on the query size rather than an average-case estimate. When used in place of traditional estimates, this guarantees that there will be no underestimates. Because bounds on query sizes are helpful for complexity analysis, these bounds have been thoroughly studied by the theory community and have motivated areas of algorithm design, such as worst-case-optimal join algorithms. However, the bound formulas, which are interesting to theoreticians, have generally relied on minimal statistics about the underlying dataset, e.g., the size of each table and the maximum frequency of each column. This provides good interpretability and insight, but it generally does not result in tight bounds that could be practically used by a query optimizer. The paper \u201cPessimistic Cardinality Estimation\u201d was the first work to attempt to adapt these formulas to cardinality estimation, and it managed to produce fairly tight bounds, which significantly improved query execution time. However, it couldn\u2019t handle filter predicates (e.g., \u201cR.A < 10\u201d), and its inference latency increased exponentially in the granularity of its statistics.<\/p>\n\n\n\n To effectively support filter predicates and enable efficient inference, we describe two novel practical bound-based cardinality estimators: FactorJoin and SafeBound. FactorJoin formulates the problem of cardinality estimation of general multi-table join queries as a well-studied inference problem in the field of probabilistic graphical models. FactorJoin can quickly construct a factor graph model from the database schema in the offline phase, which will be used to efficiently deliver a probabilistic cardinality bound for any query. SafeBound draws on recent theoretical advances in cardinality bounding to produce deterministic bounds using degree sequence statistics.<\/p>\n\n\n\n These two approaches inherit the robustness of bound-based cardinality estimators while overcoming their drawbacks to provide flexible and efficient inference. The experimental results demonstrate that FactorJoin and SafeBound can achieve up to 80% lower end-to-end runtimes than PostgreSQL on well-established benchmarks. This performance is comparable to or better than the state-of-the-art (SOTA) machine learning methods. Furthermore, FactorJoin can achieve 40x less estimation latency, a 100x smaller model size, and 100x faster training\/updating than the previous SOTA methods. SafeBound can save up to 500x in query planning latency and 6.8x less space when compared to previous SOTA methods.<\/p>\n\n\n\n Before looking at the formulation, let\u2019s go through a simple example of a query joining two tables. The figure above illustrates query ? joining tables ? and ? on the inner join1 condition ?.?? = ?.??? with base table filter predicates ?(?) and ?(?). Table ? first goes through the filter ?(?), resulting in an intermediate table ?|?(?) (records in ? that satisfy the filter ?(?)). The same procedure is applied to table ?. Then, the query ? will match the value of join keys ?.?? and ?.??? from these two intermediate tables. Specifically, the value ? appears 8 times in table ?|?(?) and 6 times in table ?|?(?), resulting in value ? appearing 48 times in the join result. Therefore, we can calculate the cardinality of this query ? as 8 \u00d7 6 + 4 \u00d7 5 + 3 \u00d7 5 = 83. <\/p>\n\n\n\n We can formulate the above procedure for calculating ? as a statistical equation, where ?(?.??) denotes the domain of all unique values of ?.??. We observe that only single-table distributions ? and ? are required to accurately compute the ?? cardinality of this join query. Also in this equation, ??<\/sub>(?.?? = ?|?(?)) \u2217 |?(?)| equals to ??<\/sub>(?.?? = ? \u2227 ?(?)) \u2217 |?|, which is exactly what single-table CardEst methods estimate. Thus, we can accurately calculate the cardinalities of two-table join queries using single-table estimators. Note that the summation over the domain of join key D(?.??) has the same complexity as computing the join. Therefore, we need to approximate this calculation for FactorJoin to be practical.<\/p>\n\n\n\n A general join query can involve a combination of different forms of joins (e.g., chain, star, self, or cyclic joins), so its counterpart equation of Equation 1 can be very difficult to derive and compute. We provide a generalizable formulation that automatically decomposes join queries into single-table estimations using the factor graph model. Let\u2019s take a look at a more complicated example below.<\/p>\n\n\n\n <\/p>\n\n\n\n Figure (i) shows a SQL query ? joining four tables ?,?,?,?. We visualize its join template as a graph in Figure 3-(ii), where each dashed rectangle represents a table, each ellipse (node) represents a join-key in ?, and each solid line (edge) represents an equi-join relation between two join keys connected by it. Note that both sides of an equi-join relation represent the semantically equivalent join keys. We call them equivalent key group variables. In Figure (ii), there are three connected components and thus three equivalent key group variables?1<\/sub>,…,?3<\/sub>. ?1<\/sub> represents ?.?? and ?.??? in this group since ? contains the join condition ?.?? = ?.???. <\/p>\n\n\n\n Next, we explain how to compute the cardinality of ? using a factor graph. Let\u2019s first explain what a factor graph is. A factor graph is a bipartite graph with two types of nodes: variable nodes, and factor nodes representing an unnormalized probability distribution w.r.t. the variables connected to it. Figure (iii) shows the constructed factor graph F<\/em> for computing the cardinality of ?. Specifically, F<\/em> contains a variable node for each equivalent key group variable ?, and a factor node for each table ? touched by ?. A factor node is connected to a variable node if the variable represents a key in the table. In this case, the factor node representing table ? is connected to ?1<\/sub> (equivalent to ?.??) and ?2<\/sub> (equivalent to ?.??2<\/sub>). Each factor node maintains an unnormalized probability distribution for the variable nodes connected to it, e.g., node ? maintains ??<\/sub>(?1<\/sub>,?2<\/sub>|(?(?))) \u2217 |?(?)|, which is the same as the distribution ??<\/sub>(?.??, ?.??2<\/sub>|(?(?))) \u2217 |?(?)|. The factor graph model utilizes the graph structure to compute the sum using well-studied inference algorithms. We can more formally state this relationship between computing the join cardinalities and factor graphs as the following lemma, whose proof is provided in the original paper. <\/p>\n\n\n\n Lemma1<\/strong>: Given a join graph G<\/em> representing a query ?, there exists a factor graph F<\/em> such that the variable nodes in F<\/em> are the equivalent key group variables of G<\/em> and each factor node represents a table ? touched by ?. A factor node is connected to a variable node if and only if this variable represents a joining key in table ?. The potential function of a factor node is defined as table ?\u2019s probability distribution of the connected variables (join keys) conditioned on the filter predicates ?(?). Then, calculating the cardinality of ? is equivalent to computing the partition function of F<\/em>.<\/p>\n\n\n\n The computation of such probabilistic inference on this factor graph is very expensive. The complexity is O(N * |D|max(|JK|)<\/sup>), where N is the number of equivalent key groups (3 in the above example), |D| is the largest domain size of all join keys, and ???(|??|) is the maximum number of join keys in a single table (2 in the above example). This complexity of conducting exact inference is not practical for real-world queries, as |D| can be millions, and ???(|??|) can be larger than 4 in real-world DB instances, such as IMDB.<\/p>\n\n\n\n Therefore, in the following, we will show how FactorJoin designs approximate probabilistic inference on factor graph to estimate the cardinality, which reduces the complexity to O(N * k2<\/sup>) where N (less than 10) and k are typically small (hundreds). <\/p>\n\n\n\n The key idea behind our bound-based approximate probabilistic inference on factor graph is to bin the domain D of the join key into k bins where we can compute an upper bound of cardinality within each bin. This helps reduce the complexity |D| to k, and users can arbitrarily set the number of bins k for performance-latency trade-offs. For example, Equation (1) above can be approximated as Equation (2).<\/p>\n\n\n\n Now, we will illustrate the probabilistic bound the within each bin using a simple example query Q joining two tables. Specifically, assuming that value {?, ?, ?, ?, ? } of ?.?? and ?.??? are binned into ???1 as shown in Figure 5. We know the summation of all values in bin1<\/sub> equals to 8\u00d76+4\u00d75+3\u00d75=83. This summation has a dominating term of 8 \u00d7 6, because the count of MFV of bin1<\/sub> is 8 for ?.?? (denoted as ?1<\/sub>*<\/sup>(?.??)) and 6 for?.??? (denoted as ?2<\/sub>*<\/sup>(?.???)) so each value can appear at most 8 \u00d7 6 times in the denormalized table after the join. Since we know the total count of values in bin1<\/sub> for ?.?? is 16, there can be at most 16\/8 = 2 MFVs. Similarly, there can be at most 4 MFVs in bin1<\/sub> for ?.???. Therefore, we have the summation of all values in bin1<\/sub> is upper bounded by ???(2, 4) \u00d7 8 \u00d7 6 = 96. <\/p>\n\n\n\n We formally represent the aforementioned procedure in Equation (3),where ?i<\/sub>\u2217<\/sup>(?.??) and ??<\/sub>(?.?? \u2208???i<\/sub>|?(?)) \u2217 |?(?)| are the MFV count and estimated total count of ???i<\/sub> for?.??. Our bound is probabilistic because ??<\/sub>(?.?? \u2208 ????<\/sub>|?(?)) \u2217 |?(?)| is estimated with a single table CardEst method, which may have some errors.<\/p>\n\n\n\n We evaluate the performance of our CardEst framework on two well-established benchmarks: STATS-CEB and IMDB- JOB and compare with a wide range of representative baselines, including traditional methods (PostgreSQL, JoinHist, WJSample), learned methods (MSCN, BayesCard, DeepDB, FLAT), bound-based methods (PessEst, U-Block) and the optimal baseline with true cardinality (TrueCard). The overall performance plots and tables are given below.<\/p>\n\n\n\n To summarize, FactorJoin achieves the best performance among all the baselines on both benchmarks. Specifically, FactorJoin is as effective as the previous state-of-the-art learned methods, and simultaneously as efficient and practical as the traditional CardEst methods. <\/p>\n\n\n\n Our goal in SafeBound was to make the theoretical work on cardinality bounding practical without sacrificing the deterministic, provable nature of the bounds. So, to understand SafeBound, we need to start by introducing the Degree Sequence Bound, which SafeBound is based on, and the degree sequence statistics, which that is based on.<\/p>\n\n\n\n The degree sequence of a column in a database is the sorted list of value frequencies<\/em>. As an example, consider the \u201cName\u201d column below and the accompanying degree sequence on its right. The name \u201cEseah\u201d is the most frequent value and appears 5 times, so there is a 5 at the start of the degree sequence. Carlos and Vivek both appear 3 times and so on.<\/p>\n\n\n\n This statistic has a few nice characteristics that we take advantage of in our work: 1) it fully captures the skew of join columns, 2) it is monotonic and decreasing, 3) we can upper bound it very efficiently with simple piecewise constant functions. We can see all of these on a degree sequence from the IMDB dataset below. Specifically, this is the ActorID column in the CastInfo table, where each row represents a single actor being cast in a single movie or TV show. The most-cast actor appeared ~10,000 times, while over half of the actors appeared just a single time. Further, the true degree sequence is 4 million data points because there are over 4 million unique actors, but the approximation shown in green is only 7 segments while largely capturing the shape of the curve.<\/p>\n\n\n\n Without going into the mathematical details, the Degree Sequence Bound can be thought of as a black box algorithm. It takes in 1) a simple join query (only joins, no selections) and 2) the degree sequence approximations of every join column, and it outputs a provable, deterministic bound on the size of the query\u2019s output. Further, it does this in log-linear time with respect to the size of the approximations, so it\u2019s very fast when the approximations are small (~20 segments in our experiments).<\/p>\n\n\n\n![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-1-3.png\")
<\/figure>\n\n\n\nRecent CardEst Methods<\/h3>\n\n\n\n
![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-2-1024x753.png\")
<\/figure>\n\n\n\nTraditional Approaches<\/h4>\n\n\n\n
Learned Approaches<\/h4>\n\n\n\n
Previous Cardinality Bounds<\/h4>\n\n\n\n
Our Practical Cardinality Bounds<\/h4>\n\n\n\n
FactorJoin<\/h3>\n\n\n\n
Formulating Cardinality Estimation as PGM Inference Problem<\/strong><\/h4>\n\n\n\n
![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-3-1024x256.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-4-1024x112.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-5-1-1024x406.png\")
<\/figure>\n\n\n\nEfficient bound-based cardinality estimation<\/h4>\n\n\n\n
![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-6-1024x236.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-7-1024x298.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-8-1-1024x234.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-9-1-1024x250.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-10-1024x555.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-11-1024x392.png\")
<\/figure>\n\n\n\nSafeBound<\/h3>\n\n\n\n
The Degree Sequence Bound<\/h4>\n\n\n\n
![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-12.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-13-1024x683.png\")
<\/figure>\n\n\n\n
![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-14.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/07\/unnamed-15-1024x572.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/09\/unnamed-17.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/09\/Kyle_Deeds_Headshot_resized.jpg\")
<\/figure>![\"\"](\"https:\/\/wp.sigmod.org\/wp-content\/uploads\/2023\/09\/ziniu-ID_photo.jpeg\")
<\/figure>