Pith. sign in

REVIEW 2 major objections 7 minor 87 references

BaCon: Efficient Batch Processing of Counting Queries [Full Version]

T0 review · 2 major / 7 minor · reviewed 2026-07-08 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read BaCon speeds up counting-query batches up to 178× for CE training

desk verdict Solid systems paper with a real implementation and clear speedups; the missing LMFAO comparison is the main gap. read the letter →

arxiv 2607.05832 v1 pith:VAYTSZFX submitted 2026-07-07 cs.DB

Yuxi Liu , Xiao Hu , Pankaj K. Agarwal , Jun Yang This is my paper
classification cs.DB
keywords countingqueriesbacondatadatabasesystembatchbatches
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

BaCon addresses the problem of efficiently executing large batches of counting queries — queries that join multiple tables, apply selection predicates, and return only a count — which arise primarily when generating training data for learned cardinality estimation models. The standard approach runs each query independently; a more advanced baseline computes the full join once and post-filters for each query, but this materializes potentially enormous intermediate results. BaCon combines two ideas to avoid enumerating join outputs. First, it exploits conditional orthogonality of joins (Lemma 3.1): when join attribute values are fixed, the count of a star-shaped join factorizes into a product of per-table counts, so the join result need never be enumerated tuple-by-tuple. Second, it applies workload-aware domain quantization (Lemma 3.2): by partitioning each selection attribute's domain into buckets defined by the endpoints of all query predicates in the batch, BaCon compresses tuples into compact count maps — sparse dictionaries mapping grid coordinates to tuple counts — that preserve exact query answers. These count maps are combined via two operators: ⊗ (multiply), which merges maps from disjoint table sets whose join attributes agree, and ⊕ (add), which accumulates maps across different join-attribute bindings. The algorithm recursively traverses a plan tree over the join pattern, calling a SQL-based ProcessTable function to produce per-table count maps for each binding of join attributes, then combining them client-side. The final count map is used to compute per-query results by summing counts within each query's quantized hyperrectangle. BaCon is implemented as a client application on PostgreSQL with a lightweight C UDF for quantization, requiring no DBMS internals modification. Across nine real cardinality estimation workloads spanning IMDB, STATS, and DSB benchmarks, BaCon achieves 2× to 178× speedup over independent query processing, with the largest gains on expensive multi-table join patterns and competitive performance on simple ones.

What carries the argument

Count maps combined via ⊗ (multiply across disjoint table sets with matching join bindings) and ⊕ (add across disjoint binding groups); ProcessTable SQL function for per-table quantization and grouping; recursive plan-tree traversal (BaConRecurse); quantize C-language UDF

What would settle it

A workload where queries within each join pattern have selection predicates with little mutual overlap, so quantization produces many singleton cells and the count maps are not meaningfully smaller than the raw join output — in this regime the overhead of cursor-based table scanning and client-side map merging would exceed both independent processing (which can leverage indices and selection pushdown) and post-filtering (which processes everything server-side).

Watch

Extended reading notes

Core claim

The central mechanism is the combination of factorized join computation with workload-aware quantization, yielding compact count maps that replace full join materialization. The factorization rests on the observation that a counting query over an acyclic equality join can be evaluated by grouping tuples by join-attribute values and multiplying per-group counts across tables, rather than enumerating joined tuples. Quantization then compresses each table's contribution: by constructing a grid whose cell boundaries are the predicate endpoints from the entire query batch, all tuples within a cell are indistinguishable from the perspective of every query, so they can be replaced by a single count

Load-bearing premise

The method assumes all queries use acyclic equality joins with no self-joins, and that selection predicates are conjunctions of single-attribute range or equality comparisons. This excludes disjunctive predicates, cyclic joins, and string-pattern matching. The performance advantage also depends on the number of distinct join patterns being much smaller than the number of queries, which holds for the evaluated CE training workloads but may not for arbitrary query batches.

Editorial extensions

If this is right

  • Learned cardinality estimation model training and retraining cycles can be shortened by one to two orders of magnitude, making continuous model maintenance with fresh query-count pairs practical rather than prohibitive.
  • Any database application that evaluates large batches of aggregate queries over shared join structures — not just CE training — could benefit from the factorize-then-quantize approach, including data monitoring, materialized view refresh, and approximate query processing.
  • The quantization strategy generalizes beyond COUNT to other distributive and algebraic aggregates (SUM, MIN, MAX, AVG, STDDEV), since the compression preserves per-cell counts that can support these aggregations.
  • The approach could be integrated natively into DBMS query optimizers as a batch-aware execution strategy, eliminating the client-server cursor overhead that currently limits BaCon's performance on simple patterns.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 7 minor

Summary. The paper proposes BaCon, an algorithm for efficient batch evaluation of counting queries on top of an unmodified DBMS. The method combines two ideas: (1) factorized computation via conditional orthogonality of joins (Lemma 3.1), which allows counting join results without enumerating them by grouping on join attribute values and multiplying per-group counts; and (2) workload-aware domain quantization (Lemma 3.2), which compresses selection attribute domains into coarse grids whose boundaries are defined by query predicate endpoints, enabling compact 'count maps' as intermediate representations. Count maps are combined via tensor-product (⊗) and addition (⊕) operators (Lemmas 3.3–3.4). The algorithm partitions queries by join pattern, constructs a plan tree, and recursively processes subslices via SQL queries with a C-language UDF for quantization. Experiments on nine real CE training workloads across IMDB, STATS, and DSB show 2×–178× speedups over independent processing (IndProc) and join-then-postfilter (PostFilt) baselines, with a Hybrid variant that can switch to baselines for patterns where BaCon is slower.

