Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

LpBound: Pessimistic Cardinality Estimation using $\ell_p$-Norms of Degree Sequences

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

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

Pith's one-line read LpBound solves a linear program over entropy variables to convert \ell_p-norm degree statistics into a tight, guaranteed upper bound on query output size.

desk verdict LpBound is a genuinely useful pessimistic estimator with strong experiments, but the tightness theorem is deferred and the realizability step needs proof before the guarantees advertised in the abstract are fully backed. read the letter →

arxiv 2502.05912 v1 pith:2A4UM5R2 submitted 2025-02-09 cs.DB

Haozhe Zhang , Christoph Mayer , Mahmoud Abo Khamis , Dan Olteanu , Dan Suciu This is my paper · ORCID
classification cs.DB MSC 68P1594A17
keywords cardinalityestimationpessimisticdegreesequencesℓ_p-normslinearprogrammingShannoninequalitiesqueryoptimizationgroup-byqueries
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

This paper introduces LpBound, a pessimistic cardinality estimator that returns a guaranteed upper bound on the output size of multijoin queries, with support for acyclic and cyclic joins, selection predicates, and group-by clauses. The bound is the optimal value of a linear program whose constraints combine $\ell_p$-norms of degree sequences with basic Shannon inequalities. The paper claims the bound is tight: no estimator using only these statistics can guarantee a smaller bound in the worst case, and there exists a database instance matching the statistics whose query output reaches the bound. If that claim holds, query optimizers gain a one-sided safety guarantee against underestimation while staying accurate enough to produce plans comparable to those made with true cardinalities.

What carries the argument

The central object is the degree sequence $\deg_R(V|U)$, the sorted list of frequencies with which attribute values in $U$ co-occur with values in $V$; its $\ell_p$-norm is a compact statistic that interpolates between the relation cardinality ($p=1$) and the maximum degree ($p=\infty$). The central identity is inequality (18), $\frac{1}{p}h(U)+h(V|U)\le \log||\deg_R(V|U)||_p$, which connects entropy to these database statistics and is the source of every q-inequality LpBound produces. LPbase maximizes $h(V_0)$ under these constraints and the Shannon inequalities; the optimizer returns the bound $2^{h^*(V_0)}$ and reads the dual weights as a q-inequality. LPBerge and LPflow are reformulations that shrink the LP from exponential to linear or quadratic size, making millisecond estimation feasible.

What would settle it

Fix a small cyclic query, say the 3-clique with specified $\ell_p$-norm values for the three edge relations, solve LPbase to get the bound, and exhaustively enumerate all small relation instances matching those norms; if the largest true output is ever strictly below the LP optimum beyond the paper's stated query-dependent constant, the tightness claim fails.

Watch

Extended reading notes

Core claim

LpBound establishes that $\ell_p$-norms of simple degree sequences are sufficient statistics for a tight upper bound on query output. It solves LPbase, a linear program that maximizes the entropy $h(V_0)$ of the group-by variables under statistics constraints of the form $\frac{1}{p}h(U)+h(V|U)\le \log ||\deg_R(V|U)||_p$ and under the basic Shannon inequalities; the bound is $2^{h^*(V_0)}$. The dual solution gives an explicit q-inequality $|Q| \le \prod ||\deg_R(V|U)||_p^{w^*}$ together with a Shannon-inequality proof of it. Two reformulations, LPBerge for Berge-acyclic queries and LPflow for arbitrary conjunctive queries, reduce the LP to practical size. In experiments on standard benchmarks, the estimates are orders of magnitude closer to true cardinalities than traditional estimators, and injecting them into Postgres yields query plans at least as good as plans produced with true cardinalities.

Load-bearing premise

The whole guarantee rests on inequality (18) being valid for every simple degree sequence and on every normal polymatroid used in the appendix being realizable as the entropy vector of an actual database instance with the given statistics; the paper asserts the tightness theorem but leaves its proof to the full version.

Editorial extensions

