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

• US 5,742,806 A
• Filed: 01/31/1994
• Issued: 04/21/1998
• 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): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/189,497
• Time in Patent Office: 1,541 Days
• Field of Search: 395/600, 395/200.05, 395/200.06, 395/200.2, 395/840, 395/477, 395/421.06, 395/182.09, 364/DIG. 1
• 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 digital data processing system comprising:

A. a database table for storing data records in a plurality of independently accessible partitions, and a database management system (DBMS) coupled to said database table for accessing data records stored therein by any of a direct reference to said database table and to views thereof, said DBMS including a standard interface for receiving a query signal representative of a request for access to one or more selected data records and for applying that request to said stored data records to generate a result signal representative of the result thereof,

B. a parallel interface for intercepting, from an application, a selected query signal representative of a request for access to selected data records in said database table, said parallel interface including

i. a query decomposer for generating, from said intercepted query signal, a plurality of subquery signals, each representative of a request for access to data records stored in one or more respective partitions of said database table,

ii. a subquery processor coupled to said query decomposer for applying in parallel to said standard interface said plural subquery signals, and

iii. a result assembler, coupled to said standard interface, for responding to result signals generated thereby in response to application of said subquery signals for generating an assembled result signal representative of a response to said query signal.

2. A digital data processing system according to claim 1, said DBMS including a result signal generator for generating said result signal as a function of a predicate list component of an applied query signal, said predicate list including zero, one or more predicates that evaluate true for data records requested by that query signal, said query decomposer being responsive to at least selected intercepted query signals for generating a plurality of subquery signals to be substantially identical to that query signal, which subquery signals additionally include in said predicate list an intersecting predicate that evaluates true for all data records in the respective partitions of said database table and evaluates false otherwise.

3. A digital data processing system according to claim 2, in which

A. said standard interface is responsive to a query signal representative of an insert/select request for placing selected data from said database table in a designated database table, and

B. said query decomposer is responsive to an intercepted signal representative of an insert/select request for generating said plural subquery signals based on said intercepted query signal and representative of requests for said selected data in said one or more respective partitions of said database table, said subquery signals for causing said standard interface to place data accessed in response thereto in said designated database table.

4. A digital data processing system according to claim 2, comprising

A. a plurality of database tables, each for storing a respective plurality of data records in a plurality of independently accessible partitions,

B. said database management system (DBMS) being coupled to said plural database tables, for accessing data records stored therein by any of a direct reference to said database table and to views thereof, said DBMS further determining an optimal order for applying the corresponding request to said plural database tables and for generating a strategy signal representative thereof and generating the result signal as a function of a predicate list component of an applied query signal, said predicate list including zero, one or more predicates that evaluate true for data records requested by that query signal,

C. said query decomposer including

i. a driving database table identifier responsive to said strategy signal for identifying a driving database table, and

ii. a subquery signal generator responsive to an intercepted query signal representative of a request for access to data records joined from said plural database table for generating said plural subquery signals to additionally include in said predicate list an intersecting predicate that evaluates true for all data records in the respective partitions of the driving database table and evaluates false otherwise.

5. A digital data processing system according to claim 2, wherein said result assembler responds to at least a selected intercepted query signal, for generating said assembled result signal by variably interleaving the result signals generated by said DBMS in response to application of said plural subquery signals in an order, if any, specified by said intercepted query signal.

6. A digital data processing system according to claim 2, wherein said result assembly includes responds to at least a selected intercepted query signal representative of a request for access based on an aggregate function of said data records stored in said database table, by generating said assembled result signal as an aggregate function applied to the result signals generated by said DBMS in response to application of said plural subquery signals.

7. A digital data processing system according to claim 2, wherein

A. said subquery processor comprises a plurality of subcursor buffer sets, each associated with each of said subquery signals, each said subcursor buffer set comprising a plurality of subcursor buffers each storing a result signal generated by the standard interface in response to application of the associated subquery signal,

B. said result assembler comprises:

i. a root buffer for storing a current assembled result signal, and

ii. a root fetch element for generating and storing in said root buffer an assembled result signal based on a result signal stored in one or more of selected subcursor buffer for, thereby, emptying those selected subcursor buffer, and

C. said query processor applying to said standard interface a subquery signal associated with an emptied one of said subcursor buffers, said subquery signal being applied to said standard interface asynchronously with respect to demand for a current assembled result signal.

8. A digital data processing system according to claim 2, wherein

