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.0001443284
Overall Rank: 726 | 95.14%
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
259	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022881075
398	On Saying "Enough Already!" in SQL	1997	SIGMOD	0.00019117739
959	RDF-3X: a RISC-style Engine for RDF	2008	VLDB	0.00012825889
1,497	MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine	2006	SIGMOD	0.00010447125
2,132	Reusing Invariants: A New Strategy for Correlated Queries	1998	SIGMOD	8.9837489e-05
2,565	AQuery: Query Language for Ordered Data, Optimization Techniques, and Experiments	2003	VLDB	8.2689928e-05
2,700	Major Technical Advancements in Apache Hive	2014	SIGMOD	8.096888e-05
3,453	Advanced Partitioning Techniques for Massively Distributed Computation	2012	SIGMOD	7.2720027e-05
3,605	A Combined Framework for Grouping and Order Optimization	2004	VLDB	7.1534371e-05
3,793	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	6.9967739e-05
3,842	Optimization of Analytic Window Functions	2012	VLDB	6.968919e-05
3,974	Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database	1999	VLDB	6.8733375e-05
4,415	Bitvector-aware Query Optimization for Decision Support Queries	2020	SIGMOD	6.5965677e-05
4,423	Avoiding Sorting and Grouping In Processing Queries	2003	VLDB	6.5900826e-05
4,435	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.5858211e-05
4,476	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	6.5696859e-05
5,303	Fast Approximate Denial Constraint Discovery	2023	VLDB	6.1758652e-05
5,909	Pattern tree algebras: sets or sequences?	2005	VLDB	5.9342596e-05
6,177	Fundamentals of Order Dependencies	2012	VLDB	5.8432596e-05
6,439	Expressiveness and Complexity of Order Dependencies	2013	VLDB	5.7676676e-05
6,779	Guided automated learning for query workload re-optimization	2019	VLDB	5.6686556e-05
6,877	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	5.6429454e-05
7,949	Including Bloom Filters in Bottom-up Optimization	2025	SIGMOD	5.4031665e-05
9,145	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	5.2067758e-05
9,381	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	5.170504e-05
10,181	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	5.0550978e-05
10,947	Window Function Optimization: Co-Evaluation and Other Techniques	2026	VLDB	4.9605343e-05
10,955	Storing and Indexing Multiple Tables by Interesting Orderings: For Efficient Joins, Groupings, and Updates in Relational Databases	2026	VLDB	4.9605343e-05
12,709	Score-Consistent Algebraic Optimization of Full-Text Search Queries with GRAFT	2011	SIGMOD	4.9605343e-05
12,842	Ordering, Distinctness, Aggregation, Partitioning and DQP Optimization in Sybase ASE 15	2009	SIGMOD	4.9605343e-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.0023948467
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081781676
73	Including Group-By in Query Optimization	1994	VLDB	0.00037420958
109	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.00032702871
118	The EXODUS Optimizer Generator	1987	SIGMOD	0.00031320165
197	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD	0.00025558952
275	Extensible Query Processing in Starburst	1989	SIGMOD	0.000224395
322	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021032289
2,033	Practical Predicate Placement	1994	SIGMOD	9.1389597e-05

Semantically Similar Papers

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