PVLDB Reference Format:
. . PVLDB, 19(9): 2508-2521, 2026.
doi:10.14778/3819518.3819567

¹

1 Introduction↩︎

Batches of counting queries are not only useful in their own right for database applications, but also frequently serve to collect basic statistics from data for monitoring and optimization. With the growing popularity of learned query optimization [1]–[4] in recent years, an interesting workload has emerged: collecting training data for learned cardinality estimation (CE) [5]–[13]. CE is a critical component of query optimization, as its accuracy directly impacts the quality of query execution plans [14], [15]. In these workloads, queries typically involve joins and selections over base tables but report only the final counts of the result sets. These query-count pairs are subsequently used to train CE models. Such queries may be derived from past workloads or synthesized specifically for training. While the number of distinct join patterns is naturally limited by the database schema, the queries themselves additionally contain a variety of selection conditions, targeting different attributes with varying constants. Beyond simple equality comparisons, many conditions involve inequality or range predicates. 1 summarizes nine public query workloads widely used in CE research for training and evaluation. These workloads span three commonly studied benchmark databases—IMDB [15], STATS [16] and DSB [17]—and capture a broad range of query shapes, join structures, and predicate types.

Executing such workloads is time-consuming. Even when viewed as a one-time training cost, the overhead can be daunting; in our experience, some workloads require hours or even more than a day to execute (5). Furthermore, models are rarely trained once and then forgotten. As the database state changes, they can become outdated [18], [19]: cardinalities from previously executed queries may no longer be accurate, necessitating the re-execution of queries to retrain the models. While monitoring real result counts from query execution feedback can mitigate this issue, simply observing final query result counts is insufficient [9], [13], [16]. Effective training requires (1) the size of intermediate results for subqueries within potentially optimal plans, not just the plan actually executed, and (2) feedback from unseen queries to prepare for potential workload shifts [18], [20], [21]. In a continuously running environment, executing these monitoring or training queries must not disrupt normal workloads. These observations underscore the need for more efficient support for executing batches of counting queries.

Given the extensive literature on query processing, many ideas are applicable to the general problem of batch counting queries—including multi-query optimization, scalable continuous query processing, and factorized databases—see Section 6 for more discussion. A reasonable starting point, leveraging multi-query optimization, is to exploit the fact that many queries share the same join pattern, differing only in their selection conditions. Instead of executing them independently, one could perform the full join first and then apply individual selection conditions to obtain per-query counts. While this baseline enables shared join processing, it leads to materializing the full join result, which can be massive for large databases.

We propose BaCon, a practical, scalable algorithm for efficient Batch processing of Counting queries. A key idea, inspired by work on factorized databases [22]–[24], is that a counting query over a join can be evaluated without enumerating the join result. While the count operator cannot generally be pushed down through a join, if the join is processed in a “factorized” manner—grouped by joining attribute values—we can simply count the joining “factors” and multiply these counts, avoiding enumeration of the joined result tuples. A second key idea is workload-aware quantization of selection attribute domains. This idea allows the data required for counting queries to be compressed, naturally exploiting the overlap and sharing of selection predicates within the workload. BaConseamlessly combines these ideas, using compact “count maps” rather than bloated join tuples to represent intermediate results; to combine these intermediate results, it uses a pair of operators \(\otimes\) and \(\oplus\), defined with clear semantics and amenable to optimization. Finally, to ensure practicality and ease of adoption, we implement BaCon as a client application on top of a database system (DBMS) without modifying its internals. BaConleverages the DBMS for processing, utilizes user-defined functions (UDFs), and carefully balances database- and client-side execution to minimize interface overhead.

Our experimental results show that BaCon is highly competitive for training workloads for learned CE in 1, achieving \(2\times\) to \(178\times\) speedups over baselines. Moreover, BaConperforms well across diverse workloads, providing significant speedups for expensive join patterns while remaining competitive on those where baseline approaches are already efficient.

2 Preliminaries↩︎

2.0.0.1 Problem Statement and Notations

Consider a database \(\mathcal{D}\) with \(n\) tables \(R_1, \dots, R_n\), where each table \(R_i\) has a set of attributes denoted \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}{[R_i]}\). We are interested in processing a set of counting queries \(\pmb{\mathcal{Q}}\) over \(\mathcal{D}\).² Each query counts the number of tuples returned by a single-table selection or a selection-join over a subset of the tables in \(\mathcal{D}\). We assume equality joins with no cycles or self-joins, and that the selection is a conjunction of predicates comparing a single attribute with a literal using \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape=}}}\), \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape>}}}\), \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape<=}}}\), etc. We begin by introducing some useful notations (a table of notations is presented in the full version [37]). Given each query \(Q\in \pmb{\mathcal{Q}}\):

• \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{Q}\) denotes the subset of tables in \(\mathcal{D}\) referenced by \(Q\).

• \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\Join}_{Q}\) denotes the subset of attributes in \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{Q}\) referenced by the join predicates of \(Q\).

• \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\Join}_{Q}\) denotes \(Q\)’s join predicates, represented as the set of equivalent classes of attributes in \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\Join}_{Q}\) induced by \(Q\)’s join predicates. Two attributes \(A_1, A_2\) belong to the same equivalent classes iff \(A_1 = A_2\) is logically implied by \(Q\)’s join predicates.

• Given a pair of disjoint subsets \(\mathcal{R}\) and \(\mathcal{R}'\) of tables in \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{Q}\), \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\Join}_{Q}[\mathcal{R}|\mathcal{R}']\) denotes the subset of attributes of \(\mathcal{R}\) used by \(Q\) to join with \(\mathcal{R}'\); i.e., \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\Join}_{Q}[\mathcal{R}|\mathcal{R}'] = \{ A\in \bigcup_{R\in \mathcal{R}} \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}{[R]} \mid \exists \mathcal{E} \in \text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\Join}_{Q}: A\in \mathcal{E} \land (\exists A' \in \mathcal{E}: A' \in \bigcup_{R\in \mathcal{R}'} \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}{[R]}) \}.\)

• \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{Q}\) denotes the subset of attributes in \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{Q}\) referenced by \(Q\)’s selection predicates.

• \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\sigma}_{Q}\) denotes \(Q\)’s selection predicates, represented as a mapping from each attribute \(A\in \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{Q}\) to a range \(G\) over the domain of \(A\), such that \(G\) is the widest range such that \(A\in G\) is logically implied by \(Q\)’s selection predicates.

• Given a subsets \(\mathcal{R}\) of tables in \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{Q}\), \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{Q}[\mathcal{R}]\) denotes the set of attributes of \(\mathcal{R}\) referenced by \(Q\)’s selection conditions; i.e., \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{Q}[\mathcal{R}] = \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{Q} \cap \bigcup_{R\in \mathcal{R}} \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}{[R]}\).

For example, [sql:stats_ceb_example] shows the first four queries in the workload stats_ceb [30] over the STATS database [16]. For \(Q_4\):

• \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{Q_4} = \{ \text{\scalebox{0.9}[1.0]{\textsf{\upshape comments}}}, \text{\scalebox{0.9}[1.0]{\textsf{\upshape postHistory}}} \}\);

• \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\Join}_{Q_4} = \{ \text{\scalebox{0.9}[1.0]{\textsf{\upshape comments.UserId}}}, \text{\scalebox{0.9}[1.0]{\textsf{\upshape postHistory.UserId}}} \}\);

• \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\Join}_{Q_4} = \{ \{ \text{\scalebox{0.9}[1.0]{\textsf{\upshape comments.UserId}}}, \text{\scalebox{0.9}[1.0]{\textsf{\upshape postHistory.UserId}}} \} \}\) (both join attributes are in one equivalence class);