A. said database table comprises a second data store for storing and retrieving signals representative of said data records,

B. said database management system (DBMS) includes

i. a selectively invocable hashing element for storing said data record-representative signals in hash bucket regions in said secondary data store, each such data record-representative signal 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,

ii) a selectively invocable indexer for selectively indexing each data record-representative signal so stored for access in accord with a respective value of the corresponding data record,

C. said query decomposer includes:

i) a hash bucket identifier for detecting whether said data record-representative signals are stored in said hash bucket regions based on a hash function of a value upon which those same data record-representative signals are indexed, and

ii) a record selection specifier for selectively specifying, in connection with applying said plural subquery signals to said standard interface, that said data record-representative signals are to be retrieved from said database table based on such indexing.

9. A digital data processing system according to claim 2 further comprising

A. a procedure/function call response element responsive to query signal in the form of a procedure/function call for invoking said parallel interface in lieu of said standard interface, and

B. said query decomposer selectively responds to such a query signal for generating a plurality of subquery signals in the form of further procedure/function calls for invoking said standard interface.

10. A digital data processing system according to claim 2, further comprising

A. a procedure/function call response element responsive to query signal in the form of a procedure/function call for invoking said parallel interface in lieu of said standard interface, and

B. said query decomposer selectively responds to such a query signal for generating a plurality of subquery signals in the form of further procedure/function calls for invoking said standard interface.

11. A digital data processing system according to claim 10, wherein said query processor comprises a plurality of threads, each for applying a respective one of said subquery signal to said DBMS.

12. A digital data processing system according to claim 11, further comprising parallel thread control element for controlling execution in parallel said plurality of threads on a plurality of central processing units.

13. A digital data processing system according to claim 10, wherein

A. said standard interface comprises an object code library,

B. said query signal comprises at least a portion of a sequence of computer programming instructions capable of linking with such an object code library, and

C. said parallel interface comprises an object code library for linking with said sequence of computer programming instructions.

14. A digital data processing system according to claim 1, wherein:

A. said standard interface responds to a query signal representative of an insert/select request for placing selected data from said database table in a designated database table,

B. said query decomposer responds to an intercepted signal representative of an insert/select request for generating said plural subquery signals based on said intercepted query signal and representative of requests for said selected data in said one or more respective partitions of said database table, said subquery signals for causing said standard interface to place data accessed in response thereto in said designated database table.

15. A digital data processing system according to claim 14, further comprising

A. a plurality of database tables, each for storing a respective plurality of data records in a plurality of independently accessible partitions,

B. said database management system (DBMS) being coupled to said plural database tables, for accessing data records stored therein by any of a direct reference to said database table and to views thereof, said DBMS further determining an optimal order for applying the corresponding request to said plural database and for generating a strategy signal representative thereof and generating the result signal as a function of a predicate list component of an applied query signal, said predicate list including zero, one or more predicates that evaluate true for data records requested by that query signal,

C. said query decomposer including

i. a driving database table identifier responsive to said strategy signal for identifying a driving database table, and

ii. a subquery signal generator responsive to an intercepted query signal representative of a request for access to data records joined from said plural database table for generating said plural subquery signals to additionally include in said predicate list an intersecting predicate that evaluates true for all data records in the respective partitions of the driving database table and evaluates false otherwise.

16. A digital data processing system according to claim 14, wherein said result assembler responds to at least a selected intercepted query signal, for generating said assembled result signal by variably interleaving the result signals generated by said DBMS in response to application of said plural subquery signals in an order, if any, specified by said intercepted query signal.

17. A digital data processing system according to claim 14, wherein said result assembler responds to at least a selected intercepted query signal representative of a request for access based on an aggregate function of said data records stored in said database table, for generating said assembled result signal as an aggregate function applied to the result signals generated by said DBMS in response to application of said plural subquery signals.

18. A digital data processing system according to claim 14, wherein

A. said subquery processor comprises a plurality of subcursor buffer sets, each associated with each of said subquery signals, each said subcursor buffer set comprising a plurality of subcursor buffers each storing a result signal generated by the standard interface in response to application of the associated subquery signal,

B. said result assembler comprises:

i. a root buffer for storing a current assembled result signal, and

ii. a root fetch element for generating and storing in said root buffer an assembled result signal based on a result signal stored in one or more of selected subcursor buffers for, thereby, emptying those selected subcursor buffer, and

