Scholarlink

<p>Real-world DBMS workloads invariably exhibit skewed access patterns, where a small number of "hot" records are accessed much more frequently than the remaining "cold" records. Page-oriented data structures, such as B+trees, dynamic hash tables, heap files, and LSM-tree, are sub-optimal in terms of memory utilization under skewed access conditions. Hot records might be co-located with cold ones on pages in the data structure. Caching those lukewarm pages in the buffer pool lowers memory utilization due to the mismatch of caching granularity (page) and access granularity (record), leading to sub-optimal performance. Recently, the <span>2-Tree</span> approach was proposed to improve caching efficiency for B+trees using record-level migration. In this paper, we generalize the <span>2-Tree</span> approach to <span>Tiered-Indexing</span> that can be applied to common buffer-managed data structures to efficiently handle skew using record migration. Using this architecture, we extend hash tables, heap files, and LSM-trees with I/O-efficient record migration. Moreover, we design a general mechanism to ensure data structure consistency for <span>Tiered-Indexing</span> data structures during record migration using optimistic lock coupling. Compared to traditional <span>1-Tier</span> and state-of-the-art record-caching designs, we observe significant throughput and memory utilization improvement across B+tree, hash table, heap file, and LSM-tree under skewed workloads.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Tiered-Indexing: Optimizing Access Methods for Skew

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年5月24日

查看全文
  • Xinjing Zhou,
  • Xiangpeng Hao,
  • Xiangyao Yu,
  • Michael Stonebraker

摘要

Real-world DBMS workloads invariably exhibit skewed access patterns, where a small number of "hot" records are accessed much more frequently than the remaining "cold" records. Page-oriented data structures, such as B+trees, dynamic hash tables, heap files, and LSM-tree, are sub-optimal in terms of memory utilization under skewed access conditions. Hot records might be co-located with cold ones on pages in the data structure. Caching those lukewarm pages in the buffer pool lowers memory utilization due to the mismatch of caching granularity (page) and access granularity (record), leading to sub-optimal performance. Recently, the 2-Tree approach was proposed to improve caching efficiency for B+trees using record-level migration. In this paper, we generalize the 2-Tree approach to Tiered-Indexing that can be applied to common buffer-managed data structures to efficiently handle skew using record migration. Using this architecture, we extend hash tables, heap files, and LSM-trees with I/O-efficient record migration. Moreover, we design a general mechanism to ensure data structure consistency for Tiered-Indexing data structures during record migration using optimistic lock coupling. Compared to traditional 1-Tier and state-of-the-art record-caching designs, we observe significant throughput and memory utilization improvement across B+tree, hash table, heap file, and LSM-tree under skewed workloads.