Transparent edge-of-network data cache

• US 6,950,823 B2
• Filed: 12/23/2002
• Issued: 09/27/2005
• Est. Priority Date: 12/23/2002
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Park, Sanghyun, Amiri, Khalil S., Padmanabhan, Sriram, Tewari, Renu
• Primary Examiner(s): Corrielus, Jean M.
• Assistant Examiner(s): Chen, Chongshan
• Application Number:
  US10/328,229
• Publication Number:
  US 20040133538A1
• Time in Patent Office: 1,009 Days
• Field of Search: 707/2, 707/3, 707/10
• US Class Current: 707/690
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A system, apparatus and method are provided for the dynamic caching of data based on queries performed by a local application, where the system includes a remote server having a complete database, a local database on an edge server including a subset of the complete database, the edge server in communication with the remote server, shared tables within the local database on the edge server for caching results from the complete database, receiving locally generated data, and adjusting the contents of the cache based on available storage requirements while ensuring consistency of the data between the local database and the remote database; the apparatus includes an edge data cache including a query evaluator, a cache index, cache repository, resource manager, containment checker, query parser and consistency manager all in signal communication with the query evaluator; and the method for a local server to satisfy a database query meant for at least one remote server includes dynamically caching results of previous database queries of the remote server, associating a local database with the local server, storing a plurality of the caching results in shared tables in the local database, and using the plurality of the caching results in satisfying a new database query with the local server.

Claims

1. A method for a local server to satisfy a database query for at least one remote server, the method comprising:

dynamically caching results of previous database queries of the at least one remote server in an edge cache;

associating a local database with the local server;

storing a plurality of the caching results in shared tables in the local database; and

using the plurality of the caching results in transparently satisfying a new database query with the local server,

wherein the step of storing comprises;

inserting results of simple and Top-N queries over a single database table in shared base tables;

saving results of join queries in shared join tables;

forming a shared table repository including shared base tables and shared join tables;

storing results of complex queries in separate tables one per query result; and

forming an exact-match repository from a plurality of the separate tables.

2. A method as defined in claim 1, wherein the step of inserting comprises:

creating a single local table in the edge cache to correspond to a base table in an origin server whenever a simple query is first received to a base table;

inserting results of the simple query in the local table; and

inserting results of all subsequent simple queries to the base table in the local table.

3. A method as defined in claim 1, wherein the step of saving comprises:

creating a local join table in the edge cache to correspond to each join condition and table list in a join query; and

inserting results of all subsequent join queries over the same table list and having the same join condition in the local join table.

4. A method as defined in claim 2, wherein the step of attempting comprises at least one of:

finding a matching cached query satisfying conditions that a list of columns in a select list of the new query is included in that of a matching query, that a predicate of the new query logically implies that of a predicate of the matching query, and that all columns mentioned in clauses of the new query are included in a select list of the matching query; and

finding a set of matching cached queries satisfying conditions that a list of columns in a select list of the new query is included in that of each one of the matching cached queries, that a predicate of the new query logically implies that of a predicate formed by a disjunction of all predicates of the matching cached queries, when all predicates of the matching cached queries are connected by a logical OR operator, and that all columns mentioned in clauses of the new query are included in select lists of each of the matching cached queries.

5. A method for a local server to satisfy a database query from an application for at least one remote server, the method comprising:

dynamically caching results of previous database queries of the at least one remote server in an edge cache comprising an exact-match repository;

associating a local database with the local server;

storing a plurality of the caching results in shared tables comprising a shared-table repository in the local database; and

using the plurality of the caching results in transparently satisfying a new database query with the local server,

wherein the step of using comprises at least one of;

searching for a response to the new query in the exact-match repository if the new query is complex; and

sub-selecting a response to the new query from the shared-table repository if the new query is not complex,

wherein the step of searching comprises;

returning a query result in the edge cache corresponding to an SQL string to the application if the SQL string of the new query is found in the exact-match repository;

sending the new query to the remote server if the SQL string of the new query is not found in the exact-match repository;

inserting a received query result in the exact-match repository if the SQL string of the new query is not found in the exact-match repository; and

associating the received query result in edge cache with the new query'"'"'s SQL string if the SQL string of the new query is not found in the exact-match repository.

6. A method as defined in claim 5 wherein the shared table cleaning comprises:

forming a control column in each table from the shared tables;

setting entries in a control column to false;

identifying good queries to be maintained in the shared tables;

marking all entries in the control column corresponding to rows belonging to responses for good queries; and

deleting any rows in the shared tables for which the control column entry is still false.

7. A method for a local server to satisfy a database query received from an application for at least one remote server, the method comprising:

dynamically caching results of previous database queries of the at least one remote server in an edge cache comprising an exact-match repository;

associating a local database with the local server;

storing a plurality of the caching results in shared tables comprising a shared-table repository in the local database; and

using the plurality of the caching results in transparently satisfying a new database query with the local server,

wherein the step of using comprises at least one of;

searching for a response to the new query in the exact-match repository if the new query is complex; and

sub-selecting a response to the new query from the shared-table repository if the new query is not complex,

wherein the step of sub-selecting comprises;

attempting to prove that a result of the new query'"'"'s result set is contained in a union of cached query results with a containment checker;

substituting tables mentioned in the new query with local table names if the step of attempting to prove is completed successfully;

evaluating the new query over the shared-table repository if the step of attempting to prove is completed successfully; and

counting the number of rows received from the edge cache if the new query is a Top-N query, and if the number of rows do not exceed the number of rows requested by the application, processing by rewriting the new query and generating a rewritten query, sending the rewritten query to the remote server and storing results received from the remote server in the shared-table repository, adding a predicate of the rewritten query to an index of the shared-table repository, evaluating the new query over the shared-table repository, and returning results of the step of evaluating to the application.

8. A method as defined in claim 7, wherein the step of rewriting includes the steps of:

adding primary keys of accessed tables to a select list of the new query;

dropping an aggregation operator from the select list if a resource manager estimates a resulting result set to be not too large or worth caching; and

expanding a number of rows (N) requested by the new query to retrieve more rows.

9. A method for a local server to satisfy a database query for at least one remote server, the method comprising:

dynamically caching results of previous database queries of the at least one remote server in an edge cache;

associating a local database with the local server;

storing a plurality of the caching results in shared tables in the local database;

using the plurality of the caching results in transparently satisfying a new database query with the local server;

ensuring delta-consistency of results of previous queries including the steps of;

subscribing an edge cache to refresh messages propagated by an origin server and including updates, deletes and inserts applied to the back-end tables;

applying updates, deletes, and inserts to locally cached tables in a shared-table repository whenever refresh messages are received;

invalidating any shared join tables or tables in an exact-match repository which are referred to in a refresh message as changed;

associating a refresh message timestamp with a refresh message that is equal to the largest timestamp of any transaction whose effects are included in the refresh message;

associating a cached set timestamp with results of previous queries that equals a timestamp of the last refresh message applied to the edge cache;

associating a new query timestamp with a new query;

comparing the new query timestamp with the cached set timestamp;

inserting a response to the new query if the new query timestamp exceeds the cached set timestamp; and

retrieving pending refresh messages from the database server if the new query timestamp exceeds the cached set timestamp.

10. A method for ensuring delta-consistency of a set of query results retrieved from a database server, the method comprising the steps of:

dynamically caching results of previous database queries of a remote server in an edge cache;

associating a local database with a local server;

storing a plurality of the caching results in shared tables in the local database;

using the plurality of the caching results in transparently satisfying a new database query with the local server;

subscribing the edge cache to refresh messages propagated by an origin server and including updates, deletes and inserts applied to back-end tables;

applying the updates, deletes, and inserts transparently to locally cached tables whenever refresh messages are received;

associating a timestamp with a refresh message that is equal to the largest timestamp of any transaction whose effects are included in the refresh message;

associating a set timestamp with results of previous queries that equals the timestamp of the last refresh message applied to the edge cache;

associating a new query timestamp with a new query;

comparing the new query timestamp with the set timestamp;

inserting a response to the new query if the new query timestamp exceeds the set timestamp; and

retrieving pending refresh messages from the database server if the new query timestamp exceeds the set timestamp.

11. A system comprising a local edge server for dynamic caching of data based on queries performed by a local application and ensuring delta-consistency of a set of query results retrieved from a database server, the system further comprising:

means for dynamically caching results of previous database queries of a remote server in an edge cache;

means for associating a local database with the local server;

means for storing a plurality of the caching results in shared tables in the local database;

means for using the plurality of the caching results in transparently satisfying a new database query with the local server;

means for subscribing the edge cache to refresh messages propagated by an origin server and including updates, deletes and inserts applied to back-end tables,

means for applying the updates, deletes, and inserts to locally cached tables whenever refresh messages are received;

means for associating a timestamp with a refresh message that is equal to the largest timestamp of any transaction whose effects are included in the refresh message;

means for associating a set timestamp with results of previous queries that equals the timestamp of the last refresh message applied to the edge cache;

means for associating a new query timestamp with a new query;

means for comparing the new query timestamp with the set timestamp;

means for inserting a response to the new query if the new query timestamp exceeds the set timestamp; and

means for retrieving pending refresh messages from the database server if the new query timestamp exceeds the set timestamp.

12. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for dynamic caching of data based on queries performed by a local application and for ensuring delta-consistency of a set of query results retrieved from a database server, the method steps comprising:

dynamically caching results of previous database queries of a remote server in an edge cache;

associating a local database with a local server;

storing a plurality of the caching results in shared tables in the local database;

using the plurality of the caching results in transparently satisfying a new database query with the local server;

subscribing the edge cache to refresh messages propagated by an origin server and including updates, deletes and inserts applied to back-end tables;

applying the updates, deletes, and inserts to locally cached tables whenever refresh messages are received;

associating a timestamp with a refresh message that is equal to the largest timestamp of any transaction whose effects are included in the refresh message;

associating a set timestamp with results of previous queries that equals the timestamp of the last refresh message applied to the edge cache;

associating a new query timestamp with a new query;

comparing the new query timestamp with the set timestamp;

inserting a response to the new query if the new query timestamp exceeds the set timestamp; and

retrieving pending refresh messages from the database server if the new query timestamp exceeds the set timestamp.