C. said query processor applying to said standard interface a subquery signal associated with an emptied one of said subcursor buffers, said subquery signal being applied to said standard interface asynchronously with respect to demand for a current assembled result signal.

19. A digital data processing system according to claim 14, wherein

A. said database table comprises a secondary data store for storing and retrieving signals representative of said data records,

B. said database management system (DBMS) includes

i. a selectively invocable hashing element for storing said data record-representative signals in hash bucket regions in said secondary data store, each such data record-representative signal 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,

ii) a selectively invocable indexer for selectively indexing each data record-representative signal so stored for access in accord with a respective value of the corresponding data record,

C. said query decomposer includes:

i) a hash bucket identifier for detecting whether said data record-representative signals are stored in said hash bucket regions based on a hash function of a value upon which those same data record-representative signals are indexed, and

ii) a record selection specifier for selectively specifying, in connection with applying said plural subquery signals to said standard interface, that said data record-representative signals are to be retrieved from said database table based on such indexing.

20. A digital data processing system according to claim 14, further comprising

A. a procedure/function call response element responsive to query signal in the form of a procedure/function call for invoking said parallel interface in lieu of said standard interface, and

B. said query decomposer selectively responds to such a query signal for generating a plurality of subquery signals in the form of further procedure/function calls for invoking said standard interface.

21. In a digital data processing system according to claim 1, wherein

A. said database table comprises a secondary data store for storing and retrieving signals representative of said data records,

B. said database management system (DBMS) includes

i. a selectively invocable hashing element for storing said data record-representative signals in hash bucket regions in said secondary data store, each such data record-representative signal 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,

ii) a selectively invocable indexer for selectively indexing each data record-representative signal so stored for access in accord with a respective value of the corresponding data record,

C. said query decomposer includes:

i) a hash bucket identifier for detecting whether said data record-representative signals are stored in said hash bucket regions based on a hash function of a value upon which those same data record-representative signals are indexed, and

ii) a record selection specifier for selectively specifying, in connection with applying said plural subquery signals to said standard interface, that said data record-representative signals are to be retrieved from said database table based on such indexing.

22. A digital data processing system according to claim 21, wherein said result assembler responds to at least a selected intercepted query signal, for generating said assembled result signal by variably interleaving the result signals generated by said DBMS in response to application of said plural subquery signals in an order, if any, specified by said intercepted query signal.

23. A digital data processing system according to claim 21, wherein said result assembler responds to at least a selected intercepted query signal representative of a request for access based on an aggregate function of said data records stored in said database table, for generating said assembled result signal as an aggregate function applied to the result signals generated by said DBMS in response to application of said plural subquery signals.

24. A digital data processing system according to claim 21, wherein

A. said subquery processor comprises a plurality of subcursor buffer sets, each associated with each of said subquery signals, each said subcursor buffer set comprising a plurality of subcursor buffers each storing a result signal generated by the standard interface in response to application of the associated subquery signal,

B. said result assembler comprises:

i. a root buffer for storing a current assembled result signal, and

ii. a root fetch element for generating and storing in said root buffer an assembled result signal based on a result signal stored in one or more of selected subcursor buffers for, thereby, emptying those selected subcursor buffers, and

C. said query processor applying to said standard interface a subquery signal associated with an emptied one of said subcursor buffers, said subquery signal being applied to said standard interface asynchronously with respect to demand for a current assembled result signal.

25. A digital data processing system according to claim 21, wherein

A. said database table comprises a secondary data store for storing and retrieving signals representative of said data records,

B. said database management system (DBMS) includes

i. a selectively invocable hashing element for storing said data record-representative signals in hash bucket regions in said secondary data store, each such data record-representative signal 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,

ii) a selectively invocable indexer for selectively indexing each data record-representative signal so stored for access in accord with a respective value of the corresponding data record,

C. said query decomposer includes:

i) a hash bucket identifier for detecting whether said data record-representative signals are stored in said hash bucket regions based on a hash function of a value upon which those same data record-representative signals are indexed, and

ii) a record selection specifier for selectively specifying, in connection with applying said plural subquery signals to said standard interface, that said data record-representative signals are to be retrieved from said database table based on such indexing.

26. A digital data processing system according to claim 21, further comprising

A. a procedure/function call response element responsive to query signal in the form of a procedure/function call for invoking said parallel interface in lieu of said standard interface, and

B. said query decomposer selectively responds to such a query signal for generating a plurality of subquery signals in the form of further procedure/function calls for invoking said standard interface.

