Asymptotically Better Query Optimization Using Indexed Algebra

Summary: Introduces Indexed Algebra — a relational-algebra representation augmented with a link/cut-tree index to enable dynamic data-flow analysis and O(log n) updates/queries, avoiding quadratic per-operator column tracking. Delivers asymptotically faster optimization with >1.8x speedups on TPC-H/TPC-DS and unbounded gains for deep plans. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13141
Venue: VLDB
Year: 2023
Pagerank: 4.1945683e-05
Overall Rank: 11,254 | 21.71%
DOI: 10.14778/3611479.3611505

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 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.0040449103
60	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00064439773
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
132	The EXODUS Optimizer Generator	1987	SIGMOD	0.00042994082
544	Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources	2018	SIGMOD	0.00020521965
586	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00019685374
659	The Making of TPC-DS	2006	VLDB	0.00018500853
735	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00017452467
849	ORDPATHs: Insert-Friendly XML Node Labels	2004	SIGMOD	0.00015962987
1,027	Accelerating XPath Location Steps	2002	SIGMOD	0.0001458865
1,263	Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation	2016	SIGMOD	0.00012982857
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
2,249	Orca: A Modular Query Optimizer Architecture for Big Data	2014	SIGMOD	9.2034693e-05
2,383	How to Architect a Query Compiler	2016	SIGMOD	8.9294108e-05
2,691	Greenplum: A Hybrid Database for Transactional and Analytical Workloads	2021	SIGMOD	8.2909126e-05
2,838	How to Architect a Query Compiler, Revisited	2018	SIGMOD	8.0408472e-05
3,702	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	6.8295759e-05
4,948	Designing an Open Framework for Query Optimization and Compilation	2022	VLDB	5.8116879e-05
7,816	1,000 Tables Under the From	2009	VLDB	4.6437215e-05
9,414	TreeToaster: Towards an IVM-Optimized Compiler	2021	SIGMOD	4.3441378e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,860	Optimization of Queries with User-defined Predicates	1996	VLDB	7.9934503e-05
6,554	Rule-Based Translation of Relational Queries into Iterative Programs	1986	SIGMOD	5.0155947e-05
1,702	An Architecture For Query Optimization	1982	SIGMOD	0.0001085438
7,693	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB	4.6759281e-05
5,299	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB	5.5796719e-05
6,374	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.0927058e-05
5,727	Enabling Incremental Query Re-Optimization	2016	SIGMOD	5.3510544e-05
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022734812
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00041510555
8,347	QPPT: Query Processing on Prefix Trees	2013	CIDR	4.5410746e-05