Pith. sign in

REVIEW 4 major objections 5 minor 69 references

Algorithmic Complexity Attacks on All Learned Cardinality Estimators: A Data-centric Approach

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Poisoning just 0.8% of a database's training tuples can make learned cardinality estimators report cardinalities that are off by three orders of magnitude, and the same attack degrades every estimator architecture.

desk verdict The empirical attack is credible and the oracle-surrogate idea is genuinely new, but the theory overclaims: NP-hardness and the (1-kappa) bound apply to a surrogate objective, and transfer to real estimators on test workloads is asserted, not shown. read the letter →

arxiv 2507.07438 v1 pith:M5ZFLETW submitted 2025-07-10 cs.DB

Yingze Li , Xianglong Liu , Dong Wang , Zixuan Wang , Hongzhi Wang , Kaixing Zhang , Yiming Guan This is my paper
classification cs.DB
keywords cardinalityestimationdatapoisoningalgorithmiccomplexityattacklearnedestimatorsblack-boxqueryoptimizationNP-hardnesssupermodular
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

The paper claims that all learned cardinality estimators share a single exploitable weakness: once trained, they closely approximate the true cardinality oracle on their training data. An attacker who can modify a small number of tuples in the training database can therefore degrade any learned estimator by degrading the oracle itself, even without knowing which estimator is deployed. The paper proves that finding the optimal set of tuples to delete or duplicate is NP-hard, and gives a polynomial-time greedy algorithm with a $(1-\kappa)$ approximation guarantee. Experiments on STATS-CEB and IMDB-JOB show that modifying about 0.8% of training tuples raises the 90th-percentile Qerror by three orders of magnitude and increases end-to-end query processing time up to 20 times. The point of the work is to establish that this fragility is universal across data-driven, query-driven, and hybrid estimators, not an artifact of any one model.

What carries the argument