27. A digital data processing system according to claim 1, wherein said result assembler in response to at least a selected intercepted query signal, generates said assembled result signal by variably interleaving the result signals generated by said DBMS in response to application of said plural subquery signals in an order, if any, specified by said intercepted query signal.

28. A digital data processing system according to claim 27, wherein said result assembler in response to at least a selected intercepted query signal representative of a request for access based on an aggregate function of said data records stored in said database table, generates said assembled result signal as an aggregate function applied to the result signals generated by said DBMS in response to application of said plural subquery signals.

29. A digital data processing system according to claim 27, wherein

A. said subquery processor comprises a plurality of subcursor buffer sets, each associated with each of said subquery signals, each said subcursor buffer set comprising a plurality of subcursor buffers each storing a result signal generated by the standard interface in response to application of the associated subquery signal,

B. said result assembler comprises:

i. a root buffer for storing a current assembled result signal, and

ii. a root fetch element for generating and storing in said root buffer an assembled result signal based on a result signal stored in one or more of selected subcursor buffers for, thereby, emptying those selected subcursor buffers, and

C. said query processor applying to said standard interface a subquery signal associated with an emptied one of said subcursor buffers, said subquery signal being applied to said standard interface asynchronously with respect to demand for a current assembled result signal.

30. A digital data processing system according to claim 27, wherein

A. said database table comprises a secondary data store for storing and retrieving signals representative of said data records,

B. said database management system (DBMS) includes

i. a selectively invocable hashing element for storing said data record-representative signals in hash bucket regions in said secondary data store, each such data record-representative signal 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,

ii) a selectively invocable indexer for selectively indexing each data record-representative signal so stored for access in accord with a respective value of the corresponding data record,

C. said query decomposer includes:

i) a hash bucket identifier for detecting whether said data record-representative signals are stored in said hash bucket regions based on a hash function of a value upon which those same data record-representative signals are indexed, and

ii) a record selection specifier for selectively specifying, in connection with applying said plural subquery signals to said standard interface, that said data record-representative signals are to be retrieved from said database table based on such indexing.

31. A digital data processing system according to claim 27, further comprising

A. a procedure/function call response element responsive to query signal in the form of a procedure/function call for invoking said parallel interface in lieu of said standard interface, and

B. said query decomposer selectively responds to such a query signal for generating a plurality of subquery signals in the form of further procedure/function calls for invoking said standard interface.

32. A digital data processing system according to claim 1, wherein said result assembler in response to at least a selected intercepted query signal representative of a request for access based on an aggregate function of said data records stored in said database table, generates said assembled result signal by applying the same aggregate function, or an aggregate function based thereon, to the result signals generated by said DBMS in response to application of said plural subquery signals.

33. A digital data processing system according to claim 32, wherein

A. said subquery processor comprises a plurality of subcursor buffer sets, each associated with each of said subquery signals, each said subcursor buffer set comprising a plurality of subcursor buffers each storing a result signal generated by the standard interface in response to application of the associated subquery signal,

B. said result assembler comprises:

i. a root buffer for storing a current assembled result signal, and

ii. a root fetch element for generating and storing in said root buffer an assembled result signal based on a result signal stored in one or more of selected subcursor buffers for, thereby, emptying those selected subcursor buffer, and

C. said query processor applying to said standard interface a subquery signal associated with an emptied one of said subcursor buffers, said subquery signal being applied to said standard interface asynchronously with respect to demand for a current assembled result signal.

34. A digital data processing system according to claim 32, further comprising

A. a procedure/function call response element responsive to query signal in the form of a procedure/function call for invoking said parallel interface in lieu of said standard interface, and

B. said query decomposer selectively responds to such a query signal for generating a plurality of subquery signals in the form of further procedure/function calls for invoking said standard interface.

35. A digital data processing system according to claim 32, wherein

A. said query decomposer is responsive to an intercepted query signal representative of a request for an average value of a selected datum from data records stored in a database table for generating said plural subquery signals to be representative of requests for a sum and count of said selected datum in respective partitions of that database table,

B. said result assembler is responsive to such an intercepted query signal for generating said assembled result signal as a function of the sum values and count values of said result signals generated by said DBMS in response to application of said subquery signals.

36. A digital data processing system according to claim 32, wherein

A. said query decomposer is responsive to an intercepted query signal representative of a request for any of a standard deviation and variance of selected data from data records stored in a database table for generating said plural subquery signals to be representative of requests for related functions of said selected data in said one or more respective partitions of that database table,

