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.00013372073
Overall Rank: 862 | 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.00034470298
426	Cost-based Query Scrambling for Initial Delays	1998	SIGMOD	0.00018432573
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
792	Parametric Query Optimization	1992	VLDB	0.00013903954
1,423	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010696781
1,611	The Data Calculator*: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models	2018	SIGMOD	0.00010066379
2,241	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.7710222e-05
2,351	Extending the Search Strategy in a Query Optimizer	1991	VLDB	8.5799847e-05
2,671	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.1310287e-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
4,209	Schedule Optimization for Data Processing Flows on the Cloud	2011	SIGMOD	6.7214185e-05
4,249	Commutativity and Its Role in the Processing of Linear Recursion	1989	VLDB	6.6912366e-05
4,528	A Blackboard Architecture for Query Optimization in Object Bases	1993	VLDB	6.5456474e-05
6,095	From Auto-tuning One Size Fits All to Self-designed and Learned Data-intensive Systems	2019	SIGMOD	5.8706416e-05
6,231	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.8255825e-05
8,307	A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization	1988	VLDB	5.3423863e-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.00058816744
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.0003786983
144	Optimization of Nonrecursive Queries	1986	VLDB	0.00029092688
319	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021142713
345	R* Optimizer Validation and Performance Evaluation for Distributed Queries	1986	VLDB	0.00020445813
396	R* Optimizer Validation and Performance Evaluation for Local Queries	1986	SIGMOD	0.00019119719
407	Distributed Query Processing In A Relational Data Base System	1978	SIGMOD	0.00019003397
595	Global Query Optimization	1986	SIGMOD	0.00015791231
950	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00012888761
1,292	On the Computation of the Transitive Closure of Relational Operators	1986	VLDB	0.00011145435

Semantically Similar Papers

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