The load-bearing machinery is the oracle surrogate transformation. The paper observes that learned estimators are trained to predict the true cardinality on the training database, so for the oracle $E_O$ we have $\mathrm{est}(q|E_O) = C_{D'}(q)$; the Qerror between the oracle's prediction on the poisoned database and the true cardinality on the clean database then stands in for the Qerror of any learned estimator. This turns the black-box attack into a tuple-selection problem in which each tuple $t_i$ has a joint weight $w_{ij}$, its contribution to query $q_j$'s result cardinality. The theory that carries the algorithm is the supermodularity of the delete-only objective (marginal gains increase as the selected set grows, Theorem 4.1) and the modularity of the insert-only objective (Theorem 4.2), which let the greedy Algorithm 1 achieve a $(1-\kappa)$-approximation in the delete-only case and exact optimality in the insert-only case.

What would settle it

Take a learned estimator and a test workload whose join predicates and filter columns differ from the workload used to generate the attack, retrain the estimator on the poisoned database produced by Algorithm 1, and measure the 90th-percentile Qerror on the clean database. If the Qerror does not rise by roughly three orders of magnitude, the oracle surrogate no longer stands in for the real estimator, and the paper's central transfer claim fails.

Watch

Extended reading notes

Core claim

The central discovery is a reduction: the worst-case data-centric attack on all learned cardinality estimators can be formulated as a combinatorial tuple-selection problem. Because learned estimators are near-oracle on their training data, the paper replaces the unknown estimator $E$ with the exact oracle $E_O$ that reports $C_{D'}(q)$ on the poisoned database. The attack objective becomes maximizing, over a budget of $K$ tuple deletions or duplications, the Qerror between the poisoned cardinality $C_{D'}(q_j)$ and the clean cardinality $C_D(q_j)$ (Eq. 3). The paper proves this optimization is NP-hard by reduction from Densest-$K$-Subgraph, even when only deletions are allowed, and shows that for deletions the objective is supermodular while for insertions it is modular. Algorithm 1 greedily selects the tuple operation with the largest marginal Qerror gain, and the supermodularity yields a $(1-\kappa)$ approximation ratio. Empirically the strategy reproduces the predicted degradation on real benchmarks: 0.8% tuple modifications raise the 90th-percentile Qerror by three orders of magnitude and slow end-to-end processing by up to 20$\times$.

Load-bearing premise

The whole attack rests on the premise that a learned estimator trained on the poisoned database will predict close to the true cardinality of that poisoned database for the test queries; if the estimator generalizes imperfectly to the test workload, the oracle-based Qerror may not match what the estimator actually reports.

Editorial extensions

If this is right

  • A deployed learned estimator whose training data has drifted is exposed: an adversary who modifies a small fraction of rows, not queries, can push its cardinality estimates to values that force the optimizer into nested-loop plans.
  • Because the attack targets the oracle rather than the model, it transfers across data-driven, query-driven, and hybrid estimators without any white-box knowledge of the model.
  • The $(1-\kappa)$-approximation algorithm gives database administrators a polynomial-time way to compute an upper bound on the worst-case degradation, so estimators can be audited before deployment.
  • The measured 20x end-to-end slowdown shows the Qerror degradation translates into physical plan changes that hurt real query latency, not just a metric artifact.
  • The paper's two countermeasures - ensembling several estimators and injecting calibrated noise into estimates - reduce but do not eliminate the attack, so robust learned optimizers still need a different design principle.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The oracle-surrogate logic suggests an accuracy paradox: as learned estimators get more accurate on their training data, they may become more, not less, vulnerable to data-centric attacks, because the attacker's surrogate becomes a better stand-in for the real model.
  • The same tuple-weight machinery could be adapted to other learned database components trained on stale snapshots, such as learned cost models or learned indexes; the paper does not explore that extension.
  • If an estimator is retrained periodically, the attacker's problem becomes a timing game between retraining frequency and data drift; the paper's static clean-versus-poisoned setup does not model that dynamic.
  • A direct test of the transfer assumption would compare the oracle-predicted Qerror with each estimator's observed Qerror on a workload outside the attack's training distribution; the gap between the two would measure how universal the attack actually is.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper proposes a data-centric algorithmic complexity attack (DACA) against learned cardinality estimators in a black-box setting. The authors observe that learned estimators are highly accurate on their training database, so they replace the unknown estimator by an oracle that returns true cardinalities on the poisoned database (Section 3.2, Eq. 2). This yields a constrained integer nonlinear program (Eq. 3). They prove NP-hardness by reduction from Densest-k-Subgraph for deletion-only and mixed operations (Theorems 3.1 and 3.2), analyze supermodularity and modularity of restricted objectives (Theorems 4.1 and 4.2), and present a greedy algorithm with a claimed (1−κ) approximation guarantee (Theorem 4.3). Experiments on STATS-CEB and IMDB-JOB with six learned estimators show large increases in Qerror and end-to-end latency, and two countermeasures are explored.

Significance. If the claims hold, this would be one of the first attacks to degrade query-driven, data-driven, and hybrid cardinality estimators with a single data-centric strategy, and it would provide a tractable worst-case analysis framework for learned estimators. The empirical study is broad: six estimators, two benchmarks, percentile Qerrors, end-to-end latency, and plan-shape analysis. The DKS reduction is a sound NP-hardness argument for the surrogate objective, and the observation that high training accuracy creates a common attack surface is valuable. However, the central transfer from the oracle surrogate to arbitrary learned estimators is not established, and the greedy algorithm analyzed in Theorem 4.3 is not the algorithm implemented in the experiments. The empirical phenomenon may be real, but the theoretical package as written overstates what is proven.

major comments (4)
  1. [Section 3.2, Eq. (2)] The oracle-surrogate transformation is load-bearing but unvalidated. The original black-box objective (Eq. 1) is over est(q|E), the prediction of the actual estimator trained on D′. Eq. (2) replaces this by C_{D′}(q), which requires est(q|E) ≈ C_{D′}(q) for the test workload W_Test. Section 5.1 shows that query-driven models (LWNN, MSCN, ALECE) are trained on a separate synthetic workload of 2,000 queries, not on W_Test, and no experiment measures the closeness of est(q|E) to C_{D′}(q) on W_Test after poisoning. If this closeness fails, the NP-hardness result (Theorem 3.1) and the approximation guarantee (Theorem 4.3) apply to the wrong objective, and Algorithm 1 can select suboptimal tuples for the true estimator. Please add a direct comparison between the oracle Qerror and each estimator's actual Qerror on D′ for W_Test, and discuss the deviations.
  2. [Section 4.2, Algorithm 1, lines 6 and 10] The implemented gain does not match the marginal gain used in Theorem 4.3. For a deletion, the marginal contribution of adding tuple t_i to the current set ΔD should be Q(ΔD_i + t_i) − Q(ΔD_i), which equals (C_D+1)/(C_D+1−W−w) − (C_D+1)/(C_D+1−W), where W is the total weight of deletions already in ΔD_i. Line 6 instead computes Q(C_{D+ΔD}(q), C_{D+ΔD}(q)−w), i.e., the Qerror between the current state and the state after one deletion. These quantities are not equal; for example, with C_D=100, W=0, w=10, the true marginal contribution is 101/91 − 1, while line 6 returns 100/90. As a result, the algorithm's selection can differ from the greedy rule analyzed in the proof. The paper should either modify Algorithm 1 to compute true marginal gains or provide a separate approximation analysis for the implemented rule.
  3. [Section 4.3, Theorem 4.3] The proof of Eq. (5) is not valid as written. The definition of κ restricts A and B in the ratio to subsets of R_x − t, but in the proof A=ΔD_i can already contain t_i1, an element of the optimal solution that the greedy algorithm may have selected earlier. In that case Q(A + t_i1) − Q(A) = 0, so the inequality (Q(ΔD_i + t_i1) − Q(ΔD_i)) ≥ (1−κ)(Q(O_i + t_i1) − Q(O_i)) fails when 1−κ > 0. The final telescoping step also requires Q(ΔD_K) to equal the sum of exact marginal gains, which is not guaranteed under the algorithm's actual gain computation. As presented, the claimed (1−κ) approximation guarantee is not established.
  4. [Section 5.2 and Abstract] The abstract and Section 1 claim that modifying 'just 0.8% of training tuples' causes the reported degradation, but Section 5.2 sets the attack budget to 20% of the attacked table. For IMDB-JOB this is 0.8% of all tuples, and for STATS-CEB it is about 1.2% of all tuples. Please clarify whether the percentage is relative to the whole database or to the attacked table, and align the abstract, Section 1, and Section 5.2.
minor comments (5)
  1. [Abstract] There is a grammatical error: 'the first to theoretical investigate' should be 'the first to theoretically investigate'.
  2. [Table 1] Several rows in Table 1 are difficult to read because of missing separators and corrupted numeric formatting, e.g., '62013.04·10 4', '20055.15·10 5', and '15668741'. Please regenerate the table with clear scientific notation.
  3. [Figure 4] The axis labels and plot text in Figure 4 appear as encoded strings (e.g., '/s49/s48'), making the figure unreadable in the submitted PDF. Please replace with legible text.
  4. [Section 3.2, Eq. (3)] The +1 smoothing added to numerator and denominator changes the objective relative to the standard Qerror in Eq. (1). The paper should state explicitly that all theoretical and experimental results are for the smoothed objective, since the smoothing can change the ranking of candidate attacks when cardinalities are small.
  5. [Section 5.4] The ensemble countermeasure is described as providing 'certain defense' but the reported result shows that the ensemble does not significantly outperform the best individual model. Consider presenting this as a preliminary observation rather than a validated countermeasure.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the oracle-surrogate objective is evaluated against independent estimators, and no fitted parameter is relabeled as a prediction; only a minor non-load-bearing self-citation ([39]) appears.

full rationale

Walking the derivation chain: Eq. 1 states the black-box objective with the actual estimator E; Eq. 2 replaces E with an oracle E_O by the explicit assumption that learned estimators approach oracle accuracy on their training data. This is a surrogate step, not a circular definition, because the resulting Eq. 3 is computed entirely from true cardinalities C_D and C_D' and tuple joint weights w_ij, none of which are taken from the victim estimators. Algorithm 1 then greedily maximizes Eq. 3 with no fitted parameters and no constants learned from the six evaluated estimators. The experiments in Section 5.2 train LWNN, MSCN, NeuroCard, FactorJoin, ALECE, and RobustMSCN on the poisoned database D' and test them on the clean database D using the same workload the attacker used, which is an independent empirical test rather than a re-statement of the attack objective. The NP-hardness reductions (Theorems 3.1 and 3.2) reduce the Densest-K-Subgraph problem to the surrogate objective, and the approximation results (Theorems 4.3 and 4.4) are mathematical statements about that same surrogate objective; neither feeds its conclusions back into the experimental setup. The only self-citation is reference [39] in the related-work enumeration of data-driven estimators, and it is not load-bearing: the attack's validity does not rest on it. The main limitation, which I flag as a correctness/evidence gap rather than circularity, is that the surrogate transfer est(q|E) = C_D'(q) is justified only by training-set accuracy in Section 3.2, while Section 5.1 trains query-driven models on 2,000 synthetic queries, so the transfer to out-of-distribution test queries is not proven. This affects the strength of the theoretical claims, but it does not make any result equivalent to its input by construction. The 0.8%-budget and three-orders-of-magnitude Qerror claims are empirical measurements, not predictions derived from fitted inputs.

Assumptions & free parameters 2 free parameters · 5 assumptions · 1 invented entities

The central claim rests on the oracle-transfer assumption (an unquantified proxy) and on a strong attacker capability (exact per-tuple weights from test results). The optimization itself is parameter-free for real data except for the hand-set budget K and the +1 smoothing. The NP-hardness and approximation results are conditioned on the surrogate objective and on kappa, not on the original black-box estimator objective.

free parameters (2)
  • Attack budget K = 20% of the attacked table (5e5 of 6.21e7 total tuples on IMDB-JOB; 1.8e4 of 1.03e6 on STATS-CEB)
    Hand-set experimental constant. The headline '0.8% of tuples' depends on this choice; Figure 6 shows attack effectiveness scales with K, so the magnitude of the reported damage is partly a consequence of picking a 20% table budget.
  • +1 smoothing constant = 1
    Added to the Qerror ratio in Eq. 3 to avoid division by zero. This changes the optimization landscape, e.g., deleting every tuple of a query gives a finite contribution 1/(C_D+1) instead of an unbounded ratio, so the attack optimizes a smoothed objective rather than the raw Qerror stated in Eq. 1.
assumptions (5)
  • domain assumption A learned estimator trained on poisoned database D' predicts approximately the true cardinalities C_{D'}(q) on the test workload, so the oracle E_O is a faithful surrogate (Eq. 2, Section 3.2).
    This is the load-bearing transfer premise. If the estimator has non-trivial error on D' for the test queries, the oracle-optimal poisoning can select the wrong tuples. The paper justifies it only by citing prior results on high training accuracy of learned CE models.
  • domain assumption The attacker can obtain exact per-tuple joint weights w_ij by grouping the materialized test-query results S(q_j|D) on the primary key of the attacked relation (Section 2.3, Section 4.2).
    This grants the attacker near-oracle visibility into tuple contributions for every test query, a strong capability that may not hold when query results are too large to materialize or when the attacker cannot run the test workload on the clean database.
  • domain assumption Test queries are SPJ queries of the form given in Section 2.1, and the Qerror metric uses the +1 smoothing of Eq. 3 for both attack and evaluation.
    Bounds the scope to the standard CE benchmark setting; the smoothing affects which deletions are considered beneficial.
  • standard math Densest-K-Subgraph is NP-hard and the polynomial-time reduction in Theorem 3.1 is valid (queries with two tuples, weight x, and budget K).
    Standard hardness result; the reduction is presented as a sketch with a worked example, and the full formal mapping is not given in the appendix.
  • ad hoc to paper For the (1-kappa) analysis, marginal gains Q(A+t)-Q(A) are well-defined and non-negative for all A, B, t with the denominator ratio finite (Theorem 4.3).
    The proof of the approximation bound implicitly requires all denominators in kappa and in Eq. 5 to be nonzero; the paper does not state or prove this condition.