• \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\Join}_{Q_4}[\{\text{\scalebox{0.9}[1.0]{\textsf{\upshape comments}}}\}|\{\text{\scalebox{0.9}[1.0]{\textsf{\upshape postHistory}}}\}] = \{ \text{\scalebox{0.9}[1.0]{\textsf{\upshape comments.UserId}}} \}\);

• \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\Join}_{Q_4}[\{\text{\scalebox{0.9}[1.0]{\textsf{\upshape postHistory}}}\}|\{\text{\scalebox{0.9}[1.0]{\textsf{\upshape comments}}}\}] = \{ \text{\scalebox{0.9}[1.0]{\textsf{\upshape postHistory.UserId}}} \}\);

• \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{Q_4} = \{ \text{\scalebox{0.9}[1.0]{\textsf{\upshape postHistory.PostHistoryTypeId}}}, \text{\scalebox{0.9}[1.0]{\textsf{\upshape postHistory.CreationDate}}} \}\);

• \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\sigma}_{Q_4} = \{ \text{\scalebox{0.9}[1.0]{\textsf{\upshape postHistory.PostHistoryTypeId}}} \mapsto [1, 1],\\ \text{\scalebox{0.9}[1.0]{\textsf{\upshape postHistory.CreationDate}}} \mapsto [\text{\scalebox{0.9}[1.0]{\textsf{\upshape'2010-09-14 11:59:07'::timestamp}}}, \infty) \}\).

2.0.0.2 The First Baseline: Independent Processing (IndProc)

A straightforward solution, adopted by most existing work on learned CE, runs the queries in \(\pmb{\mathcal{Q}}\) one by one, independently, using the DBMS that manages \(\mathcal{D}\). We call this approach IndProc for short. The performance of IndProcis heavily dependent on the underlying DBMS. A capable DBMS will optimize each query by pushing down selection conditions, reordering joins, and choosing appropriate join methods, leveraging data statistics and available indices. Caching by the DBMS buffer pool may also improve execution performance across queries. On the other hand, most DBMS lack advanced methods for optimizing multiple queries simultaneously. Moreover, most of them choose to execute a counting query \(Q\) by first joining all tables in \(Q\) before applying the final \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape COUNT}}}\) aggregation, failing to explore opportunities for pushing \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape COUNT}}}\) below joins.

2.0.0.3 Join Patterns

Before presenting a more advanced baseline solution as well as our solution in 3, we introduce a concept used by both. The join pattern of a query \(Q\) is characterized by \(\langle \text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{Q}, \text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\Join}_{Q} \rangle\), i.e., the tables that \(Q\) joins, and \(Q\)’s join predicates. Suppose queries in \(\pmb{\mathcal{Q}}\) have \(q\) distinct join patterns \(\mathfrak{J}_1, \ldots, \mathfrak{J}_q\); these patterns partition \(\pmb{\mathcal{Q}}\) into a disjoint union of \(q\) subsets of queries, denoted \(\pmb{\mathcal{Q}}[\mathfrak{J}_1], \ldots, \pmb{\mathcal{Q}}[\mathfrak{J}_q]\), where each \(\pmb{\mathcal{Q}}[\mathfrak{J}_i]\) is the set of queries with join pattern \(\mathfrak{J}_i\) (but may differ in their selection predicates). For example, \(Q_3\) and \(Q_4\) in [sql:stats_ceb_example] have the same join pattern (with tables \(\{ \text{\scalebox{0.9}[1.0]{\textsf{\upshape comments}}}, \text{\scalebox{0.9}[1.0]{\textsf{\upshape postHistory}}} \}\) and join predicate \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape comments.UserId}}}\) \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape=}}}\) \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape postHistory.UserId}}}\), despite having different selection predicates). \(Q_1\) and \(Q_2\) each contribute a distinct join pattern. In practice, because all queries in \(\pmb{\mathcal{Q}}\) come from the same underlying database \(\mathcal{D}\), the number of distinct join patterns tends to be much smaller than the number of queries. For example, JOB’s synthetic [25] contains 5,000 queries but only 16 distinct join patterns.

2.0.0.4 The Second Baseline: Join and Post-Filtering (PostFilt)

This approach seeks to avoid redundant computation across queries with identical join patterns. We pre-process the queries into partitions \(\pmb{\mathcal{Q}}[\mathfrak{J}_1], \ldots, \pmb{\mathcal{Q}}[\mathfrak{J}_q]\) according to their join patterns. This step requires only a scan over \(\pmb{\mathcal{Q}}\) to perform syntactical analysis. For each partition \(\pmb{\mathcal{Q}}[\mathfrak{J}_i]\), we compute the join only once, followed by a post-filtering step, which checks each join result tuple against the selection predicates of queries in \(\pmb{\mathcal{Q}}[\mathfrak{J}_i]\) to determine which queries’ counts to increment. We call this baseline PostFilt.

There are many options for implementing the post-filtering step, as discussed in 6, including methods that first build a data structure for \(\pmb{\mathcal{Q}}[\mathfrak{J}_i]\) for efficient identification and updating of counters in time sublinear to \(|\pmb{\mathcal{Q}}[\mathfrak{J}_i]|\) per join result tuple. While these methods can scale to thousands or millions of queries, the typical workloads we target do not have so many queries per join pattern, as evidenced in 1. Through our experiments, we have found a simple strategy leveraging the underlying DBMS to be the most effective. Given a join pattern \(\mathfrak{J} = \langle \text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}, \text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\Join}_{\mathfrak{J}} \rangle\) and \(k\) queries \(Q_1, \ldots, Q_k\) sharing this pattern, we issue a single SQL query in [sql:postfilter] to compute all of them. Here, \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\sigma}_{}\), \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{}\), and \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\Join}_{}\) are translated into SQL. Each \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape CASE}}}\) expression determines whether a join result tuple contributes to a query \(Q_i\) by checking its selection predicates (a failed check yields \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape NULL}}}\), which is ignored by \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape COUNT}}}\)). In the end, a single \(k\)-component result tuple is computed, with each component holding the result count for one query.

2.0.0.5 Discussion

Compared with IndProc, PostFilteliminates redundant computation of joins among queries sharing the same join pattern. However, IndProccan still outperform PostFiltif the selection predicates of these queries have little overlap, and if database indices enable IndProcto apply selective selection predicates early in query processing. In contrast, PostFilthas no effective means to push selection predicates down because in most workloads, the disjunction of all selection predicates from multiple queries cannot be expressed as a succinct, “sargable” [38] \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape WHERE}}}\) condition without introducing many false positives. Furthermore, most database optimizers do not push aggregation below joins, let alone those with conditional expression inputs as in [sql:postfilter]. Therefore, PostFilteffectively enumerates the full join result before post-filtering and counting—a key limitation that we seek to overcome.

3 Basic BaCon↩︎

This section introduces basic BaCon, focusing on key ideas and the high-level algorithm. Many implementation and optimization details are also crucial to making BaConcompetitive in practice, but to simplify presentation, we defer them to 4. We start with three key ideas, along with some results and definitions based on them; we then describe the algorithm. Like PostFilt, given a set \(\pmb{\mathcal{Q}}\) of queries, BaConpartitions \(\pmb{\mathcal{Q}}\) into subsets according to join patterns, such that queries in each subset \(\pmb{\mathcal{Q}}[\mathfrak{J}]\) share the same join pattern \(\mathfrak{J} = \langle \text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}, \text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\Join}_{\mathfrak{J}} \rangle\). Hence, most of this section focuses on how to process one such subset of queries given \(\mathfrak{J}\).