Significance. The paper addresses a practical and timely problem: generating training data for learned cardinality estimation models requires executing large batches of counting queries, which is expensive. The core technical contribution—combining factorized join computation with workload-aware quantization to produce compact count maps—is well-motivated and the lemmas (3.1–3.4) are correct and clearly derived from relational algebra properties. The implementation is practical: it works on top of unmodified PostgreSQL with a lightweight C UDF, and the code is publicly available. The experimental evaluation covers nine publicly available workloads spanning three benchmark databases, which is thorough for the target domain. The per-join-pattern analysis (Section 5.2) honestly reports cases where BaCon regresses, and the Hybrid validation (Section 5.4) confirms BaCon is a safe default. The scalability experiment (Section 5.3) showing BaCon's advantage grows with workload size is a useful result.

major comments (2)
  1. [Section 5 / Section 6] The most significant experimental gap is the absence of a comparison with LMFAO [62], which is the most directly comparable prior work: it also evaluates batches of aggregate queries over shared joins without fully materializing intermediates, using a join-tree decomposition. The paper discusses LMFAO in related work and notes architectural differences (standalone engine vs. on-top-of-DBMS, no predicate-overlap preprocessing), but without an experimental comparison, the reader cannot determine how much of BaCon's speedup is algorithmic (factorized count maps + quantization) versus implementation-level (avoiding PostgreSQL overhead for conditional expressions in PostFilt, or differences with LMFAO's engine). This matters because if LMFAO achieves comparable speedups on these workloads, BaCon's contribution narrows to 'works on top of unmodified DBMS' rather than 'better algorithm for the批
  2. [Section 5, Table 2] Several speedup values are marked with '+' (e.g., '6.07+×', '2.22+×', '178.14+×'), indicating they are computed against lower-bound baseline times because IndProc or PostFilt hit timeout caps. For stats-ceb-join, the 178× speedup is against an IndProc time that is a lower bound (35,292+ seconds). The true speedup could be much higher, but the paper does not clearly communicate which specific workloads have lower-bound speedups and how this affects the headline '2× to 178×' claim. A footnote or column annotation in Table 2 explicitly flagging which speedup ratios are lower bounds would improve precision.
minor comments (7)
  1. [Section 2, Problem Statement] The restriction to acyclic equality joins with no self-joins and conjunctive single-attribute predicates is clearly stated, but the paper could briefly quantify how many queries from the original DSB workload were removed (it says 'queries not applicable to our methods' were removed for dsb-grasp-20k) to help readers gauge applicability.
  2. [Section 4.1] The heuristic for choosing the plan tree root (highest-degree table) is described informally. A brief note on sensitivity to this choice—or whether alternative root selections were evaluated—would strengthen the evaluation.
  3. [Table 2] The speedup column header reads 'Speedup vs. IndProc' but several IndProc values are lower bounds. The '+' notation is explained, but the column could be clearer about which ratios are themselves lower bounds.
  4. [Section 4.2, batching parameter β] Table 9 shows results for β=5,000, 50,000, 500,000 on job-light only. A brief note on whether the sensitivity trend holds for other workloads would be helpful.
  5. [Figure 2] The count map notation M_mc uses entries like (0,1)↦0, which is clear, but the figure caption could explicitly state that the first coordinate corresponds to b_company_type_id and the second to b_company_id to avoid ambiguity when first encountering it.
  6. [Section 3.4, Algorithm 2] The variable naming in Algorithm 2 (e.g., S[v] for subsequences, v for bindings) is somewhat dense. A brief inline comment or a small worked example trace for a 2-table case would improve readability.
  7. [Lemma 3.3] The condition 'no join condition across R1,...,Rn that is not already implied by ∪i θi' is important but stated compactly. A one-sentence clarification that this ensures the star-shaped decomposition is valid would help readers unfamiliar with the condition.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address both major comments below.

read point-by-point responses

  1. Referee: Absence of experimental comparison with LMFAO [62], which is the most directly comparable prior work. Without it, the reader cannot determine how much of BaCon's speedup is algorithmic versus implementation-level.

    Authors: We agree that a comparison with LMFAO would strengthen the paper and clarify the source of BaCon's gains. We have attempted to set up LMFAO on our workloads. There are practical obstacles: LMFAO is a standalone execution engine with its own storage layer, so it does not run directly on PostgreSQL-managed data; it requires loading data into its own format. Additionally, LMFAO's query interface expects group-by aggregate queries with conditional expressions encoding selections (similar to PostFilt), and adapting all nine workloads—which use diverse predicate types including inequalities on timestamps, strings, and categorical attributes—requires non-trivial engineering effort on both the data ingestion and query translation sides. That said, we acknowledge this is an experimental gap, not a fundamental impossibility. In the revision, we will take one of two approaches, depending on what we can complete in the revision window: (1) If we can successfully run LMFAO on at least a subset of workloads (e.g., the IMDB workloads, whose schemas are simpler), we will add a direct experimental comparison and discuss the results honestly, including cases where LMFAO is competitive. (2) Regardless of outcome, we will add a more detailed analytical comparison in the related work section, articulating specifically which aspects of BaCon's performance gains we attribute to algorithmic innovations (factorized count maps + workload-aware quantization enabling inter-query predicate sharing) versus implementation choices (on-top-of-DBMS with UDFs vs. standalone engine). We note that the paper already provides evidence that BaCon's gains are not purely implementation-level: the per-join-pattern analysis in Section 5.2 shows BaCon outperforming PostFilt (which also avoids full materialization) revision: no

  2. Referee: Lower-bound speedup values in Table 2 are not clearly communicated; need explicit annotation of which speedup ratios are lower bounds.

    Authors: This is a fair and easily addressable point. The '+' notation is currently defined in the table caption but is not applied consistently to the speedup column, and the headline '2× to 178×' claim does not clarify that some values are lower bounds. In the revision, we will: (1) Add a '+' suffix to every speedup value in Table 2 that is computed against a lower-bound baseline time (specifically: scale, job-light, job-light-join, stats-ceb, and stats-ceb-join). (2) Add a footnote to the headline speedup claim in the abstract and introduction noting that some speedup ratios are conservative lower bounds because baselines hit timeout caps. (3) Add a column or annotation in Table 2 explicitly indicating which baseline (IndProc, PostFilt, or both) hit the timeout cap for each workload. This will make it clear to the reader that, e.g., the 178× speedup for stats-ceb-join is a lower bound and the true speedup may be higher. revision: yes

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; core lemmas are mathematical facts from relational algebra, and speedups are measured against external baselines on public workloads.