B. said result assembler is responsive to such an intercepted query signal for generating said assembled result signal as a function of said data represented by said result signals generated by said DBMS in response to application of said subquery signals.

37. A digital data processing system according to claim 32, wherein

A. said query decomposer is responsive to an intercepted query signal representative of a request for any of the following aggregate functions

i) a minimum of selected data from data records stored in a database table,

ii) a maximum of selected data from data records stored in a database table,

iii) a sum of selected data from data records stored in a database table,

iv) a count of data records in a database table,

v) a count of data records containing non-null values of selected data in a database table,

for generating said plural subquery signals to be representative of requests for said same aggregate function, or an aggregate function based thereon, on selected data in said one or more respective partitions of that database table,

B. said result assembler is responsive to such an intercepted query signal for generating said assembled result signal as a function of said result signals generated by said DBMS in response to said subquery signals.

38. A digital data processing system according to claim 32, wherein

A. said query decomposer is responsive to an intercepted query signal including a clause representative of a request for grouping of selected data from data records stored in a database table, for generating said plural subquery signals based on said intercepted query signal absent a having clause, if any, therein,

B. said result assembler is responsive to such an intercepted query signal for storing, in a further database table, data represented by said result signals, and applying to said standard interface a further query signal for application to said further database table, said further query signal being based on said intercepted query signal, including a having clause, if any, in said intercepted query signal and further including a group-by clause,

C. said result assembler further generates said assembled result signal as a function of said result signals generated by said DBMS in response to said further query signal.

39. A digital data processing system according to claim 1, wherein

A. said subquery processor comprises a plurality of subcursor buffer sets, each associated with each of said subquery signals, each said subcursor buffer set comprising a plurality of subcursor buffers each storing a result signal generated by the standard interface in response to application of the associated subquery signal,

B. said result assembler comprises:

i. a root buffer for storing a current assembled result signal, and

ii. a root fetch element for generating and storing in said root buffer an assembled result signal based on a result signal stored in one or more of selected subcursor buffers for, thereby, emptying those selected subcursor buffer, and

C. said query processor applying to said standard interface a subquery signal associated with an emptied one of said subcursor buffers, said subquery signal being applied to said standard interface asynchronously with respect to demand for a current assembled result signal.

40. A digital data processing system according to claim 39, wherein

A. said database table comprises a secondary data store for storing and retrieving signals representative of said data records,

B. said database management system (DBMS) includes

i. a selectively invocable hashing element for storing said data record-representative signals in hash bucket regions in said secondary data store, each such data record-representative signal 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,

ii) a selectively invocable indexer for selectively indexing each data record-representative signal so stored for access in accord with a respective value of the corresponding data record,

C. said query decomposer includes:

i) a hash bucket identifier for detecting whether said data record-representative signals are stored in said hash bucket regions based on a hash function of a value upon which those same data record-representative signals are indexed, and

ii) a record selection specifier for selectively specifying, in connection with applying said plural subquery signals to said standard interface, that said data record-representative signals are to be retrieved from said database table based on such indexing.

41. A digital data processing system according to claim 39, further comprising

A. a procedure/function call response element responsive to query signal in the form of a procedure/function call for invoking said parallel interface in lieu of said standard interface, and

B. said query decomposer selectively responds to such a query signal for generating a plurality of subquery signals in the form of further procedure/function calls for invoking said standard interface.

42. A digital data processing system according to claim 1, wherein

A. said database table comprises a secondary data store for storing and retrieving signals representative of said data records,

B. said database management system (DBMS) includes

i. a selectively invocable hashing element for storing said data record-representative signals in hash bucket regions in said secondary data store, each such data record-representative signal 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,

ii) a selectively invocable indexer for selectively indexing each data record-representative signal so stored for access in accord with a respective value of the corresponding data record,

C. said query decomposer includes:

i) a hash bucket identifier for detecting whether said data record-representative signals are stored in said hash bucket regions based on a hash function of a value upon which those same data record-representative signals are indexed, and

ii) a record selection specifier for selectively specifying, in connection with applying said plural subquery signals to said standard interface, that said data record-representative signals are to be retrieved from said database table based on such indexing.

43. A digital data processing system according to claim 42, further comprising

A. a procedure/function call response element responsive to query signal in the form of a procedure/function call for invoking said parallel interface in lieu of said standard interface, and

B. said query decomposer selectively responds to such a query signal for generating a plurality of subquery signals in the form of further procedure/function calls for invoking said standard interface.

