DBScholar

Back to papers

Randomized Algorithms For Optimizing Large Join Queries

Summary: Randomized search strategies (SA, II) optimize large project–select–join queries. Two-Phase Optimization (SA+II) improves quality and runtime; SA more often yields lower-cost plans, explained by a cup-shaped cost landscape with a shallow bottom. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h06025d77344b8469
Venue
SIGMOD
Year
1990
Pagerank
0.00017402488
Overall Rank
489 | 96.73%
DOI
10.1145/93597.98740

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{ioannidis_sigmod90,
        title = {{RANDOMIZED ALGORITHMS FOR OPTIMIZING LARGE JOIN QUERIES}},
        author = {Ioannidis, Yannis E. and Kang, Younkyung Cha},
        series = {{SIGMOD} '90},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/93597.98740},
        url = {https://dl.acm.org/doi/10.1145/93597.98740},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 36 of 36 citing papers.

Rank Citing Paper Year Venue Pagerank
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047654188
73 Including Group-By in Query Optimization 1994 VLDB 0.00037420958
94 Efficient and Effective Clustering Methods for Spatial Data Mining 1994 VLDB 0.00034470298
426 Cost-based Query Scrambling for Initial Delays 1998 SIGMOD 0.00018432573
728 Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization 1991 SIGMOD 0.0001441771
792 Parametric Query Optimization 1992 VLDB 0.00013903954
1,124 Least Expected Cost Query Optimization: An Exercise in Utility 1999 PODS 0.00011898749
2,151 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB 8.9483042e-05
2,351 Extending the Search Strategy in a Query Optimizer 1991 VLDB 8.5799847e-05
2,397 Performance Tradeoffs for Client-Server Query Processing 1996 SIGMOD 8.5108976e-05
2,521 Optimization of Queries with User-defined Predicates 1996 VLDB 8.3339593e-05
2,888 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.8895201e-05
3,009 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.7439468e-05
3,051 Fast, Randomized Join-Order Selection—Why Use Transformations? 1994 VLDB 7.6933177e-05
3,144 Solving the Join Ordering Problem via Mixed Integer Linear Programming 2017 SIGMOD 7.5846375e-05
3,785 Parallelizing Query Optimization 2008 VLDB 7.0012696e-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
4,394 Lifting the Burden of History from Adaptive Query Processing 2004 VLDB 6.6084598e-05
4,640 Join Query Optimization Techniques for Complex Event Processing Applications 2018 VLDB 6.4742349e-05
4,708 Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams 2004 SIGMOD 6.4419838e-05
4,954 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.3263552e-05
5,032 Reducing Multidatabase Query Response Time By Tree Balancing 1995 SIGMOD 6.2942678e-05
5,446 Efficient Massively Parallel Join Optimization for Large Queries* 2022 SIGMOD 6.1117489e-05
5,549 A Cost Model for Clustered Object-Oriented Databases 1995 VLDB 6.071306e-05
5,810 Network-Aware Query Processing for Stream-based Applications 2004 VLDB 5.9703192e-05
5,926 Quantum-Inspired Digital Annealing for Join Ordering 2024 VLDB 5.9282142e-05
6,063 Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs 2009 SIGMOD 5.8826785e-05
6,231 Window Query-Optimal Clustering of Spatial Objects 1995 PODS 5.8255825e-05
6,989 Efficient Evaluation of Queries in a Mediator for WebSources 2002 SIGMOD 5.6106442e-05
8,167 Optimization of Object-Oriented Recursive Queries using Cost-Controlled Strategies 1992 SIGMOD 5.3707278e-05
8,594 The Fittest Survives: An Adaptive Approach to Query Optimization 1995 VLDB 5.2933942e-05
8,677 Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation 2026 VLDB 5.2745941e-05
8,999 A Fast Randomized Algorithm for Multi-Objective Query Optimization 2016 SIGMOD 5.2270052e-05
9,656 Parallelizing Query Optimization on Shared-Nothing Architectures 2016 VLDB 5.1303051e-05
12,916 Optimization of Multi-Domain Queries on the Web 2008 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
1 Access Path Selection in a Relational Database Management System 1979 SIGMOD 0.0023948467
144 Optimization of Nonrecursive Queries 1986 VLDB 0.00029092688
197 Grammar-like Functional Rules for Representing Query Optimization Alternatives 1988 SIGMOD 0.00025558952
470 Optimization of Large Join Queries 1988 SIGMOD 0.00017699145
714 Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques 1989 SIGMOD 0.00014578551
862 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00013372073
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,712 Rank-aware Query Optimization 2004 SIGMOD
2 2,602 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB
3 144 Optimization of Nonrecursive Queries 1986 VLDB
4 1,603 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB
5 862 Query Optimization by Simulated Annealing 1987 SIGMOD
6 1,185 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD
7 8,999 A Fast Randomized Algorithm for Multi-Objective Query Optimization 2016 SIGMOD
8 3,051 Fast, Randomized Join-Order Selection—Why Use Transformations? 1994 VLDB
9 714 Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques 1989 SIGMOD
10 470 Optimization of Large Join Queries 1988 SIGMOD