Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries

The focus of this paper is on streaming data analysis, a prominent application area for synopsis data structures (Gibbons and Matias, 1999), which involves real-time processing of data that arrives at a high frequency. Streaming data naturally arises in many big data applications, including network traffic monitoring (Cormode et al., 2003; Dobra et al., 2002), recommendation systems (Huang et al., 2015; Chen et al., 2013, 2020), natural language processing (Goyal et al., 2012), smart cities (Giatrakos et al., 2017; Biem et al., 2010), and analysis of market data in financial systems (Cao et al., 2014; Ross et al., 2011; Stonebraker et al., 2005). Algorithms for streaming data are designed to handle data that can only be observed once, in arbitrary order, as it continuously arrives (Dobra et al., 2002). Consequently, these algorithms must be highly efficient in processing each input, while utilizing limited memory resources, to keep up with the rapid influx of new data.

By presenting our method within the streaming data setting, we establish its applicability to a broad range of scenarios. This is because streaming algorithms are also applicable when multiple data accesses or a specific access order are allowed. Inversely, algorithms that require multiple data accesses or a specific access order, like many learning-based methods, clearly do not apply in a streaming data setting. Even when a streaming algorithm is not strictly necessary, optimizing for fewer data accesses remains advantageous because it minimizes potentially costly I/O operations.

We formulate the problem as follows, based on Cormode and Muthukrishnan (2005): consider a vector ${\bm{f}}(t)\in\mathbb{R}^{n}$, which is assumed too large to be stored explicitly and is therefore presented implicitly in an incremental fashion. Starting as a zero vector, ${\bm{f}}(t)$ is updated by a stream of pairs $(i_{t},\Delta_{t})$ which increments the $i_{t}$-th element by $\Delta_{t}$, meaning that ${f}_{i_{t}}(t)={f}_{i_{t}}(t-1)+\Delta_{t}$, while the other dimensions remain unchanged. The items $i_{t}$ are members of the domain¹¹1Without loss of generality, we can assume $i\in[n]$ (Dobra et al., 2002; Ganguly et al., 2004). $[n]=\{0,1,\dots,n-1\}$; $\Delta_{t}\in\mathbb{R}$ are the changes in frequency and ${\bm{f}}(t)$ is called the frequency vector. At any time $t$, a query may request the computation of a function on ${\bm{f}}(t)$. Specific streaming settings are further classified by their type of updates, as follows:

• •

  cash-register: $\Delta_{t}>0$ on every update;

• •

  strict turnstile: for some updates $\Delta_{t}$ can be negative, but ${f}_{i}(t)\geq 0$ for all $i$ and $t$;

• •

  general turnstile: both updates and entries of the vector ${\bm{f}}(t)$ can assume negative values at any time $t>0$.

The algorithms we discuss utilize synopsis data structures to efficiently handle data streams, eliminating the need to explicitly store and compute over ${\bm{f}}(t)$ to answer a set of supported queries. In the following section, we will introduce a group of sketching techniques known as linear sketches. This family of methods, which includes the approach proposed in this paper, is designed to support the most general streaming setting, i.e., the general turnstile.

Sketching techniques are a popular set of methods for dealing with streaming data and approximate query processing (Cormode, 2011). Both the baselines and the method proposed in this paper are linear sketches, meaning that the summaries they generate can be represented as a linear transformation of the input. In contrast, the Bloom filter (Bloom, 1970) serves as a classic example of a non-linear sketch.

Formally, for a given vector ${\bm{x}}\in\mathbb{R}^{n}$, we define a linear sketch as a vector obtained by ${\bm{\Pi}}{\bm{x}}$, where ${\bm{\Pi}}\in\mathbb{R}^{m\times n}$ is some random matrix, and $m\ll n$. The linearity of the transformation offers notable advantages (Cormode, 2011): it allows for processing items in any order and combining different sketches through addition. This enables efficient handling of data and supports map-reduce style processing of large data streams. In every sketching method, the random matrix is thoughtfully designed to enable the estimation of one or multiple functions over ${\bm{x}}$, utilizing only its “summary” captured by ${\bm{\Pi}}{\bm{x}}$, thereby eliminating the necessity for accessing ${\bm{x}}$ itself. When sketching techniques are used in a streaming scenario they are often referred to as frequency-based sketches, where the input vector ${\bm{x}}$ is the frequency vector ${\bm{f}}(t)$ defined in Section 2.1. Hereafter, we will omit the time argument from the frequency vector for brevity.

At this point, one naturally wonders: how can we transform the vector ${\bm{f}}$ of size $n$, which is already considered too large, using a matrix ${\bm{\Pi}}$ that is even larger with size $mn$? Streaming algorithms cleverly represent the matrix ${\bm{\Pi}}$ succinctly using hash functions, enabling them to generate just the column of ${\bm{\Pi}}$ that is needed to add a given item. Further details on this process will be provided later. Furthermore, it is crucial to ensure that the sketch is efficiently updated as ${\bm{f}}$ changes, i.e, as new items stream in. This can be achieved by making ${\bm{\Pi}}$ sparse, as we will explore shortly. The effectiveness and versatility of a sketching method primarily relies on the following key properties (Cormode, 2011):

• •

  Sketch size: The total number of counters and random seeds required by the sketch, determined by the parameter $m$.

• •

  Initialization time: The time it takes to initialize the sketches. Typically, this involves simply setting a block of memory to zeros, and sampling the random seeds for the hash functions.

• •

  Update time: In streaming settings, algorithms must keep pace with the high influx of items. The update time determines the highest item throughput rate that can be sustained.

• •

  Inference time: The time it takes to compute an estimate from the generated sketches.

• •

  Accuracy: It is crucial to understand the accuracy of an estimator for a given memory budget (limiting the sketch size) and throughput requirement (constraining the update time).

• •

  Supported queries: Each sketch is designed to enable estimation of a specific set of functions on the input vector. Typically, a query-specific procedure needs to be performed on the sketch to approximate the value of a particular function.

In the following, we will describe some important sketching methods from the existing literature that have particularly space- and time-efficient ways of representing and computing ${\bm{\Pi}}{\bm{f}}$.

The AMS sketch, also referred to as the Tug-of-War or AGMS sketch, is a pioneering technique for frequency-based sketching that was first introduced by Alon, Matias, and Szegedy (AMS) (Alon et al., 1996). The method was originally proposed as a way to estimate the second frequency moment $F_{2}$ of a data stream, where $F_{2}=\lVert{\bm{f}}\rVert^{2}_{2}=\sum_{i=0}^{n-1}{f}_{i}^{2}$ and ${\bm{f}}$ is the frequency vector of the stream as defined in Section 2.1. The AMS sketch is represented by a vector ${\mathbf{c}}$, containing $m=O(1/\epsilon^{2})$ counters ${\textnormal{c}}_{j}$, for $j\in[m]$, where $0<\epsilon<1$ is the relative error bound. The counters are i.i.d. random variables obtained by ${\textnormal{c}}_{j}=\sum_{i=0}^{n-1}{f}_{i}s_{j}(i)$, where each $s_{j}:[n]\to\{-1,+1\}$ is drawn from a family of 4-wise independent hash functions (see Definition 2.1). These hash functions are used to compute the random projection ${\bm{\Pi}}{\bm{f}}$ without representing ${\bm{\Pi}}$ explicitly, since ${\Pi}_{j,i}=s_{j}(i)$. To establish a confidence level $\delta$, one can take the median of $O\lparen\log 1/\delta\rparen$ independent estimates. The overall method then requires only $O\lparen\lparen 1/\epsilon^{2}\rparen\log 1/\delta\rparen$ counters. Taking the median of i.i.d. estimates, sometimes called the “median trick”, is universal among sketching methods because it is an effective way to rapidly improve the confidence level of an estimate by the Chernoff Bound (Alon et al., 1996). We will, therefore, revisit this concept in the subsequent discussions of other methods.

In their original work, Alon et al. (1996) showed that $\frac{1}{m}\langle{\bm{\Pi}}{\bm{f}},{\bm{\Pi}}{\bm{f}}\rangle$ is an unbiased estimator of $F_{2}$. In fact, it can be demonstrated more generally that for any two vectors ${\bm{f}}$ and ${\bm{g}}$, the normalized inner product of their AMS sketches $\frac{1}{m}\langle{\bm{\Pi}}{\bm{f}},{\bm{\Pi}}{\bm{g}}\rangle$ is an unbiased estimator for their inner product $\langle{\bm{f}},{\bm{g}}\rangle$ (Alon et al., 1999). Notably, when ${\bm{f}}$ and ${\bm{g}}$ correspond to the frequency vectors of a given attribute of two database relations, this estimated value corresponds to the equi-join size of these relations over that attribute. Theorem 2.2 formally states the expectation, and bounds the variance of the AMS sketch.

In order to ensure fast sketch updates, i.e., sublinear with respect to its size $m$, it is desirable for sketching methods to use a sparse linear transformation ${\bm{\Pi}}$ when processing input vectors. However, note that the AMS sketch requires changes in all $m$ counters for each update. Consequently, the accuracy of the estimator is constrained by the need to maintain a throughput that corresponds to the rate of incoming items as well as the available memory budget.

The Count sketch is another linear sketching method that emerged after AMS and overcomes this limitation by allowing the update time to be independent of the sketch size. It achieves this by employing a technique called the “hashing trick,” (Weinberger et al., 2009; Cormode, 2011) which ensures that only one counter per estimate is modified during each update. As a result, the Count sketch improves the update time complexity from $O\lparen\lparen 1/\epsilon^{2}\rparen\log 1/\delta\rparen$ to just $O\lparen\log 1/\delta\rparen$, while maintaining not only the same error bounds, but also the same space and inference time complexities as the AMS sketch. The AMS sketch and Count sketch update procedures are compared in Figure 2. Although the Count sketch was originally introduced for the heavy hitters problem (Charikar et al., 2002), the same hashing trick can be applied to speed up the AMS sketch, which is commonly known as the Fast-AMS sketch (Cormode and Garofalakis, 2005).

The value of each counter in the Count sketch is given by ${\textnormal{c}}_{j}=\sum_{i=0:h(i)=j}^{n-1}{f}_{i}s(i)$, where $h:[n]\to[m]$ is a random bin function drawn from a family of 2-wise independent hash functions, and $s:[n]\to\{-1,+1\}$ is again a random sign function drawn from a family of 4-wise independent hash functions. The corresponding random matrix ${\bm{\Pi}}$ is specified by ${\Pi}_{j,i}=s(i)\operatorname{\mathbf{1}}(h(i)=j)$. Notice that ${\bm{\Pi}}$ has only one non-zero value per column, making it highly sparse. Also, the Count sketch requires only one sign and bin hash function per estimate, regardless of the required precision, resulting in a further reduction in memory usage. An estimate is obtained by taking the inner product between sketches. Theorem 2.3 formally states the expectation and bounds the variance of the Count sketch.

The Count sketch has also been shown to outperform the AMS sketch in estimation precision for skewed data distributions (Rusu and Dobra, 2008). This is because the Count sketch is able to separate out the few high frequency components with high probability. This is an important trait, as it has been widely acknowledged in the literature that the majority of real-world data distributions exhibit a skewed nature (Dobra et al., 2002; Leis et al., 2015; Manerikar and Palpanas, 2009; Yang et al., 2017; Roy et al., 2016). We further discuss this topic in Section 4.1.

The Count sketch was originally introduced for single-dimensional data which is represented by the frequency vector ${\bm{f}}$. More recently, however, several extensions to the Count sketch have been proposed which enable its usage for higher-dimensional data represented by a frequency tensor ${\bm{\mathcal{F}}}$ instead (Liu et al., 2022). The most notable extensions are the Tensor sketch (Pham and Pagh, 2013) and the Higher-Order Count (HOC) sketch (Shi and Anandkumar, 2019). Both methods set out to reduce the computational complexity of machine learning applications. The Tensor sketch was used to approximate the polynomial kernel, but finds its origin in estimating matrix multiplication (Pagh, 2013). The HOC sketch was introduced to compress the training data or neural network parameters, in order to speed up training and inference processes.

For each incoming item of the stream, both methods start by encoding all axes separately using independent instances of the Count sketch. They differ in the way these individually sketched axes are combined: the Tensor sketch employs circular convolution (see Definition 2.4), generating a sketch vector, whereas the HOC sketch utilizes the tensor product to produce a sketch tensor of the same order but with reduced dimensions compared to ${\bm{\mathcal{F}}}$. The use of the tensor product ensures that axis information about the sketched data is preserved, at the cost of an exponential increase in sketch size with the order of the tensor. The circular convolution, in contrast, preserves the dimensionality of the sketch vector for any tensor order, i.e., it maps tensors to vectors.

In the context of databases, COMPASS (Izenov et al., 2021) uses HOC sketches to estimate the cardinality of multi-join queries. They additionally propose a method to approximate HOC sketches by merging Count sketches. While they show promising results for query optimization, their estimation method lacks theoretical error guarantees. Moreover, Section 4.2 will show that, in practice, our proposed method achieves significantly higher estimation accuracy. The Tensor sketch (see Definition 2.5) is the most related to our method, however, our method and application are novel and solves an important open problem in the streaming and databases community, as will be detailed in Section 3.

Another significant advancement in linear sketching techniques emerged around the same period as the Count sketch. Dobra et al. (2002) proposed a generalization of the AMS sketch that enables the estimation of complex multi-join aggregate queries, such as count and sum queries. These estimates are useful for big data analytics and query optimization (Leis et al., 2015). The proposed method addresses the scenario where a query $Q(R_{0},R_{1},\dots,R_{r-1})$ involves multiple relations $R_{k}$ for $k\in[r]$. An example is illustrated in Figure 3, which provides an intuitive visualization of this type of complex query as a disconnected, undirected graph. In this abstraction, each vertex corresponds to an attribute, edges represent the joins between them, and attributes are grouped to form relations.

The technique generates sketches for each relation by iterating over all the tuples $i$ in each relation once. This iterative traversal of the tuples aligns with the streaming data scenario described in Section 2.1, enabling the sketches to be created on-the-fly as the relations are updated. The sketch ${\bm{c}}_{k}$ for relation $R_{k}$ is given by:

where we use the following notation: $i$ represents a tuple that belongs to the domain $I_{k}$ of relation $R_{k}$; $I_{k}$ is the cross product of item domains $[n]\times\cdots\times[n]$ for each joined attribute of relation $R_{k}$; ${\mathcal{F}}_{k}(i)$ gives the frequency of tuple $i$ in relation $R_{k}$; $i_{u}$ denotes the value in tuple $i$ for attribute $u$; $u$ is an attribute from the set of joined attributes of $R_{k}$ in the query, denoted as $\Omega(R_{k})$ (for example, $\Omega(R_{1})=\{1,2\}$ in Figure 3); $v$ is an attribute from the set of attributes joined with $u$, denoted as $\Gamma(u)$ (for example, $\Gamma(1)=\{0,3\}$ in Figure 3). We represent a join between two attributes with $\{u,v\}$. Both $u,v\in[w]$ are from the set of all joined attributes. Our notation assumes that all attributes are globally unique, which can easily be achieved in practice, for instance, by concatenating the relation and attribute names. Moreover, following Dobra et al. (2002), we assume that joins are non-cyclic, a self-join is thus represented as a join with a fictitious copy of the relation. It is worth noting that the copy does not need to be physically created, this is done solely to simplify the notation. Note also that the functions $\Gamma$ and $\Omega$ are defined for a specific query $Q$. We omit this dependence in the notation for brevity, as it is evident from their definitions.

Once the sketches are created, a query estimate is derived by performing the element-wise multiplication of the sketches, often referred to as the Hadamard product of sketches. This is followed by calculating the mean over the counters. Formally, this can be expressed as: $X=\frac{1}{m}\sum_{j=0}^{m-1}\prod_{k=0}^{r-1}{c}_{k,j}$, where $X$ is an unbiased estimate of the cardinality of query $Q$. The expectation and variance of $X$ are formally stated in Theorem 2.6.

From the perspective of the Count sketch extensions discussed in Section 2.5, this method can be interpreted as a similar generalization but for the AMS sketch. It can thus be seen as one of the first methods to generalize sketching for tensor data, although this aspect was not explicitly mentioned in the original work.

In this section, we discuss other recent work in cardinality estimation. The Pessimistic Estimator (Cai et al., 2019) is an interesting sketching technique which provides an upper bound of the cardinality. They show that it improves upon the cardinality estimator within PostgreSQL. However, the practical use of the method is limited due to its lengthy estimation time (Han et al., 2021), at times exceeding the query execution time, as also mentioned by the authors.

Since the inception of sketching, a number of techniques have been proposed that complement the aforementioned sketches. Among these techniques, the Augmented Sketch (Roy et al., 2016) and the JoinSketch (Wang et al., 2023) aim to improve the accuracy of sketches for skewed data by separating the high- from the low-frequency items in the sketch. The counters of the high-frequency items are explicitly represented in an additional data structure, thereby preventing them from causing high estimation error due to hash collisions. Another notable technique is the Pyramid sketch (Yang et al., 2017), which employs a specialized data structure that dynamically adjusts the number of allocated bits for each counter, preventing overflows in the case of high-frequency items. It is important to note that these techniques are proposed as complementary tools, compatible with a variety of sketching methods, including the one proposed in this work.

Recently, there has been a parallel effort aimed at harnessing the power of machine learning for cardinality estimation. Among the various approaches, the most promising ones are data-driven methods that build query-independent models to estimate the joint probability of tuples (Han et al., 2021). Notable examples of such techniques include DeepDB (Hilprecht et al., 2020), BayesCard (Wu et al., 2020), NeuroCard (Yang et al., 2020), and FLAT (Zhu et al., 2021). While machine learning-based cardinality estimation techniques have been receiving increasing attention, they still face important limitations: these methods are presently viable only in scenarios where supervised training is feasible, their accuracy has not consistently lived up to expectations (Müller, 2022), and they prove impractical in situations with frequent data updates, such as streaming settings, due to their high cost of model updates (Han et al., 2021). In Section 4.4, we demonstrate that our proposed method not only avoids these performance limitations but also achieves significantly higher accuracy compared to the machine learning techniques.

We start with an intuitive discussion on the main insight behind the proposed method, using the example illustrated in Figure 4. The main challenge of combining the Count sketch with the method proposed by Dobra et al. (2002) lies in the inability to effectively merge Count sketches using the Hadamard product. Dobra et al. (2002) create the sketch for a tuple as the Hadamard product of the AMS sketches for each value in the tuple. As discussed earlier, the advantages of the Count sketch stem from its sparsity. However, as illustrated in the left part of the figure, it is precisely this characteristic that results in a loss of information, with high probability, when combining sketches with the Hadamard product. Essentially, due to the sparsity, the non-zero entry in each sketch is highly likely to appear at a different position, causing the result of the element-wise multiplication to yield a zero vector, devoid of information.

To address this issue, the core concept behind our method, as depicted in the right part of Figure 4, involves the utilization of circular convolution paired with circular cross-correlation (see Definitions 2.4 and 3.1) during inference. With circular convolution, the resulting sketch has the product of the non-zero entries in the bin that corresponds to the sum of the non-zero indices, modulo $m$. Unlike the Hadamard product, this operation guarantees that the information is preserved. We will delve deeper into this intuition and formalize it in the subsequent sections. Crucially, the circular convolution of single-item Count sketches can be computed in $O(1)$ time, with respect to the sketch size $m$. This means that the sketch of a stream can be updated in constant time for each arriving tuple, in contrast to the $O(m)$ time required by the AMS sketch with the Hadamard product. As we will show empirically in Section 4.3, this translates to sketch updates that are orders of magnitude faster.

In order to facilitate a better understanding of the proposed method, we begin by demonstrating it through an illustrative example query. By showcasing the estimation process, we aim to provide valuable insights into the inner workings of our method. Following this, we formally present the method through its pseudocode. Furthermore, we prove that our method is an unbiased cardinality estimator for the previously defined family of multi-join queries and provide bounds on the estimation error. A general overview of our estimation procedure is provided in Algorithm 1. In the following description, we shall use the example query from Figure 3.

Now that we have discussed the estimation procedure, we present a theoretical analysis of the proposed method. We show that it is an unbiased estimator for the cardinality of multi-join queries in Theorem 3.2, and provide guarantees on the estimation error. Lastly, we provide the time complexity for each estimation stage.

