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: 13142
Venue: VLDB
Year: 2023
Pagerank: 4.1905499e-05
Overall Rank: 11,256 | 21.78%
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.0040465394
59	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.0006445664
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482
134	The EXODUS Optimizer Generator	1987	SIGMOD	0.00043070028
542	Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources	2018	SIGMOD	0.00020522627
585	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00019682634
659	The Making of TPC-DS	2006	VLDB	0.00018514913
729	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00017448059
843	ORDPATHs: Insert-Friendly XML Node Labels	2004	SIGMOD	0.00015975516
1,028	Accelerating XPath Location Steps	2002	SIGMOD	0.00014578947
1,260	Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation	2016	SIGMOD	0.00012990853
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
2,247	Orca: A Modular Query Optimizer Architecture for Big Data	2014	SIGMOD	9.201975e-05
2,383	How to Architect a Query Compiler	2016	SIGMOD	8.9198524e-05
2,693	Greenplum: A Hybrid Database for Transactional and Analytical Workloads	2021	SIGMOD	8.2845883e-05
2,843	How to Architect a Query Compiler, Revisited	2018	SIGMOD	8.0334687e-05
3,706	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	6.8232992e-05
4,952	Designing an Open Framework for Query Optimization and Compilation	2022	VLDB	5.806142e-05
7,822	1,000 Tables Under the From	2009	VLDB	4.6392682e-05
9,420	TreeToaster: Towards an IVM-Optimized Compiler	2021	SIGMOD	4.3399748e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,867	Optimization of Queries with User-defined Predicates	1996	VLDB	7.9931252e-05
6,550	Rule-Based Translation of Relational Queries into Iterative Programs	1986	SIGMOD	5.0113524e-05
1,700	An Architecture For Query Optimization	1982	SIGMOD	0.00010842044
7,693	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB	4.6714423e-05
5,285	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB	5.583298e-05
6,372	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.0878306e-05
5,737	Enabling Incremental Query Re-Optimization	2016	SIGMOD	5.3459609e-05
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022796106
144	Optimization of Nonrecursive Queries	1986	VLDB	0.00041430126
8,342	QPPT: Query Processing on Prefix Trees	2013	CIDR	4.5367151e-05