full rationale

The paper's derivation chain is self-contained. Lemma 3.1 (Conditional Orthogonality) is a straightforward set-theoretic identity: conditioning a star-shaped join on specific join-attribute values factorizes the count into a product of per-subquery counts. Lemma 3.2 (Quantization Preserves Selections) holds by construction—quantization buckets are defined by sorting the endpoints of query predicate ranges, so every predicate range is exactly a union of complete buckets, making the existence of the mapping function f trivially true. Lemmas 3.3 and 3.4 follow directly from 3.1 and basic set partitioning (disjoint subsets add, conditionally independent subsets multiply). No lemma depends on a self-citation for its proof. The self-citations present ([27] by overlapping authors on learnability of selectivity functions, [26] by co-author Hu on join-aggregate algorithms) appear only as motivation or related work, not as load-bearing derivation steps. The experimental speedup claims (2×–178×) are measured against two external baselines (IndProc, PostFilt) on nine publicly available workloads across three standard benchmark databases. No parameter is fitted to a subset of data and then presented as a prediction. The one minor self-citation ([42], the full version of this paper) is standard practice and does not introduce circularity. The score of 1 reflects the presence of author-overlapping citations that are non-load-bearing, which is normal and does not constitute circularity.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

No new entities, particles, forces, or dimensions are introduced. The count maps and quantization scales are data structures, not ontological commitments.

free parameters (3)
  • β (batching parameter) = 50,000
    Controls how many consecutive bindings are batched into a single SQL query (Section 4.2). Set to 50,000 for all experiments; sensitivity analysis in Table 9 shows moderate impact (728s vs 922s vs 584s for β=50K/5K/500K).
  • Plan tree root selection heuristic = highest-degree table in join graph
    Section 4.1: root chosen as table with highest degree in join graph. Not tuned per workload; stated as a heuristic without optimization.
  • Hybrid precision threshold = 0.9
    Section C.2: RandomForest classifier threshold for selecting baselines. Calibrated on held-out validation data. Not a parameter of BaCon itself but of the optional Hybrid optimizer.
assumptions (4)
  • domain assumption Queries use acyclic equality joins with no self-joins
    Section 2, Problem Statement: 'We assume equality joins with no cycles or self-joins.' This is load-bearing — the plan tree construction (Section 3.4) and conditional orthogonality (Lemma 3.1) depend on acyclicity.
  • domain assumption Selection predicates are conjunctions of single-attribute comparisons with literals
    Section 2: 'the selection is a conjunction of predicates comparing a single attribute with a literal using =, >, <=, etc.' Disjunctions, multi-attribute predicates, and string patterns are excluded.
  • domain assumption Number of distinct join patterns is much smaller than number of queries
    Section 2: 'the number of distinct join patterns tends to be much smaller than the number of queries.' This motivates the partition-by-pattern approach. Holds for CE training workloads (Table 1) but not universally.
  • standard math Distributive/algebraic aggregate semantics for generalization beyond COUNT
    Footnote 1: methods generalize to SUM, MIN, MAX, AVG, STDDEV via distributive/algebraic aggregate properties (Gray et al. 1997).

how reviews work

0 comments
Cite this review

Pith. "Pith review of BaCon: Efficient Batch Processing of Counting Queries [Full Version]." pith.science (2026). https://pith.science/paper/VAYTSZFX

@misc{pith2026260705832,
  author       = {Pith},
  title        = {Pith review of: BaCon: Efficient Batch Processing of Counting Queries [Full Version]},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VAYTSZFX}},
  note         = {Machine review of arXiv:2607.05832}
}
abstract

Counting queries are ubiquitous in database systems, particularly for driving internal system optimization. Learned models for cardinality estimation rely heavily on large-scale training data, yet generating such data by executing massive batches of counting queries is expensive. We propose BaCon, an efficient algorithm for batch evaluation of counting queries on top of a database system, without modifying its internals. BaCon integrates the idea of factorized databases with a workload-aware domain quantization strategy, allowing it to evaluate batches of counting queries using compact data structures rather than materializing massive join results. BaCon's design is compatible with most database management system, and we have implemented it as a client-side application on PostgreSQL with a lightweight C-language UDF (user-defined function). This implementation delivers speedups between 2$\times$ and 178$\times$ over baselines and good performance across various workloads, making training and maintenance of learned cardinality estimation models significantly more practical.

Figures

Figures reproduced from arXiv: 2607.05832 by the authors.

Figure 1
Figure 1. A join pattern in the IMDB schema [36]. Section 3.2). For example, in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Quantized selection count map for a projected subslice of table mc. The quantization scales for mc are induced by queries 𝑄1 and 𝑄2 (only selection predicates on mc are shown). 𝔟𝐴 ∈ 𝔅𝔍, such that for any 𝑄 ∈ Q[𝔍] and every selection predicate 𝐴 ↦→ 𝛿 in Preds𝜎 𝑄 : 𝑥 ∈ 𝛿 ⇔ 𝔟𝐴 (𝑥) ∈ 𝑓 (𝔟𝐴, 𝛿). As an example, [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Illustration of Algorithm 2, continuing [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: Running time (seconds) per join pattern across 283 join patterns from 9 workloads. Join patterns are ordered by IndProc’s times. The inset is the zoom-in of the first 200 indices [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: Log-scale running time per join pattern in scale. Join patterns are ordered by the number of tables involved, and the figure is partitioned accordingly (labels shown above). Hatched bars (baselines only) indicate the lower bounds for timed-out cases [PITH_FULL_IMAGE:f…
Figure 7
Figure 7. Figure 7: Log-scale running time per join pattern (where a baseline is chosen) in scale and stats_ceb, including Hybrid’s. in stats_ceb, while selecting BaCon for all other join patterns and workloads. Even with Hybrid’s conservative design, end-to￾end running times show that mi…
Figure 8
Figure 8. Figure 8: Features used by Hybrid, and their importance in a model trained as described in Section 5.4. will see in Section 5.4, BaCon performs well across our target work￾loads, so Hybrid only serves to validate the robustness of BaCon. Nonetheless, we briefly describe Hybrid h…
Figure 9
Figure 9. Figure 9: Log-scale running time per join pattern in synthetic [PITH_FULL_IMAGE:figures/full_fig_p019_9.png]
Figure 12
Figure 12. Figure 12: Log-scale running time per join pattern in stats_ceb [PITH_FULL_IMAGE:figures/full_fig_p019_12.png]
Figure 15
Figure 15. Figure 15: Log-scale running time per join pattern in dsb_grasp_20k [PITH_FULL_IMAGE:figures/full_fig_p020_15.png]
Figure 16
Figure 16. Figure 16: Log-scale running time per join pattern in job_light_1k [PITH_FULL_IMAGE:figures/full_fig_p020_16.png]
Figure 17
Figure 17. Figure 17: Log-scale running time per join pattern in job_light_2k [PITH_FULL_IMAGE:figures/full_fig_p020_17.png]
Figure 18
Figure 18. Figure 18: Log-scale running time per join pattern in job_light_4k [PITH_FULL_IMAGE:figures/full_fig_p020_18.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

87 extracted references · 87 canonical work pages

  1. [62]

    Silvan Reiner and Michael Grossniklaus. 2023. Sample-Efficient Cardinality Estimation Using Geometric Deep Learning.Proc. VLDB Endow.17, 4 (Dec. 2023), 740–752. https://doi.org/10.14778/3636218.3636229

    work page doi:10.14778/3636218.3636229 2023

  2. [1]

    PostgreSQL 17. 2025. Extending SQL: C-Language Functions. https://www. postgresql.org/docs/current/xfunc-c.html

    work page 2025

  3. [2]

    Aberger, Andrew Lamb, Susan Tu, Andres Nötzli, Kunle Oluko- tun, and Christopher Ré

    Christopher R. Aberger, Andrew Lamb, Susan Tu, Andres Nötzli, Kunle Oluko- tun, and Christopher Ré. 2017. EmptyHeaded: A Relational Engine for Graph Processing.ACM Trans. Database Syst.42, 4, Article 20 (Oct. 2017), 44 pages. https://doi.org/10.1145/3129246

    work page doi:10.1145/3129246 2017

  4. [3]

    Agarwal, Junyi Xie, Jun Yang, and Hai Yu

    Pankaj K. Agarwal, Junyi Xie, Jun Yang, and Hai Yu. 2006. Scalable continuous query processing by tracking hotspots. InProceedings of the 32nd International Conference on Very Large Data Bases(Seoul, Korea)(VLDB ’06). VLDB Endowment, 31–42

    work page 2006

  5. [4]

    Anaconda et al

    Inc. Anaconda et al . 2025. Numba - a just-in-time compiler for Python that works best on code that uses NumPy arrays and functions, and loops. https: //numba.pydata.org/numba-doc/dev/index.html#

    work page 2025

  6. [5]

    Xin, Cheng Lian, Yin Huai, Davies Liu, Joseph K

    Michael Armbrust, Reynold S. Xin, Cheng Lian, Yin Huai, Davies Liu, Joseph K. Bradley, Xiangrui Meng, Tomer Kaftan, Michael J. Franklin, Ali Ghodsi, and Matei Zaharia. 2015. Spark SQL: Relational Data Processing in Spark. InProceedings of the 2015 ACM SIGMOD International Conference on Management of Data(Mel- bourne, Victoria, Australia)(SIGMOD ’15). Asso...

    work page doi:10.1145/2723372.2742797 2015

  7. [6]

    Albert Atserias, Martin Grohe, and Dániel Marx. 2017. Size bounds and query plans for relational joins. arXiv:1711.03860 [cs.DB] https://arxiv.org/abs/1711. 03860

    work page Pith review arXiv 2017

  8. [7]

    Nurzhan Bakibayev, Tomáš Kočiský, Dan Olteanu, and Jakub Závodný. 2013. Aggregation and ordering in factorised databases.Proc. VLDB Endow.6, 14 (Sept. 2013), 1990–2001. https://doi.org/10.14778/2556549.2556579

    work page doi:10.14778/2556549.2556579 2013

Show all 87 references
  1. [8]

    Nurzhan Bakibayev, Dan Olteanu, and Jakub Závodný. 2012. FDB: a query engine for factorised relational databases.Proc. VLDB Endow.5, 11 (July 2012), 1232–1243. https://doi.org/10.14778/2350229.2350242

    2012 doi

  2. [9]

    Surajit Chaudhuri and Kyuseok Shim. 1994. Including Group-By in Query Optimization. InProceedings of the 20th International Conference on Very Large Data Bases (VLDB ’94). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 354–366

    1994

  3. [10]

    Bailu Ding, Surajit Chaudhuri, Johannes Gehrke, and Vivek Narasayya. 2021. DSB: a decision support benchmark for workload-driven and traditional database systems.Proc. VLDB Endow.14, 13 (Sept. 2021), 3376–3388. https://doi.org/10. 14778/3484224.3484234

    2021

  4. [11]

    Bailu Ding, Surajit Chaudhuri, Johannes Gehrke, and Vivek Narasayya. 2021. DSB Initialization Files and Scripts. https://github.com/microsoft/dsb/tree/main/ scripts

    2021

  5. [12]

    Lyric Doshi, Vincent Zhuang, Gaurav Jain, Ryan Marcus, Haoyu Huang, Deniz Altinbüken, Eugene Brevdo, and Campbell Fraser. 2023. Kepler: Robust Learning for Parametric Query Optimization.Proc. ACM Manag. Data1, 1, Article 109 (May 2023), 25 pages. https://doi.org/10.1145/3588963

    2023 doi

  6. [13]

    Anshuman Dutt, Chi Wang, Azade Nazi, Srikanth Kandula, Vivek Narasayya, and Surajit Chaudhuri. 2019. Selectivity estimation for range predicates using lightweight models.Proc. VLDB Endow.12, 9 (May 2019), 1044–1057. https: //doi.org/10.14778/3329772.3329780

    2019 doi

  7. [14]

    Michael Freitag, Maximilian Bandle, Tobias Schmidt, Alfons Kemper, and Thomas Neumann. 2020. Adopting worst-case optimal joins in relational database systems. Proc. VLDB Endow.13, 12 (July 2020), 1891–1904. https://doi.org/10.14778/ 3407790.3407797

    2020

  8. [15]

    Georgios Giannikis, Darko Makreshanski, Gustavo Alonso, and Donald Koss- mann. 2014. Shared workload optimization.Proc. VLDB Endow.7, 6 (Feb. 2014), 429–440. https://doi.org/10.14778/2732279.2732280

    2014 doi

  9. [16]

    Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, and Paul Valiant. 2012. Size and Treewidth Bounds for Conjunctive Queries.J. ACM59, 3, Article 16 (June 2012), 35 pages. https://doi.org/10.1145/2220357.2220363

    2012 doi

  10. [17]

    Jim Gray, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, Murali Venkatrao, Frank Pellow, and Hamid Pirahesh. 1997. Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub- Totals.Data Min. Knowl. Discov.1, 1 (Jan. 1997), 29–53. ht...

    1997 doi

  11. [18]

    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 doi

  12. [19]

    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. 2023. job-light- join.sql. https://github.com/Nathaniel-Han/End-to-End-CardEst-Benchmark/ blob/mast...

    2023

  13. [20]

    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. 2023. job-light-single.sql. https://github.com/ Nathaniel-Han/End-to-End-CardEst-Benchmark/blob/mas...

    2023

  14. [21]

    Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, Zhengping Qian, Jin- gren Zhou, Jiangneng Li, and Bin Cui. 2023. STATS Initialization Files and Scripts. https://github.com/Nathaniel-Han/End-to-End-CardEst...

    2023

  15. [22]

    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. 2023. stats_ceb_join.sql. https://github.com/Nathaniel-Han/End-to-End-CardEst-Benchmark/blob/ maste...

    2023

  16. [23]

    Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, Zhengping Qian, Jin- gren Zhou, Jiangneng Li, and Bin Cui. 2023. stats_ceb_single.sql. https: //github.com/Nathaniel-Han/End-to-End-CardEst-Benchmark/blob/m...

    2023

  17. [24]

    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. 2023. stats_ceb.sql. https://github.com/Nathaniel-Han/End-to-End-CardEst-Benchmark/blob/ master/wor...

    2023

  18. [25]

    Mike Heddes, Igor Nunes, Tony Givargis, and Alex Nicolau. 2024. Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries.Proc. ACM Manag. Data2, 3, Article 129 (May 2024), 26 pages. https://doi.org/10.1145/3654932

    2024 doi

  19. [26]

    Xiao Hu. 2025. Output-Optimal Algorithms for Join-Aggregate Queries.Proc. ACM Manag. Data3, 2, Article 104 (June 2025), 27 pages. https://doi.org/10.1145/ 3725241

    2025

  20. [27]

    Agarwal, Debmalya Panigrahi, Sudeepa Roy, and Jun Yang

    Xiao Hu, Yuxi Liu, Haibo Xiu, Pankaj K. Agarwal, Debmalya Panigrahi, Sudeepa Roy, and Jun Yang. 2022. Selectivity Functions of Range Queries are Learnable. InSIGMOD(Philadelphia, PA, USA)(SIGMOD ’22). 959–972

    2022

  21. [28]

    Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2018. job-light.sql. https://github.com/andreaskipf/learnedcardinalities/ blob/master/workloads/job-light.sql

    2018

  22. [29]

    Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2018. Learned cardinalities: Estimating correlated joins with deep learning.arXiv preprint arXiv:1809.00677(2018)

    2018 arXiv

  23. [30]

    Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2018. scale.sql. https://github.com/andreaskipf/learnedcardinalities/ blob/master/workloads/scale.sql

    2018

  24. [31]

    Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2018. synthetic.sql. https://github.com/andreaskipf/ learnedcardinalities/blob/master/workloads/synthetic.sql

    2018

  25. [32]

    Meghdad Kurmanji and Peter Triantafillou. 2023. Detect, Distill and Update: Learned DB Systems Facing Out of Distribution Data.Proc. ACM Manag. Data1, 1, Article 33 (May 2023), 27 pages. https://doi.org/10.1145/3588713

    2023 doi

  26. [33]

    Matthias Lanzinger, Reinhard Pichler, and Alexander Selzer. 2025. Avoiding Materialisation for Guarded Aggregate Queries.Proc. VLDB Endow.18, 5 (Jan. 2025), 1398–1411. https://doi.org/10.14778/3718057.3718068

    2025 doi

  27. [34]

    2013-2019

    Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2013-2019. IMDB Initialization Files and Scripts. https: //event.cwi.nl/da/job/

    2013

  28. [35]

    Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2015. How good are query optimizers, really?Proc. VLDB Endow.9, 3 (Nov. 2015), 204–215. https://doi.org/10.14778/2850583.2850594

    2015 doi

  29. [36]

    Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2015. IMDB Relational Schema by JOB. https://event.cwi.nl/ da/job/

    2015

  30. [37]

    Beibin Li, Yao Lu, and Srikanth Kandula. 2022. Warper: Efficiently Adapting Learned Cardinality Estimators to Data and Workload Drifts. InProceedings of the 2022 International Conference on Management of Data(Philadelphia, PA, USA)(SIGMOD ’22). Association for Computing Machin...

    2022 doi

  31. [38]

    Beibin Li, Yao Lu, Chi Wang, and Srikanth Kandula. 2021. Car- dinality Estimation: Is Machine Learning a Silver Bullet?. InAIDB. https://www.microsoft.com/en-us/research/publication/cardinality- estimation-is-machine-learning-a-silver-bullet/

    2021

  32. [39]

    Pengfei Li, Wenqing Wei, Rong Zhu, Bolin Ding, Jingren Zhou, and Hua Lu

  33. [40]

    VLDB Endow.17, 2 (Oct

    ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads.Proc. VLDB Endow.17, 2 (Oct. 2023), 197–210. https: //doi.org/10.14778/3626292.3626302

    2023 doi

  34. [41]

    Jie Liu, Wenqian Dong, Qingqing Zhou, and Dong Li. 2021. Fauce: fast and accurate deep ensembles with uncertainty for cardinality estimation.Proc. VLDB Endow.14, 11 (July 2021), 1950–1963. https://doi.org/10.14778/3476249.3476254

    2021 doi

  35. [42]

    Yuxi Liu, Xiao Hu, Pankaj Agarwal, and Jun Yang. 2026. dsb_grasp_20k.sql. https://github.com/louisja1/bacon/blob/main/workload/dsb_grasp_20k.sql

    2026

  36. [43]

    Yuxi Liu, Xiao Hu, Pankaj Agarwal, and Jun Yang. 2026. [Full Version] BaCon: Efficient Batch Processing of Counting Queries. https://github.com/louisja1/ bacon/blob/main/fullversion.pdf

    2026

  37. [44]

    Yuxi Liu, Xiao Hu, Pankaj Agarwal, and Jun Yang. 2026. Github Repository of BaCon. https://github.com/louisja1/bacon

    2026

  38. [45]

    Yuxi Liu, Xiao Hu, Pankaj Agarwal, and Jun Yang. 2026. Script for generating dsb_grasp_20k.sql. https://github.com/louisja1/bacon/blob/main/workload/ raw/dsb_grasp_csv_to_sql.py

    2026

  39. [46]

    Hellerstein, and Vijayshankar Raman

    Samuel Madden, Mehul Shah, Joseph M. Hellerstein, and Vijayshankar Raman

  40. [47]

    InProceedings of the 2002 ACM SIGMOD International Conference on Management of Data(Madison, Wisconsin)(SIGMOD ’02)

    Continuously adaptive continuous queries over streams. InProceedings of the 2002 ACM SIGMOD International Conference on Management of Data(Madison, Wisconsin)(SIGMOD ’02). Association for Computing Machinery, New York, NY, USA, 49–60. https://doi.org/10.1145/564691.564698

    2002 doi

  41. [48]

    Ryan Marcus, Parimarjan Negi, Hongzi Mao, Nesime Tatbul, Mohammad Al- izadeh, and Tim Kraska. 2021. Bao: Making Learned Query Optimization Practical. InProceedings of the 2021 International Conference on Management of Data(Vir- tual Event, China)(SIGMOD ’21). Association for C...

    2021 doi

  42. [49]

    Ryan Marcus, Parimarjan Negi, Hongzi Mao, Chi Zhang, Mohammad Alizadeh, Tim Kraska, Olga Papaemmanouil, and Nesime Tatbul. 2019. Neo: a learned query optimizer.Proc. VLDB Endow.12, 11 (July 2019), 1705–1718. https://doi. org/10.14778/3342263.3342644

    2019 doi

  43. [50]

    Amine Mhedhbi and Semih Salihoglu. 2019. Optimizing subgraph queries by combining binary and worst-case optimal joins.Proc. VLDB Endow.12, 11 (July 2019), 1692–1704. https://doi.org/10.14778/3342263.3342643

    2019 doi

  44. [51]

    Microsoft. [n.d.]. Microsoft SQL Server: Common Language Runtime (CLR) Integration. https://learn.microsoft.com/en-us/sql/relational-databases/clr- integration/common-language-runtime-integration-overview?view=sql- server-ver17

  45. [52]

    Magnus Müller, Lucas Woltmann, and Wolfgang Lehner. 2023. Enhanced Fea- turization of Queries with Mixed Combinations of Predicates for ML-based Cardinality Estimation. InProceedings 26th International Conference on Extending Database Technology, EDBT 2023, Ioannina, Greece, M...

    2023 doi

  46. [53]

    Parimarjan Negi, Ryan Marcus, Andreas Kipf, Hongzi Mao, Nesime Tatbul, Tim Kraska, and Mohammad Alizadeh. 2021. Flow-loss: learning cardinality estimates that matter.Proc. VLDB Endow.14, 11 (July 2021), 2019–2032. https://doi.org/10. 14778/3476249.3476259

    2021

  47. [54]

    Parimarjan Negi, Ziniu Wu, Andreas Kipf, Nesime Tatbul, Ryan Marcus, Sam Madden, Tim Kraska, and Mohammad Alizadeh. 2023. Robust Query Driven Cardinality Estimation under Changing Workloads.Proc. VLDB Endow.16, 6 (Feb. 2023), 1520–1533. https://doi.org/10.14778/3583140.3583164

    2023 doi

  48. [55]

    Hung Q. Ngo. 2018. Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems. InProceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems(Houston, TX, USA)(PODS ’18). Association for Computing Machinery, New York, NY, USA, 111...

    2018 doi

  49. [56]

    Ngo, Ely Porat, Christopher Ré, and Atri Rudra

    Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. 2012. Worst-case Optimal Join Algorithms. arXiv:1203.1952 [cs.DB] https://arxiv.org/abs/1203. 1952

    2012 arXiv

  50. [57]

    Hung Q Ngo, Christopher Ré, and Atri Rudra. 2014. Skew strikes back: new developments in the theory of join algorithms.SIGMOD Rec.42, 4 (Feb. 2014), 5–16. https://doi.org/10.1145/2590989.2590991

    2014 doi

  51. [58]

    Dan Olteanu and Jakub Zavodny. 2012. Factorised representations of query results: size bounds and readability. In15th International Conference on Database Theory, ICDT ’12, Berlin, Germany, March 26-29, 2012, Alin Deutsch (Ed.). ACM, 285–298. https://doi.org/10.1145/2274576.2274607

    2012 doi

  52. [59]

    Oracle. [n.d.]. Oracle Database: External Procedures. https://docs.oracle.com/en/ database/oracle/oracle-database/19/ntqrf/external-procedures-overview.html

  53. [60]

    Y. Park, S. Zhong, and B. Mozafari. 2020. Quicksel: Quick selectivity learning with mixture models. InProc. 39th ACM SIGMOD Int. Conf. Management Data,. 1017–1033

    2020

  54. [61]

    Mark Raasveldt. 2022. DuckDB - A Modern Modular and Extensible Database System. InCDMS@VLDB. https://api.semanticscholar.org/CorpusID:252384081

    2022

  55. [63]

    Wolfgang Scheufele and Guido Moerkotte. 1997. On the complexity of generating optimal plans with cross products. InProceedings of the Sixteenth ACM SIGACT- SIGMOD-SIGART Symposium on Principles of Database Systems. 238–248

    1997

  56. [64]

    Ngo, and XuanLong Nguyen

    Maximilian Schleich, Dan Olteanu, Mahmoud Abo Khamis, Hung Q. Ngo, and XuanLong Nguyen. 2019. A Layered Aggregate Engine for Analytics Workloads. InProceedings of the 2019 International Conference on Management of Data(Ams- terdam, Netherlands)(SIGMOD ’19). Association for Com...

    2019 doi

  57. [65]

    2007-2025

    scikit-learn developers. 2007-2025. scikit-learn – RandomForestClassi- fier. https://scikit-learn.org/stable/modules/generated/sklearn.ensemble. RandomForestClassifier.html#randomforestclassifier

    2007

  58. [66]

    Selinger, Morton M

    Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, and Thomas G. Price. 1979. Access Path Selection in a Relational Database Management System. InProceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston, Massachus...

    1979 doi

  59. [67]

    Timos K. Sellis. 1988. Multiple-query optimization.ACM Trans. Database Syst. 13, 1 (March 1988), 23–52. https://doi.org/10.1145/42201.42203

    1988 doi

  60. [68]

    2001-2021

    The Psycopg Team. 2001-2021. Psycopg – Client-side Cursors. https://www. psycopg.org/docs/cursor.html

    2001

  61. [69]

    2001-2021

    The Psycopg Team. 2001-2021. Psycopg – PostgreSQL database adapter for Python. https://www.psycopg.org/docs/#

    2001

  62. [70]

    2001-2021

    The Psycopg Team. 2001-2021. Psycopg – Server-side Cursors. https://www. psycopg.org/docs/usage.html#server-side-cursors

    2001

  63. [71]

    Veldhuizen

    Todd L. Veldhuizen. 2013. Leapfrog Triejoin: a worst-case optimal join algorithm. arXiv:1210.0481 [cs.DB] https://arxiv.org/abs/1210.0481

    2013 arXiv

  64. [72]

    Yisu Remy Wang, Max Willsey, and Dan Suciu. 2023. Free Join: Unifying Worst- Case Optimal and Traditional Joins.Proc. ACM Manag. Data1, 2, Article 150 (June 2023), 23 pages. https://doi.org/10.1145/3589295

    2023 doi

  65. [73]

    Peizhi Wu and Gao Cong. 2021. A unified deep model of learning from both data and queries for cardinality estimation. InProceedings of the 2021 International Conference on Management of Data. 2009–2022

    2021

  66. [74]

    Peizhi Wu and Zachary G. Ives. 2024. Modeling Shifting Workloads for Learned Database Systems.Proc. ACM Manag. Data2, 1, Article 38 (March 2024), 27 pages. https://doi.org/10.1145/3639293

    2024 doi

  67. [75]

    Peizhi Wu, Rong Kang, Tieying Zhang, Jianjun Chen, Ryan Marcus, and Zachary G. Ives. 2025. Data-Agnostic Cardinality Learning from Imperfect Workloads.Proc. VLDB Endow.18, 8 (April 2025), 2519–2532. https://doi.org/10. 14778/3742728.3742745

    2025

  68. [76]

    Peizhi Wu, Rong Kang, Tieying Zhang, Jianjun Chen, Ryan Marcus, and Zachary G. Ives. 2025. Original query workload of GRASP. https://github. com/shoupzwu/GRASP/blob/master/queries/dsb.csv

    2025

  69. [77]

    Peizhi Wu, Haoshu Xu, Ryan Marcus, and Zachary G. Ives. 2025. A Practical Theory of Generalization in Selectivity Learning.Proc. VLDB Endow.18, 6 (Feb. 2025), 1811–1824. https://doi.org/10.14778/3725688.3725708

    2025 doi

  70. [78]

    Yan and Per-Åke Larson

    Weipeng P. Yan and Per-Åke Larson. 1995. Eager Aggregation and Lazy Aggre- gation. InProceedings of the 21th International Conference on Very Large Data Bases (VLDB ’95). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 345–357

    1995

  71. [79]

    Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen, and Ion Stoica. 2020. NeuroCard: one cardinality estimator for all tables.Proc. VLDB Endow.14, 1 (Sept. 2020), 61–73. https://doi.org/10.14778/3421424.3421432

    2020 doi

  72. [80]

    Hellerstein, Sanjay Krishnan, and Ion Stoica

    Zongheng Yang, Eric Liang, Amog Kamsetty, Chenggang Wu, Yan Duan, Xi Chen, Pieter Abbeel, Joseph M. Hellerstein, Sanjay Krishnan, and Ion Stoica

  73. [81]

    VLDB Endow.13, 3 (Nov

    Deep unsupervised cardinality estimation.Proc. VLDB Endow.13, 3 (Nov. 2019), 279–292. https://doi.org/10.14778/3368289.3368294

    2019 doi

  74. [82]

    Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. InProceed- ings of the Seventh International Conference on Very Large Data Bases - Volume 7 (Cannes, France)(VLDB ’81). VLDB Endowment, 82–94

    1981

  75. [83]

    Haozhe Zhang, Christoph Mayer, Mahmoud Abo Khamis, Dan Olteanu, and Dan Suciu. 2025. LpBound: Pessimistic Cardinality Estimation Using 𝓁p-Norms of Degree Sequences.Proc. ACM Manag. Data3, 3 (2025), 184:1–184:27. https: //doi.org/10.1145/3725321

    2025 doi

  76. [84]

    Jingren Zhou, Per-Ake Larson, Johann-Christoph Freytag, and Wolfgang Lehner

  77. [85]

    In Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data(Beijing, China)(SIGMOD ’07)

    Efficient exploitation of similar subexpressions for query processing. In Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data(Beijing, China)(SIGMOD ’07). Association for Computing Machinery, New York, NY, USA, 533–544. https://doi.org/10.1145/124...

    2007 doi

  78. [86]

    0”: 1, “1

    Rong Zhu, Lianggui Weng, Bolin Ding, and Jingren Zhou. 2024. Learned Query Optimizer: What is New and What is Next. InCompanion of the 2024 International Conference on Management of Data(Santiago AA, Chile)(SIG- MOD ’24). Association for Computing Machinery, New York, NY, USA,...

    2024 doi

  79. [87]

    The previous works have achieved two flavors of results: worst- case optimal and output-sensitive

    Processing such queries usually first push down the selection predicate to the base table, and ends up with processing join-count queries, which is the focus below. The previous works have achieved two flavors of results: worst- case optimal and output-sensitive. Namely, worst...

Pith tools

Reviewed July 8, 2026 · model on record in the stance chip above.