Using the Chebyshev inequality and the upper bound on the variance from Theorem 3.2, we can bound the absolute estimation error by $\epsilon>0$ with $m\geq 3^{r}\epsilon^{-2}\prod_{k=0}^{r-1}\left\lVert{\bm{\mathcal{F}}}_{k}\right\rVert^{2}_{2}$. Furthermore, to guarantee the error with probability at most $1-\delta$, one selects the median of $l=O(\log{1/\delta})$ i.i.d. estimates by the Chernoff bound (Alon et al., 1996). The exponential term $3^{r}$ indicates that accurately estimating queries involving many relations quickly becomes infeasible. It remains an open problem whether this exponential dependence can be improved. However, as we will show in the following section, for moderate sized queries, involving up to 6 relations, our estimation accuracy constitutes a significant improvement over the baselines.

In Table 2, we present the time complexity of each estimation stage, comparing our method with the AMS-based technique by Dobra et al. (2002) and the two variations of COMPASS (partition and merge) (Izenov et al., 2021). The symbols $r$, $l$, and $m$ denote the number of relations, medians, and the sketch size, respectively. The update time of our method for each incoming tuple is remarkably efficient, with a time complexity of only $O(r\log{1/\delta})$. The efficient update time complexity, independent of the estimation error $\epsilon$, enables the sketching of high-throughput streams even when requiring a high level of accuracy. While COMPASS also has fast updates, its exponential dependence on $r$ during inference limits its practical use even for moderately sized queries. Our method achieves fast updates yet introduces only an additional $\log m$ term during the inference stage, compared to the AMS baseline. This slight increase in inference time is negligible when considering the substantial improvement in update time. For instance, our experiments go up to $m=10^{6}$ with $l=5$, which means that our method achieves roughly $10^{6}$ times faster sketch updates, while having only $\log_{2}(10^{6})\approx 20$ times slower inference. As a result, our method effectively minimizes the overall estimation time in various crucial scenarios. These claims are further supported by our empirical results, which are detailed in Section 4.

The quintessential application of our proposed method is the cardinality estimator within query optimizers. Query optimizers use a plan enumeration algorithm to find a good join order. The cost of a join order dependents upon the sizes of the intermediate results. The cardinality estimator’s role is to provide the estimates for these intermediate sizes (Lan et al., 2021). Each intermediate cardinality can be expressed as a sub-query which our method can estimate. The sketches for all the evaluated sub-queries can be created in a single pass over the data. Typically, each sub-query requires its own sketches; however, in cases where an attribute is joined multiple times, the sketches can be reused for each join involving that attribute. For example, to decide the join order of joins $\{0,1\}$ and $\{1,3\}$ in Figure 3, the sketch for attribute 1 can be reused for attributes 0 and 3. In Section 4.5, we demonstrate the improvement in query execution time after integrating our proposed cardinality estimator into the query optimizer of PostgreSQL.

The limitations of synthetic databases in accurately reflecting real-world performance have been widely acknowledged in the literature (Leis et al., 2015; Han et al., 2021). To address this concern, our experiments were conducted using two established benchmarking databases containing real data: the IMDB database (Leis et al., 2015), which encompasses information on movies, actors, and their associated production companies, and the STATS database (Han et al., 2021), which comprises user-contributed content from the Stats Stack Exchange network. To provide insights into the characteristics of the databases, Table 3 presents statistics detailing their sizes. Additionally, Figure 5 showcases the distribution skewness of the database entries, highlighting the significant skewness often observed in real data (Dobra et al., 2002; Leis et al., 2015; Manerikar and Palpanas, 2009; Yang et al., 2017; Roy et al., 2016). Our experimentation covers all the 146 STATS-CEB and 70 JOB-light queries, in addition to the 3299 associated sub-queries from the cardinality estimation benchmark (Han et al., 2021). These queries collectively represent a diverse range of real-world workloads.

