We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 24 Issue 4
July  2009
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Hua Luan, Xiao-Yong Du, Shan Wang. Prefetching J+-Tree: A Cache-Optimized Main Memory Database Index Structure[J]. Journal of Computer Science and Technology, 2009, 24(4): 687-707.
Citation: Hua Luan, Xiao-Yong Du, Shan Wang. Prefetching J+-Tree: A Cache-Optimized Main Memory Database Index Structure[J]. Journal of Computer Science and Technology, 2009, 24(4): 687-707.
shu

Prefetching J+-Tree: A Cache-Optimized Main Memory Database Index Structure

  • Key Laboratory of Data Engineering and Knowledge Engineering (Renmin University of China), MOE, Beijing 100872, China
    School of Information, Renmin University of China, Beijing 100872, China

Funds: This work is supported by a grant from HP Lab China, and the National Natural Science Foundation of China under Grant Nos. 60496325 and 60573092.
More Information
  • Author Bio:

    Hua Luan received her M.S. degree from Shandong University. She isa Ph.D. candidate at Renmin University of China. Her research interestsinclude databases and data warehouses. She is a student member of CCF.

    Xiao-Yong Du received the Ph.D. degree from Nagoya Institute ofTechnology, Japan in 1997. He is a professor and doctoral supervisorat Renmin University of China. His research interests include highperformance databases, intelligent information retrieval andsemantic web. He is a member of CCF.

    Shan Wang received the M.S. degree in computer science from RenminUniversity of China in 1981. She is a professor and doctoralsupervisor at Renmin University of China. Her research interestsinclude high performance databases, knowledge systems, datawarehouses and grid data management. She is a senior member of CCFand a member of ACM.

  • Received Date: September 21, 2007
  • Revised Date: March 02, 2009
  • Published Date: July 04, 2009
    Abstract
  • As the speed gap between main memory and modern processors continues to widen, the cache behavior becomes more important for main memory database systems (MMDBs). Indexing technique is a key component of MMDBs. Unfortunately, the predominant indexes --- B+-trees and T-trees --- have been shown to utilize cache poorly, which triggers the development of many cache-conscious indexes, such as CSB+-trees and pB+-trees. Most of these cache-conscious indexes are variants of conventional B+-trees, and have better cache performance than B+-trees. In this paper, we develop a novel J+-tree index, inspired by the Judy structure which is an associative array data structure, and propose a more cache-optimized index --- Prefetching J+-tree (pJ+-tree), which applies prefetching to J+-tree to accelerate range scan operations. The J+-tree stores all the keys in its leaf nodes and keeps the reference values of leaf nodes in a Judy structure, which makes J+-tree not only hold the advantages of Judy (such as fast single value search) but also outperform it in other aspects. For example, J+-trees can achieve better performance on range queries than Judy. The pJ+-tree index exploits prefetching techniques to further improve the cache behavior of J+-trees and yields a speedup of 2.0 on range scans. Compared with B+-trees, CSB+-trees, pB+-trees and T-trees, our extensive experimental study shows that pJ+-trees can provide better performance on both time (search, scan, update) and space aspects.
    • FullText(HTML)
    • References (19)
  • [1]
    Ailamaki A, DeWitt D J, Hill M D, Wood D A. DBMSs on a modern processor: Where does time go? In Proc. VLDB Conference, Edinburgh, UK, Sept. 7-10, 1999, pp.266-277.
    [2]
    Barroso L A, Gharachorloo K, Bugnion E D. Memory system characterization of commercial workloads. In Proc. the 25th ISCA, Barcelona, Spain, June 27-July 1, 1998, pp.3-14.
    [3]
    Keeton K, Patterson D A, He Y Q, Raphael R C, Baker W E. Performance characterization of a Quad Pentium Pro SMP using OLTP workloads. In Proc. the 25th ISCA, Barcelona, Spain, June 27-July 1, 1998, pp.15-26.
    [4]
    Becker M, Mancheril N, Okamoto S. DBMSs on a modern processor: \Where does time go?" revisited. Technical Report, Carnegie Mellon University, USA, 2004.
    [5]
    Rao J, Ross K A. Cache conscious indexing for decisionsupport in main memory. In Proc. VLDB Conference, Edinburgh, UK, Sept. 7-10, 1999, pp.78-89.
    [6]
    Hennessy J L, Patterson D A. Computer Architecture: A Quantitative Approach. Morgan Kaufmann Publishers Inc., 2002.
    [7]
    Boncz P, Manegold S, Kersten M L. Database architecture optimized for the new bottleneck: Memory access. In Proc. VLDB Conference, Edinburgh, UK, Sept. 7-10, 1999, pp.54- 65.
    [8]
    Rao J, Ross K A. Making B+-trees cache conscious in main memory. In Proc. ACM SIGMOD, Dallas, USA, May 16-18, 2000, pp.475-486.
    [9]
    Shatdal A, Kant C, Naughton J F. Cache conscious algorithms for relational query processing. In Proc. VLDB Conference, Santiago, Chile, Sept. 12-15, 1994, pp.510-521.
    [10]
    Chen S, Gibbons P B, Mowry T C. Improving index performance through prefetching. In Proc. ACM SIGMOD, Santa Barbara, USA, May 21-24, 2001, pp.235-246.
    [11]
    Nyberg C, Barclay T, Cvetanovic Z, Gray J, Lomet D. AlphaSort: A RISC machine sort. In Proc. ACM SIGMOD, Minneapolis, USA, May 24-27, 1994, pp.233-242.
    [12]
    Lehman T J, Carey M J. A study of index structures for main memory database management systems. In Proc. VLDB Conference, Kyoto, Japan, Aug. 25-28, 1986, pp.294-303.
    [13]
    Baskins D. Judy functions | C libraries for creating and accessing dynamic arrays. http://judy.sourceforge.net.
    [14]
    Comer D. The ubiquitous B-Tree. ACM Computing Surveys, 1979, 11(2): 121-137.
    [15]
    Garcia-Molina H, Ullman J D, Widom J. Database System Implementation. Prentice Hall, 2000.
    [16]
    Luk C K, Mowry T C. Compiler-based prefetching for recursive data structures. In Proc. the 7th ASPLOS, Cambridge, USA, Oct. 1-5, 1996, pp.222-233.
    [17]
    Luk C K, Mowry T C. Automatic compiler-inserted prefetching for pointer-based applications. IEEE Transactions on Computers, 1999, 48(2): 134-141.
    [18]
    IA-32 Intel architecture optimization reference manual. Intel, http://developer.intel.com.
    [19]
    Hankins R A, Patel J M. Effect of node size on the performance of cache-conscious B+-trees. In Proc. ACM SIGMETRICS, San Diego, USA, June 9-14, 2003, pp.283-294.
    • Relative Articles

  • Related Articles

    [1]Surendra Byna, Yong Chen, Xian-He Sun. Taxonomy of Data Prefetching for Multicore Processors[J]. Journal of Computer Science and Technology, 2009, 24(3): 405-417.
    [2]Philip Machanick. The Value of a Small Microkernel for Dreamy Memory and the RAMpageMemory Hierarchy[J]. Journal of Computer Science and Technology, 2005, 20(5): 586-595.
    [3]WANG Wei, WaNG Yujun, SHI Baile. Dynamic Interval Index Structure in Constraint Database Systems[J]. Journal of Computer Science and Technology, 2000, 15(6): 542-551.
    [4]WEN Jirong, CHEN Hong, WANG Shan. POTENTIAL: A Highly Adaptive Core of Parallel Database System[J]. Journal of Computer Science and Technology, 2000, 15(6): 527-541.
    [5]WEN Jirong, CHEN Hong, WANG Shan. POTENTIAL:A Highly Adaptive Core of Parallel Database System[J]. Journal of Computer Science and Technology, 2000, 15(6).
    [6]Gu Ning, Lin Zongkai, Guo Yuchai. On Model, Memory Management and Interface in EDBMS/3[J]. Journal of Computer Science and Technology, 1998, 13(4): 337-347.
    [7]Hu Weiwu, Shi Weisong, Tang Zhimin, Li Ming. A Lock-Based Cache Coherence Protocol for Scope Consistency[J]. Journal of Computer Science and Technology, 1998, 13(2): 97-109.
    [8]Fang Zhiyi, Ju Jiubin. NONH:A New Cache-Based Coherence Protocol for Linked List Structure DSM System and Its Performance Evaluation[J]. Journal of Computer Science and Technology, 1996, 11(4): 405-415.
    [9]Zhou Jianqiang, Xie Li, Dai Fei, Sun Zhongxiu. Adaptive Memory Coherence Algorithms in DSVM[J]. Journal of Computer Science and Technology, 1994, 9(4): 365-372.
    [10]Zhang Bo, Zhang Ling. On Memory Capacity of the Probabilistic Logic Neuron Network[J]. Journal of Computer Science and Technology, 1993, 8(3): 62-66.
    • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (16) PDF downloads (2469) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return