If this is right

  • Query optimizers gain a one-sided guarantee: an intermediate join can no longer be underestimated, the failure mode behind many poor plans.
  • Group-by queries receive principled estimates, because the LP objective directly targets the entropy of the group-by variables instead of ignoring the clause.
  • Cyclic queries, including graph pattern matching workloads, can be handled pessimistically without the acyclicity restriction of earlier degree-sequence bounds.
  • Every estimate comes with an explicit q-inequality and its Shannon-inequality proof, making the bound explainable rather than a black-box number.
  • The weights of a returned q-inequality stay valid when the norm values change, so bounds can be maintained under data updates without a full LP re-solve.

Reading between the lines

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

  • Beyond the paper: if the realizability premise behind tightness ever fails for some statistics, the method would still return valid upper bounds, because the statistics constraints themselves are sound; the one-sided safety guarantee would survive even if the worst-case optimality claim weakened.
  • Beyond the paper: the dual weights attached to each statistic reveal which $\ell_p$-norms are doing the work, suggesting an active-statistics strategy to collect the norms the dual prices most highly, an approach the paper does not explore.
  • Beyond the paper: the same entropy-LP formulation could in principle estimate other projection aggregates, such as the number of distinct groups, since the objective $h(V_0)$ directly prices the entropy of the projected variables rather than the full join.
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

3 major / 5 minor

Summary. The paper introduces LpBound, a pessimistic cardinality estimator that bounds the output size of multijoin queries (acyclic or cyclic, with selections and group-by) using a linear program whose constraints are Shannon inequalities and statistics constraints of the form (1/p)h(U)+h(V|U) ≤ log||deg(V|U)||_p. The authors claim that the LP optimum gives a guaranteed and tight upper bound (Theorem 3.1), that two optimized LPs (LPBerge and LPflow) achieve the same optimum as the basic LP, and that an experimental study on JOB, STATS, and subgraph-matching workloads shows orders-of-magnitude accuracy improvements over traditional estimators at practical time/space cost, with Postgres plans at least as good as those obtained from true cardinalities.

Significance. If the theoretical claims are fully established, LpBound is a significant practical contribution: it extends pessimistic cardinality estimation from SafeBound's combinatorics to information-theoretic ℓp-norm statistics, supports cyclic queries and group-by, returns explainable q-inequalities, and the two LP optimizations appear to make millisecond-scale estimation feasible. The experimental evaluation is broad and generally careful, covering multiple benchmarks, plan-quality injection, and statistics construction time. The main novelty advertised in the abstract—a guaranteed and tight bound—is exactly the part that is not verifiable from the submitted text because Theorem 3.1 is deferred to a full paper. The equivalence theorems for the optimized LPs are proved in the appendix, but those proofs themselves rely on imported results about normal polymatroids. The paper does not appear to ship code, which limits reproducibility of the experimental claims.

major comments (3)
  1. [§3.4, Theorem 3.1] Theorem 3.1 is the central correctness and tightness claim of the paper, but it is not proved in this submission: the text says only "We prove in the full paper." The upper-bound direction depends on inequality (18), imported from [1], and the tightness direction additionally requires a realizability argument: an optimal polymatroid h* of LPbase must be shown to arise from an actual database instance whose simple degree-sequence ℓp-norms exactly match the input statistics and whose query output is 2^{h*(V0)}. Appendix A proves only the equality of LPbase with LPBerge and LPflow and does not supply this realizability argument. Since the abstract and Section 3 advertise a guaranteed and tight bound, this is a load-bearing gap that must be closed in the submission.
  2. [§6.6 and Abstract] The abstract states that "Postgres derives query plans at least as good as those derived using the true cardinalities," but the supporting experiment in §6.6 is restricted to the 20 longest-running queries across JOBlight, JOBrange, and STATS. Figure 11 (right) shows that for less expensive queries the relative evaluation time of LpBound can exceed the true-cardinality baseline; the text itself acknowledges that overestimation can be detrimental for cheaper queries. The claim should either be restricted to the tested expensive queries or be supported by a full distribution of plan-quality results over all benchmark queries.
  3. [Appendix A.1, Definition A.1 and Lemma A.2] Definition A.1 defines a normal polymatroid solely by h(∅)=0 and inequality (24), but condition (24) alone does not imply monotonicity or submodularity; for example, on two variables h({1})=10, h({2})=1, h({1,2})=5 satisfies (24) yet is not monotone and cannot be entropic. The proof of Lemma A.2 uses the alternative representation of normal polymatroids as nonnegative combinations of step functions, which is not equivalent to (24) as written. The same issue affects the assertion that "every normal polymatroid is an entropic vector" and the use of that assertion in the proof of Theorem 4.1. The definition should be corrected (e.g., a polymatroid that additionally satisfies (24), or the step-function representation), and the equivalence or the needed direction should be proved.
