Apparatus and method for decomposing database queries for database management system including multiprocessor digital data processing system

• US 6,289,334 B1
• Filed: 01/31/1997
• Issued: 09/11/2001
• Est. Priority Date: 01/31/1994
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Miller, Jeffrey M., Reiner, David, Wheat, David C.
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/791,898
• Time in Patent Office: 1,684 Days
• Field of Search: 707/10, 707/3, 707/2, 707/201, 395/200.31, 395/200.38, 395/200.45
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: Y10S 707/966 Distributed
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

An improved system for database query processing by means of “query decomposition” intercepts database queries prior to processing by a database management system (“DBMS”). The system decomposes at least selected queries to generate multiple subqueries for application, in parallel, to the DBMS, in lieu of the intercepted query. Responses by the DBMS to the subqueries are assembled by the system to generate a final response. The system also provides improved methods and apparatus for storage and retrieval of records from a database utilizing the DBMS'"'"'s cluster storage and index retrieval facilitates, in combination with a smaller-than-usual hash bucket size.

Claims

1. A parallel database query generating system adapted to be used with a database system including

a database store adapted to store data records in a plurality of partitions,

a database management system adapted to access data records stored in said database store, said database management system including a standard interface adapted to receive a query and to apply that query to said stored data records to generate a result,

the parallel database query generating system comprising:

A. a parallel interface adapted to receive from an application, a query representative of a request for access to selected data records in said database store, said parallel interface including a query decomposer adapted to generate, from said received query, a plurality of subqueries, each representative of a request for access to data records stored in one or more respective partitions of said database store;

B. a query processor adapted to apply said plurality subqueries in parallel to the database management system'"'"'s standard interface; and

C. a result assembler adapted to receive results from said database management system generated in response to said subqueries and generate an assembled result representative of a response to said query.

2. A parallel database query generating system adapted to be used with a database system including

a database store adapted to store data records in a plurality of partitions,

a database management system adapted to access data records stored in said database store, said database management system including a standard interface adapted to receive a query and to apply that query to said stored data records to generate a result,

the parallel database query generating system comprising:

A. a computer; and

B. a control subsystem comprising;

i. a parallel interface module adapted to enable said computer to receive from an application, a query representative of a request for access to selected data records in said database store, said parallel interface module including a query decomposer module adapted to enable said computer to generate, from said received query, a plurality of subqueries, each representative of a request for access to data records stored in one or more respective partitions of said database store;

ii. a query processor module adapted to enable said computer to apply said plurality subqueries in parallel to the database management system'"'"'s standard interface; and

iii. a result assembler module adapted to enable said computer to receive results from said database management system generated in response to said subqueries and generate an assembled result representative of a response to said query.

3. A control subsystem adapted to be used with a computer to form a parallel database query generating system, the parallel database query generating system adapted to be used in connection with a database system including

a database store adapted to store data records in a plurality of partitions,

a database management system adapted to access data records stored in said database store, said database management system including a standard interface adapted to receive a query and to apply that query to said stored data records to generate a result,

the control subsystem comprising:

A. a parallel interface module adapted to enable said computer to receive from an application, a query representative of a request for access to selected data records in said database store, said parallel interface module including a query decomposer module adapted to enable said computer to generate, from said received query, a plurality of subqueries, each representative of a request for access to data records stored in one or more respective partitions of said database store;

B. a query processor module adapted to enable said computer to apply said plurality subqueries in parallel to the database management system'"'"'s standard interface; and

C. a result assembler module adapted to enable said computer to receive results from said database management system generated in response to said subqueries and generate an assembled result representative of a response to said query.

4. A parallel database query generating system computer program product adapted to be used with a computer to form a parallel database query generating system, the parallel database query processing system adapted to be used with a database system including

a database store adapted to store data records in a plurality of partitions,

a database management system adapted to access data records stored in said database store, said database management system including a standard interface adapted to receive a query and to apply that query to said stored data records to generate a result,

the parallel database query generating system computer program product comprising a machine readable medium having encoded thereon:

A. a parallel interface module adapted to enable said computer to receive from an application, a query representative of a request for access to selected data records in said database store, said parallel interface module including a query decomposer module adapted to enable said computer to generate, from said received query, a plurality of subqueries, each representative of a request for access to data records stored in one or more respective partitions of said database store;

