Storing and Indexing Multiple Tables by Interesting Orderings: For Efficient Joins, Groupings, and Updates in Relational Databases

Summary: Generalizes merged indexes into order-sharing pipelines for joins and groupings, using interesting orderings to partially precompute multi-table processing. Delivers near-materialized-view query speed while retaining traditional single-table index update performance and lower storage costs. (summarized by gpt-5.6-luna on Aug 28 2026)

Paper ID: hf90f8e03d702a56c
Venue: VLDB
Year: 2026
Pagerank: 4.9793485e-05
Overall Rank: 10,885 | 26.82%
DOI: 10.14778/3836663.3836713

Incoming Non-self Citations Over Time

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

Authors

1. Wenhui Lyu (University of Wisconsin)
2. Goetz Graefe (Google)

BibTeX Citation

@article{lyu_vldb26,
        title = {{Storing and Indexing Multiple Tables by Interesting Orderings: For Efficient Joins, Groupings, and Updates in Relational Databases}},
        author = {Lyu, Wenhui and Graefe, Goetz},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {11},
        pages = {3621--3634},
        doi = {10.14778/3836663.3836713},
        url = {https://doi.org/10.14778/3836663.3836713},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 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.0023947656
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
49	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.00043160717
379	Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources	2018	SIGMOD	0.00019514689
398	View Maintenance in a Warehousing Environment	1995	SIGMOD	0.00019152162
400	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00019129175
408	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018900199
442	Differential dataflow	2013	CIDR	0.00018210463
637	Answering Conjunctive Queries under Updates	2017	PODS	0.00015341557
724	Fundamental Techniques for Order Optimization	1996	SIGMOD	0.00014477566
812	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013729015
901	Maintenance of Data Cubes and Summary Tables in a Warehouse	1997	SIGMOD	0.00013185553
966	Incremental Organization for Data Recording and Warehousing	1997	VLDB	0.0001279879
3,112	Incremental View Maintenance with Triple Lock Factorization Benefits	2018	SIGMOD	7.6357579e-05
5,452	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB	6.1242445e-05
6,796	Intermittent Query Processing	2019	VLDB	5.6803529e-05
7,542	Foreign Keys Open the Door for Faster Incremental View Maintenance	2023	SIGMOD	5.4986181e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	951	Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates	1992	SIGMOD
2	3,595	A Combined Framework for Grouping and Order Optimization	2004	VLDB
3	1,514	Computing Joins Of Relations	1975	SIGMOD
4	13,047	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB
5	6,123	Parallel Index-based Stream Join on a Multicore CPU	2020	SIGMOD
6	11,765	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB
7	4,136	Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases	1994	VLDB
8	971	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD
9	2,136	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
10	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB