LEARNT: A Practical Estimator for Cardinality of LIKE Queries with Formal Accuracy Guarantees Hai Lan
Zhifeng Bao
Divesh Srivastava
The University of Queensland Brisbane, Australia [email protected]
The University of Queensland Brisbane, Australia [email protected]
AT&T Chief Data Office Bedminster, NJ, USA [email protected]
Shixun Huang
Yuwei Peng
Yang Yu
University of Wollongong Wollongong, Australia [email protected]
Wuhan University Wuhan, China [email protected]
Wuhan University Wuhan, China [email protected]
ABSTRACT We study the problem of cardinality estimation for LIKE queries on string data, focusing on the most common patterns in real workloads: prefix, suffix, and substring queries. We propose LEARNT, a LIKE query Estimator with Accuracy, Robustness, Negligible overhead, Tunability, and Theoretical guarantees. LEARNT formulates estimation as a bucket-classification problem, and upon correct classification, it yields formal bounds on Q-error for the queries with non-empty answer. It employs a memory-efficient bucketed layered-filter architecture with Bloom filters and compact auxiliary tables, together with optimizations that exploit query skew to reduce storage. For the queries that have empty answer, LEARNT incorporates dedicated filter-based and prefix-walk strategies, providing probabilistic guarantees on correct identification. Furthermore, to support arbitrarily long query strings, we extend LEARNT with Markov modeling scheme that composes short-query statistics into estimates for longer queries. A theoretical framework guides parameter selection to minimize storage under accuracy and robustness constraints. Extensive experiments on four real-world datasets show that LEARNT consistently outperforms state-of-theart methods such as CLIQUE and LPLM, achieving 1.3–1.7× lower mean Q-error, significantly lower tail errors, and up to 70× faster construction with comparable memory usage. PVLDB Reference Format: Hai Lan, Zhifeng Bao, Divesh Srivastava, Shixun Huang, Yuwei Peng, and Yang Yu. LEARNT: A Practical Estimator for Cardinality of LIKE Queries with Formal Accuracy Guarantees. PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/DataAutonomyLab/ce4str.
1
INTRODUCTION
Cardinality estimation is a cornerstone of modern cost-based query optimizers [22, 25], and numerous approaches have been proposed 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 [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX
Table 1: LIKE Query Pattern Frequencies in Real Benchmarks Benchmark JOB [7] TPC-H [11] CEB [6] STACK [9] TPC-DS [10] DSB [14]
𝑆% 17 3 0 8 1 1
%𝑆 0 1 0 1538 0 0
%𝑆% 68 1 4865 346 0 0
Others 32 2 0 0 0 0
for different data types [15, 20, 23, 28, 30]. In this paper, we focus on cardinality estimation for LIKE queries. Motivated by the prevalence of prefix (𝑆%), suffix (%𝑆), and substring (%𝑆%) patterns observed in real workloads (Table 1), we concentrate on these three cases. Studied Problem. Let a string 𝑆 be a sequence of characters 𝑠 1 . . . 𝑠 |𝑆 | drawn from a predefined vocabulary V. A (prefix, suffix, or substring) LIKE query 𝑄, [%]𝑞 1 . . . 𝑞 |𝑄 | [%], is a string where each 𝑞𝑖 ∈ V and has at least one wildcard symbol %. A string 𝑆 matches 𝑄 if it satisfies the pattern of 𝑄, denoted as 𝐼 (𝑆, 𝑄) = 1; otherwise, 𝐼 (𝑆, 𝑄) = 0. To this end, given a string dataset S and a LIKE query 𝑄, the cardinality estimation for 𝑄 on S aims to estimate the ∑︁ number of strings in S that match 𝑄, i.e., 𝑆 ∈ S 𝐼 (𝑆, 𝑄). Depending on whether 𝑄 returns an empty result, we classify 𝑄 as a non-empty-answer query if it matches at least one string in the dataset, and as a empty-answer query otherwise. As we will show shortly, empty-answer queries are often overlooked by previous work but very important to handle effectively.
1.1
Identified Research Gaps
For a cardinality estimator to be practical in a production database system, accuracy alone is not sufficient. Since cardinality estimates are invoked repeatedly during query optimization, an estimator must provide reliable predictions across diverse query patterns and cardinality ranges, avoid catastrophic errors that may mislead the optimizer, handle empty-answer queries conservatively, and impose low construction, storage, and inference overheads. These requirements are particularly important for LIKE queries over string data, where query patterns, string distributions, and workloads can vary significantly across applications. Existing methods fall into two major categories: non-learning based approaches [18, 24] and learning-based approaches [13, 21, 26, 27, 29] (see Sec. 2 for details). Based on an in-depth survey, summarized in Table 2, we identify four key research gaps: G1: Insufficient Accuracy for Non-empty-answer Queries. Learningbased methods have shown notable accuracy gains over traditional
MO
techniques such as PostgreSQL’s estimator [1]. However, due to the complexity of string data distributions, these methods often struggle to generalize across datasets, query patterns, cardinality spectrum. For example, our experiments show that existing learning-based estimators yield high mean Q-errors on the DBLP-AN dataset (cf. Sec.8.2) and fail to handle low-cardinality and high-cardinality queries simultaneously (cf. Sec.8.3). Such inconsistent behavior across the cardinality spectrum can lead to brittle or suboptimal query plans in cost-based optimizers.
Prep. Time
Acc. (G1) + ++ +
Err. Bound (G2) ✕ ✕ ✕
Empty-ans. (G3) + +++ +++
Prep. (G4) +++ ++ +
Space (G4) +++ + +
E2E [27] Astrid [26] LPLM [13] CLIQUE [21] SSCard [29]
+ ++ + ++ ++
✕ ✕ ✕ ✕ ✕
+ ++ ++ +++ +++
+ + + + ++
+ +++ +++ +++ ++
LEARNT
+++
✓
+++
+++
+++
E2E
Accuracy
Astrid
LPLM
DBLP-AN
Infer. Time
Robust. Prep. Time
Storage Empty Ans. Query
CLIQUE
SSCard
Accuracy
Robust.
Storage Empty Ans. Query
query into its corresponding bucket. This idea allows us to provide formal guarantees on the maximum estimation error if we can correctly assign each query into its bucket. We parameterize the bucket boundaries with a user-specified error bound, enabling the control between estimation accuracy and memory usage. Bucketed Layered Filter Architecture (Sec. 4). To assign queries to their corresponding buckets, LEARNT adopts a bucketed layered filter architecture (cf. Sec. 4.2). Each bucket contains a multi-layer structure of Bloom filters and a small auxiliary table. The Bloom filters serve as compact probabilistic tests for determining whether a query belongs to the bucket, quickly filtering out non-members, while the auxiliary table removes residual false positives. This layered design enables accurate bucket assignment with low storage and computation overhead. To further reduce memory consumption, we exploit the empirical skew in query distributions. We avoid constructing explicit filters for the first bucket, which captures the majority of non-empty-answer queries. Additionally, we introduce a frontier-based optimization (cf. Sec. 4.3), which selectively retains only representative (“frontier”) queries during filter construction, further reducing space without sacrificing accuracy. Empty-answer Query Estimation (Sec. 5). LEARNT also provides dedicated support for empty-answer query estimation upon the structure built for non-empty-answer queries. We design two complementary strategies: a direct filter-based method and a prefixwalk refinement that leverages partial membership checks to detect queries with cardinality equal to 0 early. Both strategies are formally analyzed, and we derive theoretical bounds on their misclassification probabilities, demonstrating that LEARNT achieves conservative yet efficient estimation for empty-answer queries. Theoretical Parameter Selection (Sec. 6). We present a theoretical framework for parameter selection. We derive expressions for the storage cost in terms of the number of layers and the false positive rates of the Bloom filters, and formulate an optimization problem under user-defined error bound and probability of misclassification of empty-answer queries to minimize memory usage. Long Queries Support (Sec. 7). The core LEARNT approach is designed for queries with the limited length. Here, we extend LEARNT to support long queries via Markov modeling. By modeling dependencies among consecutive short substrings, this extension reuses LEARNT’s structure to effectively estimate long queries. Extensive Experiments (Sec. 8). We conduct extensive experiments on four real-world datasets and observe that LEARNT (1) consistently achieves 1.3–1.7× lower mean Q-error than state-ofthe-art methods (e.g., CLIQUE [21]), while also significantly reducing tail errors with competitive memory usage; (2) LEARNT requires at most one-third of the construction time of non-learning-based
Note: (1) Acc. refers to estimation accuracy. empty-ans. refers to empty-answer queries. Prep. indicates preprocessing time required before supporting queries. (2) More + means higher accuracy or lower cost, ✓ : supported, ✕: not supported.
G2: Lack of Robustness and Error Bound for Non-empty-answer Queries. Existing estimators often fail to maintain accuracy across the full spectrum of cardinalities and varying query string lengths (cf. Sec. 8.3). For instance, CLIQUE [21] incurs large errors on highcardinality queries, while LPLM [13] underperforms in low-cardinality cases. More importantly, none of these methods offers formal error bounds – individual estimates can be arbitrarily far from the truth. G3: Unreliable Handling of Empty-answer Queries. None of the existing approaches offers formal guarantees for correctly identifying empty-answer queries, leaving their reliability in such cases uncertain. How to properly handle them remains overlooked by existing methods and causes inconsistent accuracies: some perform poorly across test cases, while others succeed only on specific datasets. For example, in our experiments, LPLM [13] identifies at most 25% of empty-answer queries on DBLP-AN. G4: Excessive Memory and Computation Overheads. We evaluate both memory efficiency (i.e., memory footprint) and time efficiency, including the preprocessing time required before supporting queries and the online inference latency. Existing estimators often incur substantial overheads in at least one of these aspects. For example, LPLM [13] requires approximately 11 hours to prepare its training data, even with 30 parallel processes on the IMDB-MT dataset, and E2E [27] consumes more than 20 MB of memory at inference time.
1.2
LEARNT
Author
Figure 1: Comparison of Estimators on Substring Queries
Table 2: Comparative Analysis of Representative Cardinality Estimation Methods for 𝑆%, %𝑆, and %𝑆% Queries. Note: MO, LBS, and SSCard only support substring queries (%𝑆%). Method PostgreSQL [1] MO [18] LBS [24]
LBS
Infer. Time
Our Proposed Methods and Contributions
To address the above research gaps, we introduce LEARNT, a LIKE query Estimator with Accuracy, Robustness, Negligible overhead, Tunability, and Theoretical guarantees. Classification-based Formulation (Sec. 3). For non-empty-answer queries, LEARNT reformulates cardinality estimation as a bucket classification problem. Instead of directly regressing the exact cardinality, we partition the cardinality space into a sequence of buckets, each defined by a lower and upper bound and associated with a representative estimate. The estimator then classifies each 2
methods and less than 1/70 of the time required by learning-based methods. Overall Takeaway. To provide an intuitive overview of our method’s strengths, Figure 1 compares LEARNT with state-of-the-art estimators across key evaluation dimensions: accuracy, robustness, empty-answer query identification, preprocessing time, inference time, and storage overhead. Taken together, these results show that LEARNT is not only an accurate estimator, but also a practical one under deployment-oriented evaluation criteria. It addresses the key requirements of practical LIKE-query cardinality estimation in a unified design: accurate estimates for non-empty-answer queries, formal robustness guarantees, conservative handling of empty-answer queries, tunable accuracy–overhead trade-offs, and low construction, storage, and inference overheads. This balance is important for cost-based optimizers, where cardinality estimators must be invoked frequently and maintained efficiently as data and workloads evolve.
2
for all generated substrings. However, LPLM’s memory footprint is low since it only needs to store the trained model. SSCard [29], the latest study, is designed specifically for substring queries. It extends the FM-index to support multiple strings and organizes it using a pruned suffix tree, enabling accurate estimation for short patterns and effective compression – especially on large, skewed alphabets. It also incorporates spline interpolation with error bounds, along with bidirectional estimation and incremental updates to balance accuracy and space efficiency. Traditional Approaches. Early estimators build summary structures – such as suffix trees or pruned suffix trees – to predict substring selectivity. MO [16–18] uses a pruned suffix tree, LBS [24] adds minimal substrings with an 𝑁 -gram table, and P-LSH [12] relies on histograms of frequent positional patterns. However, in recent studies, Astrid [26] and LPLM [13] show that these methods still could suffer from a large mean Q-error because they cannot capture complex dependencies among characters and substrings.
3
RELATED WORK
Existing cardinality estimation on strings (matching LIKE predicates) falls into two categories: learning-based methods and traditional non-learning based methods. Learning-based Approaches. Five recent methods –E2E [27], Astrid [26], CLIQUE [21], LPLM [13], SSCard [29] – use learned models. E2E and Astrid are designed to support the three query patterns considered in this study. E2E generates and embeds a set of representative patterns and indexes them with a in-memory trie. For an online query, E2E identifies a stored pattern that covers the query and uses its embedding as input to the estimation model. In E2E, the in-memory trie incurs a substantial memory overhead. Astrid [26] provides two variants: Embed and NLM. The Embed variant learns embeddings that queries with similar string patterns and selectivities are mapped to nearby vectors, while NLM employs a neural language model to predict the probability of each character conditioned on the preceding characters in the query. Although Embed achieves lower Q-error than NLM, it incurs significantly higher training cost, as it requires processing a large number of training triplets to learn the embedding space effectively. In addition to the three fundamental patterns, CLIQUE [21] also supports %𝑆%𝑆%, %𝑆%𝑆, and 𝑆%𝑆%. CLIQUE presents an efficient algorithm to compute exact cardinalities for a given query set. It then trains a learning-based model enhanced with extended 𝑁 gram tables: for each query, it uses these tables to derive an upper bound1 on the true cardinality, feeds this bound (along with the query string) into the model, which predicts a coefficient 𝑝 ∈ [0, 1], and outputs the final estimate as 𝑝 times the upper bound. LPLM [13] generalizes to queries with any number of ‘%’ and ‘_’ wildcards by decomposing a query into a sequence of substrings and training a model to predict each substring’s conditional probability. It then multiplies these probabilities by the dataset size to obtain the final cardinality estimate. Despite this flexibility, LPLM underperforms on the most common patterns (𝑆%, %𝑆, %𝑆%), and incurs high training cost because it must compute true cardinalities
RECASTING ESTIMATION AS CLASSIFICATION
The key estimation idea of our approach for non-empty-answer queries lies in transforming the cardinality estimation problem for LIKE queries into a classification task. Specifically, we: • Partition the cardinality domain into 𝑛 buckets {𝐵𝑖 }𝑛𝑖=1 , each defined by a lower bound 𝐵𝑖 .𝑐𝑙 , an upper bound 𝐵𝑖 .𝑐𝑢 , and a representative estimate 𝐵𝑖 .𝑒𝑠𝑡. • Classify 𝑄 by assigning it to 𝐵𝑖 such that the cardinality of 𝑄 is in the range, [𝐵𝑖 .𝑐𝑙 , 𝐵𝑖 .𝑐𝑢 ], and returning 𝐵𝑖 .𝑒𝑠𝑡 as the estimate. This classification-based formulation guarantees that, for any query that is correctly assigned to its (︂ true bucket)︂ 𝐵𝑖 , the relative esti-
.𝑐𝑢 𝐵𝑖 .𝑒𝑠𝑡 mation error is bounded by max 𝐵𝐵𝑖𝑖.𝑒𝑠𝑡 , 𝐵𝑖 .𝑐 . Thus, correctness 𝑙 of bucket classification directly implies a formal bound on Q-error. To enable explicit control over the maximum estimation error, we introduce a user-tunable error bound parameter 𝑒𝑏 > 1. The bucket boundaries are defined as follows: (1) 𝐵 1 .𝑐𝑙 = 1; (2) 𝐵𝑖 .𝑐𝑙 = 𝐵𝑖 −1 .𝑐𝑢 +1 for 𝑖 > 1; (3) 𝐵𝑖 .𝑐𝑢 = ⌊𝐵𝑖 .𝑐𝑙 · 𝑒𝑏 2 ⌋; (4) 𝐵𝑖 .𝑒𝑠𝑡 = 𝐵𝑖 .𝑐𝑙 · 𝑒𝑏. Under the assumption of correct bucket classification, the worstcase Q-error of the estimator is exactly 𝑒𝑏. In practice, we set 1 < 𝑒𝑏 < 2 to ensure the Q-error remains below 2, yielding consistently small estimation errors.
3.1
Potential Solutions and Why They Fall Short
While viewing the estimation problem as a classification problem is promising, the biggest challenge is how to reliably assign each query to its true bucket to avoid misclassifications? 3.1.1 Learning-based Approaches. One natural idea is to train a learning-based classifier, e.g., an embedding model [26] or a sequential model [13, 26] to map each query to its bucket. However, such models struggle to capture the character dependencies required for accurate bucket assignment. Moreover, the query distribution across buckets is highly skewed, making the classification problem imbalanced and training such models particularly challenging. 3.1.2 Summary-based Approaches. Ideally, a summary-based approach would index all non-empty-answer queries to provide exact bucket assignments. However, enumerating all possible non-emptyanswer queries is impractical due to unmanageable construction and storage overhead. Following existing studies [13, 21, 26], we
1 This upper bound can still be arbitrarily larger than the true cardinality and lacks
theoretical guarantees. 3
Table 3: Number of Non-empty-answer Queries on Author, DBLP-AN, and IMDB-MT with 𝐿 = 10. Pattern Author DBLP-AN IMDB-MT 𝑆% 815, 393 2, 145, 437 1, 108, 871 %𝑆 990, 451 1, 630, 169 1, 183, 711 %𝑆% 5, 377, 686 9, 574, 392 10, 159, 610
Table 4: Percentages (%) of Non-empty-answer Queries in Each Cardinality Range. Type Author-𝑆% Author-%𝑆 Author-%𝑆% DBLP-AN-𝑆% DBLP-AN-%𝑆 DBLP-AN-%𝑆% IMDB-MT-𝑆% IMDB-MT-%𝑆 IMDB-MT-%𝑆%
introduce a maximum query length 𝐿, rendering the query set finite and enumerable offline. While exact summaries, e.g., tries, hash table, are accurate, they incur prohibitive memory costs. Alternatively, we can construct a Bloom filter [5] for each bucket, a more compact approach, but suffers from two drawbacks: 1) High Memory Footprint. The filter size scales linearly with the number of non-empty-answer queries. With roughly 9.56 bits per item at a 1% false-positive rate, this design consumes 10.9 MB on the IMDB-AN dataset’s %𝑆% pattern based on Table 3. (2) Unresolved False Positives. False positives in Bloom filter may cause queries to match multiple buckets, resulting in ambiguous classification.
3.2
[3,6] 13.3 14.34 15.83 17.15 17.65 18.61 8.73 8.19 9.19
[7,15] 4.31 4.31 5.35 6.46 6.57 7.51 2.87 2.72 3.19
handle misclassified positive queries Prefix Query L=2, 𝒆𝒃 = 𝟏. 𝟓 Dataset ABCD ABBD AABC ABBC ADBA BCDA ABBA CDDA ACDA DADA ACDD ACDB
Overall Workflow of LEARNT
To address the limitations of these potential solutions, we propose LEARNT, a bucketed layered filter architecture (Sec. 4) based on Bloom filters, to support prefix, suffix, and substring non-emptyanswer queries with formal error guarantees for queries of length at most 𝐿. We further extend LEARNT to handle empty-answer queries (Sec. 5) and queries whose length exceeds 𝐿 (Sec. 7). Specifically, given a dataset S, an error bound 𝑒𝑏 , an optional probability threshold 𝑝𝑛 for correctly identifying empty-answer queries, and a query length limit 𝐿, for each query type: Offline Construction. LEARNT first enumerates all non-emptyanswer queries of length at most 𝐿 in S and partitions them into buckets according to 𝑒𝑏, thereby determining the number of buckets and the number of queries in each bucket. It then invokes the parameter selection method in Sec. 6 to determine the optimal configuration (e.g., number of layers and Bloom filter false positive rates) and constructs the estimator based on Algo. 1 in Sec. 4 accordingly. Online Estimation. For a query 𝑄, if |𝑄 | > 𝐿, LEARNT applies the Markov-based extension described in Sec. 7. Otherwise, it performs the prefix-walk refinement in Sec. 5.2, which handles both emptyanswer and non-empty-answer queries in a unified manner. Both process are based on the estimation process in Algo. 2 in Sec. 4.2.3.
4
[1,2] 80.13 79.63 76.19 72.62 72.43 69.34 86.54 87.39 85.38
𝑩𝟏[𝟏, 𝟐] AA%,AD%, BC% CD%,DA%, B%,C%,D%
[16,36] 1.33 1.14 1.62 2.37 2.25 2.87 1.16 1.04 1.31
[37,83] 0.53 0.36 0.57 0.81 0.69 0.99 0.43 0.41 0.54
[84,) 0.41 0.22 0.44 0.59 0.4 0.69 0.28 0.25 0.4
handle misclassified negative queries
Layer 1
Layer 2
Layer 3
No layered filter constructed for 𝑩𝟏 based (based on Sec. 4.1)
𝑩𝟐 [3,6] AB%, AC%
𝓜𝟏,𝟐 BF([AB%, AC%])
𝑩𝟑 [7,15] A%
𝓜𝟏,𝟑 Table(A%)
𝓜𝟐,𝟐 BF([A%,AD%])
𝓜𝟑,𝟐 Table([AB%])
Figure 2: Example of Bucketed Layered Filter
4.1
Skipping Filter Construction Motivated by Query Skew
A major issue with Bloom filters is their large memory cost when many non-empty-answer queries exist. Can we reduce the number of queries used in filter construction? Our empirical study on common string datasets shows that this is indeed feasible. Table 42 shows the percentages of queries in each predefined cardinality ranges (𝑒𝑏 with 1.5) under three datasets and different query patterns. It reveals the following key observation: Observation 1. The query distribution (the number of queries in each cardinality range) across datasets and query patterns is highly skewed, with the majority of queries exhibiting low cardinality. This skewed distribution simplifies filter construction. Since most queries lie in [1, 2], i.e., 𝐵 1 , building a layered filter for 𝐵 1 is unnecessary. We can instead build filters only for buckets 𝐵𝑖 (𝑖 > 1). During classification, if a query matches none of these filters, we assign it to 𝐵 1 with estimate 𝑒𝑏. This greatly reduces memory while preserving classification accuracy.
BUCKETED LAYERED FILTER: A MEMORY-EFFICIENT CLASSIFIER
4.2
A Layered Filter for Each Bucket
4.2.1 Idea of A Layered Filter. Figure 2 illustrates the bucketed layered filter structure and construction using a concrete prefixquery example with 𝐿 = 2 and 𝑒𝑏 = 1.5. The enumerated queries are partitioned into three buckets, 𝐵 1 , 𝐵 2 , and 𝐵 3 . The first bucket 𝐵 1 is skipped based on Sec. 4.1 and we focus on building the filter for 𝐵 2 here. The goal is to ensure that all queries in 𝐵 2 return true, while queries from other buckets return false. Layer 1. We first build a Bloom filter on the positive set 𝐵 2 .𝐾 = {AB%, AC%} and store it in M1,2 (M 𝑗,𝑖 stores the data structure of 𝑗-layer of 𝐵𝑖 ). This guarantees that all 𝐵 2 queries pass Layer 1.
To ensure the formal error bounds in Sec. 3, we require precise bucket assignments, which learning-based models struggle to guarantee on skewed distributions. We hence introduce a summarybased classifier that assigns every non-empty-answer query within length 𝐿 to its correct bucket. We extend support to arbitrarily long queries in Sec. 7. Bloom filters offer an excellent starting point due to their favorable space–accuracy balance, but two challenges emerge, a large memory footprint, and unresolved false positives. We address the first challenge by exploiting the skew in query distributions (Sec. 4.1), storing far fewer entries than a naive design. To eliminate false positives, we adopt a layered filter with a small lookup table (Sec. 4.2). We further cut storage by leveraging relationships among queries (Sec. 4.3), while preserving correct classification.
2 To produce the empirical query cardinality distributions, we enumerate all prefix,
suffix, and substring with length at most 𝐿 for each dataset and compute their exact cardinalities by counting matching records. The resulting counts are aggregated to form the empirical distributions reported. 4
Layer 2. However, false positives in Bloom filter may allow some queries from 𝐵 1 or 𝐵 3 to pass M1,2 as well. We evaluate all negative queries (i.e., queries from 𝐵 1 and 𝐵 3 ) against M1,2 and collect those misclassified as positive. They are 𝐴% and 𝐴𝐷% in the example. We then build a second-layer structure to capture these misclassified negative queries. Here we build another bloom filter stored in M2,2 . Layer 3. Some queries from 𝐵 2 may be mistakenly rejected (false negatives) as they may be incorrectly classified as positive in M2,2 , which is built on the queries not in 𝐵 2 . In the example, 𝐴𝐵% is classified in M2,2 . To correct this, we add a third layer that records 𝐴𝐵% by building up a lookup table stored in M3,2 . Query Example. Consider the query AB%, which belongs to bucket 𝐵 2 . It first passes Layer 1 (M1,2 ), which is built on 𝐵 2 ’s positive keys. However, it incurs a false positive at Layer 2 (M2,2 ), which is constructed to capture misclassified negative queries. This would incorrectly reject 𝐴𝐵%. The final lookup table (M3,2 ) corrects this by explicitly storing such remaining positive queries, ensuring AB% is correctly classified into 𝐵 2 . Discussion. The above example consists of three layers in 𝐵 2 , but the process can be extended with additional alternating Bloom filters. In general, odd-numbered layers are built on the currently misclassified positive queries, while even-numbered layers are built on the currently misclassified negative queries. The final layer is always implemented as a deterministic lookup table. This design is crucial: although intermediate Bloom filters may introduce false positives, the final lookup table explicitly corrects any remaining misclassifications, ensuring exact bucket assignment. Consequently, the error bound derived in Sec. 3 is guaranteed to hold. In Sec. 4.2.2, we formalize the layered architecture for a general bucket 𝐵𝑖 and present its systematic construction algorithm. The number of Bloom-filter layers is determined in Sec. 6, where we develop a principled parameter selection strategy. The formal online query process is described in Sec. 4.2.3. 4.2.2 Bucketed Layered Filter Building. Algo. 1 presents the process of building the bucketed layered filter. Suppose the two-dimensional array, M with 𝑚 rows and 𝑛 columns, is used to store the bucketed layered filter. For each bucket 𝐵𝑖 , we build a layered filter with 𝑚 (𝑚 ≥ 2) layers. M 𝑗,𝑖 refers to the summary (either a Bloom filter or a lookup table) of bucket 𝐵𝑖 at the 𝑗-th layer. Let 𝑓 𝑗 denote the false positive ratio of 𝑗-th layer.3 For each 𝐵𝑖 (𝑖 > 1), we build the layered filter with following steps: Step 1: Collect Negative and Positive Queries. To avoid classifying the queries not in 𝐵𝑖 with 𝐵𝑖 , we collect queries from other buckets and check their classification during our building process. We call them as negative queries for 𝐵𝑖 . Based on Observation 1, we design an online classification process that starts from 𝐵 2 , i.e., from the buckets with a large number of non-empty-answer queries. Hence, the queries in 𝐵 𝑗 (𝑗 < 𝑖 and 𝑗 ≠ 1) will never be misclassified in the layered filter of 𝐵𝑖 . We only collect queries from 𝐵 1 and 𝐵 𝑗 ( 𝑗 > 𝑖) and store them in Q𝑛𝑒𝑞 (Lines 2-6) and we initialize Q𝑝𝑜𝑠 with 𝐵𝑖 .𝐾 (Line 7). In what follows, Q𝑛𝑒𝑞 and Q𝑝𝑜𝑠 store the currently misclassified negative queries and the positive queries, respectively. Step 2: Build Bloom Filters. Next, we proceed to build 𝑚 − 1 Bloom filters. The filter at each odd-numbered layer is built using the 3 For simplicity, we assume that the same layer of different buckets use the same false
positive ratio. This assumption is lifted in our parameter selection process. 5
Algorithm 1: Bucketed Layered Filter Building Process Input: bucket set 𝐵𝑖 (𝑖 ∈ [1, 𝑛]), number of layers 𝑚, false positive rates 𝑓 𝑗 (𝑗 ∈ [1, 𝑚 − 1]) Output: Bucketed Layered Filter M 1 M ← [ ]; 2 foreach 𝑖 ∈ [2, 3, ..., 𝑛] do 3 Q𝑛𝑒𝑔 ← [ ]; 4 foreach 𝑗 ∈ [1, 2, ..., 𝑛] do 5 if 𝑗 > 𝑖 or 𝑗 = 1 then 6 Q𝑛𝑒𝑔 .𝑎𝑑𝑑 (𝐵 𝑗 .𝐾 ); 7 8 9 10 11 12 13 14
Q𝑝𝑜𝑠 ← 𝐵𝑖 .𝐾; foreach 𝑗 ∈ [1, 2, ..., 𝑚 − 1] do Q𝑚𝑖𝑠 ← [ ]; if 𝑗 mod 2 = 1 then M 𝑗,𝑖 ← BuildBloomFilter(Q𝑝𝑜𝑠 , 𝑓 𝑗 ); foreach 𝑄 ∈ Q𝑛𝑒𝑔 do if 𝑄 ∈ M 𝑗,𝑖 then Q𝑚𝑖𝑠 .𝑎𝑑𝑑 (𝑄 ); Q𝑛𝑒𝑔 ← Q𝑚𝑖𝑠 ;
15
else
16
20
M 𝑗,𝑖 ← BuildBloomFilter(Q𝑛𝑒𝑔 , 𝑓 𝑗 ); foreach 𝑄 ∈ Q𝑝𝑜𝑠 do if 𝑄 ∈ M 𝑗,𝑖 then Q𝑚𝑖𝑠 .𝑎𝑑𝑑 (𝑄 );
21
Q𝑝𝑜𝑠 ← Q𝑚𝑖𝑠 ;
22 23
if 𝑚 mod 2 = 1 then M𝑚,𝑖 ← BuildTable(Q𝑝𝑜𝑠 );
24
else
17 18 19
25 26
M𝑚,𝑖 ← BuildTable(Q𝑛𝑒𝑔 ); return M
currently misclassified positive queries, i.e., Q𝑝𝑜𝑠 (Line 11) while the filter at each even-numbered layer is built using the currently misclassified negative queries, i.e., Q𝑛𝑒𝑞 (Line 17). After building the filter at each layer, we evaluate the effectiveness of the filter by checking which queries from the opposing class, Q𝑛𝑒𝑞 or Q𝑝𝑜𝑠 , incorrectly pass through the filter, i.e., the currently misclassified queries (Lines 12-14 and Lines 18-20). They are stored in Q𝑚𝑖𝑠 , which becomes the new Q𝑛𝑒𝑞 or Q𝑝𝑜𝑠 for the next layer.
Step 3: Construct the Lookup Table. The final layer is a built lookup table rather than a Bloom filter to ensure precise membership decisions. If 𝑚 is odd, the table is constructed from the remaining Q𝑝𝑜𝑠 ; otherwise, it is built from Q𝑛𝑒𝑔 . 4.2.3 Online Classification Process. The pseudo-code is presented in Algo. 2. Given a query 𝑄, we sequentially check whether 𝑄 belongs to a bucket 𝐵𝑖 in ascending order, starting from 𝐵 2 , followed by 𝐵 3, 𝐵 4 , and so on. For each 𝐵𝑖 , we check 𝑄 layer by layer. Since the odd-numbered layers and even-numbered layers are built upon positive queries and negative queries, respectively, if 𝑄 is not in an odd-numbered layer, it must be a negative query and we go to check next bucket. Similarly, it 𝑄 is not in an even-numbered layer, it must be a positive query and we return 𝑖. If 𝑄 is filtered out from all buckets 𝐵𝑖 for 𝑖 ≥ 2, the algorithm returns 1.
Algorithm 2: Query Classification
set of patterns, which is infeasible. Moreover, practical query optimizers, e.g. PostgreSQL, rarely predict a cardinality of zero unless emptiness can be proven (e.g., contradictory predicates). Assigning zero without certainty may prematurely eliminate execution paths or suppress necessary joins, leading to severely suboptimal plans. In our framework, 𝐵 1 represents the smallest non-zero cardinality range (e.g., [1, 2] when 𝑒𝑏 = 1.5). Mapping an empty-answer query to 𝐵 1 therefore introduces only a minimal, bounded overestimate. Compared to assigning a larger bucket, this conservative choice limits the impact on plan generation while preserving the lightweight design of the estimator. Motivated by this, we assign empty-answer queries to bucket 𝐵 1 and develop two strategies: a naive filter-based method (Sec.5.1) and a prefix-walk refinement (Sec.5.2), both of which integrate naturally with our layered filter framework and provide formal guarantees.
Input: query 𝑄, a bucketed layered filer M, bucket number 𝑛, layer number 𝑚 Output: bucket ID that 𝑄 belongs to 1 foreach 𝑖 ∈ [2, 3, ..., 𝑛] do 2 foreach 𝑗 ∈ [1, 2, ..., 𝑚 − 1] do 3 if 𝑄 ∉ M 𝑗,𝑖 then 4 if 𝑗 mod 2 = 1 then 5 break; ⊲ 𝑄 is an invalid query for 𝐵𝑖 . else
6
return 𝑖;
7
if 𝑄 ∈ M𝑚,𝑖 XOR (𝑚 mod 2 = 1) then return 𝑖;
8 9 10
return 1;
4.3
Frontier-based Pruning
5.1
Recall that to guarantee correct bucket ID predictions for all queries, the construction of the second-layer Bloom filter in each bucket 𝐵𝑖 (𝑖 ≥ 2) requires checking for potential false matches against the queries in bucket 𝐵 1 (Lines 5-6 in Algo. 1). Because 𝐵 1 can be large, false positives at the first-layer Bloom filter may cause a substantial number of its queries to be misclassified. This enlarges the candidate set for the second layer, requiring it to be built over a much larger query set and thus incurring higher memory cost.
Filter-Based Classification
Let 𝑄 zero denote an empty-answer query. Assume we have 𝑛 buckets, 𝐵 1, . . . , 𝐵𝑛 , where each 𝐵𝑖 (𝑖 ≥ 2) is equipped with a layered filter of 𝑚 layers. Each layer 𝑗 has a false positive rate 𝑓 𝑗 , and the final layer is a lookup table. During classification, we sequentially probe the buckets from 𝐵 2 to 𝐵𝑛 , as Sec. 4.2.3. Under the assumption of independence between false-positive events across layers, which follows from using independent hash functions for each Bloom filter layer.4 We derive the probability that an empty-answer query is assigned to each bucket, formalized in Lemma 5.1.
Construction Process. We propose a frontier-based pruning strategy that selectively uses a subset of 𝐵 1 ’s queries when constructing the Bloom filter for each 𝐵𝑖 . Specifically, we define frontier queries (𝐵 1 .𝐹𝑄) as those that are not covered by any other query in 𝐵 1 . Formally, a query 𝑄 ∈ 𝐵 1 .𝐾 is a frontier query if there does not exist another 𝑄 ′ ∈ 𝐵 1 .𝐾 such that 𝑄 ′ is a prefix of 𝑄. For example, 𝐵 1 .𝐾 in Figure 2 is {𝐵%, 𝐶%, 𝐷%, 𝐴𝐴%, 𝐴𝐷%, 𝐵𝐶%, 𝐶𝐷%, 𝐷𝐴%}, then 𝐵 1 .𝐹𝑄 = {𝐵%, 𝐶%, 𝐷%, 𝐴𝐴%, 𝐴𝐷%}. In Algo. 1, this pruning is applied by replacing 𝐵 1 .𝐾 with 𝐵 1 .𝐹𝑄 in Line 6 when 𝑗 = 1, i.e., reducing the number of queries in 𝐵 1 being checked.
Lemma 5.1 (Classification Probability of Empty-answer Queries into 𝐵𝑖 ). Under the assumption of independent false-positive events, the probability 𝑝𝑖 of 𝑄 zero assigned to bucket 𝐵𝑖 is 𝑝𝑖 =
⌊ 𝑚−1 −1 2 ⌋ 2𝑘 ∑︂ ∏︂ 𝑘=1
𝑓 𝑗 · (1 − 𝑓2𝑘 ) + 1 {𝑚 mod 2=0} ·
𝑗=1
and the fall-through to 𝐵 1 is Pr[𝑄 zero → 𝐵 1 ] =
Online Classification. Using only frontier queries introduces a challenge during prediction. If a query 𝑄 ∈ 𝐵 1 is not a frontier query, it could be misclassified, since such a query is not explicitly considered during the filter construction process. To mitigate this, we refine the online prediction process. Instead of evaluating only 𝑄 itself (as in Sec. 4.2.3), we perform a prefix walk, which iteratively checks the bucket IDs associated with 𝑄 and its prefixes. If any prefix of 𝑄 is classified into 𝐵 1 , we assign 𝑄 to 𝐵 1 . Otherwise, we select the bucket with the smallest predicted ID. In Figure 2, consider a query 𝑄 = 𝐵𝐶%. By checking each prefix of it, {𝐵𝐶%, 𝐵%}, based on Algo. 2, we find that 𝐵% maps to 𝐵 1 . Thus, 𝑄 is predicted to belong to 𝐵 1 .
𝑚−1 ∏︂
𝑓𝑗
∏︁𝑛
𝑖=2 (1 − 𝑝𝑖 ).
Proof. There are two main cases that 𝑄 zero will be classified into 𝐵𝑖 : (1) it is not in any odd-numbered layer – the probability ∑︁ ⌊ 𝑚−1 ⌋ ∏︁2𝑘 −1 is 𝑘=22 𝑗=1 𝑓 𝑗 · (1 − 𝑓2𝑘 ); (2) if the last Bloom filter is at an even-numbered layer, i.e. 𝑚 mod 2 = 0, and 𝑄 zero is in that filter – ∏︁ the probability is 𝑚−1 𝑗=1 𝑓 𝑗 . Thus, the probability that 𝑄 zero will be classified in 𝐵𝑖 is the sum of them. For each 𝑖 ≥ 2, let 𝐸𝑖 be the event “𝑄𝑧𝑒𝑟𝑜 is classified in 𝐵𝑖 ”. So Pr[𝐸𝑖 ] = 𝑝𝑖 . By sequential probing and independence, 𝑖 −1 (︂∏︂ )︂ (︁ )︁ Pr[𝑄 zero → 𝐵𝑖 ] = Pr ¬𝐸 2 ∧ · · · ∧ ¬𝐸𝑖 −1 Pr[𝐸𝑖 ] = (1 − 𝑝 𝑗 ) 𝑝𝑖 , 𝑗=2
and if we end up in 𝐵 1 , giving the product over 𝑗 = 2..𝑛.
5
𝑖 ≥ 2,
𝑗=1
CLASSIFYING EMPTY-ANSWER QUERIES WITH THEORETICAL GUARANTEES
□
To simplify analysis, we assume all layers in 𝐵𝑖 share the same false positive rate 𝑓 . The misclassification probability becomes: {︄ 𝑓 −𝑓 𝑚 if 𝑚 mod 2 = 1 𝑝𝑖 = 𝑓 1+𝑓 (1) +𝑓 𝑚 if 𝑚 mod 2 = 0 1+𝑓
We now describe how our estimator handles empty-answer queries. Rationale for Mapping Empty-answer Queries to 𝐵 1 . Accurately identifying that a query has a cardinality of zero is intrinsically difficult. The space of potential empty-answer queries is substantially larger than that of non-empty-answer queries, and complete detection would require enumerating a prohibitively large
4 Each Bloom filter layer in each bucket is instantiated using an independent universal
hash function drawn from a hash family with pairwise independence. As a result, membership tests across layers and buckets correspond to independent Bernoulli trials. 6
5.2
(𝑛+𝑡𝑡 −2) (1 − 𝑞)𝑡 · (𝑛−1) 𝑡 . Hence, the desired probability is: Pr[𝑄 zero → (𝑛+𝑡𝑡 −2) 𝐵 1 ] = 1 − (1 − 𝑞)𝑡 · (𝑛−1) □ 𝑡 .
Prefix-Walk Refinement
To further improve robustness, we introduce a prefix-walk refinement strategy that examines multiple prefixes of the query. This approach increases the likelihood of correctly assigning 𝑄 zero to 𝐵 1 by detecting inconsistencies across prefix classifications. Let 𝑙 be the length of 𝑄 zero . We define a sequence of 𝑡 = 𝑙 − 𝑙 1 + 1 prefixes: 𝑄 0 = 𝑄 zero, 𝑄 1 = 𝑄 zero [: −1], . . . , 𝑄𝑡 −1 = 𝑄 zero [: 𝑙 1 ], where 𝑄 zero [: 𝑙 1 ] is the longest known non-empty-answer prefix. Each prefix 𝑄𝑘 is classified into a bucket ID 𝑏𝑘 ∈ {1, . . . , 𝑛} using Algo. 2. Since 𝑄𝑖 is a prefix of 𝑄𝑖 −1 , its true cardinality must be no smaller than that of 𝑄𝑖 −1 , i.e., 𝑏𝑖 ≥ 𝑏𝑖 −1 , and 𝑏 0 must be the smallest among all 𝑏𝑖 . Based on this monotonicity property, we determine the bucket assignment:
𝑞 above is also the probability of an empty-answer query classified with 𝐵 1 in Lemma 5.1. Here, we prove we can achieve a (𝑛+𝑡𝑡 −2) higher probability in Lemma 5.2. When 𝑡 ≥ 2, (𝑛−1) 𝑡 < 1. Thus, (𝑛+𝑡𝑡 −2) 𝑡 𝑡 2 1 − (1 − 𝑞) · (𝑛−1) 𝑡 ≥ 1 − (1 − 𝑞) ≥ 1 − (1 − 𝑞) . When 𝑞 ∈ (0, 1), (𝑛+𝑡𝑡 −2) 1 − (1 − 𝑞) 2 > 𝑞. Thus, we have 1 − (1 − 𝑞)𝑡 · (𝑛−1) 𝑡 > 𝑞, i.e., achieving a larger probability to classify 𝑄𝑧𝑒𝑟𝑜 with 𝐵 1 . Note 𝑙 1 is used solely for theoretical analysis and is not needed during online estimation. This is because for any prefixes 𝑄𝑖 and 𝑄 𝑗 , if 𝑖 < 𝑗, then the corresponding bucket IDs satisfy, 𝑏𝑖 ≤ 𝑏 𝑗 .
• If any 𝑏𝑘 = 1, assign 𝑄 zero to 𝐵 1 . Since our estimator never misclassifies non-empty-answer queries, the 𝑏𝑖 = 1 guarantees that 𝑄 must belong to 𝐵 1 based on the monotonicity property. • If there exists an index 𝑖 such that 𝑏𝑖 < 𝑏𝑖 −1 , we assign the query to 𝐵 1 . 𝑏𝑖 < 𝑏𝑖 −1 violates monotonicity property, i.e., at least 𝑄𝑖 −1 is assigned to wrong buckets. Since non-empty-answer queries are never misclassified, this implies that 𝑄𝑖 −1 is empty-answer; hence 𝑄𝑧𝑒𝑟𝑜 must be assigned to 𝐵 1 . • Otherwise, assign to 𝑏 0 , the smallest bucket id.
6
One of the key advantages of LEARNT is its tunability: users can control both estimation accuracy and system overhead via two intuitive parameters, the desired error bound 𝑒𝑏 for non-empty-answer queries and the minimum probability 𝑝𝑛 of correctly identifying empty-answer queries. Achieving this tunability requires configuring LEARNT, which is defined by parameters such as the number of buckets, the number of filter layers, and the false positive rates of the Bloom filters. In this section, we present a formal framework to guide parameters selection.
This rule enhances robustness by exploiting prefix-based signals indicative of invalidity. In the following, we present a probabilistic analysis of correctly classifying an empty-answer query under the assumption that each prefix 𝑄𝑘 is classified independently.5
6.1
𝑡
(𝑛 − 1)𝑡
Cost Modeling
We begin by analyzing the storage cost for a single bucket 𝐵𝑖 . Let 𝑁𝑝 = |𝐵𝑖 .𝐾 | denote the number of positive (in-bucket) queries and ∑︁ 𝑁𝑛 = 𝑗 ∈ [1,2,...,𝑛]∩( 𝑗 >1∪𝑗=1) |𝐵 𝑗 .𝐾 | denote the number of negative queries (from other buckets) considered during filter construction for 𝐵𝑖 . Let 𝐿 denote the maximum length of a query. Thus, a query in the lookup table takes 8𝐿 bits. The storage usage of 𝐵𝑖 consists of three parts: (1) Bloom filters in ∑︁ ⌊ 𝑚 ⌋ −ln𝑓2𝑖 −1 ∏︁𝑖 odd-number layers: 𝑖=12 (ln2) 2 𝑁𝑝 𝑗=1 𝑓2𝑗 −2 ; (2) Bloom filters ∑︁ ⌊ 𝑚−1 ∏︁ 2 ⌋ −ln𝑓2𝑖 −1 in even-number layers: 𝑖=1 𝑁𝑛 𝑖𝑗=1 𝑓2𝑗 −1 (3) Lookup (ln2) 2 𝑚 ∏︁ ⌊ ⌋ table in the last layer: 𝑁𝑝 𝑗=12 𝑓2𝑗 8𝐿 if 𝑚 mod 2 = 1, otherwise 𝑚 ∑︁ ⌊ ⌋ 𝑁𝑛 𝑗=12 𝑓2𝑗 −1 8𝐿. For simplicity in our analysis, we assume all Bloom filter layers within a bucket share the same false positive rate, 𝑓 . Given this, we can express the storage cost with: If 𝑚 mod 2 = 1, let 𝑚 = 2𝑘 + 1 (𝑘 ≥ 1) and we have:
Lemma 5.2 (Prefix-Walk Classification Probability of Empty-answer Queries into 𝐵 1 ). Assume each prefix 𝑄𝑘 is classified independently, and the probability of 𝑏𝑘 = 1 is 𝑞. Let 𝑡 be the number of prefixes. Then the probability of 𝑄𝑧𝑒𝑟𝑜 classified into 𝐵 1 is (︁𝑛+𝑡 −2)︁ Pr[𝑄 zero → 𝐵 1 ] = 1 − (1 − 𝑞)𝑡 ·
PARAMETER SELECTION
.
Proof. Let 𝑏 0, 𝑏 1, . . . , 𝑏𝑡 −1 be the bucket IDs assigned to prefixes 𝑄 0, . . . , 𝑄𝑡 −1 . The method outputs 1 if either of the following occurs: (1) At least one prefix is classified into bucket 1: ∃𝑘 : 𝑏𝑘 = 1. (2) The sequence contains a decrease: ∃𝑖 ∈ [1, 𝑡 − 1] : 𝑏𝑖 < 𝑏𝑖 −1 . We compute the complement event: • All 𝑏𝑘 > 1, which occurs with probability (1 − 𝑞)𝑡 . • The sequence 𝑏 0, . . . , 𝑏𝑡 −1 is non-decreasing over {2, . . . , 𝑛}. Let 𝑆 be the number of non-decreasing sequences of length 𝑡 over {2, . . . , 𝑛}, i.e., over a support of size (𝑛 − 1). This is a standard (︁ (︁ )︁ −1)︁ stars-and-bars problem [2]: 𝑆 = (𝑛−1)+𝑡 = 𝑛+𝑡𝑡 −2 . 𝑡 The total number of possible sequences with values in {2, . . . , 𝑛} is (𝑛 − 1)𝑡 , assuming independence. Therefore, the probability of a (𝑛+𝑡𝑡 −2) non-decreasing sequence conditioned on all 𝑏𝑘 > 1 is: (𝑛−1) 𝑡 . Multiplying this by the probability that all 𝑏𝑘 > 1, we obtain the total probability of not predicting bucket 1: Pr[𝑄 zero ̸→ 𝐵 1 ] =
𝑆 odd (𝑘, 𝑓 ) =
−ln𝑓 𝑁𝑝 + 𝑁𝑛 𝑓 (1 − 𝑓 𝑘 ) + 8𝐿𝑁𝑝 𝑓 𝑘 (ln2) 2 1 − 𝑓
(2)
And if 𝑚 mod 2 = 0, let 𝑚 = 2𝑘 (𝑘 > 1) and we have: ]︁ −ln𝑓 1 [︁ 𝑆 even (𝑘, 𝑓 ) = 𝑁𝑝 (1 − 𝑓 𝑘 ) + 𝑁𝑛 𝑓 (1 − 𝑓 𝑘 −1 ) + 8𝐿𝑁𝑛 𝑓 𝑘 2 (ln2) 1 − 𝑓 (3) The total storage is the sum of them over all buckets, 𝐵𝑖 (𝑖 ≥ 2).
5 Although prefix queries are structurally related, this assumption holds because each
6.2
prefix is mapped to hash values using independent hash functions. Even a singlecharacter change between successive prefixes (e.g., from 𝑄𝑖 to 𝑄𝑖 −1 ) results in an uncorrelated hash output under universal hashing. Consequently, membership tests for different prefixes are independent trials with respect to Bloom filter false positives.
6.2.1 Optimizing Parameters Without Empty-answer Query Constraints. Our primary goal is to select the number of layers 𝑚 (or equivalently, 𝑘 in Equation 2 and 3) and the false positive rate 𝑓 7
Parameters Optimization
Table 5: Statistics of string sets (S𝐷 ) and query sets (S𝑄 ).
in Bloom filters to minimize the total storage cost. Once the user specifies the desired error bound 𝑒𝑏, the number of buckets 𝑛 is determined. The values of 𝑁𝑝 , 𝑁𝑛 , and 𝐿 for each 𝐵𝑖 are fixed. However, this presents a mixed-integer optimization problem as in Equation 2 and 3, 𝑓 is continuous while 𝑘 is restricted to integers. To solve this efficiently, we adopt a practical, iterative approach: (1) Enumerate Layer: We iterate through a small set of integer values for the number of layers, 𝑚, starting from 2 and set 𝑘 = ⌊ 𝑚2 ⌋. And based on our empirical analysis, only a few values of 𝑚 suffice. (2) Find Optimal 𝑓 : For each chosen 𝑚 (𝑘), we find the optimal false positive rate, 𝑓 , that minimizes the storage cost function. 𝑆𝑜𝑑𝑑/𝑒𝑣𝑒𝑛 is a contentious function when 𝑓 ∈ (0, 1). Thus, the minimized value of 𝑆𝑜𝑑𝑑/𝑒𝑣𝑒𝑛 is obtained at the root of 𝑆 ′ (𝑘, 𝑓 ) = 0 or at the end point. However, setting 𝑆 ′ (𝑓 ) = 0 mixes ln 𝑓 and 𝑓 𝑘 terms – no closed-form root for generic 𝑘, 𝑁 1 , 𝑁 2 and it even has more than one root. Thus, we employ DIRECT [19], a deterministic, derivative-free method for global optimization over bounded domains. (3) Select Best Configuration: We choose the (𝑚, 𝑓 ) pair that results in the minimum storage cost across all tested values of 𝑚.
Author DBLP-AN IMDB-AN IMDB-MT
53 27 27 38
String Set (S𝐷 ) |S𝐷 | ℓavg ℓmax 111,162 13.86 43 450,000 14.61 44 550,000 14.14 39 357,923 18.44 79
Query Set (S𝑄 ) |S𝑄 | ℓavg ℓmax 414,614 7.70 10 701,460 8.26 10 750,000 8.47 10 750,000 8.19 10
7
SUPPORT LONGER QUERIES
The core LEARNT approach supports prefix, suffix, and substring queries under a length constraint on the query string. Here, we extend LEARNT to handle longer query strings. For clarity, we first use (%𝑆%) queries as an example to illustrate the main idea. Suppose the maximum substring length that LEARNT can accurately estimate is 𝐿. For a query string 𝑄 = 𝑞 1𝑞 2 . . . 𝑞 |𝑄 | with |𝑄 | > 𝐿, we estimate 𝐶𝑎𝑟𝑑 (%𝑄%) by converting the problem into a Markov process [8] that models dependencies among consecutive substrings up to length 𝐿. We rewrite the probability of 𝑄 (and hence its expected cardinality) using the chain rule: 𝑃 (𝑞 1, . . . , 𝑞 |𝑄 | ) = ∏︁ |𝑄 | 𝑃 (𝑞 1, . . . , 𝑞𝐿 ) 𝑖=𝐿+1 𝑃 (𝑞𝑖 | 𝑞 1, . . . , 𝑞𝑖 −1 ). Since LEARNT provides cardinality (selectivity) up to length 𝐿, we approximate each conditional term by conditioning on the most recent 𝐿 − 1 characters, leading to an (𝐿 − 1)-order Markov process: 𝑃 (%𝑞𝑖 −𝐿+1 ...𝑞𝑖 %) 𝑃 (𝑞𝑖 | 𝑞 1, . . . , 𝑞𝑖 −1 ) ≈ 𝑃 (𝑞𝑖 | 𝑞𝑖 −𝐿+1, . . . , 𝑞𝑖 −1 ) = 𝑃 (%𝑞𝑖 −𝐿+1 ...𝑞𝑖 −1 %) . ∏︁ 𝑃 (%𝑞𝑖 −𝐿+1 ...𝑞𝑖 %) |𝑄 | ̂︄ This yields: 𝐶𝑎𝑟𝑑 (%𝑄%) ≈ |S| 𝑃 (𝑞 1, . . . , 𝑞𝐿 ) , 𝑖=𝐿+1 𝑃 (%𝑞𝑖 −𝐿+1 ...𝑞𝑖 −1 %)
≤ 𝑐′
1+𝑓 𝑓 +𝑓 𝑚 ′ 1+𝑓 ≤ 𝑐
where |S| denotes the total number of strings. This approximation assumes that the probability of a new character depends primarily on its most recent 𝐿 − 1 predecessors, i.e., long-range correlations are negligible once the last 𝐿 characters are known. Empirically, most real string distributions exhibit such local dependency [18]. Theoretical Error Bound (under an (𝐿−1)-order Markov assumption). Let 𝑒𝑏 be the maximum Q-error guarantee of LEARNT for any substring of length ≤ 𝐿: 𝑒𝑏−1𝐶 (𝑈 ) ≤ 𝐶ˆ︁(𝑈 ) ≤ 𝑒𝑏 𝐶 (𝑈 ) (∀ |𝑈 | ≤ 𝐿). Under this assumption, for any query 𝑄 with |𝑄 | > 𝐿, the Q1+2( |𝑄 | −𝐿) error of the Markov-based estimator is bounded by 𝑒𝑏 . The bound follows because the estimator uses one 𝐿-gram term (with error ≤ 𝑒𝑏 ) and |𝑄 | − 𝐿 ratio terms, each involving two ≤ 𝐿 substrings (contributing at most 𝑒𝑏2 per step). Discussion. The same Markov-process idea can apply to prefix queries. For |𝑄 | > 𝐿, we adopt an (𝐿 − 1)-order Markov model to
if 𝑚 mod 2 = 1 (4) if 𝑚 mod 2 = 0
are constants, 𝑐 ′ is a constant. Due to Abel-Ruffini
Since 𝑛 and 𝑝𝑛 theorem [4], there are no direct formula to compute the value of 𝑓 for general 𝑚. Thus, we employ numeric solver to compute the range of 𝑓 . After getting the feasible range of 𝑓 , we and apply the same optimization strategy as in Sec. 6.2.1, restricted to this range.
6.3
|V |
is needed and leads to a larger Bloom filter size. We design a new strategy to reduce the number of buckets with the layered filters. Specifically, we build a tree-based index to manage queries within 𝐵𝑖 if 𝑖 is larger than a predefined threshold. The nodes in the tree are stored in a contiguous array. Each node utilizes 4 bits to record the bucket ID (which bucket) of the query and 2 bytes to represent the index of its first child. The children of each node are stored sequentially, and a 1-bit flag is used to indicate whether a node is the last child in its sequence. This representation reduces memory overhead while preserving efficient query operations. We incorporate the threshold value selection process into our parameter selection framework. Specifically, we first enumerate candidate thresholds (from 𝑛 to 1) to determine which buckets will adopt the tree-based index. For each threshold, we then apply the same optimization strategy as in Sec. 6.2.1.
6.2.2 Optimizing Parameters with Empty-answer Query Guarantees. To enhance accuracy in identifying empty-answer queries, users can specify an additional constraint: a lower bound 𝑝𝑛 on the probability that an empty-answer queries is classified into bucket 𝐵 1 . This constraint restricts the feasible range for the false positive rate 𝑓 . Based on Lemma 5.26 , we derive the constraint: 1 − (1 − 𝑞)𝑡 · (𝑛+𝑡𝑡 −2) ≥ 𝑝𝑛 and we get the condition on 𝑞 that 𝑞 ≥ 1 − (𝑛 − (𝑛−1) 𝑡 (︃ )︃ 𝑡1 1−𝑝𝑛 1) 𝑛+𝑡 −2 . For a given 𝑒𝑏, 𝑛 is determined and is a constant here ( 𝑡 ) while different empty-answer queries may have different values of (︃ )︃ 𝑡1 1−𝑝𝑛 𝑡. Let 𝑔(𝑡) = 𝑛+𝑡 −2 . 𝑔(𝑡) increases as 𝑡 increases. To support ( 𝑡 ) different 𝑡s, we therefore set 𝑞 ≥ 1 − (𝑛 − 1)𝑔(2). Let 𝑐 = 1−(𝑛−1)𝑔(2) and we have the constraint: 𝑞 ≥ 𝑐. Based on ∏︁ Lemma 5.1 and Lemma 5.2, we have 𝑞 = 𝑛𝑖=2 (1−𝑝𝑖 ), where 𝑝𝑖 is the probability that a query is a false positive in 𝐵𝑖 (𝑖 ≥ 2). For simplicity in our analysis, we assume that 𝑝𝑖 is the same cross different buckets. Otherwise, there can be lots of different assignments of 𝑝𝑖 for 𝐵𝑖 . 1 1 Then, we have 𝑞 = (1 − 𝑝)𝑛−1 and 𝑝 ≤ 1 − 𝑐 𝑛−1 . Let 𝑐 ′ = 1 − 𝑐 𝑛−1 . Based on Equation 1, we have: {︄ 𝑓 −𝑓 𝑚
Dataset
Tree Index for High-Cardinality Buckets
Since 𝑞 = (1 − 𝑝)𝑛−1 , the probability of an empty-answer query classified with 𝐵 1 in Lemma 5.1 and Lemma 5.2 is also affected by 1 the number of buckets. Based on Equation 4 and 𝑐 ′ = 1 − 𝑐 𝑛−1 , where 𝑐 ∈ (0, 1), a larger 𝑛 results in a smaller 𝑐 ′ . Thus, a smaller 𝑓 6 The analysis for Lemma 5.1 follows a similar process but is more straightforward, so we omit it.
8
𝑃 (%𝑞𝑖 −𝐿+1 ...𝑞𝑖 %) ̂︄ (%𝑄%) ≈ |S| 𝑃 (𝑞 1 . . . 𝑞𝐿 %) ∏︁ |𝑄 | express: 𝐶𝑎𝑟𝑑 𝑖=𝐿+1 𝑃 (%𝑞𝑖 −𝐿+1 ...𝑞𝑖 −1 %) . By reversing the query string and treating the suffix as a prefix, the (𝐿 − 1)-order Markov estimator can support suffix queries as well.
Evaluation Aspects. We evaluate all the methods above from: Accuracy – How closely do their predictions match the ground truth for fundamental query patterns in CE4Str? We use Q-error as the evaluation metric, reporting both the mean Q-error and its distribution (50%, 90%, 99%, and 100% quantile). Robustness – Do these methods maintain consistent accuracy across different cardinality ranges and the lengths of queries? We break down accuracy across varying cardinality ranges and queries’ lengths. We report the corresponding Q-error for each range/length. Empty-answer Queries Support – How well these methods support empty-answer queries? We report the percentage of empty-answer queries with the estimated cardinality smaller than 2. Overhead – How quickly can each method start to handle online queries (preparation time), and how efficiently can it perform online estimation (inference time)? Evaluating both metrics helps ensure that the method is not only accurate but also practical for deployment. We also report the on-disk size (storage usage) of the data structures used by each method. Tunability & Optimization – How does LEARNT perform under different user-specified parameters, and what are the benefits of our proposed optimizations?
8 EXPERIMENTAL STUDY 8.1 Experimental Setup Datasets. For synthetic testing, where queries are randomly generated, we conduct experiments on four widely used datasets, referenced in existing studies [13, 26–28]. The detailed statistics of these datasets are presented in Table 57 . Methods for Comparison. We compare the following methods: • PostgreSQL [1]: We utilize the EXPLAIN statement to obtain the cardinality estimation of LIKE queries. • MO [18]: A substring cardinality estimator based on pruned suffix tree. We set the prune threshold to 2%, reserving 2% nodes of the full suffix tree. • LBS [24]: One of the traditional state-of-the-art methods designed for patterns of the form %𝑆% based on 𝑛-gram. • E2E [27]: A deep learning-based method that uses sample bitmap as encoding and supports 𝑆%, %𝑆, and %𝑆%. • Astrid [26]: A state-of-the-art deep learning method that supports 𝑆%, %𝑆, and %𝑆%. We adopt its embedding-based variant, as it performs better than the natural language model-based variant. • LPLM [13]: A state-of-the-art learning-based method designed for universal LIKE queries. • CLIQUE [21]: A state-of-the art learning-based method designed to support basic patterns and combined patterns. • LEARNT: Our proposed estimator that focuses on 𝑆%, %𝑆, and %𝑆%. The source code is available at [3].
8.2
Overall Estimation Accuracy
Table 6 reports the Q-error of six estimators across four datasets. We summarize the key observations as follows: (1) Overall, LEARNT consistently ranks among the top two methods across nearly all datasets and Q-error percentiles, demonstrating strong robustness. For instance, on DBLP-AN, LEARNT achieves a mean Q-error of 1.37 on all query patterns and significantly outperforms the second-best, CLIQUE with a mean Q-error around 2.2. (2) In terms of worst-case behavior, LEARNT shows strong tail robustness. Across all datasets, its maximum Q-error remains under 1.5, whereas methods like CLIQUE and LPLM suffer from high variance – e.g., on DBLP-AN with the substring query, CLIQUE reaches a maximum Q-error of 479.0, and LPLM exceeds 1000. (3) PostgreSQL consistently underperforms across all metrics. Its mean Q-error ranges from 7.9 to 9.6. While learning-based methods like LPLM and E2E improve over PostgreSQL in the mean case, they suffer from high variance and large tail errors. (4) On %𝑆%, methods specifically designed for substring patterns (MO, LBS, SSCard) achieve impressive accuracy, particularly in terms of 90th percentile Q-error.
We adopt PostgreSQL v13.1 and for other baselines we adopt the codes provided by the authors and use the default settings. For our method, we set 𝑒𝑏 = 1.5 in default, enabling the frontier-based optimization (cf. Sec. 4.3) and building the tree structure for the large cardinality (cf. Sec. 6.3). Note that for each method, we compare it only against the query patterns that it supports. Query Generation. We consider three LIKE query patterns: 𝑆%, %𝑆, %𝑆%, where |𝑆 | <= 10. For non-empty-answer queries, we evaluate them on the same 250, 000 queries8 by random sampling. Existing learning-based methods often adopt their own training and testing data generation strategies, varying in query patterns and the number of queries used. To ensure a fair and meaningful comparison, we train all learning-based methods on the same training queries. This unified setup ensures that performance differences reflect model design rather than discrepancies in data exposure. Specifically, we randomly sample 500, 000 queries for each query pattern as training data . For methods that train a single model across all query patterns – such as LPLM, E2E, and CLIQUE – we combine the training and testing data from all query patterns to train and evaluate a unified model. For empty-answer query testing, we generate queries by appending a random number of characters to existing non-empty-answer testing queries.
8.3
Robustness of Each Estimator
Robustness on Different Query Lengths. Figure 3 illustrates how Q-error changes with query string length across four benchmarks and three query patterns (𝑆%, %𝑆, %𝑆%). We observe the following trends: (1) Our method consistently yields the lowest Q-error across almost all lengths and query patterns, showcasing strong robustness and generalization. It usually delivers a 1.5 − 2x lower Q-error than the next-best method. For example, when the query length ∈ [3, 7], it maintains Q-error close to 1, while others – especially LPLM and E2E – can exceed 5; (2) As query strings grow longer, most methods improve due to increased selectivity and they tends to predict the cardinality with small value; (3) When the query length is 1 or 2, CLIQUE achieves slightly better best Q-error than ours. CLIQUE introduces extend N-gram table. to store all frequent N-grams. The queries with small length, i.e., 1 or 2, usually have a large cardinality and are included in the extend N-gram table. Thus, CLIQUE directly
7We exclude PartName in TPC-H [11], which is widely used in existing benchmarks,
as it is synthetically generated and contain repeated words, which do not reflect real-world query patterns. 8We aim to maintain a training-to-testing ratio of 2:1. If it is not possible to sample the desired number of queries, we adjust the sample sizes while preserving this ratio. 9
Table 6: Q-error for different estimators on valid queries
S%
PostgreSQL LEARNT E2E Astrid LPLM CLIQUE
Mean 9.6 1.38★ 2.30 1.94 8.98 1.7‡
Author 90th 99th 11.0 11.0 1.41 1.46★ 1.49 12.26 1.24★ 10.68 3.41 86.53 1.35‡ 6.33‡
Max 1098.0 1.5★ 1446.39 412.31 7269.58 166.0‡
Mean 9.81 1.4★ 1.74 1.61 4.93 1.5‡
IMDB-AN 90th 99th 11.0 11.0 1.41 1.41★ 1.01‡ 10.73 1.0★ 9.5 2.73 34.65 1.07 7.24‡
Max 838.09 1.5★ 370.95 876.22 10829.71 292.02‡
Mean 7.99 1.37★ 2.57 2.32 8.95 2.19‡
DBLP-AN 90th 99th 11.0 11.0‡ ★ 1.41 1.46★ 1.82 15.26 1.67 12.76 3.11 102.48 1.62‡ 11.4
Max 1355.18 1.5★ 474.23‡ 768.65 5303.01 589.77
Mean 9.36 1.39★ 1.99 1.78 6.55 1.66‡
IMDB-MT 90th 99th 11.0 11.0 1.41 1.46★ 1.10‡ 12.43 1.03★ 11.78 2.21 65.66 1.23 8.29‡
Max 1098.0 1.5★ 4727.97 211.02‡ 28987.37 215.5
%S
PostgreSQL LEARNT E2E Astrid LPLM CLIQUE
9.5 1.38★ 2.08 2.63 4.75 1.77‡
11.0 1.41‡ 1.52 1.3★ 3.42 1.44
11.0 1.46★ 9.03 17.49 22.05 6.45‡
1098.0 1.5★ 589.68 3418.58 4727.97 50.8‡
9.83 1.4★ 1.99 2.32 7.57 1.59‡
11.0 1.41 1.06‡ 1.0★ 3.21 1.1
11.0 1.46★ 12.88 19.98 69.68 7.82‡
7220.64 1.5★ 12785.0 4606.3 10798.68 927.21‡
7.91 1.37★ 2.44 3.02 6.25 2.23‡
11.0 1.41★ 1.83 1.62‡ 3.14 1.75
11.0 1.46★ 12.62 22.49 33.73 10.84‡
2257.18 1.5★ 842.46 2833.54 23830.59 267.64‡
9.46 1.39★ 1.95 2.07 11.97 1.62‡
11.0 1.41 1.12‡ 1.01★ 3.00 1.2
11.0 1.46★ 11.00 16.88 83.22 8.0‡
2226.09 1.5★ 1147.66 1731.33 87207.32 356.34‡
%S%
PostgreSQL MO LBS LEARNT E2E Astrid LPLM CLIQUE SSCard
9.17 2.88 2.15 1.38★ 2.37 2.92 10.32 1.83‡ 2.02
11.0 1.0★ 1.0★ 1.41‡ 1.57 1.42 4.19 1.46 1.0★
11.0 11.01 13.0 1.46★ 11.73 20.46 113.9 6.89‡ 12.0
1098.0 16056.0 39.4‡ 1.5★ 1278.92 6879.51 9451.88 166.0 59.0
9.50 1.51 1.52 1.4★ 2.14 2.83 9.93 1.62 1.45‡
11.0 1.0★ 1.0★ 1.41 1.16 1.0★ 3.84 1.13‡ 1.0★
11.0 6.0‡ 9.0 1.46★ 16.15 24.89 92.56 7.91 7.0
5213.55 19600.0 117.07 1.5★ 2901.0 8016.84 15360.61 557.28 72.0‡
7.74 2.33 2.47 1.37★ 2.72 3.37 114.86 2.3‡ 2.41
11.0 1.02‡ 1.0★ 1.41 1.88 1.68 4.05 1.72 1.0★
11.0‡ 14.0 15.26 1.46★ 17.02 27.9 190.55 11.93 16.0
1547.0 1321.31 277.15 1.5★ 847.46 6385.91 17860.03 479.0 82.0‡
9.33 1.5‡ 1.62 1.39★ 2.27 2.68 18.36 1.7 1.58
11.0 1.0★ 1.0★ 1.41 1.27 1.01‡ 3.88 1.24 1.0★
11.0 5.6‡ 10.0 1.46★ 14.39 23.96 220.79 8.81 9.0
7752.73 4542.0 90.91 1.5★ 3961.14 6345.04 45274.68 908.69 71.0‡
Query
Method
Note: ★ marks the best (lowest) value, while ‡ marks the second-best. PG
MO
LBS
Q-error
LPLM
1
2
3
4
5
6
7
CLIQUE
8
9 10
100
SSCard
LEARNT
IMDB-AN (S%)
IMDB-MT (S%)
102
101
1
100
Astrid
102
102 10
E2E
DBLP-AN (S%)
Author (S%)
10
1
2
3
4
5
6
7
8
9 10
101
1
100
1
2
3
DBLP-AN (%S)
Author (%S)
4
5
6
7
8
100
9 10
IMDB-AN (%S)
Q-error
102
101
101
100
1
2
3
4
5
6
7
8
9 10
100
1
2
3
4
5
6
7
8
9 10
Q-error
102
2
3 4 5 6 7 8 Query string length
101
2
9 10
100
3
4
5
6
7
8
3 4 5 6 7 8 Query string length
100
9 10
5
6
7
8
9 10
1
2
8
9 10
3 4 5 6 7 8 Query string length
9 10
3
4
5
6
7
103 102 101
101 2
4
IMDB-MT (%S%)
102
1
100
9 10
103
101
1
1
101 1
3
IMDB-MT (%S)
IMDB-AN (%S%)
102
100
102
DBLP-AN (%S%)
Author (%S%)
10
102
100
2
103
103 102
1
1
2
3 4 5 6 7 8 Query string length
9 10
100
1
2
Figure 3: Q-error of all estimators as pattern string length varies. answers the query with the exact cardinality without calling the learning model. (4) Learned estimators like LPLM and E2E show high variance and unstable behavior at small lengths (especially length = 1–3), sometimes spiking above 102 − 103 . Robustness on Different Cardinality Ranges. Figure 4 reports mean Q-error of each estimator based on actual cardinality range across all datasets and query patterns. We observe the following: (1) Although most LIKE queries have small cardinalities, a nonnegligible fraction exhibit moderate or large cardinalities. Existing methods perform poorly on these queries, often incurring extremely large Q-errors that can severely distort optimizer decisions. (2) Our method almost maintains the lowest Q-error across all cardinality
ranges and datasets, showing strong robustness. It achieves at least 2x lower Q-error that others (except for MO and PostgreSQL ) when the true cardinality is larger than 10. (3) PostgreSQL (PG) achieves a low Q-error in the range [11, 20]. This is because it usually predicts the cardinality with 11 in our testing. (4) Learning-based methods, e.g., E2E and CLIQUE, tend to exhibit increasing Q-error as the true cardinality grows, indicating degraded estimation accuracy on large-result queries. These models struggle to generalize to highcardinality patterns, likely due to skewed training distributions and overfitting to small range cases.
10
PG
MO
Q-error
Author (S%)
LBS
E2E
Astrid
LPLM
DBLP-AN (S%)
101
SSCard
LEARNT
IMDB-AN (S%)
101
100
CLIQUE
IMDB-MT (S%)
101
101
Author (%S)
DBLP-AN (%S)
IMDB-MT (%S)
IMDB-AN (%S)
Q-error
102
101
101
100
100
Q-error
Author (%S%)
IMDB-AN (%S%)
101
100
0]
[1,1
20] 21,50] 1,max] [11, [ [5 Actual cardinality
100
IMDB-MT (%S%)
102
102
101
101
100
[1,1
0]
0] 0] ax] [11,2 [21,5 [51,m Actual cardinality
100
0]
[1,1
0] 0] ax] [11,2 [21,5 [51,m Actual cardinality
0]
[1,1
0] 0] ax] [11,2 [21,5 [51,m Actual cardinality
Figure 4: Q-error of all estimators varying actual result cardinality. Table 7: Probability (Prob.) of estimates below 2
Estimation of Empty-answer Queries
Query
We report the percentages of queries with estimated cardinality smaller than 2. For LEARNT, we compare: LEARNT-N – the naive method in Sec. 5.1, and LEARNT-PW – prefix-walk strategy in Sec. 5.2. From Table 7, we can see: (1) In all datasets, LEARNTPW significantly outperforms LEARNT-N, which aligns with our theoretic analysis in Sec. 5.2. (2) LEARNT-PW is the best in 𝑆% and %𝑆 while is competitive with LBS, MO, and SSCard in %𝑆%. (3) Only LEARNT-PW has consistently high performance across datasets. In contrast, other methods exhibit fluctuations. For example, CLIQUE achieves 95.09 on Author while only 84.20 on DBLP-AN.
8.5
100
DBLP-AN (%S%)
101
8.4
101
101
S%
%S
Overhead
Preprocessing Time. Table 8 shows preprocessing time of each estimator before supporting online inference. LEARNT achieves the lowest offline construction time across all datasets by a large margin. Compared to E2E, which takes up to around 43,000 seconds, LEARNT completes in just 17–77 seconds, yielding over 500x speedup, demonstrating that LEARNT is highly efficient for offline preprocessing and well-suited for practical deployment. Inference Time. As shown in Table 9, LEARNT achieves low inference latency, significantly outperforming most learning-based approaches. Specifically, it is over 80× faster than E2E, and substantially faster than Astrid, LPLM, and CLIQUE across all datasets. Compared to non-learning-based methods such as MO and LBS, LEARNT incurs only a slight overhead (e.g., 0.05ms vs. 0.01–0.12ms), while still maintaining competitive latency.
%S%
Method PostgreSQL LEARNT-N LEARNT-PW E2E Astrid LPLM CLIQUE
Author 0 93.98 99.47 4.87 92.16 22.98 96.09
DBLP-AN 0 88.37 98.55 4.19 78.30 22.76 92.48
IMDB-AN 0 97.47 99.86 26.99 97.99 31.78 99.50
IMDB-MT 0 95.90 99.74 0.02 95.36 53.67 99.44
PostgreSQL LEARNT-N LEARNT-PW E2E Astrid LPLM CLIQUE
0 93.48 99.44 3.12 90.33 24.01 95.09
0 88.35 98.58 2.32 76.37 11.04 84.20
0 97.15 99.82 29.12 99.29 17.21 98.83
0 96.23 99.76 0.02 98.08 43.21 99.35
PostgreSQL MO LBS LEARNT-N LEARNT-PW E2E Astrid LPLM CLIQUE SSCard
0 99.21 99.99 90.31 99.10 15.04 89.16 11.53 95.44 99.92
0 99.43 99.97 85.40 98.15 6.43 86.42 6.23 92.82 99.88
0 99.78 99.97 95.62 99.73 27.69 99.43 12.66 99.42 99.75
0 99.80 99.97 95.17 99.68 0.02 98.69 20.88 99.49 99.90
Storage Usage. As shown in Table 10, LEARNT achieves the lowest storage usage among all non-learning-based methods, demonstrating strong efficiency advantages over traditional techniques like MO and LBS. Compared to learning-based methods (Astrid, E2E, CLIQUE, LPLM, and SSCard), LEARNT uses less storage than three
11
Table 8: Preprocessing time (s) comparison across datasets Method MO LBS LEARNT
Author 40.27 219.92 17.13
DBLP-AN 133.98 923.92 44.11
IMDB-AN 267.26 997.13 76.78
IMDB-MT 486.56 974.31 71.33
E2E Astrid LPLM CLIQUE SSCard
26970 22519 9419 6704 27.19
36896 38143 49767 9935 141.49
43791 56607 65376 10879 117.31
41080 51696 45457 11815 102.53
CLIQUE [21], SSCard [29], and LEARNT on PostgreSQL v13.1. Parallel execution is disabled and a 1000s timeout is enforced. Each query is executed three times per method. Table 12: Execution time comparison on JOB benchmark Method PostgreSQL SSCard CLIQUE LEARNT
Effectiveness of Long Queries Support
Table 11 shows mean Q-error of LEARNT and estimation time on the queries with the length between 11 and 20. We can observe that LEARNT achieves consistently low Q-error (around 1.3–1.4) on long queries across all datasets and query types, while keeping estimation latency below 1 ms. This shows that the Markov-based extension provides accurate and efficient support.
8.8
Table 9: Inference time (ms) comparison across datasets Method PostgreSQL MO LBS LEARNT
Author 0.09 0.02 0.09 0.04
DBLP-AN 0.09 0.01 0.12 0.05
IMDB-AN 0.09 0.02 0.12 0.04
IMDB-MT 0.09 0.02 0.11 0.04
E2E Astrid LPLM CLIQUE SSCard
6.90 3.27 1.30 3.65 0.02
6.90 3.18 1.00 3.90 0.03
6.90 3.26 1.00 4.00 0.03
7.10 3.27 1.30 3.70 0.03
Author 2.45 8.64 0.51
DBLP-AN 7.76 15.73 1.77
IMDB-AN 13.80 15.68 1.73
IMDB-MT 24.64 16.42 1.76
E2E Astrid LPLM CLIQUE SSCard
20.84 2.64 1.09 2.21 1.65
6.52 2.04 1.02 1.04 4.39
6.41 2.04 1.02 1.03 4.29
6.37 2.04 1.05 1.06 4.29
8.7
Author 1.40 0.34 1.39 0.31 1.39 0.30
DBLP-AN 1.42 0.42 1.42 0.38 1.42 0.38
IMDB-AN 1.33 0.31 1.30 0.37 1.31 0.32
Degradation Avg. Ratio (%) – 17.4 2254.6 4.0
Total Runtime (s) 1205.79 1182.17 3192.38 1106.99
Effectiveness of Our Design
Table 13: Analysis of LEARNT with different 𝑒𝑏s.
𝑒𝑏 Building time (s) Storage (MB) mean Q-error infer. time (ms)
1.3 42.09 2.09 1.09 0.12
1.5 34.15 1.36 1.37 0.07
1.7 34.78 1.27 1.4 0.07
2.0 31.69 0.76 1.71 0.04
2.5 27.76 0.53 2.01 0.03
Performance on Different 𝑝𝑛 Settings and Impact of Upper Tree. Table 14 shows the impact of enabling the upper tree and tuning 𝑝𝑛 ( the probability of classifying empty-answer query with 𝐵 1 ) on storage and empirical probability. ’Unset’ indicates that no constraint is imposed on empty-answer query classification probability. We test on DBLP-AN with %𝑆% and other datasets and query patterns have similar trend. Across all 𝑝𝑛 settings, using the upper tree consistently reduces storage usage while maintaining comparable or slightly better accuracy.
Table 11: Q-error and estimation time (ms) on long queries Query 𝑆% %𝑆 %𝑆%
#Q – 49 48 27
Performance on Different 𝑒𝑏 Settings. Table 13 summarizes the trade-offs of LEARNT under different 𝑒𝑏s. We test on DBLPAN with %𝑆% ad other datasets and query patterns have similar trend. As 𝑒𝑏 increases from 1.3 to 2.5, the storage usage, build time, and inference time significantly decrease (e.g., storage drops from 2.09MB to 0.53MB), indicating better space and runtime efficiency. However, this comes at the cost of higher mean Q-error, which rises from 1.09 to 2.01. This highlights that LEARNT provides a tunable balance between accuracy and efficiency, with smaller 𝑒𝑏 favoring estimation quality, and larger 𝑒𝑏 reducing resource consumption.
Table 10: Storage (MB) comparison across datasets Method MO LBS LEARNT
Improved Avg. Ratio (%) – 52.6 36.3 16.5
Result. Table 12 reports the number of queries with performance improvement/degradation compared to PostgreSQL, the average improvement and degradation ratios, and the total runtime. We observe: (1) LEARNT achieves the lowest total runtime, showing that its accuracy improvements translate into execution gains. (2) LEARNT improves the largest number of queries, indicating more consistent plan improvements. (3) Although LEARNT has 27 degradations, the average slowdown is only 4%, much smaller than others whose severe degradation offset its improvements and inflate total runtime.
of them (E2E, SSCard, and Astrid) and is competitive with the most compact ones (CLIQUE and LPLM).
8.6
#Q – 8 9 30
IMDB-MT 1.28 0.47 1.27 0.46 1.28 0.43
Table 14: Effect of upper tree and 𝑝𝑛 thresholds Variants
Impact on Query Optimization
w/o Tree w/ Tree
Settings. We evaluate 57 JOB queries containing prefix, suffix, and substring LIKE predicates. For fairness, estimators are constructed for all columns involving LIKE. We compare PostgreSQL,
Unset Stor. Prob. 1.36 96.11% 1.36 98.15%
99.9% Stor. Prob. 2.43 99.9% 1.92 99.8%
99.99% Stor. Prob. 2.88 99.97% 2.33 99.93%
99.999% Stor. Prob. 3.34 99.993% 2.77 99.979%
Impact of Frontier-based Pruning. Table 15 shows that applying frontier-based optimization significantly reduces both storage 12
and build time across all datasets. On average, storage drops by 20–30% (e.g., from 2.00MB to 1.48MB on IMDB-MT), and build time is reduced by up to 40% (e.g., from 103.07s to 61.01s on IMDB-MT). Table 15: Impact of frontier-based pruning Variants w/o F w/ F
9
Author Stor. Time 0.54 21.49 0.40 13.16
DBLP-AN Stor. Time 1.80 52.58 1.36 34.15
IMDB-AN Stor. Time 1.79 97.68 1.33 60.23
[22] Hai Lan, Zhifeng Bao, and Yuwei Peng. 2021. A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration. Data Sci. Eng. 6, 1 (2021), 86–101. [23] Hai Lan, Shixun Huang, Zhifeng Bao, and Renata Borovica-Gajic. 2024. Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects. Proc. VLDB Endow. 18, 3 (2024), 544–556. [24] Hongrae Lee, Raymond T. Ng, and Kyuseok Shim. 2009. Approximate substring selectivity estimation. In EDBT 2009, Vol. 360. ACM, 827–838. [25] Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter A. Boncz, Alfons Kemper, and Thomas Neumann. 2015. How Good Are Query Optimizers, Really? Proc. VLDB Endow. 9, 3 (2015), 204–215. [26] Suraj Shetiya, Saravanan Thirumuruganathan, Nick Koudas, and Gautam Das. 2020. Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning. Proc. VLDB Endow. 14, 4 (2020), 471–484. [27] Ji Sun and Guoliang Li. 2019. An End-to-End Learning-based Cost Estimator. Proc. VLDB Endow. 13, 3 (2019), 307–319. [28] Jiayi Wang, Chengliang Chai, Jiabin Liu, and Guoliang Li. 2021. FACE: A Normalizing Flow based Cardinality Estimator. Proc. VLDB Endow. 15, 1 (2021), 72–84. [29] Yirui Zhan, Wen Nie, and Jun Gao. 2025. SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index. Proc. ACM Manag. Data 3, 4, Article 265 (Sept. 2025), 24 pages. [30] Rong Zhu, Ziniu Wu, Yuxing Han, Kai Zeng, Andreas Pfadler, Zhengping Qian, Jingren Zhou, and Bin Cui. 2021. FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation. Proc. VLDB Endow. 14, 9 (2021), 1489–1502.
IMDB-MT Stor. Time 2.00 103.07 1.48 61.01
CONCLUSION
In this paper, we study the problem of cardinality estimation for LIKE queries. We introduce LEARNT, a novel classification-based estimator that transforms cardinality estimation into a tunable, bucket-based classification problem. LEARNT combines a bucketed layered filter architecture with theoretical guarantees for valid queries and effective support for negative queries. It further incorporates a parameter selection framework that minimizes storage under accuracy constraints. Our extensive experiments across realworld datasets show that LEARNT achieves consistently lower mean and tail Q-errors than state-of-the-art methods such as CLIQUE and LPLM, while also reducing preparation time by up to 70×.
REFERENCES [1] [n. d.]. PostgreSQL. https://www.postgresql.org/. [2] [n. d.]. stars-and-bars problem. https://en.wikipedia.org/wiki/Stars_and_bars_ (combinatorics). [3] [n. d.]. Technical Report. https://github.com/DataAutonomyLab/ce4str. [4] February, 2025. Abel–Ruffini theorem. https://en.wikipedia.org/wiki/Abel%E2% 80%93Ruffini_theorem. [5] February, 2025. Bloom Filter. https://en.wikipedia.org/wiki/Bloom_filter. [6] February, 2025. CEB. https://github.com/RyanMarcus/imdb_pg_dataset. [7] February, 2025. JOB. https://github.com/gregrahn/join-order-benchmark. [8] February, 2025. Markov Process. https://en.wikipedia.org/wiki/Markov_chain. [9] February, 2025. Stack. https://rmarcus.info/stack.html. [10] February, 2025. TPC-DS. https://www.tpc.org/tpcds/. [11] February, 2025. TPC-H. https://www.tpc.org/tpch/. [12] Mehmet Aytimur and Ali Cakmak. 2021. Using positional sequence patterns to estimate the selectivity of SQL LIKE queries. Expert Syst. Appl. 165 (2021), 113762. [13] Mehmet Aytimur, Silvan Reiner, Leonard Wörteler, Theodoros Chondrogiannis, and Michael Grossniklaus. 2024. LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries. Proc. ACM Manag. Data 2, 1 (2024), 54:1–54:25. [14] Bailu Ding, Surajit Chaudhuri, Johannes Gehrke, and Vivek R. Narasayya. 2021. DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems. Proc. VLDB Endow. 14, 13 (2021), 3376–3388. [15] Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, Zhengping Qian, Jingren Zhou, Jiangneng Li, and Bin Cui. 2021. Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation. Proc. VLDB Endow. 15, 4 (2021), 752– 765. [16] H. V. Jagadish, Olga Kapitskaia, Raymond T. Ng, and Divesh Srivastava. 1999. Multi-Dimensional Substring Selectivity Estimation. In VLDB’99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK. Morgan Kaufmann, 387–398. [17] H. V. Jagadish, Olga Kapitskaia, Raymond T. Ng, and Divesh Srivastava. 2000. One-dimensional and multi-dimensional substring selectivity estimation. VLDB J. 9, 3 (2000), 214–230. doi:10.1007/S007780000029 [18] H. V. Jagadish, Raymond T. Ng, and Divesh Srivastava. 1999. Substring Selectivity Estimation. In PODS, 1999, Victor Vianu and Christos H. Papadimitriou (Eds.). ACM Press, 249–260. [19] Donald R. Jones and Joaquim R. R. A. Martins. 2021. The DIRECT algorithm: 25 years Later. J. Glob. Optim. 79, 3 (2021), 521–566. [20] Kyoungmin Kim, Jisung Jung, In Seo, Wook-Shin Han, Kangwoo Choi, and Jaehyok Chong. 2022. Learned Cardinality Estimation: An In-depth Study. In SIGMOD. ACM, 1214–1227. [21] Suyong Kwon, Kyuseok Shim, and Woohwan Jung. 2025. Cardinality Estimation of LIKE Predicate Queries using Deep Learning. Proceedings of the ACM on Management of Data 3 (02 2025), 1–26. 13