DBCC-Join: A novel cache-conscious disk-based join algorithm

作者：Han Xi Xian^*; Yang Dong Hua; Li Jian Zhong

来源：Chinese Journal of Computers, 2010, 33(8): 1500-1511.

DOI：10.3724/SP.J.1016.2010.01500

• Cache utilization
• Cache-conscious
• Cache-conscious algorithm
• Construction algorithms
• Construction stages
• Data access
• DBCC-Join
• Disk-based
• Join algorithm
• Join operation
• JPIPT construction stage
• Main memory
• One-pass
• Order of magnitude
• Output stages
• System designers
• Two stage

System designers exploit cache to make up for performance gap between CPU and main memory. Since data access speed of cache is much faster than that of memory, it is important for database operations to take maximum advantage of cache to obtain higher performance. Disk-based join operation is a common but time-consuming database operation. Unfortunately, most of traditional join algorithms do not take cache into consideration. This paper analyzes low cache utilization problem in traditional join algorithms and proposes a disk-based cache-conscious join algorithm DBCC-Join. Join positional index pair table (JPIPT) is a data structure which specifies the positional index pairs of join tuples in each table. The execution of DBCC-Join consists of two stages: JPIPT construction stage and result output stage. JPIPT construction stage performs cache-conscious construction algorithm on join attributes which are kept in column-oriented model, to obtain join positional index pair table of join results. The obtained JPIPT is used in result output stage to retrieve results in a one-pass sequential scan on each table. To the best of our knowledge, this paper is the first to exploit cache to improve performance of disk-based join algorithm. Experimental results show that compared to traditional join algorithms, DBCC-Join can be improved by a factor of an order of magnitude.

• 出版日期2010