B. a query processor module adapted to enable said computer to apply said plurality subqueries in parallel to the database management system'"'"'s standard interface; and

C. a result assembler module adapted to enable said computer to receive results from said database management system generated in response to said subqueries and generate an assembled result representative of a response to said query.

5. A query decomposer adapted to be used with a digital data processing system comprising

a database store adapted to store and retrieve data records, and

a database management system (DBMS) comprising:

i. a selectively invocable hashing element adapted to store said data records in hash bucket regions in said database store, each such data record being stored in a root hash bucket region corresponding to a hash function of a value of the corresponding data record, or an overflow hash bucket region associated with that root hash bucket region, and

ii. a selectively invocable indexer adapted to selectively index each data record so stored for access in accord with a respective value of the corresponding data record,

said query decomposer comprising;

A. a hash bucket identifier adapted to determine whether said data records are stored in said hash bucket regions based on a hash function of a value upon which those same data records are indexed, and

B. a record selection specifier adapted to selectively specify, in connection with applying said plural subquery signals to said standard interface, that said data records are to be retrieved from said database store based on such indexing.

6. A query decomposer adapted to be used with a digital data processing system comprising

a database store adapted to store and retrieve data records, and

a database management system (DBMS) comprising:

i. a selectively invocable hashing element adapted to store said data records in hash bucket regions in said database store, each such data record being stored in a root hash bucket region corresponding to a hash function of a value of the corresponding data record, or an overflow hash bucket region associated with that root hash bucket region, and

ii. a selectively invocable indexer adapted to selectively index each data record so stored for access in accord with a respective value of the corresponding data record,

said query decomposer comprising;

A. a computer; and

B. a control subsystem adapted to control said computer, said control subsystem comprising;

i. a hash bucket identifier module adapted to enable said computer to determine whether said data records are stored in said hash bucket regions based on a hash function of a value upon which those same data records are indexed, and

ii. a record selection specifier module adapted to enable said computer to selectively specify, in connection with applying said plural subquery signals to said standard interface, that said data records are to be retrieved from said database store based on such indexing.

7. A control subsystem adapted to be used with a computer to form a query decomposer, the query decomposer being adapted to be used with a digital data processing system comprising

a database store adapted to store and retrieve data records, and

a database management system (DBMS) comprising:

i. a selectively invocable hashing element adapted to store said data records in hash bucket regions in said database store, each such data record being stored in a root hash bucket region corresponding to a hash function of a value of the corresponding data record, or an overflow hash bucket region associated with that root hash bucket region, and

ii. a selectively invocable indexer adapted to selectively index each data record so stored for access in accord with a respective value of the corresponding data record,

said control subsystem adapted to control said computer, said control subsystem comprising;

i. a hash bucket identifier module adapted to enable said computer to determine whether said data records are stored in said hash bucket regions based on a hash function of a value upon which those same data records are indexed, and

ii. a record selection specifier module adapted to enable said computer to selectively specify, in connection with applying said plural subquery signals to said standard interface, that said data records are to be retrieved from said database store based on such indexing.

8. A query decomposer computer program product adapted to be used with a computer to form a query decomposer, the query decomposer being adapted to be used with a digital data processing system comprising

a database store adapted to store and retrieve data records, and

a database management system (DBMS) comprising:

i. a selectively invocable hashing element adapted to store said data records in hash bucket regions in said database store, each such data record being stored in a root hash bucket region corresponding to a hash function of a value of the corresponding data record, or an overflow hash bucket region associated with that root hash bucket region, and

ii. a selectively invocable indexer adapted to selectively index each data record so stored for access in accord with a respective value of the corresponding data record,

the query decomposer comprising a computer-readable medium having encoded thereon;

i. a hash bucket identifier module adapted to enable said computer to determine whether said data records are stored in said hash bucket regions based on a hash function of a value upon which those same data records are indexed, and

ii. a record selection specifier module adapted to enable said computer to selectively specify, in connection with applying said plural subquery signals to said standard interface, that said data records are to be retrieved from said database store based on such indexing.