Before proceeding, we briefly present a geometric view of the problem for intuition. Each result tuple in the cross product of \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}\) can be seen as a point in a high-dimensional space \(\mathbb{S}\), where each dimension corresponds to an attribute in \(\bigcup_{R\in \text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}} \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}{[R]}\), ignoring those not referenced by any predicate in \(\pmb{\mathcal{Q}}[\mathfrak{J}]\). Let \(J\) denote the result of the full join of \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}\) using \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\Join}_{\mathfrak{J}}\). Points in \(J\) are those cross-product points that lie on a hyperplane \(\mathbb{J}\) in \(\mathbb{S}\) defined by \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\Join}_{\mathfrak{J}}\). Each query \(Q\in \pmb{\mathcal{Q}}[\mathfrak{J}]\) corresponds to an orthogonal hyperrectangle in \(\mathbb{S}\) with range predicates restricted to dimensions in \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{Q}\). Our problem boils down to counting, for each \(Q\), how many points in \(J\) fall into \(Q\)’s hyperrectangle.

Intuitively, these points are not positioned arbitrarily: not only do they lie on \(\mathbb{J}\) because of the join predicates, but they also come from the cross product of \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}\), meaning that their projections onto the subspace \(\mathbb{S}[\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}{[R]}]\) for each \(R\in \text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}\) cannot exceed \(|R|\) distinct points, which is often much smaller than \(|J|\). In fact, if we consider the subset of \(J\) restricted to any particular combination of values for all join attributes, their projections onto \(\mathbb{S}[\bigcup_{R\in \text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}} \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}{[R]}]\) will form a perfect Cartesian product of their projections onto each of \(\mathbb{S}[\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}{[R]}]\) for \(R\in \text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}\) (which we shall substantiate in 3.1). This property, along with the fact the query hyperrectangles may overlap significantly, makes it possible to perform counting tasks more efficiently than simply enumerating \(J\) upfront (which \(\mathrm{\small PostFilt}\) does).

To further exploit the overlaps among the query hyperrectangles, consider a subset of \(J\) that forms a Cartesian product described above. We can partition its projection onto to each subspace \(\mathbb{S}[\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}{[R]}]\) into a coarse grid, using the endpoints of the query range predicates (a process we call “quantization” later in 3.2). For example, in 2, this projection consists of a collection of red points, partitioned by a \(4 \times 4\) grid. A key property of this grid is that all points within a cell lie in the same subset of query hyperrectangles. Therefore, we can compress the red points in each cell to a single “weighted” point, yielding a compressed representation of \(J\) (which we refer to as a “count map” later in 3.3). This compressed representation is constructed recursively for each \(\mathfrak{J}\), without having to enumerate \(J\) first (3.4).

3.1 Conditional Orthogonality of Joins↩︎

The first idea has its roots in the well-studied problem of factorized databases and related worst-case optimal join algorithms (further discussed in 6). A simple observation is that, in order to count the number of tuples in a cross product between two tables \(R_1\) and \(R_2\), we just need to calculate \(|R_1| \times |R_2|\), without enumerating \(R_1 \times R_2\). While the same observation no longer holds for \(|R_1 \Join_{R_1.A=R_2.A} R_2|\) when join predicate exists, if we additionally set the join attribute value \(A=x\), then the number of result tuples conditioned on this specific setting can still be computed directly: i.e., \(|\sigma_{A=x} (R_1 \Join_{R_1.A=R_2.A} R_2)| = |\sigma_{A=x} R_1| \times |\sigma_{A=x} R_2|\). We can generalize this idea further to a star-shaped join as follows.

The style of processing illustrated by the above example has been used recently for efficient computation of aggregate queries [40]. The subexpression \(|\sigma_{\text{\scalebox{0.9}[1.0]{\textsf{\upshape ci.movie\_id}}}=y} (\text{\scalebox{0.9}[1.0]{\textsf{\upshape ci}}} \Join\text{\scalebox{0.9}[1.0]{\textsf{\upshape rt}}})|\) can be processed by the same procedure. Later in this section, we will see how to extend the idea to computing result counts of multiple queries with different selection predicates beyond simply counting the full join result.

3.2 Quantization of Selection Attributes↩︎

While tables and attribute domains can be large, the number of queries in \(\pmb{\mathcal{Q}}\) places a natural constraint on the number of constants from each domain appearing in selection predicates. In other words, from the perspective of \(\pmb{\mathcal{Q}}\), fine-grained differences among attribute values may not affect result counts. Our key idea is to compress the attribute domains using workload-aware quantiziation, turning large, complex domains into a small range of integers that are efficient to work with.

Given a join pattern \(\mathfrak{J}\), let \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{\mathfrak{J}} = \bigcup_{Q\in \pmb{\mathcal{Q}}[\mathfrak{J}]} \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{Q}\) denote the set of selection attributes in all queries of pattern \(\mathfrak{J}\). We construct a quantization scale \(\mathfrak{b}_A\) for each selection attribute \(A\in \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{\mathfrak{J}}\) as follows. First, we extract from \(\pmb{\mathcal{Q}}[\mathfrak{J}]\) the set \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\sigma}_{\mathfrak{J}}(A) = \{ \text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\sigma}_{Q}(A) \mid \exists Q\in \pmb{\mathcal{Q}}[\mathfrak{J}]: A\in \text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\sigma}_{Q} \}\) of predicate ranges associated with \(A\). We sort all range endpoints, which partition the domain of \(A\) into an ordered list of atomic ranges. For each atomic range contained in at least one query range in \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\sigma}_{\mathfrak{J}}(A)\), we create a new bucket in \(\mathfrak{b}_A\) and assign it a serial integer id (starting with \(1\)). Hence, \(\mathfrak{b}_A\) maps each relevant atomic range (bucket) to an integer, preserving order. A value \(x\) from \(A\)’s domain is quantized into an integer \(\mathfrak{b}_A(x)\), the id of the bucket containing \(x\), or \(0\) if \(x\) lies outside all of buckets in \(\mathfrak{b}_A\). We present the detailed construction algorithm in the full version [37], which handles additional intricacies with open or close intervals.

Let \(\mathfrak{B}_\mathfrak{J} = \{ \mathfrak{b}_A \mid A \in \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{\mathfrak{J}} \}\) denote the collection of all attribute quantization scales for queries in \(\pmb{\mathcal{Q}}[\mathfrak{J}]\), and \(\mathfrak{B}_\mathfrak{J}[R] = \{ \mathfrak{b}_A \mid A \in \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{\mathfrak{J}} \cap \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}{[R]} \}\) denote those for attributes in table \(R\in \text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}\). Returning to the geometric view introduced at the beginning of the section, \(\mathfrak{B}_\mathfrak{J}[R]\) induces a grid over the subspace of \(\mathbb{S}\) spanning the selection attribute dimensions of \(R\). This grid allows us to map each tuple in \(R\), by its selection attribute values \(\langle x_1, \ldots, x_k \rangle\), to a grid coordinate \(\smash{\vec{b}} = (b_1, \ldots, b_k)\), where each \(b_i = \mathfrak{b}_{A_i}(x_i)\) is the bucket id for value \(x_i\) in the quantization scale for attribute \(A_i\).

Continuing with the geometric intuition, collectively, quantization scales \(\mathfrak{B}_\mathfrak{J}\) induces a grid over the subspace \(\mathbb{S}[\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{\mathfrak{J}}]\) consisting of the selection attribute dimensions across all tables in \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}\). By construction of \(\mathfrak{B}_\mathfrak{J}\), all query hyperrectangles in \(\pmb{\mathcal{Q}}[\mathfrak{J}]\) perfectly align with grid boundaries. Hence, all selection predicates can be quantized using the same scales. Lemma 2 below formalizes the guarantee that precise evaluation of selection predicates is possible in the quantized space.

