Fundamental Techniques for Order Optimization

Summary: Proposes order optimization push down sorts in joins, reduce sorting columns, and avoid sorts via predicates, keys, or indexes. Defines core operations using predicates, uniqueness, and functional dependencies; weighs hash- vs. order-based plans. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2933
Venue: SIGMOD
Year: 1996
Pagerank: 0.00014411295
Overall Rank: 744 | 94.90%
DOI: 10.1145/233269.233320

Incoming Non-self Citations Over Time

Authors

1. David Simmen (IBM)
2. Eugene Shekita (IBM)
3. Timothy Malkemus (IBM)

BibTeX Citation

@inproceedings{simmen_sigmod96,
        title = {{Fundamental Techniques for Order Optimization}},
        author = {Simmen, David and Shekita, Eugene and Malkemus, Timothy},
        series = {{SIGMOD} '96},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/233269.233320},
        url = {https://dl.acm.org/doi/10.1145/233269.233320},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
290	An Overview of Query Optimization in Relational Systems	1998	PODS	0.0002227038
380	On Saying "Enough Already!" in SQL	1997	SIGMOD	0.00019563191
944	RDF-3X: a RISC-style Engine for RDF	2008	VLDB	0.00013067088
1,460	MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine	2006	SIGMOD	0.00010710674
2,093	Reusing Invariants: A New Strategy for Correlated Queries	1998	SIGMOD	9.1831198e-05
2,507	AQuery: Query Language for Ordered Data, Optimization Techniques, and Experiments	2003	VLDB	8.4889096e-05
2,706	Major Technical Advancements in Apache Hive	2014	SIGMOD	8.2287564e-05
3,466	Advanced Partitioning Techniques for Massively Distributed Computation	2012	SIGMOD	7.3909785e-05
3,538	A Combined Framework for Grouping and Order Optimization	2004	VLDB	7.3287689e-05
3,706	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	7.1819534e-05
3,928	Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database	1999	VLDB	7.0115196e-05
4,020	Optimization of Analytic Window Functions	2012	VLDB	6.9513881e-05
4,346	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.7510183e-05
4,347	Avoiding Sorting and Grouping In Processing Queries	2003	VLDB	6.7509984e-05
4,454	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	6.6929626e-05
4,849	Bitvector-aware Query Optimization for Decision Support Queries	2020	SIGMOD	6.4803828e-05
5,772	Pattern tree algebras: sets or sequences?	2005	VLDB	6.0930389e-05
6,114	Fundamentals of Order Dependencies	2012	VLDB	5.9713126e-05
6,720	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	5.794237e-05
6,930	Expressiveness and Complexity of Order Dependencies	2013	VLDB	5.7367175e-05
6,938	Guided automated learning for query workload re-optimization	2019	VLDB	5.733869e-05
7,982	Fast Approximate Denial Constraint Discovery	2023	VLDB	5.5138609e-05
9,172	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	5.3092396e-05
9,279	Including Bloom Filters in Bottom-up Optimization	2025	SIGMOD	5.2934632e-05
9,333	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	5.2887551e-05
10,106	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	5.1435736e-05
12,369	Score-Consistent Algebraic Optimization of Full-Text Search Queries with GRAFT	2011	SIGMOD	5.093636e-05
12,503	Ordering, Distinctness, Aggregation, Partitioning and DQP Optimization in Sybase ASE 15	2009	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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.0024089429
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00083340894
71	Including Group-By in Query Optimization	1994	VLDB	0.00038021159
110	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.0003309592
119	The EXODUS Optimizer Generator	1987	SIGMOD	0.0003183602
192	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD	0.00026028406
268	Extensible Query Processing in Starburst	1989	SIGMOD	0.00022788687
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
2,005	Practical Predicate Placement	1994	SIGMOD	9.3203144e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,959	Simplicity Done Right for Join Ordering	2021	CIDR
2	1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
3	7,882	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD
4	143	Optimization of Nonrecursive Queries	1986	VLDB
5	11,909	Improving Join Reorderability with Compensation Operators	2018	SIGMOD
6	6,114	Fundamentals of Order Dependencies	2012	VLDB
7	290	An Overview of Query Optimization in Relational Systems	1998	PODS
8	4,347	Avoiding Sorting and Grouping In Processing Queries	2003	VLDB
9	3,538	A Combined Framework for Grouping and Order Optimization	2004	VLDB
10	7,272	SQL Query Optimization: Reordering for a General Class of Queries	1996	SIGMOD