minor comments (5)
  1. [§3.4] The text says the optimal solution of LPbase "consists of 2n values h*(U)"; since there is one variable per subset U, this should be 2^n.
  2. [§4.2] In the LPflow variable count, "There are 3n∑j|Vj| total variables" appears to be a typo; the preceding sentence suggests (n+1) variables per edge, so the stated count should be reconciled with the number of edges.
  3. [§6.6] There are minor typos: "trues cardinalities" and "JOBranges" should be "true cardinalities" and "JOBrange."
  4. [§5, Multiple Predicates] For conjunction, taking the per-p norm minimum of the individual norms is valid because the norm of the intersection degree sequence is at most each individual norm, but the informal phrase "most selective one" could be misread as choosing a predicate rather than a norm; a short clarifying sentence would help.
  5. [§3.1 and §3.4] The paper uses the term "q-inequality" without a formal definition; a one-sentence definition at first use would improve readability.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the LP bound is computed from input statistics, and the imported (18)/normal-polymatroid results are parameter-free theorems; the main risk is an omitted proof, not circular reduction.

full rationale

LpBound's bound is the optimal value of LPbase, whose objective h(V0) and constraints are the input ℓp-norm statistics plus Shannon inequalities. The upper-bound direction is self-contained: for any database satisfying the statistics, its entropy vector is feasible, so log|Q| ≤ h*(V0), and the returned q-inequality is the dual certificate, not a separately fitted prediction. The group-by handling, LPBerge/LPflow formulations, predicate support, and experimental evaluation do not reduce to the input statistics by construction. The main reliance on prior work is inequality (18) from [1] and the normal-polymatroid optimality/entropic-realizability statements used in Appendix A.1/A.2, attributed to [1] and [30]; these are parameter-free theorems rather than fitted values, so they constitute real evidence rather than circular definitions. However, Theorem 3.1's tightness proof is explicitly deferred ('We prove in the full paper' in Sec. 3.4), and the appendix does not demonstrate how an optimal normal polymatroid is realized by a concrete relation instance with the exact given ℓp-norm statistics; this is an omitted-proof and verification risk, not a circularity. The plan-quality claim is an external benchmark outcome, and the minor self-citation overlap (three of the five authors on [1], and an author on [30]) does not force the central derivation.

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

No invented physical or theoretical entities are introduced; LpBound is an algorithm and system, not a postulated entity. The free parameters listed are design choices that affect tightness and accuracy but not the validity of the upper bound. The main theorems rest on prior information-theoretic results, including one from the authors' own group, and the central theorem's proof is deferred to a full paper. Tightness is existential and asymptotic, stated as 'up to a small query-dependent constant'.

free parameters (4)
  • set of lp-norms per degree sequence = P = {1,...,10, infinity}
    The estimator keeps norms for p in 1..10 plus infinity, chosen by hand based on diminishing returns shown in Fig. 12. Accuracy claims depend on this choice.
  • number of Most Common Values (MCVs) per predicate column = up to 5000 on JOB; 15x15 on SM
    Section 5 and Fig. 13 show accuracy improves with more MCVs; the number is a tunable parameter, not theoretically fixed.
  • prefix count for large degree sequences = 4 prefixes
    Section 5 states norms are kept only for the first 4 prefixes and for the entire sequence, because degrees typically decrease exponentially.
  • histogram hierarchy for range predicates = 128 buckets per layer, layers halving bucket count
    Used in Section 5 for range-predicate support; granularity affects accuracy and space but is not part of the guarantee.