44. In a digital data processing system according to claim 42, wherein said hashing element stores said data record-representative signals in hash bucket regions of a selected size, the improvement wherein said hash bucket region is sized to cause said DBMS to generate at least one overflow hash bucket region per root bucket region.

45. A digital data processing system according to claim 1, wherein

A. said query decomposer is responsive to an intercepted query signal representative of a request for distinct combinations of selected columns from data records stored in database table, for generating said plural subquery signals to be representative of requests for application of said function to said one or more respective partitions of that database table, and

B. said result assembler is responsive to such an intercepted query signal for generating said assembled result signal as said function of any data represented in said result signals generated by said DBMS in response to said subquery signals.

46. A digital data processing system according to claim 1, wherein

A. said query decomposer is responsive to an intercepted query signal representative of a request for application of any of the following functions to said database table:

i) a nested selection of data from data records stored in said database table, and

ii) a correlated nested selection of data from data records stored in said database table,

for generating said plural subquery signals to be representative of requests for application of said function to said one or more respective partitions of that database table,

B. said result assembler is responsive to such an intercepted query signal for generating said assembled result signal by interleaving the data represented by said result signals generated by said DBMS in response to application of said subquery signals.

47. A digital data processing system according to claim 1, wherein

A. said query decomposer is responsive to an intercepted query signal representative of a request for a sorted ordering of selected data from data records stored in said database table for generating said plural subquery signals to be representative of requests for a sorted ordering of said same selected datum in said one or more respective partitions of that database table,

B. said result assembler is responsive to such an intercepted query signal for generating said assembled result signal by interleaving, in an order specified by said query signal, the data represented by said result signals generated by said DBMS in response to application of said subquery signals.

48. A digital data processing system comprising

A. a database table comprising a secondary data store for storing and retrieving signals representative of said data records,

B. a database management system (DBMS) comprising

i. a selectively invocable hashing element for storing said data record-representative signals in hash bucket regions in said secondary data store, each such data record-representative signal 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,

ii) a selectively invocable indexer for selectively indexing each data record-representative signal so stored for access in accord with a respective value of the corresponding data record,

C. said query decomposer includes:

i) a hash bucket identifier for detecting whether said data record-representative signals are stored in said hash bucket regions based on a hash function of a value upon which those same data record-representative signals are indexed, and

ii) a record selection specifier for selectively specifying, in connection with applying said plural subquery signals to said standard interface, that said data record-representative signals are to be retrieved from said database table based on such indexing.

49. A digital data processing system according to claim 48, wherein said hash bucket identifier includes stores said data record-representative signals in hash bucket regions of a selected size, said hash bucket region being sized to cause said DBMS to generate at least one overflow hash bucket region per root bucket region.

50. A method of operating a digital data processing system of the type having a database table for storing data records in a plurality of independently accessible partitions, a database management system (DBMS) coupled to said database table, for accessing data records stored therein by any of a direct reference to said database table and to views thereof, said DBMS including a standard interface for receiving a query signal representative of a request for access to one or more selected data records and applying that request to said stored data records to generate a result signal representative of the result thereof, the method comprising the steps of

A. receiving a selected query signal representative of a request for access to selected data records in said database table,

B. decomposing said query to generate, from said intercepted query signal, a plurality of subquery signals, each representative of a request for access to data records stored in one or more respective partitions of said database table,

C. concurrently applying in a parallel processing step said plural subquery signals to said standard interface, and

D. responding in an assembly step to result signals generated in response to application of said subquery signals to generate an assembled result signal representative of a response to said query signal.

51. A method according to claim 50, said DBMS including said result signal as a function of a predicate list component of an applied query signal, said predicate list including zero, one or more predicates that evaluate true for data records requested by that query signal, wherein said decomposition step includes the step of responding to at least selected intercepted query signals for generating a plurality of subquery signals to be substantially identical to that query signal, which subquery signals additionally include in said predicate list an intersecting predicate that evaluates true for all data records in the respective partitions of said database table and evaluates false otherwise.

52. A method according to claim 50, wherein said standard interface is responsive to a query signal representative of an insert/select request for placing selected data from said database table in a further database table, the improvement wherein said decomposition step includes the step of responding to an intercepted signal representative of an insert/select request for generating said plural subquery signals to cause said standard interface to place said selected data in said further database table, said subquery signals being representative of requests for said selected data in said one or more respective partitions of that database table.

