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

vldb26-3039 · Regular Research · Wenhui Lyu, Goetz Graefe
Abstract

Relational database systems often face a trade-off between supporting multi-table queries and frequent updates. Materialized join views can drastically speed up queries, but they slow down updates and may consume significant storage. Conversely, query-time joins over tables and their indexes optimizes update performance at the cost of query latency. Our recent study of two-table joins introduced “merged indexes” (a form of multi-table index) to break this trade-off, approaching the query performance of materialized views without sacrificing the update efficiency of traditional single-table indexes. This study generalizes this technique to “order-sharing pipelines”—multi-table joins and grouping operations on shared keys. By incorporating interesting orderings into the physical database design, merged indexes partially pre-compute these order-sharing pipelines, closely approaching the query performance of materialized views. Meanwhile, they match traditional indexes on update performance.

Assigned reviewers

No reviewers assigned yet.

Candidates from the panel ranked by taxonomy affinity

#ReviewerMatchLoadWhy