assumptions (4)
  • standard math Entropic vectors satisfy the basic Shannon inequalities; LPbase maximizes over the larger polymatroid cone, so every feasible entropic vector is included.
    Sec. 3.4 imposes monotonicity and submodularity constraints (Eqs. 8-9), making the LP optimum an upper bound on the entropy of any real database distribution.
  • domain assumption Inequality (18) from [1]: (1/p)h(U)+h(V|U) <= log ||deg_R(V|U)||_p for p in (0,infinity] and simple U.
    This is the bridge from lp-norms to entropies, stated in Sec. 3.3 and cited to the authors' prior paper [1]. It is not proved in this submission; all q-inequalities and LP statistics constraints depend on it.
  • domain assumption The statistics used are only simple degree sequences (|U| <= 1); the tightness claim in Theorem 3.1 holds only under this restriction.
    Theorem 3.1 explicitly notes that without the simple degree-sequence assumption the tightness statement no longer holds. The paper restricts to simple degree sequences throughout.
  • domain assumption Every normal polymatroid is entropic, as stated in Appendix A.1, so feasible LPBerge and LPTD solutions can be realized by some database instance.
    Used in the proofs of Theorem 4.1 and Theorem A.7, cited to [30], a survey by an author of this paper. This converts the LP optimum into a tight bound rather than merely a relaxation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of LpBound: Pessimistic Cardinality Estimation using $\ell_p$-Norms of Degree Sequences." pith.science (2026). https://pith.science/paper/2A4UM5R2

@misc{pith2026250205912,
  author       = {Pith},
  title        = {Pith review of: LpBound: Pessimistic Cardinality Estimation using $\ell_p$-Norms of Degree Sequences},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2A4UM5R2}},
  note         = {Machine review of arXiv:2502.05912}
}
abstract

Cardinality estimation is the problem of estimating the size of the output of a query, without actually evaluating the query. The cardinality estimator is a critical piece of a query optimizer, and is often the main culprit when the optimizer chooses a poor plan. This paper introduces LpBound, a pessimistic cardinality estimator for multijoin queries (acyclic or cyclic) with selection predicates and group-by clauses. LpBound computes a guaranteed upper bound on the size of the query output using simple statistics on the input relations, consisting of $\ell_p$-norms of degree sequences. The bound is the optimal solution of a linear program whose constraints encode data statistics and Shannon inequalities. We introduce two optimizations that exploit the structure of the query in order to speed up the estimation time and make LpBound practical. We experimentally evaluate LpBound against a range of traditional, pessimistic, and machine learning-based estimators on the JOB, STATS, and subgraph matching benchmarks. Our main finding is that LpBound can be orders of magnitude more accurate than traditional estimators used in mainstream open-source and commercial database systems. Yet it has comparable low estimation time and space requirements. When injected the estimates of LpBound, Postgres derives query plans at least as good as those derived using the true cardinalities.

Figures

Figures reproduced from arXiv: 2502.05912 by the authors.

Figure 2
Figure 2. Instead of storing the two degree sequences, [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Examples of Degree Sequences. Degree Sequences Fix a relation instance R, and two sets of variables X, Y ⊆ Attrs(R). The degree sequence from X to Y in R is the sequence degR(Y |X) def = (d1, d2, . . . , dN ) obtained as follows. Compute the domain of X, Dom(R.X) = {x1, . . . , xN }, denote by di = |σX=xi (ΠXY (R))| the degree (or frequency) of xi , and sort the values in the domain Dom(R.X) such that their degrees … view at source ↗
Figure 4
Figure 4. Example for LPflow. Example 4.4. Consider the 2-way join J2 in Eq. (10), along with statistics |Dom(R.X)|, ||degR(Y |X)||∞, and ||degS (Z|Y )||∞. Our target is to find coefficients w1, w2, w3 that make the following q-inequality valid and minimize the bound: |J2| ≤ |Dom(R.X)| w1 · ||degR(Y |X)||w2 ∞ · ||degS (Z|Y )||w3 ∞ (20) For that, the following needs to be a valid information inequality: h(XY Z) ≤ w1h(X) + w2h(… view at source ↗
Figures from the paper (8 more)
Figure 5
Figure 5. Figure 5: Estimation errors for JOBJoin, JOBLight, JOBRange, and STATS. For the starred ML-based [PITH_FULL_IMAGE:figures/full_fig_p018_5.png]
Figure 6
Figure 6. Figure 6: Estimation errors for STATS. For the starred ML-based estimators, we use errors reported in the [PITH_FULL_IMAGE:figures/full_fig_p018_6.png]
Figure 7
Figure 7. Figure 7: Estimation errors for the SM cyclic queries. [PITH_FULL_IMAGE:figures/full_fig_p019_7.png]
Figure 9
Figure 9. Figure 9: Improvements on estimation errors when using the two optimizations discussed in Sec. 5. Left: PK-FK [PITH_FULL_IMAGE:figures/full_fig_p020_9.png]
Figure 10
Figure 10. Figure 10: Postgres (wall-clock) evaluation time for the 20 most expensive queries in JOBlight, JOBrange, and STATS, when injected the estimates of LpBound, SafeBound, DbX, and Postgres or the trues cardinalities for all subqueries of the query. The runtimes for STATS 104, 105, …
Figure 11
Figure 11. Figure 11: Left: Overall evaluation time of all queries in a benchmark for [PITH_FULL_IMAGE:figures/full_fig_p023_11.png]
Figure 12
Figure 12. Figure 12: The amount of useful norms follows the law of diminishing returns: Plotting the division of estimation errors for the norms {1, . . . , k, ∞} and {1, . . . , 30, ∞}, averaged over the 70 JOBlight queries. 0 1000 2000 3000 4000 5000 Number x of MCVs 1.0 1.5 2.0 2.5 3.0…
Figure 14
Figure 14. Figure 14: Estimation times for LpBound on full queries of JOBjoin using LPbase and its optimizations LPflow and LPBerge. out beyond this. LPflow uses a network flow of size at most 152 and finishes in under 70 ms for each JOBjoin query. Most of its time is spent constructing th…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Quantum Information-Theoretical Size Bounds for Conjunctive Queries with Functional Dependencies

    quant-ph 2025-06 reject novelty 5.0 of 10

    Worst-case conjunctive query size bounds can be reformulated with quantum Rényi entropy, producing sound but generally non-tight upper bounds whose classical tight version is recovered only in the α→1 limit.

Reference graph

Works this paper leans on

39 extracted references · 36 canonical work pages · cited by 1 Pith paper

  1. [30]

    Applications of information inequalities to database theory problems

    Dan Suciu. Applications of information inequalities to database theory problems. InLICS, pages 1–30, 2023

    work page 2023

  2. [1]

    Join size bounds using lp-norms on degree sequences

    Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu, and Dan Suciu. Join size bounds using lp-norms on degree sequences. Proc. ACM Manag. Data, 2(2):96, 2024

    work page 2024

  3. [2]

    Ngo, and Dan Suciu

    Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. Computing join queries with functional dependencies. In PODS, pages 327–342, 2016

    work page 2016

  4. [3]

    Ngo, and Dan Suciu

    Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? InPODS, pages 429–444, 2017. Extended version available athttp://arxiv.org/abs/1612.02503

    arXiv 2017

  5. [4]

    The space complexity of approximating the frequency moments

    Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. InSTOC, pages 20–29, 1996

    work page 1996

  6. [5]

    Size bounds and query plans for relational joins.SIAM J

    Albert Atserias, Martin Grohe, and Dániel Marx. Size bounds and query plans for relational joins.SIAM J. Comput., 42(4):1737–1767, 2013

    work page 2013

  7. [6]

    Pessimistic cardinality estimation: Tighter upper bounds for intermediate join cardinalities

    Walter Cai, Magdalena Balazinska, and Dan Suciu. Pessimistic cardinality estimation: Tighter upper bounds for intermediate join cardinalities. InSIGMOD, pages 18–35, 2019

    work page 2019

  8. [7]

    Accurate summary- based cardinality estimation through the lens of cardinality estimation graphs.Proc

    Jeremy Chen, Yuqing Huang, Mushi Wang, Semih Salihoglu, and Kenneth Salem. Accurate summary- based cardinality estimation through the lens of cardinality estimation graphs.Proc. VLDB Endow., 15(8):1533–1545, 2022

    work page 2022

Show all 39 references
  1. [8]

    Cormode and K

    G. Cormode and K. Yi.Small Summaries for Big Data. Cambridge University Press, 2020

    2020

  2. [9]

    Degree sequence bound for join cardinality estimation

    Kyle Deeds, Dan Suciu, Magda Balazinska, and Walter Cai. Degree sequence bound for join cardinality estimation. In ICDT, pages 8:1–8:18, 2023

    2023

  3. [10]

    Deeds, Dan Suciu, and Magdalena Balazinska

    Kyle B. Deeds, Dan Suciu, and Magdalena Balazinska. Safebound: A practical system for generating cardinality bounds. Proc. ACM Manag. Data, 1(1):53:1–53:26, 2023

    2023

  4. [11]

    Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm

    Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. InAnalysis of Algorithms (AOFA), page 127–146, 2007

    2007

  5. [12]

    Freitag and Thomas Neumann

    Michael J. Freitag and Thomas Neumann. Every row counts: Combining sketches and sampling for accurate group-by result estimates. InCIDR, 2019

    2019

  6. [13]

    Ullman, and Jennifer Widom.Database systems - the complete book (2

    Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer Widom.Database systems - the complete book (2. ed.). Pearson Education, 2009

    2009

  7. [14]

    Size and treewidth bounds for conjunctive queries

    Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, and Paul Valiant. Size and treewidth bounds for conjunctive queries. J. ACM, 59(3):16:1–16:35, 2012. 26

    2012

  8. [15]

    Cardinality estimation in DBMS: A comprehensive benchmark evaluation.Proc

    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. Cardinality estimation in DBMS: A comprehensive benchmark evaluation.Proc. VLDB Endow., 15(4):752–765, 2021

    2021

  9. [16]

    Simplicity done right for join ordering

    Axel Hertzschuch, Claudio Hartmann, Dirk Habich, and Wolfgang Lehner. Simplicity done right for join ordering. In CIDR, 2021

    2021

  10. [17]

    Hyperloglog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm

    Stefan Heule, Marc Nunkesser, and Alexander Hall. Hyperloglog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm. InEDBT, pages 683–692, 2013

    2013

  11. [18]

    Deepdb: learn from data, not from queries!Proc

    Benjamin Hilprecht, Andreas Schmidt, Moritz Kulessa, Alejandro Molina, Kristian Kersting, and Carsten Binnig. Deepdb: learn from data, not from queries!Proc. VLDB Endow., 13(7):992–1005, 2020

    2020

  12. [19]

    Qi Huangfu and J. A. J. Hall. Parallelizing the dual revised simplex method.Math. Program. Comput., 10(1):119–142, 2018

    2018

  13. [20]

    Ngo, Kirk Pruhs, and Alireza Samadian

    Sungjin Im, Benjamin Moseley, Hung Q. Ngo, Kirk Pruhs, and Alireza Samadian. Optimizing polymatroid functions. CoRR, abs/2211.08381, 2022

    2022 arXiv

  14. [21]

    Mining approximate acyclic schemes from relations

    Batya Kenig, Pranay Mundra, Guna Prasaad, Babak Salimi, and Dan Suciu. Mining approximate acyclic schemes from relations. InSIGMOD, pages 297–312, 2020

    2020

  15. [22]

    Boncz, and Alfons Kemper

    Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. Learned cardinalities: Estimating correlated joins with deep learning. InCIDR, 2019

    2019

  16. [23]

    Narasayya, and Surajit Chaudhuri

    Kukjin Lee, Anshuman Dutt, Vivek R. Narasayya, and Surajit Chaudhuri. Analyzing the impact of cardinality estimation on execution plans in microsoft SQL server.Proc. VLDB Endow., 16(11):2871–2883, 2023

    2023

  17. [24]

    Tony T. Lee. An information-theoretic analysis of relational databases - part I: data dependencies and information metric. IEEE Trans. Software Eng., 13(10):1049–1061, 1987

    1987

  18. [25]

    Boncz, Alfons Kemper, and Thomas Neumann

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

    2015

  19. [26]

    Boncz, Alfons Kemper, and Thomas Neumann

    Viktor Leis, Bernhard Radke, Andrey Gubichev, Atanas Mirchev, Peter A. Boncz, Alfons Kemper, and Thomas Neumann. Query optimization through the looking glass, and what we found running the join order benchmark. VLDB J., 27(5):643–668, 2018

    2018

  20. [27]

    Optimizing one-time and continuous subgraph queries using worst-case optimal joins.ACM Trans

    Amine Mhedhbi, Chathura Kankanamge, and Semih Salihoglu. Optimizing one-time and continuous subgraph queries using worst-case optimal joins.ACM Trans. Datab. Syst., 46(2):6:1–6:45, 2021

    2021

  21. [28]

    Selinger, Morton M

    Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, and Thomas G. Price. Access path selection in a relational database management system. InSIGMOD, pages 23–34, 1979

    1979

  22. [29]

    Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, Agnieszka Kluska, Aitor Lewkowycz, Akshat Agarwal, Alethea Power, Alex Ray, Alex Warstadt, Alexander W

    Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R. Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, Agnieszka Kluska, Aitor Lewkowycz, Akshat Agarwal, Alethea Power, Alex Ray, Alex Warstadt, Alexander W. Kocurek, Ali...

    2023

  23. [31]

    In-memory subgraph matching: An in-depth study

    Shixuan Sun and Qiong Luo. In-memory subgraph matching: An in-depth study. InSIGMOD, pages 1083–1098, 2020

    2020

  24. [32]

    Factorjoin: A new cardinality estimation framework for join queries.Proc

    Ziniu Wu, Parimarjan Negi, Mohammad Alizadeh, Tim Kraska, and Samuel Madden. Factorjoin: A new cardinality estimation framework for join queries.Proc. ACM Manag. Data, 1(1):41:1–41:27, 2023

    2023

  25. [33]

    Bayescard: A unified bayesian framework for cardinality estimation.CoRR, abs/2012.14743, 2020

    Ziniu Wu and Amir Shaikhha. Bayescard: A unified bayesian framework for cardinality estimation.CoRR, abs/2012.14743, 2020

    2012 arXiv

  26. [34]

    Neurocard: one cardinality estimator for all tables.Proc

    Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen, and Ion Stoica. Neurocard: one cardinality estimator for all tables.Proc. VLDB Endow., 14(1):61–73, September 2020

    2020

  27. [35]

    Yeung.Information Theory and Network Coding

    Raymond W. Yeung.Information Theory and Network Coding. Springer Publishing Company, 1 edition, 2008

    2008

  28. [36]

    On characterization of entropy function via information inequalities

    Zhen Zhang and Raymond W Yeung. On characterization of entropy function via information inequalities. IEEE Trans. Inf. Theory, 44(4):1440–1452, 1998

    1998

  29. [37]

    LpBound: Pessimistic Cardinality Estimation Usingℓp-Norms of Degree Sequences

    Rong Zhu, Ziniu Wu, Yuxing Han, Kai Zeng, Andreas Pfadler, Zhengping Qian, Jingren Zhou, and Bin Cui. Flat: fast, lightweight and accurate method for cardinality estimation.Proc. VLDB Endow., 14(9):1489–1502, 2021. 29 A Supplementary Material This is extra material for the sub...

    2021

  30. [38]

    We show that we can extend it toXm

    Assuming it holds form− 1, let h′ : 2{X1,...,Xm−1}→ R be such thath′(Xi) = ai for i = 1,m− 1 and h′(X1··· Xm−1) =A. We show that we can extend it toXm. For that we first representh′ over the basis of step functions: h′ = ∑ U⊆{X1,...,Xm−1},U̸=∅ cUhU for some coefficientscU≥ 0, ...

  31. [39]

    These flow problems are over the same networkG = (Nodes,Edges), which is similar to the flow network described above forLPflow

    describes a reduction from the problem of checking whether Eq.(40) is a valid Shannon inequality to a collection of|V0| network flow problems. These flow problems are over the same networkG = (Nodes,Edges), which is similar to the flow network described above forLPflow. In par...

Pith tools

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