53. A method according to claim 50, wherein said system is of the type has plural database tables each for storing a respective plurality of data records in a plurality of independently accessible partitions, a database management system (DBMS) coupled to said plural database tables, for accessing data records stored therein by any of a direct reference to said database table and to views thereof, said DBMS including standard interface for receiving a query signal representative of a request for access to data records joined from one or more of said plural database table for applying corresponding requests to said plural database table to generate a result signal representative of the results thereof, said DBMS being responsive a query signal for determining an optimal order for applying the corresponding request to said plural database tables and for generating a strategy signal representative thereof, said DBMS generating said result signal as a function of a predicate list component of an applied query signal, said predicate list including zero, one or more predicates that evaluate true for data records requested by that query signal, wherein the decomposition step includes the steps of

A. responding to said strategy signal for identifying a driving database table, and

B. responding to an intercepted query signal representative of a request for access to data records joined from said plural database table for generating said plural subquery signals to additionally include in said predicate list an intersecting predicate that evaluates true for all data records in the respective partitions of the driving database table and evaluates false otherwise.

54. A method according to claim 50, wherein said assembly step includes the step of responding to at least a selected intercepted query signal, for generating said assembled result signal by variably interleaving the result signals generated by said DBMS in response to application of said plural subquery signals in an order, if any, specified by said intercepted query signal.

55. A method according to claim 50, wherein said assembly step includes the step of responding to at least a selected intercepted query signal representative of a request for access based on an aggregate function of said data records stored in said database table, for generating said assembled result signal as an aggregate function applied to the result signals generated by said DBMS in response to application of said plural subquery signals.

56. A method according to claim 55, wherein

A. said decomposition step includes the step of responding to an intercepted query signal representative of a request for an average value of a selected datum from data records stored in a database table for generating said plural subquery signals to be representative of requests for a sum and count of said selected datum in respective partitions of that database table, and

B. said assembly step includes the step of responding to such an intercepted query signal for generating said assembled result signal as a function of the sum values and count values of said result signals generated by said DBMS in response to application of said subquery signals.

57. A method according to claim 55, wherein

A. said decomposition step includes the step of responding to an intercepted query signal representative of a request for any of a standard deviation and variance of selected data from data records stored in a database table for generating said plural subquery signals to be representative of requests for related functions of said selected data in said one or more respective partitions of that database table, and

B. said assembly step includes the step of responding to such an intercepted query signal for generating said assembled result signal as a function of said data represented by said result signals generated by said DBMS in response to application of said subquery signals.

58. A method according to claim 55, wherein

A. said decomposition step includes the step of, in response to an intercepted query signal representative of a request for any of the following aggregate functions

i) a minimum of selected data from data records stored in a database table,

ii) a maximum of selected data from data records stored in a database table,

iii) a sum of selected data from data records stored in a database table,

iv) a count of data records in a database table, or

v) a count of data records containing non-null values of selected data in a database table,

generating said plural subquery signals to be representative of requests for said same aggregate function, or an aggregate function based thereon, on selected data in said one or more respective partitions of that database table,

B. said assembly step including the step of, responsive to such an intercepted query signal, generating said assembled result signal as a function of said result signals generated by said DBMS in response to said subquery signals.

59. A method according to claim 55, wherein

A. said decomposition step includes the step of responding to an intercepted query signal including a clause representative of a request for grouping of selected data from data records stored in a database table, for generating said plural subquery signals based on said intercepted query signal absent a having clause, if any, therein,

B. said assembly step includes the steps of

i. responding to such an intercepted query signal for storing, in a further database table, data represented by said result signals, and applying to said standard interface a further query signal for application to said temporary database table, said further query signal being based on said intercepted query signal, including a having clause, if any, in said intercepted query signal and further including a group-by clause, and

ii. generating said assembled result signal as a function of said result signals generated by said DBMS in response to said further query signal.

60. A method according to claim 55, wherein

A. said parallel process step includes the step of providing a plurality of subcursor buffer sets, one associated with each of said subquery signals, each said subcursor buffer set comprising a plurality of subcursor buffers, each for storing a result signal generated by the standard interface in response to application of the associated subquery signal,

B. said assembly step includes the steps of

i. providing a root buffer for storing a current assembled result signal, and

ii. generating and storing in said root buffer an assembled result signal based on a result signal stored in one or more of selected subcursor buffers and for, thereby, emptying those selected subcursor buffers, and

