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.9769913e-05
Overall Rank: 10,894 | 26.78%
DOI: 10.14778/3836663.3836713
PDF: Download (CC BY-NC-ND 4.0)

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.0023943337
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061067652
49	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.0004314366
379	Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources	2018	SIGMOD	0.00019507406
398	View Maintenance in a Warehousing Environment	1995	SIGMOD	0.00019143434
400	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00019124757
408	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018894165
442	Differential dataflow	2013	CIDR	0.00018201988
637	Answering Conjunctive Queries under Updates	2017	PODS	0.00015334386
725	Fundamental Techniques for Order Optimization	1996	SIGMOD	0.00014471289
813	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013722638
901	Maintenance of Data Cubes and Summary Tables in a Warehouse	1997	SIGMOD	0.00013179526
968	Incremental Organization for Data Recording and Warehousing	1997	VLDB	0.00012793641
3,114	Incremental View Maintenance with Triple Lock Factorization Benefits	2018	SIGMOD	7.6321464e-05
5,457	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB	6.1214435e-05
6,801	Intermittent Query Processing	2019	VLDB	5.6776677e-05
7,533	Foreign Keys Open the Door for Faster Incremental View Maintenance	2023	SIGMOD	5.4991257e-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,596	A Combined Framework for Grouping and Order Optimization	2004	VLDB
3	1,514	Computing Joins Of Relations	1975	SIGMOD
4	13,053	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB
5	6,125	Parallel Index-based Stream Join on a Multicore CPU	2020	SIGMOD
6	11,771	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB
7	4,137	Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases	1994	VLDB
8	960	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD
9	2,138	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