Object-oriented query execution data structure

• US 6,915,291 B2
• Filed: 06/07/2002
• Issued: 07/05/2005
• Est. Priority Date: 06/07/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kathmann, Kevin James, Hermsmeier, David Lee, Carlson, David Glenn, McKinley, Thomas Owen
• Primary Examiner(s): Kindred, Alford W.
• Application Number:
  US10/165,293
• Publication Number:
  US 20030229627A1
• Time in Patent Office: 1,124 Days
• Field of Search: 707 1- 4, 707101-103, 715/514
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• 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/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

An apparatus, program product and method represent a database query access plan a query execution data structure including a plurality of query node objects arranged into a tree relationship to define a parent node object and at least one child node object, and an attribute data structure that references a plurality of attributes utilized by the query execution data structure. At least one of the parent and child node objects includes an attribute operation data structure configured to manipulate at least a subset of the plurality of attributes in the attribute data structure by accessing the attribute operation data structure. By partitioning the functionality of a query access plan into a collection of node objects and an attribute data structure, and then providing within at least a subset of the node objects attribute operation data structures that manipulate the attribute data structure, the resulting query engine architecture becomes significantly extendible and adaptable. Moreover, through appropriate selection of attribute operations, and coding of such operations using directly executable program code, optimal query engine performance may also be obtained.

Claims

1. A method of executing a query, comprising:

(a) accessing, from a query execution data structure representative of a database query access plan for the query, at least one of a parent node object and a child node object from among a plurality of query node objects arranged into a tree relationship; and

(b) manipulating at least a subset of a plurality of attributes referenced in an attribute data structure defined in the query execution data structure by processing at least one operation defined in an attribute operation data structure defined in the accessed node object, wherein processing the operation includes obtaining a reference for at least one attribute in the subset of attributes from the attribute data structure;

wherein at least one of the plurality of node objects in selected from a library of node objects, and wherein the plurality of node objects includes a node object selected from the group consisting of a unary node object, a binary node object, a leaf node object and a join-type node object.

2. The method of claim 1, wherein the attribute data structure is global to the plurality of node objects.

3. The method of claim 2, wherein at least one of the child nodes is configured to communicate with the parent node by modifying an attribute referenced in the attribute data structure.

4. The method of claim 1, wherein at least one of the child nodes is configured to return a status to the parent node upon execution of such child node by the parent node.

5. The method of claim 1, wherein the attribute data structure comprises an attribute descriptor array including a plurality of entries, each entry indexed by a unique index, and including a pointer to an attribute from among the plurality of attributes, and wherein a node from among the plurality of nodes is configured to access an attribute from among the plurality of attributes by accessing the attribute descriptor array entry including a pointer to such attribute.

6. The method of claim 5, wherein the plurality of attributes include at least one attribute selected from the group consisting of a dataspace attribute, an intermediate result attribute, and a result buffer attribute.

7. The method of claim 1, wherein the attribute operation data structure comprises an attribute operation list.

8. The method of claim 7, wherein the attribute operation list includes a plurality of entries, each entry associated with an operation to be performed during execution of the attribute operation list.

9. The method of claim 7, wherein the accessed node object includes additional logic configured to execute the attribute operation list.

10. A method of building an access plan for a query, comprising:

(a) generating a query execution data structure;

(b) populating the query execution data structure with an attribute data structure that references a plurality of attributes to be used during execution of a query;

(c) populating the query execution data structure with a plurality of node objects arranged into a tree relationship, the plurality of node objects including at least one parent node object and a child node object, and

(d) populating at least one of the parent and child node objects with an attribute operation data structure configured to manipulate at least a subset of the plurality of attributes by accessing the attribute operation data structure;

wherein at least one of the plurality of node objects is selected from a library of node objects, and wherein the plurality of node objects includes a node object selected from the group consisting of a unary node object, a binary node object, a leaf node object and a join-type node object.

11. The method of claim 10, wherein populating the query execution data structure with a plurality of node objects includes selecting at least one node object from a library of node objects.

12. An apparatus, comprising:

(a) a memory within which is resident a query execution data structure representative of a database query access plan, the query execution data structure including a plurality of query node objects arranged into a tree relationship to define a parent node object and at least one child node object, and an attribute data structure that references a plurality of attributes utilized by the query execution data structure, wherein at least one of the parent and child node objects includes an attribute operation data structure configured to manipulate at least a subset of the plurality of attributes by accessing the attribute operation data structure; and

(b) program code configured to access the query execution data structure resident in the memory;

wherein at least one of the plurality of node objects is selected from a library of node objects, and wherein the plurality of node objects includes a node object selected from the group consisting of a unary node object, a binary node object, a leaf node object and a join-type node object.

13. The apparatus of claim 12, wherein the program code is configured to access the query execution data structure by manipulating at least a subset of the plurality of attributes referenced in an attribute data structure defined in the query execution data structure by processing at least one operation defined in the attribute operation data structure.

14. The apparatus of claim 12, wherein the attribute data structure is global to the plurality of node objects.

15. The apparatus of claim 14, wherein at least one of the child nodes is configured to communicate with the parent node by modifying an attribute referenced in the attribute data structure.

16. The apparatus of claim 12, wherein at least one of the child nodes is configured to return a status to the parent node upon execution of such child node by the parent node.

17. The apparatus of claim 12, wherein the attribute data structure comprises an attribute descriptor array including a plurality of entries, each entry indexed by a unique index, and including a pointer to an attribute from among the plurality of attributes, and wherein a node from among the plurality of nodes is configured to access an attribute from among the plurality of attributes by accessing the attribute descriptor array entry including a pointer to such attribute.

18. The apparatus of claim 17, wherein the plurality of attributes include at least one attribute selected from the group consisting of a dataspace attribute, an intermediate result attribute, and a result buffer attribute.

19. The apparatus of claim 12, wherein the attribute operation data structure comprises an attribute operation list.

20. The apparatus of claim 19, wherein the attribute operation list includes a plurality of entries, each entry associated with an operation to be performed during execution of the attribute operation list.

21. The apparatus of claim 19, wherein the accessed node object includes additional logic configured to execute the attribute operation list.

22. The apparatus of claim 12, wherein the program code is further configured to generate the query execution data structure by populating the query execution data structure with the attribute data structure and the plurality of node objects.

23. A program product, comprising:

(a) a query execution data structure representative of a database query access plan, the query execution data structure including a plurality of query node objects arranged into a tree relationship to define a parent node object and at least one child node object, and an attribute data structure that references a plurality of attributes utilized by the query execution data structure, wherein at least one of the parent and child node objects includes an attribute operation data structure configured so manipulate at least a subset of the plurality of attributes by accessing the attribute operation data structure; and

(b) a signal bearing medium bearing the query execution data structure;

wherein at least one of the plurality of node objects is selected from a library of node objects, and wherein the plurality of node objects includes a node object selected from the group consisting of a unary node object, a binary node object, a leaf node object and a join-type node object.

24. The program product of claim 23, wherein the sign bearing medium includes at least one of a transmission medium and a recordable medium.