System and method for improving index performance through prefetching

Abstract

The present invention provides a prefetch system for use with a cache memory associated with a database employing indices. In one embodiment, the prefetch system includes a search subsystem configured to prefetch cache lines containing an index of a node of a tree structure associated with the database. Additionally, the prefetch system also includes a scan subsystem configured to prefetch cache lines based on an index prefetch distance between first and second leaf nodes of the tree structure.

What is claimed is:  
     
       1. A method of prefetching for use with a cache memory associated with a database employing indices, comprising: 
       prefetching cache lines containing an index of a node of a tree structure associated with said database; and  
       prefetching at least one cache line associated with a second leaf node of said tree structure that is located an index prefetch distance from a first leaf node said tree structure.  
     
     
       2. The method as recited in  claim 1  wherein said prefetching comprises prefetching each cache line associated with a selected node of said tree structure. 
     
     
       3. The method as recited in  claim 1  wherein said prefetching comprises prefetching each cache line associated with selected nodes along a path from a root node to a leaf node of said tree structure. 
     
     
       4. The method as recited in  claim 1  wherein said prefetching employs a binary search without waiting to fetch pointers of nodes of said tree structure. 
     
     
       5. The method as recited in  claim 1  wherein said index prefetch distance is determined by an external or internal jump pointer array. 
     
     
       6. The method as recited in  claim 5  wherein employing said internal jump pointer array employs at least two bottom non-leaf nodes of said tree structure. 
     
     
       7. The method as recited in  claim 1  wherein said index prefetch distance is limited by a bandwidth of a memory associated with said prefetch system. 
     
     
       8. A prefetch system for use with a cache memory associated with a database employing indices, comprising: 
       a search subsystem configured to prefetch cache lines containing an index of a node of a tree structure associated with said database; and  
       a scan subsystem configured to prefetch at least one cache line associated with a second leaf node of said tree structure that is located an index prefetch distance from a first leaf node of said tree structure.  
     
     
       9. The prefetch system as recited in  claim 8  wherein said search subsystem is configured to prefetch each cache line associated with a selected node of said tree structure. 
     
     
       10. The prefetch system as recited in  claim 8  wherein said search subsystem is configured to prefetch each cache line associated with selected nodes along a path from a root node to a leaf node of said tree structure. 
     
     
       11. The prefetch system as recited in  claim 8  wherein said search subsystem is configured to employ a binary search without waiting to fetch pointers of nodes of said tree structure. 
     
     
       12. The prefetch system as recited in  claim 8  wherein said index prefetch distance is determined by an external or internal jump pointer array. 
     
     
       13. The prefetch system as recited in  claim 12  wherein said internal jump pointer array is configured to employ at least two bottom non-leaf nodes of said tree structure. 
     
     
       14. The prefetch system as recited in  claim 8  wherein said index prefetch distance is limited by a bandwidth of a memory associated with said prefetch system. 
     
     
       15. A database management system, comprising: 
       a computer employing a central processing unit;  
       a main memory containing a database employing indices;  
       a cache memory associated with said central processing unit and said main memory; and  
       a prefetch system for use with said cache memory that is coupled to said database employing indices, including:  
       a search subsystem that prefetches cache lines containing an index of a node of a tree structure associated with said database; and  
       a scan subsystem that prefetches at least one cache line associated with a second leaf node of said tree structure that is located an index prefetch distance from a first leaf node of said tree structure.  
     
     
       16. The database management system as recited in  claim 15  wherein said search subsystem prefetches each cache line associated with a selected node of said tree structure. 
     
     
       17. The database management system as recited in  claim 15  wherein said search subsystem prefetches each cache line associated with selected nodes along a path from a root node to a leaf node of said tree structure. 
     
     
       18. The database management system as recited in  claim 15  wherein said search subsystem employs a binary search without waiting to fetch pointers of nodes of said tree structure. 
     
     
       19. The database management system as recited in  claim 15  wherein said index prefetch distance is determined by an external or internal jump pointer array. 
     
     
       20. The database management system as recited in  claim 19  wherein said internal jump pointer array employs at least two bottom non-leaf nodes of said tree structure. 
     
     
       21. The database management system as recited in  claim 15  wherein said index prefetch distance is limited by a bandwidth of said main memory.