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: 13329
Venue: VLDB
Year: 2023
Pagerank: 5.093636e-05
Overall Rank: 11,453 | 21.43%
DOI: 10.14778/3611479.3611505

Incoming Non-self Citations Over Time

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

Authors

1. Philipp Fent (Technical University of Munich)
2. Guido Moerkotte (University of Mannheim)
3. Thomas Neumann (Technical University of Munich)

BibTeX Citation

@article{fent_vldb23,
        title = {{Asymptotically Better Query Optimization Using Indexed Algebra}},
        author = {Fent, Philipp and Moerkotte, Guido and Neumann, Thomas},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {11},
        pages = {3018--3030},
        doi = {10.14778/3611479.3611505},
        url = {https://doi.org/10.14778/3611479.3611505},
        year = {2023}
}

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.0024089429
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
23	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00054886415
119	The EXODUS Optimizer Generator	1987	SIGMOD	0.0003183602
422	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00018732744
438	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018471721
445	Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources	2018	SIGMOD	0.00018336751
476	The Making of TPC-DS	2006	VLDB	0.00017860667
719	ORDPATHs: Insert-Friendly XML Node Labels	2004	SIGMOD	0.00014637695
893	Accelerating XPath Location Steps	2002	SIGMOD	0.00013374715
941	Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation	2016	SIGMOD	0.00013078348
1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011320736
1,621	Orca: A Modular Query Optimizer Architecture for Big Data	2014	SIGMOD	0.00010203114
1,797	How to Architect a Query Compiler	2016	SIGMOD	9.7368925e-05
1,948	Greenplum: A Hybrid Database for Transactional and Analytical Workloads	2021	SIGMOD	9.432395e-05
2,488	How to Architect a Query Compiler, Revisited	2018	SIGMOD	8.5091578e-05
3,215	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	7.6324234e-05
4,215	Designing an Open Framework for Query Optimization and Compilation	2022	VLDB	6.8275676e-05
7,671	1,000 Tables Under the From	2009	VLDB	5.5708452e-05
9,565	TreeToaster: Towards an IVM-Optimized Compiler	2021	SIGMOD	5.2528121e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,137	Rule-Based Translation of Relational Queries into Iterative Programs	1986	SIGMOD
2	2,512	An Architecture For Query Optimization	1982	SIGMOD
3	7,842	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB
4	5,164	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB
5	6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
6	5,552	Enabling Incremental Query Re-Optimization	2016	SIGMOD
7	290	An Overview of Query Optimization in Relational Systems	1998	PODS
8	143	Optimization of Nonrecursive Queries	1986	VLDB
9	8,625	QPPT: Query Processing on Prefix Trees	2013	CIDR
10	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD