US5812996A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Database system with methods for optimizing query performance with a buffer manager
Assignee: Sybase Inc
•
Filing: 1995-11-06
•
Granted: 1998-09-22
•
Expires: 2015-11-06
Abstract
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.
Inventors
- 👤 David S. Rubin
- 👤 Brijesh Agarwal
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 11:25
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0866; G06F12/0875; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24552; G06F12/0223; G06F12/023; G06F2212/00; G06F2212/31; G06F2212/311; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
227 words
In a computer system having a processor, a memory, and a storage device, said storage device storing a database comprising data records, said system including a buffer manager having a cache in the memory for caching information stored on said storage device and an optimizer for formulating an optimal query plan, a method for executing a database query for selecting particular ones of said data records, the method comprising: receiving a query for selecting particular data records; formulating at the optimizer a query plan for accessing the particular data records from said database, including the substeps of: (i) at the optimizer, examining the query for determining at least one object to be accessed for retrieving the particular data records; (ii) establishing communication between the optimizer and the buffer manager regarding said at least one object to be accessed, wherein the buffer manager transmits to the optimizer information regarding cache usage for said at least one object to be accessed; and (iii) based on said examining substep and said establishing communication substep, creating a query plan for accessing said at least one object to be accessed; and executing said query plan for retrieving particular data records, wherein said buffer manager provides access to said at least one object according to said query plan based at least in part on how said at least one object uses the cache.
Claim 2
Dependent Claim
227 words
In a computer system having a processor, a memory, and a storage device, said storage device storing a database comprising data records, said system including a buffer manager having a cache in the memory for caching information stored on said storage device and an optimizer for formulating an optimal query plan, a method for executing a database query for selecting particular ones of said data records, the method comprising: receiving a query for selecting particular data records; formulating at the optimizer a query plan for accessing the particular data records from said database, including the substeps of: (i) at the optimizer, examining the query for determining at least one object to be accessed for retrieving the particular data records; (ii) establishing communication between the optimizer and the buffer manager regarding said at least one object to be accessed, wherein the buffer manager transmits to the optimizer information regarding cache usage for said at least one object to be accessed; and (iii) based on said examining substep and said establishing communication substep, creating a query plan for accessing said at least one object to be accessed; and executing said query plan for retrieving particular data records, wherein said buffer manager provides access to said at least one object according to said query plan based at least in part on how said at least one object uses the cache.
Claim 3
Dependent Claim
64 words
The method of claim 1, wherein said substep (ii) includes: transmitting information from the buffer manager to the optimizer regarding one of said at least one object for determining whether at least a portion of the one object already exists in the cache, wherein said query plan alters its strategy if at least a portion of the one object already exists in the cache.
Claim 4
Dependent Claim
70 words
The method of claim 1, wherein said cache comprises a plurality of named caches, and wherein said substep (ii) includes: transmitting information from the buffer manager to the optimizer regarding a particular one of said at least one object for determining whether the particular object already exists in a named cache bound to the object, said named cache comprising a portion of said memory devoted for caching the particular object.
Claim 5
Dependent Claim
16 words
The method of claim 1, wherein one of said at least one object includes said database.
Claim 6
Dependent Claim
19 words
The method of claim 1, wherein one of said at least one object includes an index on said database.
Claim 7
Dependent Claim
53 words
The method of claim 1, wherein said substep (iii) includes: creating a query plan for accessing a particular one of said at least one particular object, said query plan specifying a preferred Input/Output transfer size for accessing the particular object in response to communication of information to the optimizer from the buffer manager.
Claim 8
Dependent Claim
37 words
The method of claim 6, wherein said buffer manager stores information in pages of at least two sizes, and wherein said Input/Output size for the one object is a larger one of said at least two sizes.
Claim 9
Dependent Claim
26 words
The method of claim 7, wherein said pages of at least two sizes include memory pages having a size selected from 2K, 8K, 16K, and 64K.
Claim 10
Dependent Claim
51 words
The method of claim 1, wherein said substep (iii) includes: creating a query plan for accessing a particular one of said at least one object, wherein said particular object exhibits sequential clustering when accessed for said query, and wherein said query plan specifies prefetching additional information when accessing the particular object.
Claim 11
Dependent Claim
42 words
The method of claim 9, wherein said prefetching comprises soft prefetching, wherein said buffer manager prefetches a size closest to said specified additional information, if said buffer manager is unable to prefetch a size which is identical to said specified additional information.
Claim 12
Dependent Claim
186 words
In a computer system having a processor, a memory, and a storage device, said storage device storing a database comprising data records, said system including a buffer manager having a cache in the memory for caching information stored on said storage device, a method for executing a database query specifying a database join operation, the method comprising: receiving a query specifying a database join operation between two database tables, wherein a first database table comprises an outer table of the join and a second database table comprises an inner table of the join, each table comprising a plurality of data pages, each data page comprising a plurality of data records; examining size of the inner table with respect to available cache; if the inner table is small in size with respect to available cache, specifying that the buffer manager is to preferentially discard pages of the outer table from cache, so that as data records of the outer table are processed rows for the inner table are kept in cache; and executing the query by scanning said inner table for each row of said outer table.
Claim 13
Dependent Claim
186 words
In a computer system having a processor, a memory, and a storage device, said storage device storing a database comprising data records, said system including a buffer manager having a cache in the memory for caching information stored on said storage device, a method for executing a database query specifying a database join operation, the method comprising: receiving a query specifying a database join operation between two database tables, wherein a first database table comprises an outer table of the join and a second database table comprises an inner table of the join, each table comprising a plurality of data pages, each data page comprising a plurality of data records; examining size of the inner table with respect to available cache; if the inner table is small in size with respect to available cache, specifying that the buffer manager is to preferentially discard pages of the outer table from cache, so that as data records of the outer table are processed rows for the inner table are kept in cache; and executing the query by scanning said inner table for each row of said outer table.
Claim 14
Dependent Claim
61 words
The method of claim 11, further comprising: if the inner table is large in size with respect to available cache, specifying that the buffer manager is to preferentially discard data pages of the inner table from cache, so that as new rows of the inner table are processed at least some rows for the outer table can be found in cache.
Claim 15
Dependent Claim
50 words
The method of claim 11, wherein each table includes a clustered-index for ordering data pages of the table, wherein the two tables are joined by a table field which is a prefix for the clustered-index of each table, and wherein the method further comprises: prefetching an additional amount when scanning.
Claim 16
Dependent Claim
240 words
In a computer system having a processor, a memory, and a storage device, said storage device storing a database comprising data records, said system including a buffer manager having a cache in the memory for caching information stored on said storage device, a method for executing a database query specifying a database join operation, the method comprising: receiving a query specifyiny a database join operation between two database tables, wherein a first database table comprises an outer table of the join and a second database table comprises an inner table of the join, each table comprising a plurality of data pages, each data page comprising a plurality of data records; examining size of the inner table with respect to available cache; if the inner table is small in size with respect to available cache, specifying that the buffer manager is to preferentially discard pages of the outer table from cache, so that as data records of the outer table are processed rows for the inner table are kept in cache; and executing the query by scanning said inner table for each row of said outer table; wherein said buffer manager maintains a most-recently used/least-recently used list spanning from most-recently used (MRU) pages to least-recently used (LRU) pages, and wherein said specifying step includes: specifying that pages of the outer table are placed on an LRU side of the list, so that memory buffers employed thereat are first to be re-used.
Claim 17
Dependent Claim
240 words
In a computer system having a processor, a memory, and a storage device, said storage device storing a database comprising data records, said system including a buffer manager having a cache in the memory for caching information stored on said storage device, a method for executing a database query specifying a database join operation, the method comprising: receiving a query specifyiny a database join operation between two database tables, wherein a first database table comprises an outer table of the join and a second database table comprises an inner table of the join, each table comprising a plurality of data pages, each data page comprising a plurality of data records; examining size of the inner table with respect to available cache; if the inner table is small in size with respect to available cache, specifying that the buffer manager is to preferentially discard pages of the outer table from cache, so that as data records of the outer table are processed rows for the inner table are kept in cache; and executing the query by scanning said inner table for each row of said outer table; wherein said buffer manager maintains a most-recently used/least-recently used list spanning from most-recently used (MRU) pages to least-recently used (LRU) pages, and wherein said specifying step includes: specifying that pages of the outer table are placed on an LRU side of the list, so that memory buffers employed thereat are first to be re-used.
Claim 18
Dependent Claim
236 words
In a computer system having a processor a memory, and a storage device, said storage device storing a database comprising data records, said system including a buffer manager having a cache in the memory for caching information stored on said storage device, a method for executing a database query specifying a database join operation, the method comprising: receiving a query specifying a database join operation between two database tables, wherein a first database table comprises an outer table of the join and a second database table comprises an inner table of the join, each table comprising a plurality of data pages, each data page comprising a plurality of data records; examining size of the inner table with respect to available cache; if the inner table is small in size with respect to available cache, specifying that the buffer manager is to preferentially discard pages of the outer table from cache, so that as data records of the outer table are processed rows for the inner table are kept in cache; executing the query by scanning said inner table for each row of said outer table; setting an in use flag for a page which is already in use; before specifying that the buffer manager is to preferentially discard a page, testing whether said in use flag is set; and for each page having the in use flag set, ignoring any request to preferentially discard the page.
Claim 19
Dependent Claim
236 words
In a computer system having a processor a memory, and a storage device, said storage device storing a database comprising data records, said system including a buffer manager having a cache in the memory for caching information stored on said storage device, a method for executing a database query specifying a database join operation, the method comprising: receiving a query specifying a database join operation between two database tables, wherein a first database table comprises an outer table of the join and a second database table comprises an inner table of the join, each table comprising a plurality of data pages, each data page comprising a plurality of data records; examining size of the inner table with respect to available cache; if the inner table is small in size with respect to available cache, specifying that the buffer manager is to preferentially discard pages of the outer table from cache, so that as data records of the outer table are processed rows for the inner table are kept in cache; executing the query by scanning said inner table for each row of said outer table; setting an in use flag for a page which is already in use; before specifying that the buffer manager is to preferentially discard a page, testing whether said in use flag is set; and for each page having the in use flag set, ignoring any request to preferentially discard the page.
Claim 20
Dependent Claim
196 words
A database system comprising: a database server connected to a plurality of clients, said database server having a memory and a storage device, said storage device for storing at least one database table; query means for receiving a query from at least one client for retrieving records from said at least one database table; a buffer manager having a cache in the memory for caching records retrieved from the storage device; an optimizer for generating a query plan providing an optimized access path for retrieving data records from said at least one database table when processing a query; communication means, operably coupled to said buffer manager and to said optimizer, providing bi-directional communication between said optimizer and said buffer manager regarding how said data records are to be retrieved into the cache, so that said optimizer can generate the query plan based on configuration of the cache and based on how said data records are to be retrieved into the cache; and query execution means for executing the query according to said query plan, wherein said query plan is based at least in part on how said data records are to be retrieved into the cache.
Claim 21
Dependent Claim
196 words
A database system comprising: a database server connected to a plurality of clients, said database server having a memory and a storage device, said storage device for storing at least one database table; query means for receiving a query from at least one client for retrieving records from said at least one database table; a buffer manager having a cache in the memory for caching records retrieved from the storage device; an optimizer for generating a query plan providing an optimized access path for retrieving data records from said at least one database table when processing a query; communication means, operably coupled to said buffer manager and to said optimizer, providing bi-directional communication between said optimizer and said buffer manager regarding how said data records are to be retrieved into the cache, so that said optimizer can generate the query plan based on configuration of the cache and based on how said data records are to be retrieved into the cache; and query execution means for executing the query according to said query plan, wherein said query plan is based at least in part on how said data records are to be retrieved into the cache.
Claim 22
Dependent Claim
34 words
The system of claim 16, wherein said communication means includes means for communicating a query strategy to the buffer manager, so that said buffer manager can configure the cache based on the query strategy.
Claim 23
Dependent Claim
23 words
The system of claim 16, wherein said communication means includes: means for communicating to the optimizer whether a particular object is in cache.
Claim 24
Dependent Claim
38 words
The system of claim 16, wherein said communication means includes: means for communicating from the optimizer to the buffer manager that data records retrieved from a particular database table should be preferentially discarded from cache during query execution.
Claim 25
Dependent Claim
37 words
The system of claim 16, wherein said communication means includes: means for communicating from the optimizer to the buffer manager that data records retrieved from a particular database should be preferentially maintained in cache during query execution.
References Cited (Backward Citations)
US4989132A
Cited
US5493668A
Cited
US5537574A
Cited
US5557791A
Cited
US5499367A
Cited
US5452445A
Cited
US5463772A
Cited
US5560007A
Cited
US5544345A
Cited
US5574902A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-09-21 | 2002-03-23 | 2002-09-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-09-21 | 2006-03-23 | 2006-09-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-09-21 | 2010-03-23 | 2010-09-22 | $7700.00 | Window Closed / Lapsed |