Recent studies have addressed that the cache be havior is important in the design of main memory index structures. Cache-conscious indices such as the CSB^＋-tree are shown to outperform conventional main memory indic...Recent studies have addressed that the cache be havior is important in the design of main memory index structures. Cache-conscious indices such as the CSB^＋-tree are shown to outperform conventional main memory indices such as the AVL-tree and the T-tree. This paper proposes a cacheconscious version of the T-tree, CST-tree, defined according to the cache-conscious definition. To separate the keys within a node into two parts, the CST-tree can gain higher cache hit ratio.展开更多
The recently proposed learned index has higher query performance and space efficiency than the conventional B+-tree.However,the original learned index has the problems of insertion failure and unbounded query complexi...The recently proposed learned index has higher query performance and space efficiency than the conventional B+-tree.However,the original learned index has the problems of insertion failure and unbounded query complexity,meaning that it supports neither insertions nor bounded query complexity.Some variants of the learned index use an out-of-place strategy and a bottom-up build strategy to accelerate insertions and support bounded query complexity,but introduce additional query costs and frequent node splitting operations.Moreover,none of the existing learned indices are cache-friendly.In this paper,aiming to not only support efficient queries and insertions but also offer bounded query complexity,we propose a new learned index called COLIN(Cache-cOnscious Learned INdex).Unlike previous solutions using an out-of-place strategy,COLIN adopts an in-place approach to support insertions and reserves some empty slots in a node to optimize the node’s data placement.In particular,through model-based data placement and cache-conscious data layout,COLIN decouples the local-search boundary from the maximum error of the model.The experimental results on five workloads and three datasets show that COLIN achieves the best read/write performance among all compared indices and outperforms the second best index by 18.4%,6.2%,and 32.9%on the three datasets,respectively.展开更多
Data cube computation is an important problem in the field of data warehousing and OLAP （online analytical processing）. Although it has been studied extensively in the past, most of its algorithms are designed witho...Data cube computation is an important problem in the field of data warehousing and OLAP （online analytical processing）. Although it has been studied extensively in the past, most of its algorithms are designed without considering CPU and cache behavior. In this paper, we first propose a cache-conscious cubing approach called CC-Cubing to efficiently compute data cubes on a modern processor. This method can enhance CPU and cache performances. It adopts an integrated depth-first and breadth-first partitioning order and partitions multiple dimensions simultaneously. The partitioning scheme improves the data spatial locality and increases the utilization of cache lines. Software prefetching techniques are then applied in the sorting phase to hide the expensive cache misses associated with data scans. In addition, a cache-aware method is used in CC-Cubing to switch the sort algorithm dynamically. Our performance study shows that CC-Cubing outperforms BUC, Star-Cubing and MM-Cubing in most cases. Then, in order to fully utilize an SMT （simultaneous multithreading） processor, we present a thread-based CC-Cubing-SMT method. This parallel method provides an improvement up to 27% for the single-threaded CC-Cubing algorithm.展开更多
基金Supported bythe National High Technology of 863Project (2002AA1Z2308 ,2002AA118030)
文摘Recent studies have addressed that the cache be havior is important in the design of main memory index structures. Cache-conscious indices such as the CSB^＋-tree are shown to outperform conventional main memory indices such as the AVL-tree and the T-tree. This paper proposes a cacheconscious version of the T-tree, CST-tree, defined according to the cache-conscious definition. To separate the keys within a node into two parts, the CST-tree can gain higher cache hit ratio.
基金the National Natural Science Foundation of China under Grant No.62072419the Huawei-USTC Joint Innovation Project on Fundamental System Software。
文摘The recently proposed learned index has higher query performance and space efficiency than the conventional B+-tree.However,the original learned index has the problems of insertion failure and unbounded query complexity,meaning that it supports neither insertions nor bounded query complexity.Some variants of the learned index use an out-of-place strategy and a bottom-up build strategy to accelerate insertions and support bounded query complexity,but introduce additional query costs and frequent node splitting operations.Moreover,none of the existing learned indices are cache-friendly.In this paper,aiming to not only support efficient queries and insertions but also offer bounded query complexity,we propose a new learned index called COLIN(Cache-cOnscious Learned INdex).Unlike previous solutions using an out-of-place strategy,COLIN adopts an in-place approach to support insertions and reserves some empty slots in a node to optimize the node’s data placement.In particular,through model-based data placement and cache-conscious data layout,COLIN decouples the local-search boundary from the maximum error of the model.The experimental results on five workloads and three datasets show that COLIN achieves the best read/write performance among all compared indices and outperforms the second best index by 18.4%,6.2%,and 32.9%on the three datasets,respectively.
基金supported in part by a grant from HP Labs China,the National Natural Science Foundation of China under GrantNo.60496325the Main Memory OLAP Servers Project
文摘Data cube computation is an important problem in the field of data warehousing and OLAP （online analytical processing）. Although it has been studied extensively in the past, most of its algorithms are designed without considering CPU and cache behavior. In this paper, we first propose a cache-conscious cubing approach called CC-Cubing to efficiently compute data cubes on a modern processor. This method can enhance CPU and cache performances. It adopts an integrated depth-first and breadth-first partitioning order and partitions multiple dimensions simultaneously. The partitioning scheme improves the data spatial locality and increases the utilization of cache lines. Software prefetching techniques are then applied in the sorting phase to hide the expensive cache misses associated with data scans. In addition, a cache-aware method is used in CC-Cubing to switch the sort algorithm dynamically. Our performance study shows that CC-Cubing outperforms BUC, Star-Cubing and MM-Cubing in most cases. Then, in order to fully utilize an SMT （simultaneous multithreading） processor, we present a thread-based CC-Cubing-SMT method. This parallel method provides an improvement up to 27% for the single-threaded CC-Cubing algorithm.
