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: hbcaa2ad48613778e
Venue: SIGMOD
Year: 1996
Pagerank: 0.00014471289
Overall Rank: 725 | 95.13%
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 30 of 30 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
272	An Overview of Query Optimization in Relational Systems	1998	PODS	0.0002251422
396	On Saying "Enough Already!" in SQL	1997	SIGMOD	0.00019153354
954	RDF-3X: a RISC-style Engine for RDF	2008	VLDB	0.00012866296
1,497	MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine	2006	SIGMOD	0.00010477876
2,115	Reusing Invariants: A New Strategy for Correlated Queries	1998	SIGMOD	9.0119103e-05
2,559	AQuery: Query Language for Ordered Data, Optimization Techniques, and Experiments	2003	VLDB	8.2963498e-05
2,689	Major Technical Advancements in Apache Hive	2014	SIGMOD	8.1227087e-05
3,440	Advanced Partitioning Techniques for Massively Distributed Computation	2012	SIGMOD	7.2954357e-05
3,596	A Combined Framework for Grouping and Order Optimization	2004	VLDB	7.1769743e-05
3,784	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	7.0197908e-05
3,834	Optimization of Analytic Window Functions	2012	VLDB	6.9910267e-05
3,958	Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database	1999	VLDB	6.8960375e-05
4,394	Bitvector-aware Query Optimization for Decision Support Queries	2020	SIGMOD	6.6182964e-05
4,403	Avoiding Sorting and Grouping In Processing Queries	2003	VLDB	6.6117633e-05
4,417	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.6064397e-05
4,467	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	6.5842379e-05
5,283	Fast Approximate Denial Constraint Discovery	2023	VLDB	6.1963542e-05
5,893	Pattern tree algebras: sets or sequences?	2005	VLDB	5.9538443e-05
6,173	Fundamentals of Order Dependencies	2012	VLDB	5.8595496e-05
6,427	Expressiveness and Complexity of Order Dependencies	2013	VLDB	5.7867997e-05
6,763	Guided automated learning for query workload re-optimization	2019	VLDB	5.6870172e-05
6,860	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	5.6615714e-05
7,936	Including Bloom Filters in Bottom-up Optimization	2025	SIGMOD	5.4210921e-05
9,355	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	5.1876576e-05
9,438	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	5.1761941e-05
10,144	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	5.0718686e-05
10,886	Window Function Optimization: Co-Evaluation and Other Techniques	2026	VLDB	4.9769913e-05
10,894	Storing and Indexing Multiple Tables by Interesting Orderings: For Efficient Joins, Groupings, and Updates in Relational Databases	2026	VLDB	4.9769913e-05
12,666	Score-Consistent Algebraic Optimization of Full-Text Search Queries with GRAFT	2011	SIGMOD	4.9769913e-05
12,799	Ordering, Distinctness, Aggregation, Partitioning and DQP Optimization in Sybase ASE 15	2009	SIGMOD	4.9769913e-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.0023943337
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081971778
73	Including Group-By in Query Optimization	1994	VLDB	0.0003750677
109	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.00032757423
118	The EXODUS Optimizer Generator	1987	SIGMOD	0.00031381726
196	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD	0.00025616489
273	Extensible Query Processing in Starburst	1989	SIGMOD	0.00022498382
321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021082176
2,035	Practical Predicate Placement	1994	SIGMOD	9.1519324e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,185	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
2	10,894	Storing and Indexing Multiple Tables by Interesting Orderings: For Efficient Joins, Groupings, and Updates in Relational Databases	2026	VLDB
3	8,046	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD
4	143	Optimization of Nonrecursive Queries	1986	VLDB
5	12,215	Improving Join Reorderability with Compensation Operators	2018	SIGMOD
6	6,173	Fundamentals of Order Dependencies	2012	VLDB
7	272	An Overview of Query Optimization in Relational Systems	1998	PODS
8	4,403	Avoiding Sorting and Grouping In Processing Queries	2003	VLDB
9	3,596	A Combined Framework for Grouping and Order Optimization	2004	VLDB
10	7,347	SQL Query Optimization: Reordering for a General Class of Queries	1996	SIGMOD