Query Optimization by Simulated Annealing

Summary: Proposes a simulated-annealing optimizer to navigate large, complex query plan spaces. Answers are represented in the semiring of linear relational operators, with a state space built from algebraic equivalents; experiments show near-optimal plans and suboptimality of traditional strategies like semi-naive evaluation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h331dc15577ecfbd2
Venue: SIGMOD
Year: 1987
Pagerank: 0.00013418999
Overall Rank: 859 | 94.23%
DOI: 10.1145/38713.38722

Incoming Non-self Citations Over Time

Authors

1. Yannis E. Ioannidis (University of California Berkeley; University of Wisconsin)
2. Eugene Wong (University of California Berkeley)

BibTeX Citation

@inproceedings{ioannidis_sigmod87,
        title = {{Query Optimization by Simulated Annealing}},
        author = {Ioannidis, Yannis E. and Wong, Eugene},
        series = {{SIGMOD} '87},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/38713.38722},
        url = {https://dl.acm.org/doi/10.1145/38713.38722},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
94	Efficient and Effective Clustering Methods for Spatial Data Mining	1994	VLDB	0.00034579889
424	Cost-based Query Scrambling for Initial Delays	1998	SIGMOD	0.0001848836
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
792	Parametric Query Optimization	1992	VLDB	0.00013942753
1,416	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010734049
1,605	The Data Calculator*: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models	2018	SIGMOD	0.00010093796
2,226	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.8033052e-05
2,339	Extending the Search Strategy in a Query Optimizer	1991	VLDB	8.6118503e-05
2,660	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.1611913e-05
3,005	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS	7.7621043e-05
3,042	Fast, Randomized Join-Order Selection—Why Use Transformations?	1994	VLDB	7.7213044e-05
4,188	Schedule Optimization for Data Processing Flows on the Cloud	2011	SIGMOD	6.7464862e-05
4,228	Commutativity and Its Role in the Processing of Linear Recursion	1989	VLDB	6.7165815e-05
4,510	A Blackboard Architecture for Query Optimization in Object Bases	1993	VLDB	6.5696737e-05
6,080	From Auto-tuning One Size Fits All to Self-designed and Learned Data-intensive Systems	2019	SIGMOD	5.8924903e-05
6,216	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.847583e-05
8,284	A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization	1988	VLDB	5.3626342e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038009523
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00029179719
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021220438
344	R* Optimizer Validation and Performance Evaluation for Distributed Queries	1986	VLDB	0.00020461727
397	R* Optimizer Validation and Performance Evaluation for Local Queries	1986	SIGMOD	0.00019157058
405	Distributed Query Processing In A Relational Data Base System	1978	SIGMOD	0.00019065801
592	Global Query Optimization	1986	SIGMOD	0.00015841026
946	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00012936921
1,287	On the Computation of the Transitive Closure of Relational Operators	1986	VLDB	0.00011184757

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	869	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD
2	1,257	Sampling-Based Query Re-Optimization	2016	SIGMOD
3	9,288	A General Framework for Modeling and Processing Optimization Queries	2007	VLDB
4	470	Optimization of Large Join Queries	1988	SIGMOD
5	7,261	Rule-Based Translation of Relational Queries into Iterative Programs	1986	SIGMOD
6	3,214	Efficient and Provable Multi-Query Optimization	2017	PODS
7	487	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD
8	272	An Overview of Query Optimization in Relational Systems	1998	PODS
9	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
10	143	Optimization of Nonrecursive Queries	1986	VLDB