A hybrid page layout integrating PAX and NSM

[摘要] Prior work on in-page record formats has contrasted the "N-ary storage model" (NSM) and the "partition attributes across" (PAX) format. The former is the traditional standard page layout whereas the latter "exhibits superior cache and memory bandwidth utilization" [ADH 01], e.g., in data warehouse queries with large scans. Unfortunately, space management within each page is more complex due to the mini-pages in the PAX layout. "Borrowing" space from one mini- page for another requires moving an entire mini-page. In contrast, the NSM format simply grows a slot array and the data space from opposite ends of the page until all space is occupied. The present paper explores a hybrid page layout (HPL) that aims to combine the advantages of NSM and PAX. Predicate evaluation in large scan queries have the same number of cache faults as PAX, and space management uses two data areas growing towards each other. Moreover, the design defines a continuum between NSM and PAX in order to support both efficient scans and efficient insertions and updates. This design is equally applicable to cache lines within RAM memory (the original design goal of PAX) and to small pages on flash storage within large disk pages. Our experimental evaluation is based on an implementation in the former environment. It demonstrates that the HPL design scans almost as fast as the scan-optimized PAX layout and updates almost as fast as the update- optimized NSM layout, i.e., it is competitive with both in their best use cases. 12 PagesExternal Posting Date: December 6, 2012 [Fulltext].Approved for External PublicationInternal Posting Date: December 6, 2012 [Fulltext]

[发布机构] HP Development Company

[学科分类] 计算机科学（综合）

[关键词] database;storage manager;PAX;NSM;Hybrid Page Layout (HPL);page layout