Database system with methods for improving query performance with cache optimization strategies

• US 5,822,749 A
• Filed: 02/28/1997
• Issued: 10/13/1998
• Est. Priority Date: 07/12/1994
• Status: Expired due to Term

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Agarwal, Brijesh
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US08/808,604
• Time in Patent Office: 592 Days
• Field of Search: 707/2, 707/3, 707/200
• US Class Current: 1/1
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• CPC Class Codes: G06F 2212/311 In host system
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Database system and methods are described for improving execution speed of database queries (e.g., for transaction processing and for decision support) by optimizing use of buffer caches. The system includes an Optimizer for formulating an optimal strategy for a given query. More particularly, the Optimizer communicates with a Buffer Manager before it formulates the query plan. For instance, the Optimizer may query the Buffer Manager for the purpose of determining whether the object of interest (e.g., table or index to be scanned) exists in its own buffer cache (i.e., whether it has been bound to a particular named cache). If the object exists in its own cache, the Optimizer may inquire as to how much of the cache (i.e., how much memory) the object requires, together with the optimal I/O size for the cache (e.g., 16K blocks). Based on this information, the Optimizer formulates a query strategy or plan with "hints," which are ultimately passed to the Cache or Buffer Manager. By formulating "hints" for the Buffer Manager at the level of the Optimizer, knowledge of the query is, in effect, passed down to the Buffer Manager so that it may service the query using an optimal caching strategy--one based on the dynamics of the query itself. Based on the "hints" received from the Optimizer, the Buffer Manager can fine tune input/output (i.e., cache management) for the query. Specific Optimizer strategies are described for each scan method available to the system, including heap scan, clustered index, and non-clustered index access. Additional strategies are described for multi-table access during processing of join queries.

Claims

1. In a system comprising a database for storing and retrieving information from database tables, each database table comprising a plurality of data pages for storing data records, a method for retrieving information from database tables in response to a database query, the method comprising:

receiving a query specifying retrieval of specific information of interest from a database table, said database table having a clustered index which stores data pages at its terminal nodes; and

retrieving the specific information of interest using a first input/output (I/O) block size and a second I/O block size for retrieving information by;

(i) navigating the clustered index for locating a storage location where said particular information of interest is stored using said first I/O block size to retrieve non-terminal nodes as the clustered index is traversed, and

(ii) after navigating to the storage location where said specific information of interest is stored, retrieving data pages storing said specific information of interest using said second I/O block size.

2. The method of claim 1, wherein said first I/O block size is smaller in size than said second block size.

3. The method of claim 1, wherein said first I/O block size is substantially equal to a 2K block size.

4. The method of claim 1, wherein said second I/O block size is substantially equal to a 16K block size.

5. The method of claim 1, wherein said second I/O block size is larger in size than each data page, such that substep (ii) retrieves a plurality of contiguous data pages with each I/O block retrieved.

6. The method of claim 1, wherein said first I/O block size is equal in size to each non-terminal node of the clustered index.

7. The method of claim 1, wherein each data page has a size substantially equal to a 2K block, and wherein said second I/O block size is substantially equal to a block size which is a multiple of a 2K block.

8. The method of claim 7, wherein said second I/O block size is substantially equal to a selected one of a 4K, 6K, 8K, 16K, 32K, and 64K block.

9. The method of claim 1, further comprising:

repeating substep (ii) multiple times until all data pages storing said specific information of interest have been retrieved.

10. The method of claim 1, wherein said non-terminal nodes each store a reference pointing to another non-terminal node or pointing to a terminal node which stores a data page having information of interest.

11. In a database system comprising a database for storing and retrieving information from database tables, a method for retrieving information from database tables in response to a database query, the method comprising:

receiving a query specifying retrieval of specific information of interest from a database table, said database having an index including terminal nodes each of which points to a particular data page;

retrieving the specific information of interest using a first input/output (I/O) block size and a second I/O block size for retrieving information by;

(i) navigating the index for locating a terminal node which points to a storage location where said information of interest is stored using said first I/O block size to retrieve each node of the index traversed, and

(ii) after locating a storage location where said specific information of interest is stored, retrieving data pages storing said specific information of interest using said second I/O block size.

12. The method of claim 11, wherein said first I/O block size is smaller in size than said second block size.

13. The method of claim 11, wherein said first I/O block size is substantially equal to a 2K block size.

14. The method of claim 11, wherein said second I/O block size is substantially equal to a 16K block size.

15. The method of claim 11, wherein said second I/O block size is larger in size than each data page, such that substep (ii) retrieves a plurality of contiguous data pages with each I/O block retrieve.

16. The method of claim 11, wherein said first I/O block size is equal in size to each node of the index.

17. The method of claim 11, wherein each data page has a size substantially equal to a 2K block, and wherein said second I/O block size is substantially equal to a block size which is a multiple of a 2K block.

18. The method of claim 17, wherein said second I/O block size is substantially equal to a selected one of a 4K, 6K, 8K, 16K, 32K, and 64K block.

19. The method of claim 11, further comprising:

repeating substep (ii) multiple times until all data pages storing said specific information of interest have been retrieved.

20. The method of claim 11, wherein said index comprises a non-clustered index.

21. In a database system comprising a database for storing and retrieving information from database tables, each database table comprising a plurality of data pages for storing data records, a method for retrieving information from database tables in response to a database query, the method comprising:

receiving a query specifying retrieval of specific information of interest by joining first and second database tables;

determining a join order by assigning one of the tables to serve as an outer join table and the other table to serve as an inner join table, such that the system will scan the inner join table for each record of the outer table, for locating said specific information of interest; and

retrieving the specific information of interest by using a fetch and discard strategy on the outer join table, such that most-recently used data pages of the outer join table fetched are preferentially discarded from memory.

22. The method of claim 21, wherein data pages of the inner join table are preferentially kept in memory.

23. The method of claim 21, further comprising:

As each table is scanned, retrieving data pages by using an input/output (I/O) block size which is larger than the size of each data page.

24. The method of claim 23, wherein said I/O block size is equal to a size which is a multiple of a 2K block.

25. The method of claim 21, wherein joining first and second database tables includes joining the two tables on one or more columns common to both tables.