As an example, 2 shows the grid over table \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape mc}}}\) induced by two queries. The quantization scales \(\mathfrak{b}_{\text{\scalebox{0.9}[1.0]{\textsf{\upshape company\_type\_id}}}}\) and \(\mathfrak{b}_{\text{\scalebox{0.9}[1.0]{\textsf{\upshape company\_id}}}}\) respectively correspond to the two \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape mc}}}\) attributes referenced by the queries’ selection predicates. (For now, ignore the mention of “projected subslice,” which will be formally introduced in 3.4.) The buckets for \(\mathfrak{b}_{\text{\scalebox{0.9}[1.0]{\textsf{\upshape company\_type\_id}}}}\), numbered \(1\) through \(3\), are \([a_1,a_2)\), \([a_2,\text{\scalebox{0.9}[1.0]{\textsf{\upshape succ}}}(a_2))\), and \([\text{\scalebox{0.9}[1.0]{\textsf{\upshape succ}}}(a_2), \infty)\), where \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape succ}}}(a_2)\) denotes the successor value of \(a_2\) in the domain; any value in \((-\infty, a_1)\) will be quantized to special bucket id \(0\) because this range is not contained in any selection predicate. The buckets for \(\mathfrak{b}_{\text{\scalebox{0.9}[1.0]{\textsf{\upshape company\_id}}}}\) are similarly induced by selection predicates involving \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape company\_id}}}\).

3.3 Quantized Selection Count Maps↩︎

Since queries in \(\pmb{\mathcal{Q}}[\mathfrak{J}]\) ultimately only care about counts, a natural idea following selection attribute quantization is to further aggregate the points that fall into each grid cell induced by \(\mathfrak{B}_\mathfrak{J}\) into a single count, instead of enumerating them.

Given a table \(R\in \text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}\) with selection attributes \(\{ A_1, \ldots, A_k \}\) and quantization scales \(\mathfrak{B}_\mathfrak{J}[R] = \{ \mathfrak{b}_{A_1}, \ldots, \mathfrak{b}_{A_k} \}\), we compress a subset of tuples in \(R\) into a (quantized selection) count map \(\mathfrak{M}\): each entry of \(\mathfrak{M}\) maps a grid coordinate \(\smash{\vec{b}} = (b_1, \ldots, b_k)\) to \(\mathfrak{M}[\smash{\vec{b}}]\), the count of tuples within the grid cell—i.e., any tuple \(t\) satisfying \(\mathfrak{b}_{A_i}(t.A_i) = b_i\) for \(i = 1, \ldots, k\). For example, 2 shows the count map for the set of tuples (2D points in the geometric view).

We generalize the concept of count map \(\mathfrak{M}\) over any subset of tables \(\mathcal{R} \subseteq \text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}\). Let \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{\mathfrak{J}}[\mathcal{R}] = \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{\mathfrak{J}} \cap \bigcup_{R\in \mathcal{R}} \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}{[R]}\) denote the set of selection attributes in \(\mathcal{R}\) from all queries of pattern \(\mathfrak{J}\). A grid coordinate for \(\mathfrak{M}\), with one component for each attribute in \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{\mathcal{R}}\), identifies a grid cell induced by quantization scales \(\{ \mathfrak{b}_A \mid A \in \text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{\mathcal{R}} \}\) in subspace \(\mathbb{S}[\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{\mathcal{R}}]\). Given a subset \(T\) of tuples in the cross product of \(\mathcal{R}\) corresponding to points in \(\mathbb{S}[\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\sigma}_{\mathcal{R}}]\), \(\mathfrak{M}\) counts the corresponding points of \(T\) in each grid cell.

Our goal is to construct a count map over the entire \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}\) for the full join result set \(J\), but importantly, without enumerating \(J\). Intuitively, count maps represent intermediate results compactly. Obtaining a count map for a single table is easy, but combining count maps for different subsets of tables into a big one is complicated by joins, because not all points in two grid cells in orthogonal subspaces join with each other. However, leveraging 1, we can process points in \(J\) in groups: points in each group all share appropriate join attribute values, thereby allowing count maps to be computed for different subsets of tables and then conveniently “multiplied.” Then, the product count maps across groups can be “added” to obtain the final result count map. An example will be provided in 3.4.

We formally define “multiply” and “add” as follows:

The following lemmas establish the correctness of using \(\otimes\) and \(\oplus\) for computing count maps. Formally, given \(\pmb{\mathcal{Q}}[\mathfrak{J}]\), quantization scales \(\mathfrak{B}_\mathfrak{J}\), a subset of tables \(\mathcal{R} \subseteq \text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}\), and a subset \(T\) of tuples in the cross product of \(\mathcal{R}\), we say that a count map \(\mathfrak{M}\) over \(\mathcal{R}\) is complete with respect to \(T\) if for any query \(Q\in \pmb{\mathcal{Q}}[\mathfrak{J}]\), the size of the intersection between \(T\) and the selection-join subquery of \(Q\) restricted³ to \(\mathcal{R}\) can be computed from \(\mathfrak{M}\) and \(\mathfrak{B}_\mathfrak{J}\).

3.4 Basic BaConAlgorithm↩︎

We are now ready to describe the overall BaConalgorithm (3). First, we make a pass over all queries and partition them into subset where each contains queries with the same join pattern. For each subset \(\pmb{\mathcal{Q}}[\mathfrak{J}]\) with join pattern \(\mathfrak{J}\), we construct the quantization scales for them, as discussed in 3.2. We then determine an “execution plan” for \(\mathfrak{J}\) as an ordered tree, akin to the notion of “(paths in) f-tree” in factorized database literature [22], [23]. Nodes in this tree correspond to the tables of \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}\), and edges connecting the nodes represent equijoin conditions among them. Assuming that queries are acyclic and contain no cross products, one such tree always exists to capture \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\Join}_{\mathfrak{J}}\) precisely. Indeed, there can be multiple alternative plan trees; we defer the discussion of how to choose one to 4. At a high level, we process \(\pmb{\mathcal{Q}}[\mathfrak{J}]\) using an in-order traversal of the plan tree starting from its root, by calling its main workhorse, the recursive procedure \(\mathrm{\small BaCon}\mathrm{\small Recurse}\) (Line [alg:our95main:call95recurisve]), to compute a count map for \(\pmb{\mathcal{Q}}[\mathfrak{J}]\). This count map is then used to calculate the result counts for queries, which can be done naively by summing up the counts at grid coordinates in each query hyperrectangle; we describe an optimized implementation in 4.

BaConRecurse(4, illustrated in 5) is called on a plan tree node (table) \(R\) and a filter specified by a mapping \(u\) that binds some attributes of \(R\) to specific values, which defines a “slice,” or the subset \(T\) of result tuples, of the join of \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape subtree}}}(R)\) (set of tables in the subtree rooted at \(R\)) satisfying \(u\). The goal of BaConRecurseis to compute a count map for this slice \(T\) (the call to \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape root}}}(\mathfrak{J})\) has \(u = \emptyset\), so its slice in fact contains all result tuples in the full join of \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}\)). As discussed in 3.3, processing the entirety of \(T\) efficiently is hard; instead, BaConRecursepartitions the slice into “subslices,” where each subslice \(T_v\) binds a particular combination \(v\) of values for \(R\)’s attributes that join with its children, i.e., \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Attrs}}}^{\Join}_{\mathfrak{J}}[R\,|\,\text{\scalebox{0.9}[1.0]{\textsf{\upshape children}}}(R)]\). To this end, BaConRecursecalls ProcessTable([sql:count-table]) to enumerate all possible such bindings (Line [alg:our95recursive:loop]). Each iteration of the loop (Lines [alg:our95recursive:loop]–[alg:our95recursive:loop-end]) computes a count map for the subslice \(T_v\) defined by a particular \(v\). By 3, this count map can be computed by projecting \(T_v\) into “projected sublices,” one for \(R\) and each of \(R\)’s child subqueries, and multiplying the count maps of these projected subslices. Conveniently, the call to ProcessTablecomputes, for each projected subslice of \(R\), the coordinate-count pairs to populate the count map. We recursively call BaConRecurseon each child of \(R\) to compute the count map for its projected subslice. Line [alg:our95recursive:multiply], using \(\otimes\), combines these count maps into a single count map for \(T_v\). Finally, applying 4, Line [alg:our95recursive:add] uses \(\oplus\) to accumulate the count maps for all \(T_v\)’s into the final count map for \(T\) to be returned.

Delving into ProcessTable([sql:count-table]), we see how a single SQL query over a table \(R\) performs “subslicing” (by \(\mathcal{A}^\texttt{out}\)) and computes the count maps of all projected subslices. In the \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape FROM}}}\) subquery that defines \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape TMP}}}\), the \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape WHERE}}}\) condition applies the attribute binding \(u\) that defines \(T\), the slice of interest; the \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape SELECT}}}\) clause uses a user-defined function \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape quantize}}}\) to check each selection attribute value against a quantization scale and returns its grid coordinate. The outer query groups the \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape TMP}}}\) tuples by \(\mathcal{A}^\texttt{out}\) to perform subslicing, and then by their grid coordinates to compute tuple count per grid cell for each projected subslice. Finally, \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape ORDER}}}\) \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape BY}}}\) ensures that entries for the same projected subslice, i.e., those with the same binding \(v\) for \(\mathcal{A}^\texttt{out}\), are consecutive in the output. This ordering allows the caller BaConRecurseto detect where a sequence of entries with a new \(v\) starts, so it can start processing a new subslice.

4 Additional Optimization and Implementation Details↩︎

This section fills in some of the details about BaConnot covered by 3 and describes additional optimizations needed to make BaConpractical for query workloads for training learned CE models. Before delving into details, we note that BaContakes the high-level approach of leveraging DBMS for processing, not only because it houses the data, but also because it already provides versatile support for indexing and querying. To make BaConeasy to adopt, we do not modify any DBMS internals but instead implement, in a client application, parts of the algorithm that are inefficient for the DBMS. Many optimizations thus involve balancing database- and client-side processing options and mitigating the overhead of interfacing them. Overall, we perform ProcessTable([sql:count-table]) inside the DBMS, using cursors to fetched join values, quantization grid coordinates, and associated counts. The remainder of BaConRecurse(i.e., merging of count maps along the tree structure) and the remainder of BaCon(i.e., ComputeCounts) are performed on the client side. The associated optimizations are presented below. While BaConis currently implemented on top of PostgreSQL, the ideas in this section generalize to other DBMSs, although details may differ.

Note that BaConis not optimized for join patterns characterized by queries exhibiting little opportunity for shared processing (e.g., when there are too few of them, or their predicates overlap very little), or an underlying full join that is small and cheap to compute to begin with. In such cases, BaConmay not outperform baselines IndProcor PostFilt. Therefore, we also have developed a method called Hybrid, which acts as an optimizer to choose the appropriate method to use among IndProc, PostFilt, and BaConfor a given join pattern. In our experimental comparison of these methods in 5, we empirically analyze the cases where BaConis not optimal (5.2): they follow our characterizations above and play only a small role in the overall performance of query workloads found in the learned CE literature. Furthermore, despite Hybrid’s ability to make on per-pattern decisions, it offers no consistent improvement over BaConoverall. This observation speaks to the effectiveness of BaCon, even without Hybrid, for handling practical CE training workloads. More details on Hybridcan be found in the full version [37].

4.1 Choosing Execution Plan for a Join Pattern↩︎

Give a join pattern \(\mathfrak{J}\), the cost of BaConRecurseto process \(\pmb{\mathcal{Q}}[\mathfrak{J}]\) depends on the choice of a tree-based execution plan, introduced in 3.4. A cost-based decision requires fine-grained knowledge of the data distribution, which itself is expensive to acquire. Instead, we follow some heuristics below to construct a tree-based plan.

The first heuristic is to pick tree root to be the table \(R\) with the highest degree in \(\mathfrak{J}\)’s join graph: i.e., the root joins with the largest number of other tables in \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Tables}}}_{\mathfrak{J}}\) according to \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\Join}_{\mathfrak{J}}\). The rationale is to maximize the saving opportunities identified by 3: a root with a large in-degree can potentially avoid enumerating more cross products.

Geometrically, this heuristic ensures that, during recursion, the grid coordinates in each descendant lie in low-dimensional subspaces.

Once we pick the root, the rest of the tree structure follows naturally from \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\Join}_{\mathfrak{J}}\). Since we assume queries to be acyclic, no additional join conditions are needed beyond those corresponding to the tree edges. For example, in 1, even though \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape mc}}}\) and \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape ci}}}\) can join on \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape mc.movie\_id = ci.movie\_id}}}\), there is no edge between them in the tree, because the two join conditions from root \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape t}}}\) to \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape mc}}}\) and \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape ci}}}\), involving \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape t.id}}}\), together imply \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape mc.movie\_id = ci.movie\_id}}}\).

The next optimization then marks certain tree edges that correspond to joining a foreign key (FK) of the parent table \(R\) to a primary key (PK) of the child table \(R'\). For such a marked FK-PK edge, when BaConRecurseprocesses \(R\), it will simultaneously process \(R'\): on Line [alg:our95recursive:loop], ProcessTablewill additionally query \(R'\) and compute its count map along with that for \(R\) (with appropriate changes to [sql:count-table]); and on Line [alg:our95recursive:recursive95loop], children of \(R'\) will be directly included, instead of \(R'\) itself. The justification behind this optimization is that, because of the FK-PK join, each \(v\) would yield only one joining tuple from \(R'\), meaning there is no cross product to avoid in the first place. Therefore, we should “short-cut” this edge to eliminate the associated overhead.⁴ For simplicity, our implementation currently restricts this optimization to edges incident to the root, but applying it to the entire tree is possible as future work.

The last heuristic dynamically reorders subtrees under each node. We start with an arbitrary ordering. For a node \(R\), after some iterations of the loop on Lines [alg:our95recursive:loop]–[alg:our95recursive:loop-end] of 4, we count, for each child \(R_i\), how many settings of \(v\) yield no tuples from \(R_i\). Then, we reorder the children so that those with more such cases come first. Intuitively, they are more likely to produce an empty count map, with which we can “short-circuit” the sequence of multiplies.

4.2 Mitigating SQL Querying Overhead↩︎

4.2.0.1 Server- vs.Client-Side Cursors

When BaConruns a SQL query on the underlying database, we can use either a server-side cursor [41] or a client-side one [42]. A client-side cursor fetches the entire query result set into client memory. A server-side cursor, in contrast, allows the client to iterate row-by-row without materializing a potentially massive result set. While server-side cursors offer more flexibility and improve scalability, they are considerably slower and require state to be maintained on the database server; a large number of concurrent server-side cursors can cause performance issues. Therefore, BaConuses a server-side cursor for ProcessTableon the root, but switches to client-side cursors for all other calls. The rationale is that the call on the root table (from Line [alg:our95main:call95recurisve] of 3) has no bound attributes (\(u = \emptyset\)) and may generate a large result set. In contrast, other calls access much fewer tuples per subslice, and even with the batching optimization below, their result sizes remain manageable for client-side cursors.

4.2.0.2 Batching of ProcessTable

During recursive execution of BaConRecurseover the plan tree, the overhead of issuing many SQL queries via ProcessTablecan accumulate, especially when many of these queries, with specific attribute bindings, return small result sets. To mitigate this overhead, we batch multiple invocations of ProcessTablefor the same table \(R\), using a set of bindings \(U\) rather than a single binding \(u\), into one SQL query. Specifying the combined condition precisely in the \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape WHERE}}}\) clause of [sql:count-table] is generally infeasible, as it would have to enumerate all bindings in \(U\). Instead, we compute the minimum and maximum elements⁵ of \(U\) and use \([\min(U), \max(U)]\) as a safe but possibly imprecise range bound in \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape WHERE}}}\), i.e., \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape WHERE}}}\) \((J^\text{\scalebox{0.9}[1.0]{\textsf{\upshape in}}}_1, J^\text{\scalebox{0.9}[1.0]{\textsf{\upshape in}}}_2, \ldots)\) \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape BETWEEN}}}\) \(\min(U)\) \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape AND}}}\) \(\max(U)\). We extend the query to additionally group by \(J^\text{\scalebox{0.9}[1.0]{\textsf{\upshape in}}}_1, J^\text{\scalebox{0.9}[1.0]{\textsf{\upshape in}}}_2, \ldots\) and return them, such that ProcessTablecan, using these attribute values, filter out result tuples that do not belong to \(U\).

In BaConRecurse, we implement this optimization by collecting \(\beta\) consecutive settings of \(v\) into a set \(V\) for processing as a batch, analogous to a \(\beta\)-fold loop unrolling on Lines [alg:our95recursive:loop]–[alg:our95recursive:loop-end] of 4. For each child \(R_i\), we project \(V\) to obtain the set \(U_i\) of unique bindings on its join attributes with \(R\) (Line [alg:our95recursive:project95binding]), and invoke ProcessTableon \(R_i\) with \(U_i\). The detailed algorithm is presented in the full version [37].

We now provide further analysis of this batching optimization. First, beyond reducing the overhead of issuing many queries, batching promotes reuse of ProcessTablecalls on the same table and attribute binding. Without batching, consecutive settings of \(v\) in the loop on Lines [alg:our95recursive:loop]–[alg:our95recursive:loop-end] of 4: it is likely that they agree on most components since they are sorted. Therefore, when \(v\) is projected to obtain some \(u_i\), the same \(u_i\) setting in the previous iteration may be used again to call ProcessTableon the same table \(R_i\), leading to waste unless we cache the results from previous calls. With batching, however, such reuse occurs naturally. So we have not implemented additional caching mechanisms for BaCon, although further exploration will be a good future work.

Second, compressing a set of bindings into a single range may introduce false positives. Indeed, \(R_i\) may always contain some tuples whose join attribute values lie in \([\min(U_i), \max(U_i)]\) but are not contained in \(U_i\), because \(U_i\) is generated from \(V\) and subject to all other constraints on the slice. Nonetheless, the concern with false positives is at least partly alleviated by the fact that BaConRecurseprocesses settings of \(v\) in order, meaning that it will call ProcessTableon \(R_i\) with “clustered” settings of \(u\) in \(U\).

4.2.0.3 Implementation of \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape quantize}}}\)

Since the UDF \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape quantize}}}\) in [sql:count-table] is invoked many times, efficient implementation is crucial for performance. We implement \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape quantize}}}\) as C-language UDFs in PostgreSQL [43], with one variant for each SQL data type. The quantization scale is implemented as an array of sorted boundary points, and a binary search is used to determine the correct bucket id. These C-language UDFs run as compiled code natively inside the server process, greatly outperforming SQL-based UDFs. BaConcreates these extensions at the beginning of its execution and drops them at the end. More generally, \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape quantize}}}\) can be implemented in other DBMSs using available extensions, including CLR (common language runtime) integration for Microsoft SQL Server [44] or external procedures for Oracle Database [45].

4.3 Implementation of ComputeCounts↩︎

ComputeCountsis invoked by BaConto compute the result counts of queries in \(\pmb{\mathcal{Q}}[\mathfrak{J}]\) given the final count map \(\mathfrak{M}\) computed by BaConRecurse. Conceptually, it performs a “join” between a set of query hyperrectangles (\(\pmb{\mathcal{Q}}[\mathfrak{J}]\)) and a set of weighted points (\(\mathfrak{M}\)), and reports the total weights within each hyperrectangle. Many processing strategies are possible, and the best depends on query and data distributions. For our target of query workloads for training learned CE models, we observe that \(|\pmb{\mathcal{Q}}[\mathfrak{J}]|\) is moderate (in hundreds or thousands) and \(\mathfrak{M}\) tends to be sparse (32% on average across join patterns in JOB’s synthetic). After experimenting with several methods, we have found a simple method based on nested loops to be the most effective for this setting. Basically, for each \(Q\in \pmb{\mathcal{Q}}[\mathfrak{J}]\) and for each non-zero entry \(\smash{\vec{b}} \mapsto c\) of \(\mathfrak{M}\), we check whether, for every dimension of \(Q\)’s hyperrectangle with a range bound, the corresponding coordinate in \(\smash{\vec{b}}\) falls within this bound. If yes, we add the entry’s count \(c\) to \(Q\)’s running total. While BaConis implemented in Python, we specifically use Numba’s just-in-time compilation [46] for ComputeCounts. With the help from Numba’s compiler optimizations, this simple implementation was able to beat more sophisticated methods.

5 Experiments↩︎

We compare IndProc, PostFilt,⁶ and BaCon. All algorithms are implemented in Python3, using psycopg2 [47] to connect to PostgreSQL V16.8 with default configuration. All experiments are conducted on a Linux server with an Intel(R) Xeon(R) Gold 5215 CPU (40 logical cores, 2.50GHz), 256GB of main memory, and 1TB of disk storage. We set the batching parameter \(\beta{}\) (4.2) to 50,000 for BaCon for all experiments and present results for different \(\beta\)’s in the full version [37]. Code is available in the GitHub repository [48].

We test three popular datasets: IMDB [15], STATS [16], and DSB [17] (of scaling factor 2). They are loaded and initialized using the provided scripts [49]–[51], and the algorithms use exactly the indices provided therein without creating any additional ones.

We evaluate the algorithms on nine publicly available workloads in 1. These workloads span a wide range of sizes, query templates, join structures, predicate types, and result sizes, and are widely used for training and evaluating cardinality estimation techniques [16]. Among the workloads, only dsb-grasp-20k is post-processed [52] from the source file [34]. Specifically, CE work, SeConCDF [20] and GRASP [35], have numerical/categorical definitions for several attributes that are originally defined as \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape char(...)}}}\) in DSB (e.g., \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape cd.cd\_education\_status}}}\)). As these transformations are not clearly specified, we remove the queries involving such attributes, and then randomly sample 20k queries to ensure that baselines complete within a reasonable time. We additionally construct three new workloads based on job-light, used exclusively in 5.3.

Running time is our main performance metric. For IndProc, end-to-end running time is the sum over all queries. For PostFiltand BaCon, it includes pre-processing and time for each join pattern. To prevent baselines from running for too long, we cap IndProcat 900s per query, and PostFiltat 3,600s per join pattern; therefore, some baseline numbers are only lower bounds.

In terms of client-side memory usage, because BaCon processes each join pattern separately, memory peaks at the single most complex join pattern in the workload. Across all nine workloads, the maximum memory footprint of BaCon occurs for a join pattern in synthetic, at 1.7GB. We do not report memory usage for PostFiltand IndProc, as they executed entirely inside the database server.

5.0.0.1 Single-Threaded vs.Parallel Execution

Results below focus on single-threaded execution to isolate the algorithmic differences of BaCon compared with the baselines, without the potentially confounding factor of parallelization. We disable parallelism in PostgreSQL by setting \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape max\_parallel\_workers\_per\_gather}}}\) to 0, and restrict all client-side code to a single thread. Besides this single-threaded setting, we have also evaluated all methods in a parallel setting. Under the parallel setting, IndProc and PostFilt fully leverage PostgreSQL’s built-in parallelism; for BaCon, we use a simple multi-process design in which each process handles a subset of join patterns (more sophisticated parallelization strategies for BaCon are possible as future work). Briefly, the results show that, even with this simple strategy, BaConachieves end-to-end speedups of 2\(\times\) to 598\(\times\) compared with IndProc, consistent with the single-threaded results shown below in 5.1. Additional details on the parallel setting can be found in the full version [37].

