Pith. sign in

REVIEW 4 major objections 7 minor 57 references

Optimizing Queries with Many-to-Many Joins

T0 review · 4 major / 7 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read Rank ordering fails for many-to-many joins; a new cost model fixes it.

desk verdict 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. read the letter →

arxiv 2412.16323 v3 pith:BJACN6TR submitted 2024-12-20 cs.DB

Hasara Kalumin , Amol Deshpande This is my paper · ORCID
classification cs.DB
keywords many-to-manyjoinsqueryoptimizationfactorizedrepresentationcostmodeljoinorderingsemi-joinreductionbitvectorpruningrobustprocessing
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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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 / 7 minor

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.

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 (4)
  1. [Section 3.3, Eq. (1)] 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.
  2. [Sections 3.4 and 3.6] 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.
  3. [Sections 5.5 and 5.6] 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.
  4. [Section 3.5] 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.
minor comments (7)
  1. [Section 2.1, footnote 2] 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.
  2. [Section 3.3, Footnote 4] 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.
  3. [Section 3.6, Theorem 3.5] 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.
  4. [Section 3.5] There is a typo: 'previous seciton' should be 'previous section.'
  5. [Section 5.2] 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.
  6. [Section 5.5] The five synthetic queries used for cost-model validation are not identified; please list the query shapes and the parameter ranges used for each.
  7. [Figure 15] 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.

Circularity Check

2 steps flagged · score 4.0 of 10

The central cost model and experiments are independently derived, but several new formal results (robustness bounds and the COM optimal join order) are deferred to the authors' own full version, making those claims partly self-citation load-bearing.

  1. self citation load bearing [Section 3.7 (Robustness Analysis: COM), robustness bounds θ and Θ]
    "Making a similar argument, we can show that our approach further reduces the fragility to plan selection by narrowing the spread between the best and worst plan making the lower bound θ smaller. Specifically, we can show that: θ = ... where m_min is the smallest match probability. Similarly, we show that (proofs can be found in [21]): Θ = ..."

    The paper presents θ and Θ as new analytic results ('we can show'), but the Θ formula's proof is deferred to reference [21], which is the authors' own full version of this same paper (listed as 'Hasara Kalumin and Amol Deshpande. 2025. Optimizing Queries with Many-to-Many Joins'). No independent or in-text derivation is supplied. The robustness claim that the factorized approach narrows the spread between best and worst plans therefore rests on a self-citation rather than on a demonstrated proof in this manuscript. This makes the cited full version load-bearing rather than merely bibliographic.

  2. self citation load bearing [Section 3.6 (Costing and Optimization: SJ and COM+SJ), optimal COM join order]
    "For COM, the optimal join order is to sort the relations by the product of the fanouts from the root to the relation. We defer the proof to the full version of the paper."

    This optimality claim is a formal result used to justify the optimization procedure for the COM variant. The proof is not given in the present text; it is deferred to the full version, which is reference [21] by the same authors. The optimization algorithm's guarantee is thus supported by a self-citation rather than by a proof included here. The statement is not definitionally forced by the cost model as presented, so the self-citation is load-bearing for this formal claim.

full rationale

The core derivation chain is not circular in the definitional sense. Equation 1 estimates probe counts from explicit uniformity and independence assumptions (Section 3.3), and it is not fitted to the execution-time results it later predicts; the paper even footnotes that E(cY)=cE(Y) is not true in general and states the constant-fanout assumption. Theorems 3.1 and the heuristic comparisons follow from that cost model rather than being imposed as inputs. The cost-model validation in Section 5.5 is performed on synthetic data deliberately constructed to satisfy the model's independence and uniformity assumptions, which limits external validity on skewed, correlated real workloads but is not circular. The microbenchmarked weight parameters (1/2 and 1/14 in Section 5.4) are environment calibrations of probe costs, not fits of the target probe-count predictions. The main circularity concern is the repeated deferral of proofs to reference [21], the authors' own full version, for the robustness bounds in Section 3.7 and for the COM optimal-order claim in Section 3.6. These are load-bearing formal claims whose support is a self-citation, not an in-text derivation. Equation 1's derivation is also explicitly omitted ('We omit a detailed derivation of this formula due to space constraints'), which is a completeness gap rather than a circular step. Overall, the central cost model and experiments retain independent content, so a moderate score is appropriate.

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

The central claim rests mainly on the independence, uniformity, and constant-fanout assumptions used to derive the recursive survival probabilities, and on proofs that are deferred to the authors' own full version. The microbenchmarked probe weights (1/2 and 1/14) enter the simulation and cost-model validation. No speculative physical entities are introduced; the COM representation is a system component with experimental evidence inside the paper.

free parameters (2)
  • semi-join/bloomfilter probe weight = 1/2 of a hash join probe
    Set by microbenchmarking on the prototype and used in Section 5.4 simulations and Section 5.5 cost validation; it affects relative costs of BVP and SJ plans.
  • result tuple generation weight = 1/14 of a hash join probe
    Measured by microbenchmarking and used to convert COM expansion cost into probe-equivalent units; not independently derived from first principles.
assumptions (5)
  • domain assumption Queries are acyclic and plans are left-deep with a fixed driver relation.
    Stated in Section 2.1; cyclicity is deferred to spanning-tree treatment, so the optimality results do not directly generalize.
  • domain assumption Join match events are independent across operators and tuple values are uniform, so survival probabilities factor through the join tree.
    Used in Section 3.3 to derive m_T and Equation 1, and in Section 3.1 to derive m_i and fo_i from value counts.
  • ad hoc to paper For a given join operator, every matching tuple has the same fanout, or E(cY) = c E(Y) is a valid approximation.
    Footnote 4 and Section 3.3 state this; Section 5.6 tests sensitivity to fanout variance but the cost model itself uses the assumption.
  • domain assumption For Theorem 3.3, all possible bitvectors are used and pushed down as far as possible.
    Section 3.5 states the theorem relies on this, and that optimal bitvector selection is left to future work.
  • standard math Standard random sampling arguments justify the reduced match probability and fanout formulas in Theorem 3.4.
    Section 3.6 gives the formulas and says they rely on standard random sampling arguments; the proof is not shown in this text.
invented entities (1)
  • Factorized intermediate representation (COM) with count vector columns and selection vectors independent evidence
    purpose: Postpones materialization of intermediate tuples so that redundant hash table probes are avoided in left-deep plans.
    Implemented in the prototype and subjected to probe-count and runtime comparisons in Figures 10 to 16; the cost model makes falsifiable probe-count predictions even though the entity is a data structure rather than a postulated physical object.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimizing Queries with Many-to-Many Joins." pith.science (2026). https://pith.science/paper/BJACN6TR

@misc{pith2026241216323,
  author       = {Pith},
  title        = {Pith review of: Optimizing Queries with Many-to-Many Joins},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BJACN6TR}},
  note         = {Machine review of arXiv:2412.16323}
}
read the original abstract

As database query processing techniques are being used to handle diverse workloads, a key emerging challenge is how to efficiently handle multi-way join queries containing multiple many-to-many joins. While uncommon in traditional enterprise settings that have been the focus of much of the query optimization work to date, such queries are seen frequently in other contexts such as graph workloads. This has led to much work on developing join algorithms for handling cyclic queries, on compressed (factorized) representations for more efficient storage of intermediate results, and on use of semi-joins or predicate transfer to avoid generating large redundant intermediate results. In this paper, we address a core query optimization problem in this context. Specifically, we introduce an improved cost model that more accurately captures the cost of a query plan in such scenarios, and we present several optimization algorithms for query optimization that incorporate these new cost functions. We present an extensive experimental evaluation, that compares the factorized representation approach with a full semi-join reduction approach as well as to an approach that uses bitvectors to eliminate tuples early through sideways information passing. We also present new analyses of robustness of these techniques to the choice of the join order, potentially eliminating the need for more complex query optimization and selectivity estimation techniques.

Figures

Figures reproduced from arXiv: 2412.16323 by the authors.

Figure 1
Figure 1. (i) An example 6-relation query used as the running [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Yannakakis algorithm uses two semi-join passes to [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Pushing down bitvectors for early pruning [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (10 more)
Figure 5
Figure 5. Figure 5: (i) Match probabilities and fanouts for the running [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]
Figure 6
Figure 6. Figure 6: Variation of the percentage of cost difference be [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]
Figure 7
Figure 7. Figure 7: (i) Simpler running example for query execution [PITH_FULL_IMAGE:figures/full_fig_p009_7.png]
Figure 8
Figure 8. Figure 8: Partial factorized representation for query in Fig. [PITH_FULL_IMAGE:figures/full_fig_p010_8.png]
Figure 9
Figure 9. Figure 9: Final result expansion can be done in depth-first or [PITH_FULL_IMAGE:figures/full_fig_p010_9.png]
Figure 10
Figure 10. Figure 10: Comparing the join order optimization algorithms [PITH_FULL_IMAGE:figures/full_fig_p011_10.png]
Figure 11
Figure 11. Figure 11: Relative Runtime comparison for 5 different ap [PITH_FULL_IMAGE:figures/full_fig_p012_11.png]
Figure 13
Figure 13. Figure 13: Simulation Analysis 5.4 Simulation Analysis Our cost formulas can be used to analytically compare the differ￾ent approaches under a variety of settings. We illustrate one such analysis here, where we compared the performance of the tech￾niques when all the relations a…
Figure 14
Figure 14. Figure 14: Predicted costs track the actual execution times [PITH_FULL_IMAGE:figures/full_fig_p014_14.png]
Figure 15
Figure 15. Figure 15: Evaluating the impact of varying fanouts [PITH_FULL_IMAGE:figures/full_fig_p014_15.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

57 extracted references · 29 canonical work pages

  1. [21]

    Hasara Kalumin and Amol Deshpande. 2025. Optimizing Queries with Many-to- Many Joins

    work page 2025

  2. [1]

    Chignell

    Zahid Abul-Basher, Nikolay Yakovets, Parke Godfrey, Stanley Clark, and Mark H. Chignell. 2020. Answer Graph: Factorization Matters in Large Graphs. InInterna- tional Conference on Extending Database Technology . https://api.semanticscholar. org/CorpusID:226290095

    work page 2020

  3. [2]

    Swarup Acharya, Phillip B Gibbons, Viswanath Poosala, and Sridhar Ramaswamy

    work page

  4. [3]

    Hellerstein

    Ron Avnur and Joseph M. Hellerstein. 2000. Eddies: continuously adaptive query processing. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data (Dallas, Texas, USA) (SIGMOD ’00). New York, NY, USA, 261–272. https://doi.org/10.1145/342009.335420

    arXiv 2000

  5. [4]

    Shivnath Babu, Rajeev Motwani, Kamesh Munagala, Itaru Nishizawa, and Jen- nifer Widom. 2004. Adaptive ordering of pipelined stream filters. In Pro- ceedings of the 2004 ACM SIGMOD International Conference on Management of Data (Paris, France) (SIGMOD ’04) . New York, NY, USA, 407–418. https: //doi.org/10.1145/1007568.1007615 Hasara Kalumin and Amol Deshpande

    work page arXiv 2004

  6. [5]

    Shivnath Babu, Kamesh Munagala, Jennifer Widom, and Rajeev Motwani. 2005. Adaptive Caching for Continuous Queries. In 21st International Conference on Data Engineering (ICDE ’05) . IEEE Computer Society, USA, 118–129. https: //doi.org/10.1109/ICDE.2005.15

    work page doi:10.1109/icde.2005.15 2005

  7. [6]

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

    arXiv 2012

  8. [7]

    Altan Birler, Alfons Kemper, and Thomas Neumann. 2024. Robust Join Processing with Diamond Hardened Joins. Proc. VLDB Endow. 17, 11 (Aug. 2024), 3215–3228. https://doi.org/10.14778/3681954.3681995

    arXiv 2024

Show all 57 references
  1. [8]

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

    2022

  2. [9]

    Yu Chen and Ke Yi. 2017. Two-level sampling for join size estimation. InProceed- ings of the 2017 ACM International Conference on Management of Data . 759–774

    2017

  3. [10]

    Anne Condon, Amol Deshpande, Lisa Hellerstein, and Ning Wu. 2006. Flow algorithms for two pipelined filter ordering problems. In Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (Chicago, IL, USA) (PODS ’06). New York, NY, US...

    2006

  4. [11]

    Ives, and Vijayshankar Raman

    Amol Deshpande, Zachary G. Ives, and Vijayshankar Raman. 2007. Adaptive Query Processing. Found. Trends Databases 1, 1 (2007), 1–140. https://doi.org/10. 1561/1900000001

    2007

  5. [12]

    Bailu Ding, Surajit Chaudhuri, and Vivek Narasayya. 2020. Bitvector-aware Query Optimization for Decision Support Queries. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (Portland, OR, USA) (SIGMOD ’20). Association for Computing Machinery...

    2020

  6. [13]

    Xiyang Feng, Guodong Jin, Ziyi Chen, Chang Liu, and Semih Salihoğlu. 2023. Kùzu Graph Database Management System. In CIDR

    2023

  7. [14]

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

    2020 doi

  8. [15]

    Freitag, Maximilian Bandle, Tobias Schmidt, Alfons Kemper, and Thomas Neumann

    Michael J. Freitag, Maximilian Bandle, Tobias Schmidt, Alfons Kemper, and Thomas Neumann. 2020. Combining Worst-Case Optimal and Traditional Binary Join Processing. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD ’20). https://api.s...

    2020

  9. [16]

    Goetz Graefe, Ross Bunker, and Shaun Cooper. 1998. Hash Joins and Hash Teams in Microsoft SQL Server. In Proceedings of the 24rd International Conference on Very Large Data Bases (VLDB ’98) . San Francisco, CA, USA, 86–97

    1998

  10. [17]

    Paul Groß. 2024. Dynamically Exploiting Factorized Representations . Ph. D. Dissertation. Universiteit van Amsterdam

    2024

  11. [18]

    Hellerstein and Michael Stonebraker

    Joseph M. Hellerstein and Michael Stonebraker. 1993. Predicate migration: optimizing queries with expensive predicates. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (Washington, D.C., USA) (SIGMOD ’93) . New York, NY, USA, 267–276. https...

    1993

  12. [19]

    Toshihide Ibaraki and Tiko Kameda. 1984. On the optimal nesting order for computing N-relational joins. ACM Trans. Database Syst. 9, 3 (1984), 482–502. https://doi.org/10.1145/1270.1498

    1984

  13. [20]

    Muhammad Idris, Martin Ugarte, and Stijn Vansummeren. 2017. The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates. In Proceedings of the 2017 ACM International Conference on Management of Data (Chicago, Illinois, USA) (SIGMOD ’17). Association ...

    2017

  14. [22]

    Chathura Kankanamge, Siddhartha Sahu, Amine Mhedbhi, Jeremy Chen, and Semih Salihoglu. 2017. Graphflow: An Active Graph Database. In Proceedings of the 2017 ACM International Conference on Management of Data (Chicago, Illinois, USA) (SIGMOD ’17). New York, NY, USA, 1695–1698. ...

    2017

  15. [23]

    Alfons Kemper, Donald Kossmann, and Christian Wiesner. 1999. Generalised Hash Teams for Join and Group-by. In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB ’99) . San Francisco, CA, USA, 30–41

    1999

  16. [24]

    Ravi Krishnamurthy, Haran Boral, and Carlo Zaniolo. 1986. Optimization of Nonrecursive Queries. In Proceedings of the 12th International Conference on Very Large Data Bases (VLDB ’86) . San Francisco, CA, USA, 128–137

    1986

  17. [25]

    Amine Mhedhbi, Chathura Kankanamge, and Semih Salihoglu. 2021. Optimizing One-time and Continuous Subgraph Queries using Worst-case Optimal Joins. ACM Trans. Database Syst. 46, 2, Article 6 (may 2021), 45 pages. https://doi.org/ 10.1145/3446980

    2021 doi

  18. [26]

    Amine Mhedhbi, Matteo Lissandrini, Laurens Kuiper, Jack Waudby, and Gábor Szárnyas. 2021. LSQB: a large-scale subgraph query benchmark. InProceedings of the 4th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Ana...

    2021

  19. [27]

    Guido Moerkotte, Thomas Neumann, and Gabriele Steidl. 2009. Preventing bad plans by bounding the impact of cardinality estimation errors. Proceedings of the VLDB Endowment 2, 1 (2009), 982–993

    2009

  20. [28]

    Hung Quoc Ngo. 2018. Worst-Case Optimal Join Algorithms: Techniques, Re- sults, and Open Problems. Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (2018). https://api.semanticscholar. org/CorpusID:4352932

    2018

  21. [29]

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

    Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. 2018. Worst-case Optimal Join Algorithms. J. ACM 65, 3, Article 16 (2018), 40 pages. https: //doi.org/10.1145/3180143

    2018 doi

  22. [30]

    Ngo, Christopher Ré, and Atri Rudra

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

    2014

  23. [31]

    Dan Olteanu and Maximilian Schleich. 2016. Factorized Databases. SIGMOD Rec. 45, 2 (2016), 5–16. https://doi.org/10.1145/3003665.3003667

    2016

  24. [32]

    Dan Olteanu and Jakub Zavodny. 2011. Factorised Representations of Query Results. CoRR abs/1104.0867 (2011). arXiv:1104.0867 http://arxiv.org/abs/1104. 0867

    2011 arXiv

  25. [33]

    Patrick O’Neil, Elizabeth O’Neil, Xuedong Chen, and Stephen Revilak. 2009. The Star Schema Benchmark and Augmented Fact Table Indexing . Springer-Verlag, Berlin, Heidelberg, 237–252. https://doi.org/10.1007/978-3-642-10424-4_17

    2009 doi

  26. [34]

    Lambros Petrou. 2015. Single-round Vs Multi-round Distributed Query Processing in Factorized Databases. Ph. D. Dissertation. University of Oxford

    2015

  27. [35]

    Orestis Polychroniou, Arun Raghavan, and Kenneth A. Ross. 2015. Rethinking SIMD Vectorization for In-Memory Databases. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (Melbourne, Victoria, Australia) (SIGMOD ’15). New York, NY, USA, 1493–15...

    2015

  28. [36]

    Mark Raasveldt and Hannes Mühleisen. 2019. DuckDB: An Embeddable Analyti- cal Database. In Proceedings of the 2019 International Conference on Management of Data (Amsterdam, Netherlands) (SIGMOD ’19). New York, NY, USA, 1981–1984. https://doi.org/10.1145/3299869.3320212

    2019

  29. [37]

    Vijayshankar Raman, Amol Deshpande, and Joseph M Hellerstein. 2003. Using state modules for adaptive query processing. In Proceedings 19th International Conference on Data Engineering (Cat. No. 03CH37405) . IEEE, 353–364

    2003

  30. [38]

    Suzanne Rivoire, Rebecca Schultz, Tomofumi Okuda, and Christos Kozyrakis

  31. [39]

    Tamer Özsu

    Siddhartha Sahu, Amine Mhedhbi, Semih Salihoglu, Jimmy Lin, and M. Tamer Özsu. 2020. The ubiquity of large graphs and surprising challenges of graph processing: extended survey. VLDB J. 29, 2-3 (2020), 595–618. https://doi.org/10. 1007/S00778-019-00548-X

    2020

  32. [40]

    Utkarsh Srivastava, Kamesh Munagala, Jennifer Widom, and Rajeev Motwani

  33. [41]

    Steer, Dávid Szakállas, Altan Birler, Mingxi Wu, Yuchen Zhang, and Peter Boncz

    Gábor Szárnyas, Jack Waudby, Benjamin A. Steer, Dávid Szakállas, Altan Birler, Mingxi Wu, Yuchen Zhang, and Peter Boncz. 2022. The LDBC Social Network Benchmark: Business Intelligence Workload. Proc. VLDB Endow. 16, 4 (2022), 877–890. https://doi.org/10.14778/3574245.3574270

    2022

  34. [42]

    Immanuel Trummer, Junxiong Wang, Deepak Maram, Samuel Moseley, Saehan Jo, and Joseph Antonakakis. 2019. SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning. In Proceedings of the 2019 International Conference on Management of Data (Amsterdam, Netherlands) (SI...

    2019

  35. [43]

    In Very Large Data Bases Conference

    Query optimization over web services. In Very Large Data Bases Conference. https://api.semanticscholar.org/CorpusID:7020677

  36. [44]

    Nikolaos Tziavelis, Wolfgang Gatterbauer, and Mirek Riedewald. 2021. Beyond Equi-joins: Ranking, Enumeration and Factorization. Proc. VLDB Endow. 14, 11 (2021), 2599–2612. https://doi.org/10.14778/3476249.3476306

    2021

  37. [45]

    Kostas Tzoumas, Amol Deshpande, and Christian S. Jensen. 2011. Lightweight graphical models for selectivity estimation without independence assumptions. Proc. VLDB Endow. 4, 11 (Aug. 2011), 852–863. https://doi.org/10.14778/3402707. 3402724

    2011 doi

  38. [46]

    Nikolaos Tziavelis, Deepak Ajwani, Wolfgang Gatterbauer, Mirek Riedewald, and Xiaofeng Yang. 2019. Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries. Proceedings of the VLDB Endowment. International Conference on Very Large Data Bases 13 (2019), ...

    2019

  39. [47]

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

    2023 doi

  40. [48]

    Szymon Wylezo. 2012. Cost-based Query Optimisation for Factorised Relational Databases. Ph. D. Dissertation. Master’s thesis, University of Oxford

    2012

  41. [49]

    Veldhuizen

    Todd L. Veldhuizen. 2012. Leapfrog Triejoin: A Worst-case optimal join algorithm. CoRR abs/1210.0481 (2012). https://api.semanticscholar.org/CorpusID:26626787

    2012 arXiv

  42. [50]

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

    2020

  43. [51]

    Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In Very Large Data Bases Conference . https://api.semanticscholar.org/CorpusID:5438997

    1981

  44. [52]

    Yifei Yang, Matt Youill, Matthew Woicik, Yizhou Liu, Xiangyao Yu, Marco Serafini, Ashraf Aboulnaga, and Michael Stonebraker. 2021. FlexPushdownDB: hybrid pushdown and caching in a cloud DBMS. Proc. VLDB Endow. 14, 11 (July 2021), Optimizing Queries with Many-to-Many Joins 2101...

    2021

  45. [53]

    Patel, and Theodoros Rekatsinas

    Yunjia Zhang, Yannis Chronis, Jignesh M. Patel, and Theodoros Rekatsinas. 2023. Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and Analysis. Proc. VLDB Endow. 16, 11 (2023), 2962–2975. https://doi.org/10. 14778/3611479.3611501

    2023

  46. [54]

    Jianqiao Zhu, Navneet Potti, Saket Saurabh, and Jignesh M. Patel. 2017. Looking ahead makes query plans robust: making the initial case with in-memory star schema data warehouse workloads. Proc. VLDB Endow. 10, 8 (2017), 889–900. https://doi.org/10.14778/3090163.3090167

    2017

  47. [55]

    J Zavodny. 2014. Factorisation in relational databases . Ph. D. Dissertation. Uni- versity of Oxford

    2014

  48. [1999]

    In Proceedings of the 1999 ACM SIGMOD international conference on Management of data

    Join synopses for approximate query answering. In Proceedings of the 1999 ACM SIGMOD international conference on Management of data . 275–286

    1999

  49. [2006]

    In 2006 International Conference on Parallel Pro- cessing (ICPP’06)

    Vector Lane Threading. In 2006 International Conference on Parallel Pro- cessing (ICPP’06). 55–64. https://doi.org/10.1109/ICPP.2006.74

    2006 doi

Pith tools

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