본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

Prefetch R-tree: 디스크와 CPU 캐시에 최적화된 다차원 색인 구조
Prefetch R-tree: A Disk and Cache Optimized Multidimensional Index Structure

박명선   (KT BcN본부 제어플랫폼담당 유무선통합인증개발부  );
  • 초록

    R-tree는 일반적으로 트리 노드의 크기를 디스크 페이지의 크기와 같게 함으로써 I/O 성능이 최적화 되도록 구현한다. 최근에는 주메모리 환경에서 CPU 캐시 성능을 최적화하는 R-tree의 변형이 개발되었다. 이는 노드의 크기를 캐시 라인 크기의 수 배로 하고 MBR에 저장되는 키를 압축하여 노드 하나에 더 많은 엔트리를 저장함으로써 성능을 높였다. 그러나, 디스크 최적 R-tree와 캐시 최적 R-tree의 노드 크기 사이에는 수십-수백 바이트와 수-수십 킬로바이트라는 큰 차이가 있으므로, I/O 최적 R-tree는 캐시 성능이 나쁘고 캐시 최적 R-tree는 디스크 I/O 성능이 나쁜 문제점을 가지고 있다. 이 논문에서는 CPU 캐시와 디스크 I/O에 모두 최적인 R-tree, PR-tree를 제안한다. 캐시 성능을 위해 PR-tree 노드의 크기를 캐시 라인 크기보다 크게 만든 다음 CPU의 선반입(prefetch) 명령어를 이용하여 캐시 실패 횟수를 줄이고, 트리 노드를 디스크 페이지에 낭비가 적도록 배치함으로써 디스크 I/O 성능도 향상시킨다. 또한, 이 논문에서는 PR-tree에서 검색 연산을 수행하는데 드는 캐시 실패 비용을 계산하는 분석 방법을 제시하고, 최적의 캐시와 I/O 성능을 보이는 PR-tree를 구성하기 위해, 가능한 크기의 내부 단말 노드, 중간 노드를 갖는 PR-tree 생성하여 성능을 비교하였다. PR-tree는 디스크 최적 R-tree보다 삽입 연산은 3.5에서 15.1배, 삭제 연산은 6.5에서 15.1배, 범위 질의는 1.3에서 1.9배, k-최근접 질의는 2.7에서 9.7배의 캐시 성능 향상이 있었다. 모든 실험에서 매우 작은 I/O 성능 저하만을 보였다.


    R-trees have been traditionally optimized for the I/O performance with the disk page as the tree node. Recently, researchers have proposed cache-conscious variations of R-trees optimized for the CPU cache performance in main memory environments, where the node size is several cache lines wide and more entries are packed in a node by compressing MBR keys. However, because there is a big difference between the node sizes of two types of R-trees, disk-optimized R-trees show poor cache performance while cache-optimized R-trees exhibit poor disk performance. In this paper, we propose a cache and disk optimized R-tree, called the PR-tree (Prefetching R-tree). For the cache performance, the node size of the PR-tree is wider than a cache line, and the prefetch instruction is used to reduce the number of cache misses. For the I/O performance, the nodes of the PR-tree are fitted into one disk page. We represent the detailed analysis of cache misses for range queries, and enumerate all the reasonable in-page leaf and nonleaf node sizes, and heights of in-page trees to figure out tree parameters for best cache and I/O performance. The PR-tree that we propose achieves better cache performance than the disk-optimized R-tree: a factor of 3.5-15.1 improvement for one-by-one insertions, 6.5-15.1 improvement for deletions, 1.3-1.9 improvement for range queries, and 2.7-9.7 improvement for k-nearest neighbor queries. All experimental results do not show notable declines of the I/O performance.


  • 주제어

    최적화 .   캐시 성능 .   I/O 성능 .   선반입.  

  • 참고문헌 (13)

    1. Boncz, P. A., Manegold, S. and Kersten, M. L., 'Database Architecture Optimized for the New Bottleneck: Memory Access,' In Proceedings of the 25th VLDB, pp.54-65, 1999 
    2. Rao, J. and Ross, K A., 'Cache Conscious Indexing for Decision-Support in Main Memory,' In Proceedings of 25th International Conference on Very Large Data Bases, pp.78-89, 1999 
    3. Rao, J. and Ross, K. A., 'Making B+- Trees Cache Conscious in Main Memory,' In Proceedings of the 2000 ACM SIGMOD International Conference, pp.475-486, 2000 
    4. Chen, S., Gibbons, P. B. and Mowry, T. C., 'Improving Index Performance through Prefetching,' In Proceedings of the 2001 ACM SIGMOD International Conference, pp.235-246, 2001 
    5. Chen, S., Gibbons, P. B., Mowry, T. C. and Valentin, G., 'Fractal Prefetching B+- Trees: Optimizing Both Cache and Disk Performance,' In Proceedings of the 2002 ACM SIGMOD International Conference, pp.157-168, 2002 
    6. Kim, K., Cha, S. and Kwon, K., 'Optimizing Multi-dimensional Index Trees for Main Memory Access,' In Proceedings of the 2001 ACM SIGMOD International Conference, pp.139-150, 2001 
    7. Leutenegger, S. T, Edgington, J. M. and Lopez, M. A., 'STR: A Simple and Efficient Algorithm for R-Tree Packing,' In Proceedings of the Thirteenth International Conference on Data Engineering, pp.497-506, 1997 
    8. Guttman, A., 'R-Trees: A Dynamic Index Structure for Spatial Searching,' SIGMOD'84, Proceedings of Annual Meeting, pp.47-57, 1984 
    9. Roussopoulos, N., Kelley, S. and Vincent, F., 'Nearest Neighbor Queries,' In Proceedings of the 1995 ACM SIGMOD, pp.71-79, 1995 
    10. Kamel, I. and Faloutsos, C., 'On Packing R-trees,' in Proceedings of the 1993 ACM CIKM Conference, pp.490-499, 1993 
    11. Leutenegger, S. T. and Lopez, M. A., 'The Effect of Buffering on the Performance of R-Trees,' In Proceedings of the 14th International Conference on Data Engineering, pp.164-171, 1998 
    12. Beckmann, N., Kriegel, H.-P., Schneider, R. and Seeger, B., 'The R*-Tree; An Efficient and Robust Access Method for Points and Rectangles,' In Proceedings of the 1990 ACM SIGMOD, pp.322-331, 1990 
    13. Dongarra, J., London, K., Moore, S., Mucci, P. and Terpstra, D., 'Using PAPI for Hardware Performance Monitoring on Linux Systems,' In Proceedings of the 2nd LCI International Conference on Linux Clusters: The HPC Revolution 2001 

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기