5.1 End-to-End Running Time↩︎

2 reports the end-to-end running times of all three approaches across all nine real workloads. Lower-bound values (followed by “+”) are reported if a baseline runs out of time. We additionally show the relative speedups of BaCon over IndProc, which range from approximately 2\(\times\) to 178\(\times\). Speedups over PostFilt are omitted, as IndProc outperforms PostFilt on most long-running workloads. Overall, BaCon consistently outperforms both baselines and never times out: the worst per-join-pattern overhead of BaCon across all workloads is below 380s, far below the thresholds for baselines. The observed performance trends between IndProc and PostFilt align with our analysis in 2. In particular, PostFilt is advantageous for join patterns with many queries—where predicates tend to cover larger regions—and without intermediate join blow-ups (e.g., synthetic and dsb-grasp-20k). In the remaining cases, IndProc performs substantially better due to selection push-down in each query. BaCon is able to effectively combine the strengths of both IndProc and PostFilt.

Since both PostFilt and BaCon are designed around the notion of join patterns, we further analyze the results on a per-join-pattern basis in 5.2. Before doing so, we briefly summarize the other overheads—which are negligible compared with per-join-pattern running time—and omit them from ensuing discussions. IndProc incurs no such overheads. Both PostFilt and BaCon require loading and parsing SQL queries, extracting join patterns, and grouping queries accordingly, with complexity linear in the number of queries, tables, and selection attributes. This pre-processing step happens at the beginning when processing each join pattern, and typically completes within a few seconds; the only exception is dsb-grasp-20k, where it reaches \(\approx\)​20s due to the large number of queries (but is still small relative to the end-to-end running time).

5.2 Per-Join-Pattern Result↩︎

In this section, we analyze the results on a per-join-pattern basis. Although IndProc does not operate on join patterns, we group its results accordingly to facilitate direct comparison with the others.

We first report the number of timed-out cases in 3. BaCon never times out. Overall, PostFilt times out more frequently: since it always materializes the unfiltered join, if that times out, all queries associated with the pattern time out. Additionally, workloads on STATS exhibit more time-outs, primarily due to larger intermediate joins than those on IMDB, as noted by [16].

Next, we analyze the per-join-pattern overhead across all workloads. For clarity, consistent with the pre-defined time-out thresholds, we assign 3,600s to timed-out join patterns in PostFilt and 900s to timed-out queries in IndProc; actual running times will be higher. 6 reports the running times of all join patterns, ordered by IndProc’s times. Before index 120, all join patterns under IndProc complete within 10s; beyond this point, running times increase markedly. The inset zooms in the region before index 200, where BaCon closely tracks IndProc, sometimes faster and sometimes slower within a bounded margin, while PostFilt already times out on several patterns. Between indices 160 and 200, BaCon exhibits a small number of clear regressions relative to IndProc, with the largest gap (98s) at index 165; we analyze these cases in detail later. Outside the zoomed region, where join patterns run substantially longer, BaCon consistently and significantly outperforms IndProc and PostFilt.

Additionally, we present a detailed per-join-pattern analysis for scale and job-light here; results for the remaining workloads are in the full version [37]. As shown in 7, scale contains join patterns involving 1 to 5 tables, with more tables generally run longer. Timed-out queries arise mainly from patterns with many tables. For most long-running join patterns, BaCon consistently outperforms the baselines. For fast patterns, BaCon remains competitive, as the time gaps are small. However, there are several patterns where BaCon is noticeably slower than either baseline. Taking join pattern 6 as an example, IndProc, PostFilt, and BaCon take 61s, 35s, and 153s, respectively. This pattern has conditions \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape ci.movie\_id = t.id AND mc.movie\_id = t.id}}}\) and only five queries. A breakdown of BaCon’s running time shows 118s (76%) for executing SQLs, 5s (3%) for aggregating rows by join attribute bindings and coordinates, and 18s (15%) for merging count maps; thus, SQL execution dominates and already exceeds the running times of the baselines. This regression stems from two factors. First, algorithmically, enumerating tuples from each table and quantizing them can be less efficient than IndProc when predicates are selective and overlaps are limited. Second, although BaConperforms less work than PostFilt, BaCon’s cursor invocations and row fetching/parsing incur more overhead than PostFilt’s server-side processing.

We have similar observations from 8. As discussed by [16], job-light is a classical but relatively simple workload with 1 to 8 queries for each join pattern. The true cardinality range is also a magnitude smaller than that of stats-ceb. Therefore, IndProc consistently performs well on all join patterns, except one severe time-out for join pattern 17. However, BaCon remains competitive across join patterns and never times out. Regression compared with baselines is limited: in the worst case, BaCon is 55s slower compared with IndProc on join pattern 8, and 100s compared with PostFilt on join pattern 7.

Overall, consistent with the results in 5.1, BaCon does well across join patterns: it significantly outperforms the baselines on expensive patterns and remains acceptable on cheap ones.

5.3 Scalability↩︎

In this section, we evaluate the scalability of the three approaches using three synthetic workloads, denoted job-light-*. We choose job-light as the reference because, as shown in 8, IndProc performs consistently well, except for a single join pattern that times out. Specifically, on jog-light, BaCon outperforms IndProc in only 7 out of the 18 (39%) join patterns. Earlier, we have made the observation that the baselines—especially IndProc—can outperform BaCon on simple join patterns, e.g., where the number of queries is small and intermediate join sizes remain moderate. In particular, if the number of queries is small, there is less opportunity for sharing, and IndProc’s simple approach of optimizing and evaluating queries one by one works fine. Here, we further investigate how each approach scales as the workload size increases while preserving the original distribution.

We construct workloads with 1,000, 2,000, and 4,000 queries each. Queries are generated randomly and independently. We randomly select a query from job-light, reuse its template (and thus its join pattern), but modify its predicate constants: 1) for a constant in equality and inequality predicates, we replace it with a random value from the active domain of the corresponding attribute; 2) for range predicates, we randomize the left endpoint and adjust the right accordingly to preserve the range length.

4 shows end-to-end running times and relative speedups. As expected, IndProc’s running time grows roughly linearly with workload size, since queries are processed independently. PostFilt grows more slowly because its dominant cost—computing the full join—is amortized across queries with the same join pattern; nevertheless, it still times out frequently. BaCon scales better for two reasons. First, quantization generally benefits larger workloads more. Second, the costs of enumerating join attribute bindings and quantization remain mostly stable: as the size of each quantization scale is bounded by the workload size \(|\pmb{\mathcal{Q}}[\mathfrak{J}]|\), the cost of quantizing an attribute is only \(O(\log(|\pmb{\mathcal{Q}}[\mathfrak{J}]|))\) thanks to binary search. Per-join-pattern results are provided in the full version [37]. While the number of join patterns remains 18, the number of them where BaCon outperforms IndProc increases to 14 (78%) in job-light-1k, 17 (94%) in job-light-2k, and finally 18 (100%) in job-light-4k. Overall, BaCon demonstrates superior scalability compared with both IndProc and PostFilt.

5.4 Validation against Hybrid↩︎

