基于Hilbert R树的空间连接算法Cache性能分析

Cache Performance Analysis of Spatial Join Algorithm Based on Hilbert R-tree

随着处理器和内存之间的性能差异日益增大,高速缓存被用来弥补这个差距,对于空间数据库操作来说,性能优化目标也从磁盘/内存层次转移到了内存/Cache层次。空间连接是空间数据库中最重要的操作之一,其执行效率直接影响空间查询的性能,但大多数传统的空间连接没有考虑Cache的利用。针对空间连接算法Cache使用的问题,分析了程序局部性对Cache利用的影响,对基于Hilbert R树的空间连接在内存中的性能进行了测试,比较了不同索引结点大小对空间连接性能和Cache访问性能的影响,为优化Cache敏感的空间连接提供了实验依据。

As the diversity of performance between processor and memory getting larger and larger, Cache is ued to make up the growing gap. The purpose of the performance optimization has been transferred from the disk/memory level to the memory/Cache level for operations in spatial databases. Spatial Join algorithm is one of the most important operations in spatial databases and its efficiency has a direct influence on the performance of the spatial queries. However, most of the traditional spatial join algorithms haven＇t taken enough consideration in the utilization of Cache. Focusing on the utilization of Cache in spatial join algorithms, the influence brought by the locality of the code is analyzed, the performance of spatial join based on Hilbert R-tree in main memory is tested. Besides, the impact on spatial join and performance of access to cache with different node size are compared. These results are very useful for improving the efficiency of the Cache-conscious spatial join.