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 (Expected)
Developing a new feature independently for Napa, Google's internal OLAP database systems, specifically on its ingestion/write path.
Achieved 2–10× gain in ingestion speed compared to existing path by unlocking resource bottlenecks, taking advantage of dstributed disaggregated cloud storage (i.e., Colossus), and halving network transfer operations and volume.
Developed an end-to-end prototype and wrapping up benchmarking, all across 14 major CLs, 7 submitted and 7 drafted.
Achieving the expected outcome with 5+ weeks left in the internship, now planned for making the feature production-ready