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 |
|---|---|---|---|---|
| 794 | Rapid Bushy Join-order Optimization with Cartesian Products | 1996 | SIGMOD | 0.0001389694 |
| 959 | RDF-3X: a RISC-style Engine for RDF | 2008 | VLDB | 0.00012825889 |
| 2,041 | Scalable Join Processing on Very Large RDF Graphs | 2009 | SIGMOD | 9.1287048e-05 |
| 3,807 | Query Simplification: Graceful Degradation for Join-Order Optimization | 2009 | SIGMOD | 6.9902343e-05 |
| 3,857 | EROC: A Toolkit for Building NEATO Query Optimizers | 1996 | VLDB | 6.9553827e-05 |
| 5,564 | Charting the Design Space of Query Execution using VOILA | 2021 | VLDB | 6.0660209e-05 |
| 7,983 | Excalibur: A Virtual Machine for Adaptive Fine-grained JIT-Compiled Query Execution based on VOILA | 2023 | VLDB | 5.3962907e-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 |
|---|---|---|---|---|
| 322 | Measuring the Complexity of Join Enumeration in Query Optimization | 1990 | VLDB | 0.00021032289 |
| 470 | Optimization of Large Join Queries | 1988 | SIGMOD | 0.00017699145 |
| 489 | Randomized Algorithms For Optimizing Large Join Queries | 1990 | SIGMOD | 0.00017402488 |
| 714 | Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques | 1989 | SIGMOD | 0.00014578551 |
| 728 | Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization | 1991 | SIGMOD | 0.0001441771 |
| 862 | Query Optimization by Simulated Annealing | 1987 | SIGMOD | 0.00013372073 |
| 2,630 | On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces | 1993 | VLDB | 8.1828876e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,995 | Simplicity Done Right for Join Ordering | 2021 | CIDR |
| 2 | 10,585 | Succinct Structure Representations for Efficient Query Optimization | 2026 | SIGMOD |
| 3 | 3,807 | Query Simplification: Graceful Degradation for Join-Order Optimization | 2009 | SIGMOD |
| 4 | 2,766 | Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration | 2020 | PODS |
| 5 | 793 | 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,138 | Towards Efficient Random-Order Enumeration for Join Queries | 2026 | VLDB |
| 9 | 8,999 | A Fast Randomized Algorithm for Multi-Objective Query Optimization | 2016 | SIGMOD |
| 10 | 489 | Randomized Algorithms For Optimizing Large Join Queries | 1990 | SIGMOD |