pith. sign in

arxiv: 2605.24308 · v1 · pith:UVRUZIUCnew · submitted 2026-05-23 · 💻 cs.DB

LEARNT: A Practical Estimator for Cardinality of LIKE Queries with Formal Accuracy Guarantees

Hai Lan , Zhifeng Bao , Divesh Srivastava , Shixun Huang , Yuwei Peng , Yang Yu This is my paper

Pith reviewed 2026-06-30 12:45 UTC · model grok-4.3

classification 💻 cs.DB
keywords cardinality estimationLIKE queriesstring selectivityQ-error boundsBloom filtersquery optimizationempty-result detection
0
0 comments X

The pith

LEARNT estimates LIKE query cardinalities by classifying them into buckets to deliver formal Q-error bounds on non-empty results.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tackles cardinality estimation for the most common LIKE patterns on string columns: prefixes, suffixes, and substrings. It recasts the task as bucket classification so that, once a query lands in the right bucket, explicit upper and lower bounds on Q-error become available for any non-empty answer. A layered Bloom-filter architecture keeps memory low while a Markov composition step handles queries longer than those seen in training. Dedicated filter and prefix-walk tests give probabilistic detection of empty results. On four real datasets the method records 1.3-1.7 times lower mean Q-error than CLIQUE and LPLM together with up to 70 times faster construction at comparable space.

Core claim

LEARNT formulates estimation as a bucket-classification problem. Upon correct classification it supplies formal Q-error bounds for queries with non-empty answers. It realizes the estimator with a memory-efficient bucketed layered-filter built from Bloom filters and compact auxiliary tables, plus skew-aware optimizations. Empty-answer queries are handled by separate filter-based and prefix-walk procedures that supply probabilistic correctness guarantees. A Markov modeling extension composes short-query statistics into estimates for arbitrarily long strings, and a theoretical parameter-selection framework minimizes storage subject to accuracy and robustness constraints.

What carries the argument

Bucket-classification formulation paired with the bucketed layered-filter architecture that uses Bloom filters and auxiliary tables to enforce formal Q-error bounds after correct classification.

If this is right

  • Formal Q-error bounds become available for all non-empty LIKE queries that are correctly bucketed.
  • Probabilistic guarantees allow reliable early termination for empty-answer queries.
  • Mean Q-error drops 1.3-1.7 times relative to CLIQUE and LPLM across four real datasets.
  • Construction time falls by up to 70 times while memory stays comparable.
  • Markov composition extends the same bounds and filters to query strings longer than those used in training.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • A database engine could invoke the classifier early in optimization to decide whether a LIKE predicate is cheap or expensive before choosing join order.
  • The same classification-plus-bound pattern could be tested on other selectivity estimators that currently rely on histograms or sampling.
  • If classification accuracy stays high across shifting workloads, periodic retraining of the buckets may be unnecessary.
  • An experiment that logs classification success rate per query type on production traces would directly test how often the formal bounds actually apply.

Load-bearing premise

The bucket-classification step must succeed often enough that the formal Q-error bounds cover the great majority of queries in the target workload.

What would settle it

Measure the fraction of queries that receive incorrect bucket labels on a held-out workload; if that fraction is large enough that the average Q-error on the whole workload exceeds the claimed formal bounds, the guarantee does not hold in practice.

Figures

Figures reproduced from arXiv: 2605.24308 by Divesh Srivastava, Hai Lan, Shixun Huang, Yang Yu, Yuwei Peng, Zhifeng Bao.