The key feature of our proposed method is its ability to efficiently estimate multi-join queries. As previously mentioned, our motivation for this capability is rooted in the prevalence of such queries in real-world scenarios. To further substantiate this motivation, we conducted an analysis of all the queries in both the cardinality estimation benchmark (Han et al., 2021) and the join order benchmark (Leis et al., 2015). The results, displayed in Table 4, indicate that 44% of the relations in the queries are involved in multiple joins, with single joins being the most common at 57%. Notably, 97% of the queries contain at least one relation which participates in multiple joins. These statistics underscore the significance of supporting multi-join queries to effectively address the majority of real-world query scenarios.

Following Izenov et al. (2021), in the experiments the filter predicates of each query are processed during ingestion of the tuples from their respective relation streams. In many streaming algorithms, the query is assumed to be known in advance of the stream. Consequently, filtering the tuples at the time of ingestion offers advantages in terms of performance and accuracy. This approach eliminates the need to update the sketch for tuples that do not satisfy the filters. In addition, the estimation accuracy is significantly improved as some data is already filtered out from the sketches (Izenov et al., 2021). However, it is worth mentioning that sketching methods, including the one presented, are also capable of handling filter predicates during inference. This can be achieved by treating the filters as joins with imaginary tables, a technique employed, for example, by Cormode (2011) and Vengerov et al. (2015). Lastly, in our experiments, we report the median of $l=5$ i.i.d. estimates as the cardinality estimate for all sketching methods.

We first compare the estimation accuracy of the different sketching methods in terms of the absolute relative error, defined as $\lvert y-\hat{y}\rvert$ divided by $\max(y,1)$, where $y$ is the true cardinality and $\hat{y}$ its estimate. This metric aligns with the formulation of the theoretical error bound outlined in Section 3.3. In Figure 6, we present the median and the 95th percentile of the error at varying sketch sizes. The statistics are derived from 30 repetitions, each with distinct random initializations. The results are presented for a representative subset of the queries, necessitated by space constraints, but detailed results for all 216 queries can be found online2.

It is important to note that the experiments for AMS and COMPASS (merge) do not extend to the highest memory usage levels. This limitation arises due to the extensive time required to run the AMS-based experiments, which increases exponentially with each additional data point, rendering their execution quickly infeasible. Additionally, COMPASS (merge) encountered memory constraints during the inference stage, as its memory demand grows exponentially with the number of joins. Notice that the depicted memory usage excludes intermediate representations during inference, thus understating the actual memory required for COMPASS (merge).

Upon analysing the results, we observe that the proposed method delivers comparable or lower error rates across all queries, often demonstrating orders of magnitude greater accuracy. The proposed method achieves zero error on many queries with large sketches. In realistic sketching applications, a margin of error is acceptable; therefore, sketches ranging from 1 to 10 MB could be employed for the STATS-CEB and JOB-light queries. For certain queries, like JOB-light 37 and 66, our method not only achieves significantly lower error but also demonstrates a more rapid reduction in error with each increase in memory.

To assess the rate at which our method improves the estimation error compared to the baselines, Figure 7 presents kernel density estimates of the slopes derived from the absolute relative error results for all 216 queries. These slopes are obtained by least-squares linear regression of the data for each method and query in log-log space. This means that the slope represents the exponent of a power law relationship, where the error at memory usage $m$ is given by $am^{k}$, with $k$ as the slope and $a$ as the error at $m=1$.

Remarkably, our method exhibits a significantly faster reduction in error, highlighting its ability to achieve high accuracy with substantially less memory compared to the baselines. Considering that the real data in our experiments is skewed, as indicated in Figure 5, we speculate that our method successfully inherits and expands upon the advantages associated with the Count sketch, particularly its effectiveness in handling skewed data. In the context of multi-joins, our method capitalizes on these benefits, demonstrating its ability to compute accurate cardinality estimates.

In the second set of experiments, we look into the execution time of our method and how it compares to the baselines across varying sketch sizes. In Figure 8, we present the execution times for each stage of the estimation process: initialization, sketching, and inference. The figure shows the best fit of a Gaussian process regression to the experimental results from all queries, totaling $232{,}323$ experiments. It also contains data for the learning-based methods which will be discussed in the following section. The individual timing results for all queries are provided online2.

