Fast, Randomized Join-Order Selection—Why Use Transformations?
Summary: Introduces transformation-free join-order optimization by uniformly sampling valid evaluation orders for acyclic queries, solving efficient unbiased generation. Cost-guided random candidate selection converges faster than iterative improvement and simulated annealing, with comparable plan quality. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. César Galindo-Legaria (Centrum Wiskunde & Informatica)
- 2. Arjan Pellenkoft (Centrum Wiskunde & Informatica)
- 3. Martin Kersten (Centrum Wiskunde & Informatica)
BibTeX Citation
@article{galindolegaria_vldb94,
title = {{Fast, Randomized Join-Order Selection—Why Use Transformations?}},
author = {Galindo-Legaria, César and Pellenkoft, Arjan and Kersten, Martin},
journal = {PVLDB},
series = {{VLDB} '94},
pages = {85--95},
year = {1994}
}Incoming Citations (Sorted by Pagerank)
Showing 7 of 7 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 796 | Rapid Bushy Join-order Optimization with Cartesian Products | 1996 | SIGMOD | 0.00013938011 |
| 954 | RDF-3X: a RISC-style Engine for RDF | 2008 | VLDB | 0.00012867202 |
| 2,026 | Scalable Join Processing on Very Large RDF Graphs | 2009 | SIGMOD | 9.1624074e-05 |
| 3,797 | Query Simplification: Graceful Degradation for Join-Order Optimization | 2009 | SIGMOD | 7.0163619e-05 |
| 3,849 | EROC: A Toolkit for Building NEATO Query Optimizers | 1996 | VLDB | 6.9810881e-05 |
| 5,543 | Charting the Design Space of Query Execution using VOILA | 2021 | VLDB | 6.0889645e-05 |
| 7,962 | Excalibur: A Virtual Machine for Adaptive Fine-grained JIT-Compiled Query Execution based on VOILA | 2023 | VLDB | 5.4167003e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 321 | Measuring the Complexity of Join Enumeration in Query Optimization | 1990 | VLDB | 0.00021088704 |
| 470 | Optimization of Large Join Queries | 1988 | SIGMOD | 0.00017755852 |
| 487 | Randomized Algorithms For Optimizing Large Join Queries | 1990 | SIGMOD | 0.00017462723 |
| 708 | Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques | 1989 | SIGMOD | 0.00014629998 |
| 725 | Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization | 1991 | SIGMOD | 0.00014465736 |
| 859 | Query Optimization by Simulated Annealing | 1987 | SIGMOD | 0.00013418999 |
| 2,626 | On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces | 1993 | VLDB | 8.2068909e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,982 | Simplicity Done Right for Join Ordering | 2021 | CIDR |
| 2 | 3,797 | Query Simplification: Graceful Degradation for Join-Order Optimization | 2009 | SIGMOD |
| 3 | 10,508 | Succinct Structure Representations for Efficient Query Optimization | 2026 | SIGMOD |
| 4 | 2,757 | Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration | 2020 | PODS |
| 5 | 795 | Random Sampling over Joins Revisited | 2018 | SIGMOD |
| 6 | 57 | On Random Sampling over Joins | 1999 | SIGMOD |
| 7 | 470 | Optimization of Large Join Queries | 1988 | SIGMOD |
| 8 | 11,068 | Towards Efficient Random-Order Enumeration for Join Queries | 2026 | VLDB |
| 9 | 8,971 | A Fast Randomized Algorithm for Multi-Objective Query Optimization | 2016 | SIGMOD |
| 10 | 487 | Randomized Algorithms For Optimizing Large Join Queries | 1990 | SIGMOD |