Figure 1
Figure 1. Figure 1: Comparison of Estimators on Substring Queries [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. 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 num￾ber of queries used in filter construction? Our empirical study on common string datasets shows that this is indeed feasible [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Q-error of all estimators as pattern string length varies. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Q-error of all estimators varying actual result cardinality. [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
read the original 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-the-art methods such as CLIQUE and LPLM, achieving 1.3-1.7x lower mean Q-error, significantly lower tail errors, and up to 70x faster construction with comparable memory usage.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper proposes LEARNT, a cardinality estimator for LIKE queries (prefix, suffix, substring) on string data. It frames estimation as a bucket-classification problem that yields formal Q-error bounds for non-empty-answer queries upon correct classification, uses Bloom-filter-based layered architecture with skew optimizations and Markov models for long strings, and provides probabilistic guarantees for empty-answer queries. Experiments on four real datasets report 1.3-1.7x lower mean Q-error than CLIQUE and LPLM, lower tail errors, and faster construction with comparable memory.

Significance. If the bucket-classification success rate is high on realistic workloads and the derived Q-error bounds are non-vacuous, the combination of formal guarantees, memory efficiency, and empirical outperformance would be a meaningful advance for string cardinality estimation, an area where theoretical accuracy guarantees are uncommon. The tunability framework and dedicated empty-answer handling are practical strengths.

major comments (1)
  1. [Abstract] Abstract: The formal Q-error bounds are stated to hold 'upon correct classification' for non-empty queries, yet no empirical quantification of bucket-classification accuracy (or its impact on the reported mean Q-error) is supplied for the four real datasets. This is load-bearing for the central claim of formal accuracy guarantees, because if misclassification occurs on a non-negligible fraction of queries the bounds apply only conditionally while the 1.3-1.7x improvement mixes conditional and unconditional cases.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive comment on the presentation of our formal guarantees. We agree that empirical quantification of bucket-classification accuracy is necessary to properly contextualize the Q-error results and will revise the manuscript to include this analysis.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The formal Q-error bounds are stated to hold 'upon correct classification' for non-empty queries, yet no empirical quantification of bucket-classification accuracy (or its impact on the reported mean Q-error) is supplied for the four real datasets. This is load-bearing for the central claim of formal accuracy guarantees, because if misclassification occurs on a non-negligible fraction of queries the bounds apply only conditionally while the 1.3-1.7x improvement mixes conditional and unconditional cases.

    Authors: We agree that reporting bucket-classification accuracy on the real datasets is required to substantiate the practical relevance of the formal bounds. In the revised version we will add a dedicated subsection (and accompanying table) that measures classification success rate for each dataset and query type, together with a breakdown of how misclassifications contribute to the observed mean and tail Q-errors. This will make explicit the conditional nature of the guarantees while preserving the reported performance comparisons. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper derives formal Q-error bounds conditional on correct bucket classification and uses a separate theoretical framework to select parameters minimizing storage under accuracy constraints. These elements are presented as independent constructions rather than reductions to fitted values from the evaluation data or self-citation chains; experimental comparisons on four real datasets are reported separately from the theoretical guarantees, leaving the central claims self-contained without definitional or predictive circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; paper invokes a theoretical framework for parameter selection, Bloom-filter properties, and Markov-chain composition, but specific free parameters, axioms, and invented entities cannot be enumerated without the full text.

pith-pipeline@v0.9.1-grok · 5777 in / 1243 out tokens · 26118 ms · 2026-06-30T12:45:12.768792+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 1 canonical work pages

  1. [1]

    [n. d.]. PostgreSQL. https://www.postgresql.org/

  2. [2]

    [n. d.]. stars-and-bars problem. https://en.wikipedia.org/wiki/Stars_and_bars_ (combinatorics)

  3. [3]

    [n. d.]. Technical Report. https://github.com/DataAutonomyLab/ce4str

  4. [4]

    Abel–Ruffini theorem

    February, 2025. Abel–Ruffini theorem. https://en.wikipedia.org/wiki/Abel%E2% 80%93Ruffini_theorem

    2025

  5. [5]

    Bloom Filter

    February, 2025. Bloom Filter. https://en.wikipedia.org/wiki/Bloom_filter

    2025

  6. [6]

    February, 2025. CEB. https://github.com/RyanMarcus/imdb_pg_dataset

    2025

  7. [7]

    February, 2025. JOB. https://github.com/gregrahn/join-order-benchmark

    2025

  8. [8]

    Markov Process

    February, 2025. Markov Process. https://en.wikipedia.org/wiki/Markov_chain

    2025

  9. [9]

    February, 2025. Stack. https://rmarcus.info/stack.html

    2025

  10. [10]

    February, 2025. TPC-DS. https://www.tpc.org/tpcds/

    2025

  11. [11]

    February, 2025. TPC-H. https://www.tpc.org/tpch/

    2025

  12. [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

    2021

  13. [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. Data2, 1 (2024), 54:1–54:25

    2024

  14. [14]

    Narasayya

    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

    2021

  15. [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

    2021

  16. [16]

    H. V. Jagadish, Olga Kapitskaia, Raymond T. Ng, and Divesh Srivastava. 1999. Multi-Dimensional Substring Selectivity Estimation. InVLDB’99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK. Morgan Kaufmann, 387–398

    1999

  17. [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

    work page doi:10.1007/s007780000029 2000

  18. [18]

    H. V. Jagadish, Raymond T. Ng, and Divesh Srivastava. 1999. Substring Selectivity Estimation. InPODS, 1999, Victor Vianu and Christos H. Papadimitriou (Eds.). ACM Press, 249–260

    1999

  19. [19]

    Jones and Joaquim R

    Donald R. Jones and Joaquim R. R. A. Martins. 2021. The DIRECT algorithm: 25 years Later.J. Glob. Optim.79, 3 (2021), 521–566

    2021

  20. [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

    2022

  21. [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 Data3 (02 2025), 1–26

    2025

  22. [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

    2021

  23. [23]

    Hai Lan, Shixun Huang, Zhifeng Bao, and Renata Borovica-Gajic. 2024. Cardi- nality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects.Proc. VLDB Endow.18, 3 (2024), 544–556

    2024

  24. [24]

    Ng, and Kyuseok Shim

    Hongrae Lee, Raymond T. Ng, and Kyuseok Shim. 2009. Approximate substring selectivity estimation. InEDBT 2009, Vol. 360. ACM, 827–838

    2009

  25. [25]

    Boncz, Alfons Kemper, and Thomas Neumann

    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

    2015

  26. [26]

    Suraj Shetiya, Saravanan Thirumuruganathan, Nick Koudas, and Gautam Das

  27. [27]

    VLDB Endow.14, 4 (2020), 471–484

    Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning.Proc. VLDB Endow.14, 4 (2020), 471–484

    2020

  28. [28]

    Ji Sun and Guoliang Li. 2019. An End-to-End Learning-based Cost Estimator. Proc. VLDB Endow.13, 3 (2019), 307–319

    2019

  29. [29]

    Jiayi Wang, Chengliang Chai, Jiabin Liu, and Guoliang Li. 2021. FACE: A Nor- malizing Flow based Cardinality Estimator.Proc. VLDB Endow.15, 1 (2021), 72–84

    2021

  30. [30]

    Yirui Zhan, Wen Nie, and Jun Gao. 2025. SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index.Proc. ACM Manag. Data3, 4, Article 265 (Sept. 2025), 24 pages

    2025

  31. [31]

    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. 13

    2021