System and method for improving index performance through prefetching
AssigneeLucent Technologies Inc.
InventorsShimin Chen, Phillip B. Gibbons, Todd C. Mowry
Life of this patent
Estimating the term…
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.
Claims21
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 cache lines based on an index prefetch distance between first and second leaf nodes of said tree structure.
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 cache lines based on an index prefetch distance between first and second leaf nodes of said tree structure.
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 cache lines based on an index prefetch distance between first and second leaf nodes of said tree structure.
Dependencies are inferred from the claim text.