[CS] Jun Hyuk Chang MS PresentationJun 9, 2025

[via cs]

This is an announcement of Jun Hyuk Chang's MS Presentation
===============================================
Candidate: Jun Hyuk Chang

Date: Monday, June 09, 2025

Time:  2:30 pm CST

Location: JCL 298

Title: Multi-Version Hash Table

Abstract: Hash tables are essential and frequently used data structures in database systems, particularly for hash joins and aggregation operations. Typically, a hash table is built once and discarded after the query execution. However, many database workloads repeatedly execute similar or identical joins, suggesting potential for significant performance improvements if hash tables could be reused across multiple queries. In this research, we propose the Multi-Version Hash Table (MVHT), a novel data structure designed to leverage multi-version concurrency control (MVCC) semantics, enabling the reuse and sharing of hash tables across queries executed at different snapshot timestamps. MVHT extends traditional ephemeral hash tables by maintaining versioned records organized either by linear version chains, dual chains (recent vs. historical), or timestamp-based partitioning. This design allows concurrent access from multiple queries, including long-lived analytical queries and incremental view maintenance (IVM) workloads. We investigate various design choices for MVHT, including different structural organizations, repair strategies for version chains, and garbage collection (GC) policies. Our evaluation considers diverse workloads to analyze under which scenarios MVHT significantly improves query performance and memory utilization compared to traditional approaches. This research leaves several key questions regarding optimal MVHT structures, repair timing (eager versus lazy), and the most effective GC strategies open, highlighting promising directions for future exploration.

Advisors: Aaron Elmore

Committee Members: Aaron Elmore, Raul Castro Fernandez, Michael Franklin