While the initialization time exhibits a similar trend for all methods, in sketching time there is a notable disparity between AMS and the other methods. This disparity directly reflects the difference in update time complexity. The methods also differ in initialization time complexity, but this is not visible in the timing results because they are plotted with respect to their memory usage rather than the sketch size. That is, for a given sketch size COMPASS (partition) allocates more memory, but for a given memory budget, all methods have similar initialization time. Among the inference times, our method demonstrates remarkable overall efficiency. Even for the most complex queries with the largest sketch size, our method computes its estimate within ten seconds. In contrast, the AMS-based method requires hours to compute estimates, with the majority of that time spent on sketching, all while delivering higher error rates.

To further validate the fast update time of our method, we assessed the maximum stream throughput for all baselines, as outlined in Table 5. The memory usage includes the counters of the sketches and the random seeds for the hash functions. The results were obtained by performing linear least-squares regression on the throughput measurements for each method on all queries. For smaller sketch sizes, the AMS-based method can achieve a throughput similar to the Count sketch-based approaches. However, when working with larger sketch sizes required for high estimation accuracy, the AMS-based method becomes limited to handling just a few hundred tuples per second. This significant limitation severely restricts the practical usability of AMS in streaming scenarios.

In this set of experiments, we compare the cardinality estimation performance of our proposed method with the four data-driven machine learning techniques discussed in Section 2.7. Specifically, we compare their execution time and estimation quality. To evaluate the quality of cardinality estimates, we employ the q-error metric, defined as $\max(y/\hat{y},\hat{y}/y)$ if $\hat{y}>0$ and $\infty$ otherwise (Moerkotte et al., 2009). Figure 9 presents the cumulative distribution function of the q-error for all 3299 sub-queries, showing the fraction of queries that were estimated within a certain q-error. Our method was configured with $m=1{,}000{,}000$ bins, resulting in an average estimation time of 0.30 seconds and consuming an average of 137 MB of memory. To maintain consistency with the results of the learning methods, as obtained from the cardinality estimation benchmark (Han et al., 2021), our method estimated the cardinality of each sub-query only once. We provide our cardinality estimates for the sub-queries together with the source code2 to facilitate further comparisons with the proposed method and to ensure reproducibility.

The results presented in Figure 9 highlight the superior performance of the proposed method, which delivers error-free estimates for approximately 70% of the sub-queries. Furthermore, our method achieves q-error values of less than 2 for about 95% of the sub-queries. In contrast, even the best-performing learning-based method, BayesCard, achieves this level of accuracy for less than 80% of the sub-queries. These findings demonstrate the remarkable estimation accuracy of our proposed estimator. Moreover, our sketching approach provides theoretical guarantees on the estimation error which are lacking for the learning-based methods.

Our proposed method is also notably efficient when compared to the learning-based methods. As depicted in Figure 8, the training phase of the learning-based methods requires 3 to 5 orders of magnitude more time than creating our sketches. In addition, Table 5 shows that our method can handle over 6 million updates per second. This is because our method simply adds another item to the sketch. BayesCard, on the other hand, takes 12 seconds to process an update (Han et al., 2021), and the other learning-based methods take several minutes. Consequently, these learning-based methods prove impractical for scenarios involving frequent updates.

In the last set of experiments, we evaluate the impact of our cardinality estimator on the query execution time of PostgreSQL. We utilized the evaluation setup devised by Han et al. (2021), they modified PostgreSQL to enable the injection of cardinality estimates for all the sub-queries of the STATS-CEB and JOB-light queries. We compare our method against PostgreSQL’s own cardinality estimator as well as the aforementioned learning-based methods. Table 6 shows the total execution time for all the queries. The injected sub-query cardinality estimates are those reported in Section 4.4. In the results, PostgreSQL refers to the default PostgreSQL cardinality estimator, and True Cardinality denotes an oracle method with access to the actual intermediate sizes.

Our proposed method achieved the lowest total execution time with an improvement of 43% compared to PostgreSQL. On STATS-CEB, our method improves over PostgreSQL by 48%, falling just short of FLAT, which showed an improvement of 55%. On JOB-light, our method achieved equivalent execution time to the True Cardinality, while most other learning-based methods, with the exception of BayesCard, do not improve over PostgreSQL. These results underscore the practical advancement enabled by our proposed method due to its superior estimation accuracy, in addition to its exceptional efficiency.