invented entities (1)
  • Oracle estimator E_O
    purpose: Surrogate that exactly reports the true cardinality C_{D'}(q) on the poisoned database, used to convert the black-box attack into a data-level combinatorial optimization problem (Eq. 2).
    The oracle is a conceptual device, not an implemented system. It has no falsifiable handle outside the paper: its validity depends on the unproven assumption that real learned estimators mimic it on D'. The paper itself calls this the key to the black-box transformation, but provides no independent measurement of the oracle-approximation gap.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Algorithmic Complexity Attacks on All Learned Cardinality Estimators: A Data-centric Approach." pith.science (2026). https://pith.science/paper/M5ZFLETW

@misc{pith2026250707438,
  author       = {Pith},
  title        = {Pith review of: Algorithmic Complexity Attacks on All Learned Cardinality Estimators: A Data-centric Approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/M5ZFLETW}},
  note         = {Machine review of arXiv:2507.07438}
}
abstract

Learned cardinality estimators show promise in query cardinality prediction, yet they universally exhibit fragility to training data drifts, posing risks for real-world deployment. This work is the first to theoretical investigate how minimal data-level drifts can maximally degrade the accuracy of learned estimators. We propose data-centric algorithmic complexity attacks against learned estimators in a black-box setting, proving that finding the optimal attack strategy is NP-Hard. To address this, we design a polynomial-time approximation algorithm with a $(1-\kappa)$ approximation ratio. Extensive experiments demonstrate our attack's effectiveness: on STATS-CEB and IMDB-JOB benchmarks, modifying just 0.8\% of training tuples increases the 90th percentile Qerror by three orders of magnitude and raises end-to-end processing time by up to 20$\times$. Our work not only reveals critical vulnerabilities in deployed learned estimators but also provides the first unified worst-case theoretical analysis of their fragility under data updates. Additionally, we identify two countermeasures to mitigate such black-box attacks, offering insights for developing robust learned database optimizers.

Figures

Figures reproduced from arXiv: 2507.07438 by the authors.

Figure 1
Figure 1. Query-centric ACA (Left) vs. data-centric ACA [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. DACA workflow (Left); The consequence of DACA (Right). [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Polynomial-time reduction example starting from [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Mean of Qerrors and end-to-end(E2E) latency degradation per query on STATS/IMDB database. [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: Scalability on different tables. Scalability on Attacked Tables: To validate the theoretical at￾tack effectiveness on different tables, in [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: Scalability on different budget. Scalability on Attacked Budget: To test the theoretical attack effectiveness on different attack budgets, we conducted experiments by switching the attack budget in the posts table of the STATS-CEB database from 1.25% to 20%. We choose …
Figure 7
Figure 7. Figure 7: Operator Distribution. In this section, we studied the consequence of DACA and possible defense strategies against DACA. For consequence study, we have selected LWNN as the target model. We conducted tests on IMDB￾JOB and STATS-CEB, and we analyzed the distribution of …
Figure 8
Figure 8. Figure 8: Physical plan of IMDB-JOB Q60. database, their proportion decreased by 51%. This suggests that the compromised cardinality estimator misleads the optimizer to reduce access to materialized caches, thereby increasing the rate of redundant computations and decreasing cac…
Figure 9
Figure 9. Figure 9: Countermeasure Study: Ensembling. Countermeasure: In [PITH_FULL_IMAGE:figures/full_fig_p012_9.png]
Figure 10
Figure 10. Figure 10: demonstrates the defense effectiveness across differ￾ent estimators and datasets. Our empirical analysis reveals three key findings: (1) Appropriate noise injection (QMean reduction up to 3 orders of magnitude) successfully mitigates worst-case performance degradation…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

69 extracted references · 47 canonical work pages

  1. [1]

    [n.d.]. IMDB. http://homepages.cwi.nl/~boncz/job/imdb.tgz.,

    work page

  2. [2]

    StackExchange

    [n.d.]. StackExchange. https://stats.stackexchange.com/,

    work page

  3. [3]

    Joblight Subqueries

    2021. Joblight Subqueries. https://github.com/Nathaniel-Han/End-to-End- CardEst-Benchmark/tree/master/workloads/job-light

    work page 2021

  4. [4]

    STATS Subqueries

    2021. STATS Subqueries. https://github.com/Nathaniel-Han/End-to-End- CardEst-Benchmark/tree/master/workloads/stats_CEB

    work page 2021

  5. [5]

    ALECE: Evaluation Utilities

    2023. ALECE: Evaluation Utilities. https://github.com/pfl-cs/ALECE/blob/main/ src/utils/eval_utils.py

    work page 2023

  6. [6]

    PRICE: Evaluation Utilities

    2023. PRICE: Evaluation Utilities. https://github.com/StCarmen/PRICE/blob/ master/utils/model/qerror.py

    work page 2023

  7. [7]

    2025. DACA. https://anonymous.4open.science/r/DACA-22F2/README.MD

    work page 2025

  8. [8]

    Yuichi Asahiro, Refael Hassin, and Kazuo Iwama. 2002. Complexity of finding dense subgraphs. Discrete Appl. Math. 121, 1–3 (Sept. 2002), 15–26. https: //doi.org/10.1016/S0166-218X(01)00243-8

    work page doi:10.1016/s0166-218x(01)00243-8 2002

Show all 69 references
  1. [9]

    Nirav Atre, Hugo Sadok, Erica Chiang, Weina Wang, and Justine Sherry. 2022. SurgeProtector: mitigating temporal algorithmic complexity attacks using ad- versarial scheduling. In Proceedings of the ACM SIGCOMM 2022 Conference (Amsterdam, Netherlands) (SIGCOMM ’22). Association ...

    2022

  2. [10]

    Wenruo Bai and Jeffrey A. Bilmes. 2018. Greed is Still Good: Max- imizing Monotone Submodular+Supermodular (BP) Functions. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018 (Proceedings of ...

    2018

  3. [11]

    Marco Barreno, Blaine Nelson, Anthony Joseph, and J. Tygar. 2010. The security of machine learning. Machine Learning 81 (11 2010), 121–148. https://doi.org/ 10.1007/s10994-010-5188-5

    2010 doi

  4. [12]

    Udi Ben-Porat, Anat Bremler-Barr, and Hanoch Levy. 2013. Vulnerability of Network Mechanisms to Sophisticated DDoS Attacks. IEEE Trans. Comput. 62, 5 (2013), 1031–1043. https://doi.org/10.1109/TC.2012.49

    2013 doi

  5. [13]

    Kristin P Bennett, Michael C Ferris, and Yannis E Ioannidis. 1991. A genetic algorithm for database query optimization. Technical Report. University of Wisconsin-Madison Department of Computer Sciences

    1991

  6. [14]

    Dimitris Bertsimas and John Tsitsiklis. 1993. Simulated annealing. Statistical science 8, 1 (1993), 10–15

    1993

  7. [15]

    Battista Biggio, Blaine Nelson, and Pavel Laskov. 2012. Poisoning attacks against support vector machines. In Proceedings of the 29th International Coference on International Conference on Machine Learning (Edinburgh, Scotland) (ICML’12). Omnipress, Madison, WI, USA, 1467–1474

    2012

  8. [16]

    Battista Biggio, Ignazio Pillai, Samuel Rota Bulò, Davide Ariu, Marcello Pelillo, and Fabio Roli. 2013. Is data clustering in adversarial settings secure?. In Proceedings of the 2013 ACM Workshop on Artificial Intelligence and Security (Berlin, Ger- many) (AISec ’13). Associat...

    2013

  9. [17]

    Mark Braverman, Young Kun Ko, Aviad Rubinstein, and Omri Weinstein

  10. [18]

    Chandra Chekuri, Kent Quanrud, and Manuel R. Torres. [n.d.]. Densest Subgraph: Supermodularity, Iterative Peeling, and Flow. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1531–1555. https://doi.org/10.1137/1.9781611977073.64 arXiv:https://...

    2022 doi

  11. [19]

    Crosby and Dan S

    Scott A. Crosby and Dan S. Wallach. 2003. Denial of service via algorithmic complexity attacks. In Proceedings of the 12th Conference on USENIX Security Symposium - Volume12 (Washington, DC)(SSYM’03). USENIX Association, USA, 3

    2003

  12. [20]

    Jialin Ding, Ryan Marcus, Andreas Kipf, Vikram Nathan, Aniruddha Nrusimha, Kapil Vaidya, Alexander van Renen, and Tim Kraska. 2022. SageDB: An Instance- Optimized Data Analytics System. Proc. VLDB Endow. 15, 13 (Sept. 2022), 4062–4078. https://doi.org/10.14778/3565838.3565857

    2022

  13. [21]

    W Dong, Z Chen, Q Luo, E Shi, and K Yi. 2024. Continual Observation of Joins under Differential Privacy. In Proceedings of the ACM on Management of Data, Vol. 2. ACM, 1–27

    2024

  14. [22]

    W Dong, JY Fang, KT Yi, Y Tao, and A Machanavajjhala. 2024. Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys. In ACM Transactions on Database Systems, Vol. 49. ACM, 1–40

    2024

  15. [23]

    Anshuman Dutt, Chi Wang, Azade Nazi, Srikanth Kandula, Vivek Narasayya, and Surajit Chaudhuri. 2019. Selectivity estimation for range predicates using light- weight models. Proceedings of the VLDB Endowment (May 2019), 1044–1057. https://doi.org/10.14778/3329772.3329780

    2019

  16. [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. 2021. Cardinality estimation in DBMS: a compre- hensive benchmark evaluation. Proc. VLDB Endow. 15,...

    2021

  17. [25]

    Benjamin Hilprecht and Carsten Binnig. 2022. Zero-Shot Cost Models for Out-of- the-box Learned Cost Prediction. Proc. VLDB Endow. 15, 11 (2022), 2361–2374. https://doi.org/10.14778/3551793.3551799

    2022

  18. [26]

    Benjamin Hilprecht, Andreas Schmidt, Moritz Kulessa, Alejandro Molina, Kristian Kersting, and Carsten Binnig. 2020. DeepDB: Learn from Data, Not from Queries! Proc. VLDB Endow. 13, 7 (mar 2020), 992–1005. https://doi.org/10.14778/3384345. 3384349

    2020 doi

  19. [27]

    Yannis E Ioannidis and Eugene Wong. 1987. Query optimization by simulated annealing. In Proceedings of the 1987 ACM SIGMOD international conference on Management of data. 9–22

    1987

  20. [28]

    Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita- Rotaru, and Bo Li. 2021. Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning. arXiv:1804.00308 [cs.CR] https://arxiv.org/abs/1804.00308

    2021 arXiv

  21. [30]

    Kyoungmin Kim, Sangoh Lee, Injung Kim, and Wook-Shin Han. 2024. ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation. Proc. ACM Manag. Data 2, 1, Article 45 (mar 2024), 27 pages. https://doi.org/10.1145/3639300

    2024 doi

  22. [31]

    Boncz, and Alfons Kemper

    Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. 2018. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. ArXiv abs/1809.00677 (2018). https://api.semanticscholar.org/ CorpusID:52154172

    2018 arXiv

  23. [32]

    Kornaropoulos, Silei Ren, and Roberto Tamassia

    Evgenios M. Kornaropoulos, Silei Ren, and Roberto Tamassia. 2022. The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures. In Proceedings of the 2022 International Conference on Management of Data (Philadelphia, PA, USA) (SIGMOD ’22). Assoc...

    2022

  24. [33]

    Meghdad Kurmanji, Eleni Triantafillou, and Peter Triantafillou. 2024. Machine Unlearning in Learned Databases: An Experimental Analysis. Proc. ACM Manag. Data 2, 1, Article 49 (mar 2024), 26 pages. https://doi.org/10.1145/3639304

    2024 doi

  25. [34]

    Meghdad Kurmanji and Peter Triantafillou. 2023. Detect, Distill and Update: Learned DB Systems Facing Out of Distribution Data. Proceedings of the ACM on Management of Data 1, 1 (2023), 1–27

    2023

  26. [35]

    Per-Ake Larson, Wolfgang Lehner, Jingren Zhou, and Peter Zabback. 2007. Car- dinality estimation using sample views with quality assurance. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data. 175–186

    2007

  27. [36]

    Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2015. How good are query optimizers, really? Proceedings of the VLDB Endowment (Nov 2015), 204–215. https://doi.org/10.14778/2850583. 2850594

    2015 doi

  28. [37]

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

    2022

  29. [38]

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

  30. [39]

    Yingze Li, Hongzhi Wang, and Xianglong Liu. 2024. One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting. Proc. ACM Manag. Data 2, 1, Article 15 (mar 2024), 26 pages. https://doi.org/10.1145/3639270 Conference acronym ’XX, June 03–05, 2018, Woodsto...

    2024 doi

  31. [40]

    Melanie Mitchell. 1998. An introduction to genetic algorithms. MIT press

    1998

  32. [41]

    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

  33. [42]

    Keromytis, and Suman Jana

    Theofilos Petsios, Jason Zhao, Angelos D. Keromytis, and Suman Jana. 2017. SlowFuzz: Automated Domain-Independent Detection of Algorithmic Com- plexity Vulnerabilities. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (Dallas, Texas, USA...

    2017

  34. [43]

    Haas, Yannis Ioannidis, and Eugene J

    Viswanath Poosala, Peter J. Haas, Yannis Ioannidis, and Eugene J. Shekita. 1996. Improved histograms for selectivity estimation of range predicates.International Conference on Management of Data (1996)

    1996

  35. [44]

    D Sun, W Dong, and K Yi. 2023. Confidence Intervals for Private Query Processing. In Proceedings of the VLDB Endowment, Vol. 17. VLDB, 373–385

    2023

  36. [45]

    Jiayi Wang, Chengliang Chai, Jiabin Liu, and Guoliang Li. 2021. FACE: A normal- izing flow based cardinality estimator. Proceedings of the VLDB Endowment 15, 1 (2021), 72–84

    2021

  37. [46]

    Xiaoying Wang, Changbo Qu, Weiyuan Wu, Jiannan Wang, and Qingqing Zhou

  38. [47]

    Peizhi Wu and Gao Cong. 2021. A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation. In Proceedings of the 2021 International Conference on Management of Data. 2009–2022

    2021

  39. [48]

    Ziniu Wu, Parimarjan Negi, Mohammad Alizadeh, Tim Kraska, and Samuel Madden. 2023. FactorJoin: A New Cardinality Estimation Framework for Join Queries. Proc. ACM Manag. Data 1, 1, Article 41 (may 2023), 27 pages. https: //doi.org/10.1145/3588721

    2023 doi

  40. [49]

    Ziniu Wu, Amir Shaikhha, Rong Zhu, Kai Zeng, Yuxing Han, and Jingren Zhou

  41. [50]

    Ziniu Wu, Peilun Yang, Pei Yu, Rong Zhu, Yuxing Han, Yaliang Li, Defu Lian, Kai Zeng, and Jingren Zhou. 2022. A Unified Transferable Model for ML-Enhanced DBMS. Conference on Innovative Data Systems Research (2022)

    2022

  42. [51]

    Han Xiao, Huang Xiao, and Claudia Eckert. 2012. Adversarial label flips attack on support vector machines. In Proceedings of the 20th European Conference on Artificial Intelligence (Montpellier, France) (ECAI’12). IOS Press, NLD, 870–875

    2012

  43. [52]

    Xianghong Xu, Tieying Zhang, Xiao He, Haoyang Li, Rong Kang, Shuai Wang, Linhui Xu, Zhimin Liang, Shangyu Luo, Lei Zhang, and Jianjun Chen. 2025. AdaNDV: Adaptive Number of Distinct Value Estimation via Learning to Select and Fuse Estimators. In Proceedings of the VLDB Endowme...

    2025

  44. [53]

    arXiv:2012.14743 [cs.DB] https://arxiv.org/abs/2012.14743

    BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation. arXiv:2012.14743 [cs.DB] https://arxiv.org/abs/2012.14743

    2012 arXiv

  45. [54]

    Kornaropoulos, and Yue Cheng

    Rui Yang, Evgenios M. Kornaropoulos, and Yue Cheng. 2024. Algorithmic Com- plexity Attacks on Dynamic Learned Indexes. Proc. VLDB Endow. 17, 4 (March 2024), 780–793. https://doi.org/10.14778/3636218.3636232

    2024

  46. [55]

    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 (sep 2020), 61–73. https://doi.org/10.14778/3421424.3421432

    2020

  47. [56]

    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. 2019. Deep Unsupervised Cardinality Estimation. Proc. VLDB Endow. 13, 3 (nov 2019), 279–292. https://doi.org/10.14778/3368289.3368294

    2019

  48. [57]

    Chaofei Yang, Qing Wu, Hai Li, and Yiran Chen. 2017. Generative Poisoning Attack Method Against Neural Networks. arXiv:1703.01340 [cs.CR] https: //arxiv.org/abs/1703.01340

    2017 arXiv

  49. [58]

    Tianjing Zeng, Junwei Lan, Jiahong Ma, Wenqing Wei, Rong Zhu, Pengfei Li, Bolin Ding, Defu Lian, Zhewei Wei, and Jingren Zhou. 2024. PRICE: A Pretrained Model for Cross-Database Cardinality Estimation. https://doi.org/10.48550/ arXiv.2406.01027

    2024 doi arXiv

  50. [59]

    Jintao Zhang, Chao Zhang, Guoliang Li, and Chengliang Chai. 2024. PACE: Poisoning Attacks on Learned Cardinality Estimation. Proc. ACM Manag. Data 2, 1, Article 37 (mar 2024), 27 pages. https://doi.org/10.1145/3639292

    2024 doi

  51. [60]

    Rui Zhang and Quanyan Zhu. 2017. A game-theoretic analysis of label flipping attacks on distributed support vector machines. In 2017 51st Annual Conference on Information Sciences and Systems (CISS). 1–6. https://doi.org/10.1109/CISS. 2017.7926118

    2017

  52. [61]

    Xiang Yu, Chengliang Chai, Guoliang Li, and Jiabin Liu. 2022. Cost-Based or Learning-Based? A Hybrid Query Optimizer for Query Plan Selection. Proc. VLDB Endow. 15, 13 (Sept. 2022), 3924–3936. https://doi.org/10.14778/3565838. 3565846

    2022 doi

  53. [62]

    Yingli Zhou, Yixiang Fang, Qingshuo Guo, Chenhao Ma, Yi Yang, and Laks VS Lakshmanan. 2024. In-depth Analysis of Densest Subgraph Discovery in a Unified Framework. In Proceedings of the International Conference on Very Large Data Bases (VLDB). VLDB Endowment

    2024

  54. [63]

    Yingli Zhou, Yixiang Fang, Wensheng Luo, and Yunming Ye. 2023. Influential Community Search over Large Heterogeneous Information Networks. Proc. VLDB Endow. 16, 8 (April 2023), 2047–2060. https://doi.org/10.14778/3594512. 3594532

    2023 doi

  55. [64]

    Yingli Zhou, Qingshuo Guo, Yixiang Fang, and Chenhao Ma. 2024. A Counting- based Approach for Efficient k-Clique Densest Subgraph Discovery. Proc. ACM Manag. Data 2, 3, Article 119 (May 2024), 27 pages. https://doi.org/10.1145/ 3654922

    2024

  56. [65]

    Yihang Zheng, Chen Lin, Xian Lyu, Xuanhe Zhou, Guoliang Li, and Tianqing Wang. 2024. Robustness of Updatable Learning-based Index Advisors against Poisoning Attack. Proc. ACM Manag. Data 2, 1, Article 10 (March 2024), 26 pages. https://doi.org/10.1145/3639265

    2024 doi

  57. [69]

    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 (May 2021), 1489–1502. https://doi.org/10.14778/3461535.3461539 Algorithm...

    2021

  58. [70]

    Consider the scenario where insertions are contemplated

    Under the given conditions, the optimal solution does not include insertions. Consider the scenario where insertions are contemplated. The upper bound of the potential gain from insertions arises from the repeated insertion across𝑀 queries, specifically denoted as𝐾×𝑀 . This ga...

  59. [71]

    Consider the𝐿-th step of the algorithm, where we examine an undeleted tuple 𝑡𝑖

    Under the given conditions, Algorithm 1’s will not choose to insert Algorithm 1 evaluates the remaining undeleted tuples at each step. Consider the𝐿-th step of the algorithm, where we examine an undeleted tuple 𝑡𝑖. We use 𝐷𝐿 to represent the current data- base state and let𝑆1 ...

    2018

  60. [2017]

    In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms(SODA)

    ETH hardness for densest-k-subgraph with perfect completeness. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms(SODA). SIAM, 1326–1341

  61. [2023]

    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

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.