{"id":"947f133d-c78c-48a1-ae3b-fa604e2b8c8b","arxiv_id":"2412.16323","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A cost model that splits join selectivity into match probability and fanout, and counts redundant probes, makes join-order optimization for many-to-many joins more accurate and more robust.","lead":"Database queries that join tables in many-to-many ways can waste time probing the same hash tables over and over. This paper introduces a cost model that counts those redundant probes, plus optimization algorithms and a prototype showing orders-of-magnitude speedups for graph-style join workloads.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Cost model Eq. 1 depends on per-key constant fanout and independent branch survival; §5.6 tests only fanout variance and §5.5 validates only on synthetic data engineered to satisfy the assumptions, so the probe-count formula is unvalidated on skewed, correlated real-world data.","rationale":"The reader identified the same load-bearing assumption: the cost model assumes tuple-level uniformity and independence, and Section 5.5 validates only on synthetic data engineered to satisfy those properties. I agree that this is the central concern. The theoretical counterexample in Theorem 3.1 is unaffected by the assumption—it relies on the cost function itself—but the empirical claims of orders-of-magnitude speedups and the practical robustness conclusions depend on Eq. 1 being a good predictor on real workloads. The paper's Section 5.6 addresses only the constant-fanout dimension and shows insensitivity to fanout variance; it does not address independence of matching events across branches, which is a distinct and more serious threat to the survival-probability recursion. Because this concern is real but not fatal to the theoretical contribution, and because the missing artifacts and deferred proofs noted by the reader also prevent full verification, CONDITIONAL remains the right verdict. The paper should supply a validation on skewed/correlated data or explicitly scope the cost model's guarantees to the independence/uniformity regime.","tokens_in":29199,"tokens_out":1760,"duration_ms":15158,"concrete_test":"Run a controlled experiment on a real or realistically skewed dataset (e.g., a social graph or RDF dataset with power-law degree distributions) where match events across branches are correlated. For a fixed join tree, materialize all matches and count the actual number of probes per driver key under COM execution, then compare with Eq. 1 predictions across several join orders. If predicted probe counts deviate by more than a constant factor, or if the predicted best order is not the actual best order on more than a small fraction of queries, the cost model's independence/uniformity assumption is violated in practice.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim—that rank ordering is no longer optimal and COM variants yield orders-of-magnitude speedups—rests on Eq. 1, which estimates probes into R_l as N times the fanout product along the path times branch survival probabilities m_T. This formula is the expected probe count only if (a) for each join key, every matching tuple has the same fanout, and (b) match events across different branches are independent, so that m_T = m_T_r * (1 - (1 - m_T1...m_Tk)^{fo_T_r}) is valid. The paper itself footnotes that E(cY)=cE(Y) is not true in general (Footnote 4) and states that Eq. 1 assumes 'any tuple either doesn't match or has exactly the same fanout.' Section 5.5 deliberately uses synthetic data that satisfies independence and uniformity, so it does not stress the model where it is fragile. Section 5.6 varies only the fanout distribution and keeps the query shape fixed; it does not induce correlated match events across branches or key-dependent fanout, which are precisely the cases where the survival-probability recursion and the fanout multiplication can break down. If Eq. 1 misestimates probe counts on skewed real data, then Theorem 3.1 still holds abstractly, but the headline experimental claims and the practical optimality of the survival-probability greedy heuristic lose empirical support for the very workloads (graph, social, RDF) that motivate the paper.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies join-order optimization for acyclic multi-way join queries containing many-to-many joins. The authors argue that when redundant probes are avoided through a factorized intermediate representation (COM), optionally combined with bitvector-based pruning (BVP) or full semi-join reduction (SJ), the standard rank-ordering cost model is no longer adequate. They propose a cost model that separates join selectivity into match probability (m_i) and fanout (fo_i), and estimate the number of hash-table probes into each operator under COM, BVP, and SJ, together with COM variants. They state that the COM cost function does not satisfy the adjacent-sequence-interchange property, present a dynamic-programming optimal algorithm and greedy heuristics (selectivity, expected tuple count, survival probability), and report a vectorized prototype implementation with extensive experiments on synthetic and CE-benchmark data, including comparisons of the six technique combinations and a robustness analysis. The main claims are that rank ordering can be orders of magnitude worse than the proposed heuristics, that COM-based execution avoids redundant probes and yields large speedups, and that the approach makes query plans more robust to join-order choice.","tokens_in":29495,"tokens_out":7768,"duration_ms":67599,"significance":"If the cost model and the stated theorems hold, the paper makes a useful contribution to query optimization for graph and analytic workloads: it formalizes a cost distinction that is often blurred, it gives a practical factorized execution representation with count and selection vectors, and it provides an extensive comparison of COM, BVP, and SJ variants in a real vectorized engine. The prototype implementation and the experimental study are assets, as is the attempt to connect cost modeling to robustness. However, the paper's central analytical claims are not fully self-contained: the key probe-count formula is asserted without derivation, several theorems are stated without proof or deferred to the authors' own full version, and the experimental validation is largely performed on data that satisfies the model's uniformity/independence assumptions. The significance of the work is therefore real but conditional on supplying the missing derivations and on demonstrating that the cost model remains adequate under skew and correlation.","major_comments":[{"comment":"Equation (1) is the load-bearing assertion of the paper: it is used for Theorem 3.1, for the greedy heuristics, and for all experimental cost comparisons. Yet the text says 'We omit a detailed derivation of this formula due to space constraints' and states only that it is the expected number of probes assuming 'any tuple either doesn't match or has exactly the same fanout.' The formula also depends on the recursive survival-probability definition m_T = m_T_r * (1 - (1 - m_T1...m_Tk)^{fo_T_r}), which requires independence of match events across branches, and on the approximation flagged in Footnote 4. Because these assumptions are load-bearing, the paper needs a rigorous derivation of Eq. (1) from precisely stated assumptions, including the distributional model that justifies treating branch survival probabilities as multiplicative factors. The running example for R5 is not obviously an instance of the literal text of Eq. (1), since R5's ancestors in the join tree are not the previously joined R2 and R3; the relation between 'ancestors' in the formula and 'previously evaluated joins' in a left-deep plan needs to be clarified as part of the derivation.","section":"Section 3.3, Eq. (1)"},{"comment":"Several central analytical results are asserted without proof or deferred to reference [21], which appears to be the authors' own full version. In particular, Theorem 3.2 (each greedy heuristic can be arbitrarily worse than optimal) is stated with only an informal explanation; Theorem 3.4 (adjusted match probabilities and fanouts after semi-join reduction) and Theorem 3.5 (order independence of the COM cost in the second phase) are stated without proof; and the proof that the optimal COM join order is obtained by sorting on the product of fanouts is deferred to [21]. Since [21] is not part of the submitted manuscript, these results cannot be verified from the text. The authors should include complete proofs or a precise, accessible pointer, and ensure that no circularity arises from citing their own full version for the main theorems.","section":"Sections 3.4 and 3.6"},{"comment":"The experimental validation does not yet stress the cost model where it is most fragile. Section 5.5 states that the synthetic data was generated to 'ensure the independence and uniformity properties,' so the strong agreement in Figure 14 is expected under the model's assumptions and cannot detect violations of them. Section 5.6 varies only the fanout distribution for a fixed 3-2 snowflake query and does not introduce key-dependent fanout, correlated match events across branches, or skewed key distributions, which are precisely the cases where the m_T recursion and the fanout product in Eq. (1) can break down. The CE-benchmark experiments in Section 5.3 compare execution times but do not directly validate predicted probe counts against observed probes on real data. To support the paper's motivating claim of robustness for graph, social, and RDF workloads, the authors should validate Eq. (1) on real or realistically skewed/correlated datasets by comparing predicted and observed probe counts, and ideally by measuring plan-quality degradation under such conditions.","section":"Sections 5.5 and 5.6"},{"comment":"The costing and optimization claims for the BVP and COM+BVP variants are introduced with formulas that are not derived. In particular, the separation of bitvector probes from hash-table probes, the treatment of false positives through (m_i + epsilon), and the claim that the principle of optimality holds when all possible bitvectors are pushed down require a formal derivation rather than the assertion 'we can show that.' The authors do acknowledge that Theorem 3.3 fails when only a subset of bitvectors is used, but since BVP+COM is a headline experimental configuration, the cost formulas and the linear-in-n optimization claim need to be established with the same rigor as the COM analysis.","section":"Section 3.5"}],"minor_comments":[{"comment":"The note that this class of plans is 'sometimes called right-deep' is confusing, since left-deep and right-deep plans are normally distinct; the intended meaning should be clarified or the note removed.","section":"Section 2.1, footnote 2"},{"comment":"The notation E(cY) = cE(Y) is not well-formed as written: if c is a constant the equality is trivially true, but the text says it is 'not true in general,' which implies c is a random variable. Please use explicit notation for the fanout random variable and state the assumption used.","section":"Section 3.3, Footnote 4"},{"comment":"The theorem refers to the 'third phase,' but the preceding paragraph describes a two-phase implementation; align the terminology so that the phase being referenced is unambiguous.","section":"Section 3.6, Theorem 3.5"},{"comment":"There is a typo: 'previous seciton' should be 'previous section.'","section":"Section 3.5"},{"comment":"The text says the experiments use driver relation sizes 10^4, 10^5, and 10^6, but Figure 11 shows only panels for 10^4 and 10^5; either add the missing panel or correct the text.","section":"Section 5.2"},{"comment":"The five synthetic queries used for cost-model validation are not identified; please list the query shapes and the parameter ranges used for each.","section":"Section 5.5"},{"comment":"The legend contains the misspelling 'exponetial,' and the axes of the two panels would benefit from explicit descriptions of the distributions being varied and of how the relative probe ratio is computed.","section":"Figure 15"}],"recommendation":"major_revision","confidential_remarks":"The paper has a solid practical direction and a substantial prototype, but the self-deferral to reference [21] for core proofs is a concern for a standalone submission. If the full version is publicly available, the authors should cite it explicitly with an identifier; otherwise they should include the missing derivations and proofs in this manuscript. The experimental validation should also be extended to data that violates the uniformity/independence assumptions, since the current Section 5.5 validates the model only under its own assumptions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth reading: the real contribution here is a cost model that separates match probability from fanout and charges for redundant probes in left-deep plans, plus the demonstration that rank ordering stops being optimal once you do that. Theorem 3.1's counterexample is short and convincing. The experimental campaign is also unusually thorough: six execution variants, a vectorized C++ prototype, synthetic and CE benchmark comparisons, probe counts and wall-clock time, and a separate robustness analysis. The authors know the surrounding literature, and the comparison with FDB and GraphflowDB is concrete rather than hand-wavy.\n\nThe soft spots are real but not disqualifying. The central probe-count formula, Eq. (1), is stated without derivation. Footnote 4 admits the E(cY)=cE(Y) simplification, and the formula depends on constant per-key fanout and independent branch survival. Section 5.5 validates the model only on synthetic data engineered to satisfy exactly those assumptions. Section 5.6 tests fanout skew and shows the estimate degrades gracefully—that is some evidence—but it does not test correlated match events across branches or key-dependent fanout, which is the regime the graph/RDF motivating workloads live in. So the optimality claims and the near-optimality of the survival-probability heuristic are not yet demonstrated on the data that matters most.\n\nThe other issue is completeness: Theorem 3.2 is asserted without proof, and Theorems 3.4, 3.5, and the COM ordering proof are deferred to reference [21], the paper's own full version. For a standalone submission that is a genuine gap. The authors should prove them or make the full version available and point to specific sections. No code or data artifacts are released either, which limits independent verification.\n\nBottom line: a credible, useful paper with a central idea that probably holds, but not accept-shaped yet. The missing derivation and deferred proofs need to be supplied, and the cost model needs at least one experiment on real data with correlations and skew. If those are addressed, it deserves publication. I would send it to reviewers.","headline":"A useful cost model for many-to-many joins with an honest experimental campaign, but the central formula is underived and key proofs lean on a self-cited full version.","tokens_in":30050,"tokens_out":3731,"would_cite":true,"duration_ms":35309,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Rank ordering fails for many-to-many joins; a new cost model fixes it.","keywords":["many-to-many joins","query optimization","factorized representation","cost model","join ordering","semi-join reduction","bitvector pruning","robust query processing"],"falsifier":"Take a real or deliberately skewed dataset with heavy key skew and correlated join attributes, run the paper's factorized plan over many join orders, and compare the number of hash-table probes actually observed with the count predicted by Equation (1); a systematic gap that grows with skew, or a join order that the survival-probability heuristic ranks poorly but that actually runs faster, would falsify the model. The paper's own validation (Section 5.5) uses only synthetic data constructed to satisfy the independence and uniformity assumptions, so this experiment remains open.","tokens_in":28927,"feed_emoji":"⚡","tokens_out":5843,"duration_ms":49106,"temperature":0.7,"pith_summary":"The paper confronts a common but under-modeled situation: multi-way join queries in which a single driver tuple fans out through several many-to-many joins, generating many intermediate tuples that all share the same join key. A standard left-deep plan probes the hash table once per intermediate tuple, even though one probe per distinct key would suffice. The paper argues that this redundant-probe effect defeats the classical rank-ordering rule for choosing join order, and develops a cost model that separates match probability from fanout and counts only the necessary probes. With that model, the paper gives optimal and heuristic join-order algorithms and shows experimentally that avoiding redundant probes makes execution orders of magnitude faster and much less sensitive to join-order or selectivity-estimation errors.","feed_headline":"Many-to-many joins break the classic join-order rule","feed_subtitle":"Counting probes instead of tuples makes such queries orders of magnitude faster and less sensitive to estimation errors.","key_machinery":"The load-bearing object is the probe-count cost model, built on a split of each join operator's selectivity into match probability $m_i$ (the probability an input tuple finds a match) and fanout $fo_i$ (the average number of matches given a match). For a connected subtree $T$ rooted at $T_r$ with children $T_1,\\dots,T_k$, the survival probability is $m_T = m_{T_r} \\times (1 - (1 - m_{T_1} m_{T_2} \\cdots m_{T_k})^{fo_{T_r}})$, and Equation (1) estimates probes into a later operator as $N$ times the fanouts along the root-to-operator path times the side-branch survival probabilities. This model carries the paper's three theoretical results (failure of adjacent-sequence interchange, optimality for bitvector pruning, and order independence for semi-join reduction combined with factorization) and drives the dynamic program and greedy optimizers. It is a model rather than an implementation detail: its recursive survival formula assumes each matching tuple has the same fanout and that matching events at different joins are independent.","core_discovery":"The central claim is that the cost of a left-deep pipelined plan for acyclic queries with many-to-many joins should be counted as a product of fanouts along the path from the driver to each operator, multiplied by survival probabilities of side branches, rather than as the usual product of selectivities. Equation (1) states that the estimated number of probes into operator $R_l$ is $N$ times the fanouts of the ancestors along the path times the survival probabilities $m_{T_i}$ of each already-evaluated side subtree. Because fanouts along the path multiply while branches contribute only survival probabilities, the classical rank-ordering / adjacent-sequence-interchange property fails (Theorem 3.1), and the paper instead proposes an exhaustive dynamic program plus greedy heuristics, among which a survival-probability greedy is near-optimal in experiments. For bitvector-based pruning with a fixed driver, the principle of optimality does hold (Theorem 3.3), and for two-pass semi-join full reduction the paper gives a polynomial-time optimizer and shows that with factorized representation the final join phase's cost is independent of join order (Theorem 3.5). The paper reports orders-of-magnitude speedups for the factorized (COM) variants over standard execution on synthetic and benchmark workloads, and reduced fragility of plan quality to estimation errors.","pith_inferences":["If the model holds, query optimizers for graph and analytical workloads could replace selectivity-based rank ordering with survival-probability-style heuristics and rely less on expensive cardinality estimation; the same probe-counting logic applies to expensive predicates and external API calls, where each probe carries a real monetary or latency cost.","The uniformity and independence assumption is the main risk: on real data with skewed keys or correlated join attributes, Equation (1)'s multiplicative survival formula may under- or over-count probes, so the optimality ordering and fragility conclusions could shift; a natural test is to run the same experiments on skewed and correlated datasets rather than only on synthetic data constructed to sa","The framework points toward treating the choice among standard, factorized, bitvector, and semi-join variants as a cost-based decision, using the same model to pick both the execution technique and the join order for a given query."],"forward_implications":["For left-deep plans over acyclic queries, the classical rank-ordering rule can choose plans that are orders of magnitude worse than the optimal order when fanouts are high; the paper's survival-probability greedy heuristic nearly matches the exhaustive optimal algorithm across the tested parameter ranges.","Avoiding redundant probes through a factorized representation can reduce wall-clock time by orders of magnitude compared with standard execution, even when the final output must be flattened, and it also cuts memory use.","Bitvector-based early pruning and two-pass semi-join full reduction are not competitive by themselves, but combining them with factorized execution (BVP+COM and SJ+COM) usually gives the best performance.","With a fixed driver relation, using all possible pushed-down bitvectors preserves the principle of optimality for left-deep plans, so optimization cost grows linearly in the number of possible drivers rather than exponentially.","The cost model makes plan quality less fragile: the deviation bound depends on match probabilities rather than on selectivities, so large estimation errors hurt much less for many-to-many workloads."],"supporting_citations":[{"why":"Supplies the rank-ordering algorithm and adjacent-sequence-interchange property that this paper shows fails under the new cost model.","marker":"[19]"},{"why":"Introduces the fragility framework and the star-query bound that the paper refines to match probabilities.","marker":"[54]"},{"why":"The bitvector-aware optimization work whose principle-of-optimality claim Theorem 3.3 corrects for fixed-driver left-deep plans.","marker":"[12]"},{"why":"Defines the factorized representations (f-trees and d-trees) that the paper's COM representation is equivalent to.","marker":"[6]"},{"why":"Implements factorized execution in a graph database engine, serving as a key comparison point for the paper's prototype design.","marker":"[22]"},{"why":"Provides the Yannakakis-style two-pass semi-join full reduction that the SJ variants implement and optimize.","marker":"[20]"},{"why":"The vectorized hash-join engine whose execution design the paper's prototype adapts and extends.","marker":"[36]"},{"why":"Supplies the benchmark and query workloads used in the experimental evaluation of the approaches.","marker":"[7]"}],"fun_headline_variants":["Fanout product beats selectivity for many-to-many joins","Counting probes: new cost model for many-to-many joins","Join order matters less: new optimizer for many-to-many queries","Survival probabilities: optimizing many-to-many joins","Rethink join costs: fanout-based optimizer for graph workloads"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole cost model rests on the assumption that tuples are uniform and independent: every tuple that matches a join has the same fanout, and matching at one join says nothing about matching at another; if real data is skewed or correlated, the probe counts, optimal orderings, and fragility claims built on the model may not hold.","fun_headline_variants_meta":{"raw":{"variants":["Fanout product beats selectivity for many-to-many joins","Counting probes: new cost model for many-to-many joins","Join order matters less: new optimizer for many-to-many queries","Survival probabilities: optimizing many-to-many joins","Rethink join costs: fanout-based optimizer for graph workloads"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000822,"raw_usage":{"total_tokens":3637,"prompt_tokens":1025,"completion_tokens":2612,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":641,"completion_tokens_details":{"reasoning_tokens":2541}},"tokens_in":641,"tokens_out":2612,"duration_ms":17287,"temperature":1.0,"reasoning_tokens":2541,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T10:41:56.214747+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a real or deliberately skewed dataset with heavy key skew and correlated join attributes, run the paper's factorized plan over many join orders, and compare the number of hash-table probes actually observed with the count predicted by Equation (1); a systematic gap that grows with skew, or a join order that the survival-probability heuristic ranks poorly but that actually runs faster, would falsify the model. The paper's own validation (Section 5.5) uses only synthetic data constructed to satisfy the independence and uniformity assumptions, so this experiment remains open.","supporting_citations":[],"review_version":1}