Storing and Indexing Multiple Tables by an Interesting Order
Wenhui Lyu and Goetz Graefe, Feb 2025–Mar 2026
For efficient complex joins, grouping, and updates in relational databases
To appear in VLDB 2026
Condensed abstract:
Resolved the fundamental read/write trade-off in relational databases by generalizing "merged indexes" for multi-table joins and grouping operations. By embedding "interesting orderings" into the physical database design, this architecture partially pre-computes queries to maintain the update efficiency of traditional single-table indexes. This approach matches or outperforms pre-computed materialized views in query speed by up to 2x, eliminating their severe storage and update overhead.
Indexing Join Inputs for Fast Queries and Maintenance
Repo of
experiments
C++ 17, Linux, LLDB/GDB, 70k lines of addition via agentic coding
Query Execution, Indexing and Physical Database Design, KV Store
(LeanStore and
RocksDB)
Education
2022–2027 (Expected)
Computer Science, University of Wisconsin–Madison
2025–Present, PhD2022–2024, M.S. Computer Science, GPA: 3.97/4.0
Advisors: Dr. Goetz Graefe, Prof. AnHai DoanField: Database Systems
Coursework: CS764 Topics in DBMS (Top of Class), CS736 Advanced OS, CS744 Big Data Systems
B.A., Philosophy, Politics, and Economics, Peking University
Thesis: Kant's Theory of SpaceAdvisor: Prof. Zengding WuGPA: 3.81/4.0 (Top 10%)
Selected Awards: National Scholarship (Top 0.2% nationwide), Dean's List (2019, 2020, 2021)
Internship
Software Engineering Intern
Google, San Jose, CA
May–Aug 2025
Developed and benchmarked a new feature independently across 6000+ LoC for Napa, Google's internal OLAP database systems, specifically on its ingestion/write path.
Achieved up to 20× gain in ingestion speed compared to existing path by resolving resource bottlenecks and taking advantage of distributed disaggregated cloud storage (i.e., Colossus).
Enabled ingestion of high data volumes and large row sizes that was previously impossible.
Earned shareholders' approval for production transition and granted a part-time student researcher position to facilitate the process.