{"id":"dadeedf7-3bd4-4ab6-8e9e-191ae4e2c6c6","arxiv_id":"2502.05912","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"LpBound computes a guaranteed, tight upper bound on multijoin output cardinality by solving a linear program over lp-norm degree statistics and Shannon inequalities.","lead":"This paper introduces LpBound, a component for database query optimizers that computes a guaranteed upper bound on the number of rows a multi-table query can return, using per-column statistics called degree-sequence norms. It can be thousands of times more accurate than the estimators in Postgres, DuckDB, and a commercial system, and it also handles group-by and cyclic queries.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.1's tightness claim is not proved in this submission and rests on an unverified normal-polymatroid optimality result from prior work; a brute-force small-domain comparison can settle it.","rationale":"The reader's weakest_assumption names precisely the same load-bearing point: Theorem 3.1 is not proved in this submission, and the tightness and LP-equivalence results rely on inequality (18) and on normal-polymatroid realizability. My reading confirms that this is the single most important risk. The experimental evaluation is strong and the system is plausibly practical, but the headline guarantee of a tight pessimistic bound cannot be accepted on faith from a 'full paper' citation. A concrete brute-force check on a tiny domain would settle whether the tightness claim is true at least in the small cases; if it fails there, the theoretical foundation is wrong, not merely unproved. Other concerns, such as the plan-quality claim being verified on only 20 queries or the lack of released code, are real but secondary: they affect the strength of the empirical claims, not the correctness of the core method. I therefore keep the reader's CONDITIONAL verdict unchanged rather than moving to ACCEPT or REJECT. No ad hominem is intended; the concern is about an unproven and potentially false mathematical assertion, not about the authors' integrity.","tokens_in":33057,"tokens_out":17601,"duration_ms":170656,"concrete_test":"Enumerate all relation instances over a small fixed domain (e.g., attributes taking values in {1,2,3}) for a small cyclic query such as the 3-clique C3 from Eq. (3), using only simple degree-sequence ℓp-norms (p=1,2,∞) as statistics. For each statistic vector, compute the true maximum output size over all instances that satisfy exactly those norms, and compare it with the LPbase bound from Section 3.4 solved with the same statistics and the stated Shannon constraints. If the LP bound exceeds the enumerated true maximum by more than the query-dependent constant allowed in Theorem 3.1 for any instance, the tightness claim is falsified. As a secondary check, verify whether the LP optimum produced by the solver satisfies the normal-polymatroid inequalities (24) from Appendix A.1; if the optimal value is not attained at a normal solution, the paper's route to tightness collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that LpBound returns a tight upper bound: every database satisfying the statistics has output size at most the returned bound, and some database achieves it up to a small constant. This is Theorem 3.1, but Section 3.4 says only 'We prove in the full paper' and gives no proof here. The tightness argument depends on two imported results: inequality (18) from the authors' prior paper [1], and the assertion in Appendix A.1 that 'LPbase has an optimal solution h* that is a normal polymatroid', together with 'it is known that every normal polymatroid is an entropic vector'. Even if every normal polymatroid is entropic in the abstract sense, the paper does not show how to convert that entropy vector into a concrete relation instance whose degree-sequence ℓp-norms exactly match the input statistics, while making the query output as large as 2^{h*(V0)}. This matters because the novelty of LpBound over SafeBound is precisely the tightness guarantee: if the optimal polymatroid for LPbase is not realizable by a database with the given statistics, the returned bound may still be a valid upper bound but it is not tight, and Theorems 4.1 and 4.5 (equivalence of LPBerge and LPflow with LPbase) would also lack a sound basis. The experimental plan-quality results do not test this theoretical property, so the risk is not mitigated by the strong accuracy numbers. This is a load-bearing gap because the abstract and Section 3 advertise a guaranteed and tight bound, and the entire pessimistic-estimation value proposition depends on it.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":33379,"tokens_out":17697,"duration_ms":180583,"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":[{"comment":"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.","section":"§3.4, Theorem 3.1"},{"comment":"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.","section":"§6.6 and Abstract"},{"comment":"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.","section":"Appendix A.1, Definition A.1 and Lemma A.2"}],"minor_comments":[{"comment":"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.","section":"§3.4"},{"comment":"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.","section":"§4.2"},{"comment":"There are minor typos: \"trues cardinalities\" and \"JOBranges\" should be \"true cardinalities\" and \"JOBrange.\"","section":"§6.6"},{"comment":"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.","section":"§5, Multiple Predicates"},{"comment":"The paper uses the term \"q-inequality\" without a formal definition; a one-sentence definition at first use would improve readability.","section":"§3.1 and §3.4"}],"recommendation":"major_revision","confidential_remarks":"The central theorem is deferred, and two of the key ingredients—inequality (18) from [1] and the normal-polymatroid facts from [30]—are from works by the same authors. This is not itself a defect, but combined with the missing proof of Theorem 3.1 it makes the current submission unverifiable. The editor may want to require the full proof in the revision, and to ask the authors to qualify the plan-quality claim in the abstract."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth reading. LpBound takes the information-theoretic bound from your own prior theory paper and turns it into a working estimator: LP solving over entropy constraints, group-by and predicate support, and two optimizations that bring estimation down to milliseconds. The experimental work is the real contribution here. On JOB, STATS, and subgraph matching, LpBound is orders of magnitude more accurate than Postgres/DuckDB and mostly beats SafeBound, while staying fast enough for a query optimizer. That is a solid engineering result, and the paper is honest about the cases where learned estimators do better.\n\nThe soft spot is exactly where the stress-test note points. Theorem 3.1, which states that the bound is tight up to a constant, is not proved in this submission. Section 3.4 just says \"we prove in the full paper.\" The appendix proves Theorems 4.1 and 4.5, and it leans on the claim that every normal polymatroid is an entropic vector, citing [30]. The gap is that being an entropic vector is not the same as being realizable by a concrete relation whose degree-sequence ℓp-norms exactly match the input statistics. The paper does not show how to convert that entropy vector into such a relation. Without that step, the tightness claim is unsupported, and the equivalence theorems lose their foundation. This is not a manufactured issue; the tightness guarantee is what the abstract advertises and what separates LpBound from SafeBound.\n\nThat said, the upper-bound direction probably survives even if tightness fails. For any actual database, its entropy vector satisfies the LP constraints, so the optimal LP value is an upper bound on log output size. The practical value of LpBound as a guaranteed-overestimate estimator does not depend on the tightness direction. I would not reject the paper over this, but the authors need to either provide the proof or clearly state which parts of the claimed guarantees are conditional.\n\nMinor points: no code is released, which makes the reproducibility of the experiments hard to judge. The \"plans at least as good as true cardinalities\" claim is based on 20 queries, and while Figure 10 shows large wins on expensive queries, Figure 11 shows pessimistic estimates can hurt cheaper queries. The claim is a bit broader than the evidence.\n\nYes, send it to serious referees. Ask them to focus on Theorem 3.1 and the normal-polymatroid realizability. A brute-force check on small domains would settle the tightness question cheaply. This is the kind of systems paper that deserves a fair technical review, and the missing proof is addressable.","headline":"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.","tokens_in":33949,"tokens_out":2223,"would_cite":true,"duration_ms":26848,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P15","94A17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["cardinality estimation","pessimistic cardinality estimation","degree sequences","ℓ_p-norms","linear programming","Shannon inequalities","query optimization","group-by queries"],"falsifier":"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.","tokens_in":32837,"feed_emoji":"📊","tokens_out":9722,"duration_ms":92748,"temperature":0.7,"pith_summary":"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.","feed_headline":"Guaranteed query-size upper bound beats traditional estimators","feed_subtitle":"A linear program over ℓ_p-norms gives query plans as good as true cardinalities, in milliseconds.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It supplies inequality (18), the entropy-to-norm bridge from which every q-inequality in LpBound is derived.","marker":"[1]"},{"why":"It establishes the AGM bound, the cardinality-only baseline that LpBound generalizes.","marker":"[5]"},{"why":"It introduces the max-degree bound and the Shannon-inequality framework that LpBound extends to general $\\ell_p$-norms.","marker":"[3]"},{"why":"It describes SafeBound, the prior pessimistic estimator using degree sequences, which LpBound extends and compares against.","marker":"[10]"},{"why":"It provides the network-flow characterization of Shannon inequalities that LPflow builds on.","marker":"[20]"},{"why":"It is cited for the normal-polymatroid results underpinning the tightness and LP-equivalence proofs.","marker":"[30]"},{"why":"It supplies the elemental basic Shannon inequalities used to reduce LPbase's constraint set.","marker":"[35]"},{"why":"It provides the benchmarked error numbers for learned estimators that the paper uses as experimental comparisons.","marker":"[15]"},{"why":"It supplies the JOB workload and Postgres configuration used in the evaluation.","marker":"[26]"}],"fun_headline_variants":["ℓ_p-norm bound beats traditional query estimators","Guaranteed upper bound on query size, in milliseconds","Simple norms yield query plans as good as true cardinalities","Pessimistic estimator outperforms traditional ones in accuracy","LpBound: tight query-size bound from degree-sequence norms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["ℓ_p-norm bound beats traditional query estimators","Guaranteed upper bound on query size, in milliseconds","Simple norms yield query plans as good as true cardinalities","Pessimistic estimator outperforms traditional ones in accuracy","LpBound: tight query-size bound from degree-sequence norms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001067,"raw_usage":{"total_tokens":4499,"prompt_tokens":1002,"completion_tokens":3497,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":618,"completion_tokens_details":{"reasoning_tokens":3417}},"tokens_in":618,"tokens_out":3497,"duration_ms":25160,"temperature":1.0,"reasoning_tokens":3417,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T17:25:39.758547+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Join size bounds using lp-norms on degree sequences","cited_arxiv_id":null,"evidence_quote":"It supplies inequality (18), the entropy-to-norm bridge from which every q-inequality in LpBound is derived."},{"cited_title":"Size bounds and query plans for relational joins.SIAM J","cited_arxiv_id":null,"evidence_quote":"It establishes the AGM bound, the cardinality-only baseline that LpBound generalizes."},{"cited_title":"Deeds, Dan Suciu, and Magdalena Balazinska","cited_arxiv_id":null,"evidence_quote":"It describes SafeBound, the prior pessimistic estimator using degree sequences, which LpBound extends and compares against."},{"cited_title":"Optimizing Polymatroid Functions","cited_arxiv_id":"2211.08381","evidence_quote":"It provides the network-flow characterization of Shannon inequalities that LPflow builds on."},{"cited_title":"Applications of information inequalities to database theory problems","cited_arxiv_id":null,"evidence_quote":"It is cited for the normal-polymatroid results underpinning the tightness and LP-equivalence proofs."},{"cited_title":"Yeung.Information Theory and Network Coding","cited_arxiv_id":null,"evidence_quote":"It supplies the elemental basic Shannon inequalities used to reduce LPbase's constraint set."},{"cited_title":"Cardinality estimation in DBMS: A comprehensive benchmark evaluation.Proc","cited_arxiv_id":null,"evidence_quote":"It provides the benchmarked error numbers for learned estimators that the paper uses as experimental comparisons."},{"cited_title":"Boncz, Alfons Kemper, and Thomas Neumann","cited_arxiv_id":null,"evidence_quote":"It supplies the JOB workload and Postgres configuration used in the evaluation."}],"review_version":1}