As shown in 5.2, there exist join patterns for which a baseline, IndProc or PostFilt, outperforms BaCon. These cases typically involve few queries and small intermediate join sizes. As discussed in the full version [37], we can adopt a hybrid approach that uses a classifier to pick which method to use given a join pattern. Here, we train Hybridusing observations from job_light_join and stats_ceb_join, and evaluate it on the remaining seven workloads. 5 reports the E2E running times of Hybrid (using BaCon as the reference) on the seven test workloads. Overall, Hybrid selects a baseline for 9 join patterns in scale and 4 join patterns in stats_ceb, while selecting BaConfor all other join patterns and workloads. Even with Hybrid’s conservative design, end-to-end running times show that mispredictions can occur, sometimes catastrophically. To take a closer look, 9 presents a per-join-pattern analysis, focusing on patterns where Hybridchooses a baseline. As shown in 9, for scale, all 9 switches to PostFilt are beneficial, yielding a total saving of 156s. In stats_ceb, Hybrid gains minor savings by choosing PostFilt on pattern 27 and IndProc on pattern 57, but incorrectly selecting IndProc on patterns 40 and 56 causes slowdowns of 1s and 129s, respectively. Overall, these results confirm that BaCon remains a safe bet for practical workloads. With additional data statistics or training, a better Hybridmight be possible as future work, but the overhead for statistics collection and training may outweigh its benefit.

6 Related Work↩︎

6.0.0.1 Select-Join-Aggregate Query Processing.

Counting join results (with selection predicates on base tables) is a special form of select-join-aggregate queries. Standard processing typically involves pushing down selection predicates before evaluating the join and then aggregate. The classic Yannakakis algorithm [53] computes free-connex join-count queries in \(O(N)\) time, where \(N\) is the number of tuples. Recent advancements [54] exploit a hybrid strategy of Yannakakis algorithm that handles acyclic join-count queries in \(\smash{O(N+N \cdot \mathsf{OUT}^{1-\frac{1}{w}})}\) time. BaCon draws inspiration from these techniques, specifically the recursive computation and merging of coordinate-to-count maps during backtracking from  [55]–[58]. Cost-based optimizers in these systems, such as Free Join’s [58], together with the AGM bound [59], [60], further inform our initial exploration of cost-based hybrid mechanism detailed in the full version [37]. However, more accurate cost estimates may conversely require more expensive estimation methods, such as LpBound [61], and/or specialized data storages and execution engines, such as Free Join’s COLT [58] and its integration to DuckDB [62].

6.0.0.2 Aggregation Push-down and Factorizations

Aggregation push-down reduces intermediate results via early or deferred aggregation. Classical approaches include eager and lazy aggregation [63] and integrating \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape GROUP BY}}}\) into cost-based optimization [64]. GuAo [40] identifies cases where join materialization can be avoided entirely and introduces a corresponding physical operator for SparkSQL [65]. Its propagation of frequencies grouped by join attributes resembles BaCon’s bucketization in single-query settings. However, it relies on binary joins, whereas our approach support multi-way merging of count maps. Factorized databases [22]–[24] eliminate tuple-level redundancy in query results through compact representations that can support efficient aggregation beyond \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape COUNT}}}\). These works, focusing on eliminating intra-query redundancy, are complementary to our approach, which also exploits inter-query sharing. Furthermore, these works typically employ non-traditional storage layout different from traditional relational databases.

6.0.0.3 Optimized Batch Processing of Aggregate Queries

LMFAO [66] evaluates batches of ground-by aggregates over shared joins without materializing intermediates by decomposing queries into views, organizing them via a join tree, and executing a multi-output plan. Like PostFilt, it encodes selection predicates as conditional expressions within aggregates. Unlike BaCon, LMFAO does not pre-process overlaps among cross-query predicates, but instead focuses on sharing computation of join tree traversal and attribute-ordered evaluation, and is implemented as a standalone execution engine.

6.0.0.4 Multi-Query & Shared Workload Optimization

Multi-query optimization (MQO) [67] identifies shared/similar subexpressions across queries and evaluate them jointly or via plan rewriting. Zhou et al. [68] propose a common subexpression manager integrated into Microsoft SQL Server, demonstrating improvements on workloads of tens of queries. Shared Workload Optimization (SWO) [69] extends this idea to larger workloads by sharing operators, often requiring specialized execution engines. These approaches target general workloads and require accurate cost estimates.

6.0.0.5 Learned Cardinality Estimation

Query-aware cardinality estimation (CE) models [5]–[12], [18], [70] learn from query-count pairs. Training is typically performed either in a single-shot manner, where a model is (re-)trained from scratch on a batch of queries [6], [7], [12], [18], [71], or in multiple rounds, where the model is incrementally updated as new query-count pairs become available [5], [70], [72]. Some hybrid CE models [9], [70] additionally require data statistics, e.g., samples/histograms. Recent work studies robustness, training efficiency, and adaptivity to data updates and workload shifts [13], [18]–[21], [70], [72], [73], increasing the demand for efficiently supporting counting queries.

6.0.0.6 Other Related Work

Our work is also related to continuous query processing. More details are provided in the full version [37].

7 Conclusion↩︎

In this paper, we presented BaCon, a method for efficient batch processing of counting queries. BaConbrings together multiple optimization ideas, focusing particularly on developing compact, alternative representations of intermediate results that enable fine-grained sharing of computation. BaConcombines lightweight SQL execution with client-side processing, incorporating a suite of optimizations to ensure practical performance on our target workloads. A strength of BaConis its practicality: it can be deployed without modifying DBMS internals or physical designs. Components of BaConcan be accelerated using efficient UDF implementations (such as C-extensions in PostgreSQL), if they are supported by the DBMS. Our results demonstrate significant performance gains across real workloads with diverse characteristics. This level of improvement is empowering: shorter (re)training times make learned CE more practical and allow larger, more comprehensive training workloads.

BaConopens up several promising directions for future work. Extending it to support richer join structures, more expressive selection predicates, and more complex aggregates (complex expression inputs or non-algebraic aggregate functions) would further broaden its applicability. Beyond functional extensions, there are opportunities for more optimization, such as sharing computation across join patterns; delayed evaluation of \(\oplus\) and \(\otimes\) in count map expressions (and adapting ComputeCountsto take advantage); more intelligent selection of tree-based execution plans; aggressive “short-cutting” of all FK-PK edges; caching and more sophisticated parallelization. Finally, new applications and additional optimizations will likely require models beyond the current Hybridto enable cost-based selection of processing methods.

References↩︎

---

1. This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment.
   

   Proceedings of the VLDB Endowment, Vol. 19, No. 9ISSN 2150-8097.
   doi:10.14778/3819518.3819567
   ↩︎

2. For simplicity, we discuss only counting queries here, but our methods easily generalize to all distributive and algebraic SQL aggregates [36] including also \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape SUM}}}\), \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape MIN}}}\), \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape MAX}}}\), \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape AVG}}}\), and \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape STDDEV}}}\), where each input expression is a single attribute or computable over attributes from the same table.↩︎

3. More precisely, we remove from \(Q\) any table outside \(\mathcal{R}\); remove from any equivalent class in \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\Join}_{Q}\) any attribute outside \(\mathcal{R}\) and then remove any empty or singleton equivalent class; and remove any entry in \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape Preds}}}^{\sigma}_{Q}\) for an attribute outside \(\mathcal{R}\).↩︎

4. Note that the direction is important: a PK-FK edge, where the parent table has the primary key, would be a bad candidate to “short-cut,” with an opposite argument.↩︎

5. If each binding involves multiple attributes, we order the bindings lexicographically.↩︎

6. We have also evaluated an alternative implementation of PostFilt based on materialized views. The details and results, reported in the full version [37], show that materialization introduces additional storage costs and preparation-time overhead, without providing overall performance benefits. Hence, 5 focuses on the current implementation of PostFilt.↩︎

7. For example, if \(\alpha\) is an integer, \(\text{next}{(\alpha)} = \alpha + 1\); if \(\alpha\) is a \(\text{\scalebox{0.9}[1.0]{\textsf{\upshape timestamp without time zone}}}\), \(\text{next}{(\alpha)} = \alpha + 1\) microsecond; and so on.↩︎