C. said parallel process step includes the step of applying to said standard interface a subquery signal associated with an emptied one of said subcursor buffers, said subquery signal being applied to said standard interface asynchronously with respect to demand for a current assembled result signal.

61. A method according to claim 50, said digital data processing system further comprising a secondary data store for storing and retrieving signals representative of said data records, and database management system (DBMS) includes

i. a selectively invocable hashing element for storing said data record-representative signals in hash bucket regions in said secondary data store, each such data record-representative signal 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,

ii) a selectively invocable indexer for selectively indexing each data record-representative signal so stored for access in accord with a respective value of the corresponding data record,

said query decomposition step including the steps of:

A) detecting whether said data record-representative signals are stored in said hash bucket regions based on a hash function of a value upon which those same data record-representative signals are indexed, and

B) selectively specifying, in connection with applying said plural subquery signals to said standard interface, that said data record-representative signals are to be retrieved from said database table based on such indexing.

62. A method according to claim 61, said system responding to query signal in the form of a procedure/function call for invoking said standard interface,

A. the method further comprising the step of responding to a query signal in the form of a procedure/function call for invoking said parallel interface in lieu of said standard interface,

B. said decomposition step includes the step of selectively responding to such a query signal for generating a plurality of subquery signals in the form of further procedure/function calls for invoking said standard interface.

63. A method according to claim 62, wherein said parallel process step includes the step of providing a plurality of threads, each for applying a respective one of said subquery signal to said DBMS.

64. A method according to claim 63, further comprising the step of executing in parallel said plurality of threads on a plurality of central processing units.

65. A method according to claim 61, wherein said hashing step includes the step of storing said data record-representative signals in hash bucket regions of a selected size, the improvement wherein the hash bucket region is sized to cause said DBMS to generate at least one overflow hash bucket region per root bucket region.

66. A method according to claim 62, wherein said standard interface comprises an object code library, and said query signal comprises at least a portion of a sequence of computer programming instructions capable of linking with such an object code library, wherein said parallel interface step comprises the step of providing an object code library for linking with said sequence of computer programming instructions.

67. A method according to claim 50, wherein

A. said query decomposition step includes the step of, responsive to an intercepted query signal representative of a request for distinct combinations of selected columns from data records stored in database table, generating said plural subquery signals to be representative of requests for application of said function to said one or more respective partitions of that database table, and

B. said result assembler step include the step of, responsive to such an intercepted query signal, generating said assembled result signal as said function of any data represented in said result signals generated by said DBMS in response to said subquery signals.

68. A method according to claim 50, wherein

A. said query decomposition step includes the step of, responsive to an intercepted query signal representative of a request for application of any of the following functions to said database table

i) a nested selection of data from data records stored in said database table, and

ii) a correlated nested selection of data from data records stored in said database table,

generating said plural subquery signals to be representative of requests for application of said function to said one or more respective partitions of that database table, and

B. said result assembler step includes the step of, responsive to such an intercepted query signal, generating said assembled result signal by the data represented by said result signals generated by said DBMS in response to application of said subquery signals.

69. A method according to claim 50, wherein

A. said query decomposition step includes the step of, responsive to an intercepted query signal representative of a request for a sorted ordering of selected data from data records stored in said database table, generating said plural subquery signals to be representative of requests for a sorted ordering of said same selected datum in said one or more respective partitions of that database table, and

B. said result assembler step includes the step of, responsive to such an intercepted query signal, generating said assembled result signal by interleaving, in an order specified by said query signal, the data represented by said result signals generated by said DBMS in response to application of said subquery signals.

70. A method of operating a digital data processing system comprising a secondary data store for storing and retrieving signals representative of said data records, and database management system (DBMS) includes

i. a selectively invocable hashing element for storing said data record-representative signals in hash bucket regions in said secondary data store, each such data record-representative signal 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,

ii) a selectively invocable indexer for selectively indexing each data record-representative signal so stored for access in accord with a respective value of the corresponding data record,

said method decomposing a query, including the steps of:

A) detecting whether said data record-representative signals are stored in said hash bucket regions based on a hash function of a value upon which those same data record-representative signals are indexed, and

B) selectively specifying, in connection with applying said plural subquery signals to said standard interface, that said data record-representative signals are to be retrieved from said database table based on such indexing.

71. A method according to claim 70, wherein said hashing step stores said data record-representative signals in hash bucket regions sized to cause said DBMS to generate at least one overflow hash bucket region per root bucket region.