Method of two pass processing for relational queries in a database system and corresponding database system

• US 9,400,815 B2
• Filed: 07/11/2012
• Issued: 07/26/2016
• Est. Priority Date: 07/04/2012
• Status: Active Grant

• Current Assignee: Software AG
• Original Assignee: Sotfwar AG
• Inventors: Poppitz, Michael
• Primary Examiner(s): Liao, Jason
• Application Number:
  US13/546,564
• Publication Number:
  US 20140012882A1
• Time in Patent Office: 1,476 Days
• Field of Search: 707/616
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement

Abstract

Certain example embodiments concern a computer-implemented method of processing a relational query in a database system. The relational query addresses a plurality of data objects linked by one or more relationships. For each data object addressed by the relational query, at least one result is computed in accordance with at least one index structure, with the index structure being stored in a storage device of the database system. The results computed are merged in accordance with at least one translation data structure to produce a final result of the relational query, with the translation data structure representing the one or more relationships between the data objects and being stored in a memory of the database system.

Claims

1. A computer-implemented method of processing a relational query in a database system that includes volatile memory and non-volatile storage, the non-volatile storage storing a database of the database system, wherein the relational query, which is represented as a query tree, addresses a plurality of data objects linked by one or more relationships that are included in the database, the method comprising:

a. for each data object addressed by the relational query, computing, in connection with a processor, at least one result in accordance with at least one index structure, the index structure being stored in a storage device of the database system; and

b. merging, in connection with a or the processor, the results computed in (a) in accordance with at least one translation data structure to produce a final result of the relational query, where each edge between nodes of the query tree includes a corresponding translation data structure that represents the one or more relationships between the data objects, the translation data structure being stored in a memory of the database system,

wherein the merging further comprises at least two passes;

performing a first merging as part of a first pass of processing the query tree, wherein the first pass is performed recursively on nodes of the query tree, where results of a child node of a first node are merged, using a corresponding translation data structure included with the edge of the query tree between the first node and the child node, into results of the first node to obtain intermediate results for the first node, and

performing a second merging as part of a second pass, after the first pass, of processing the query tree, wherein the second pass is performed recursively on nodes of the query tree, where the obtained intermediate results of the first node are merged, using a corresponding translation data structure included with the edge of the query tree between the first node and the child of the first node, into results of the child node to obtain results for the child node.

2. The method of claim 1, wherein the first merging comprises merging the results of each child node into the results of a corresponding parent node(s).

3. The method of claim 1, wherein the second merging comprises merging the results of each node into the results of a corresponding child node.

4. The method of claim 1, wherein the first pass and/or the second pass of processing the query tree traverses the query tree starting at the root node in a depth-first manner.

5. The method of claim 1, wherein for two given data objects which are addressed by the relational query and which are linked by a relationship, the translation data structure comprises a mapping of an identifier of the first data object to an identifier of the second data object in accordance with the relationship.

6. The method of claim 5, wherein, if the relationship is represented as a data object in a database of the database system, the translation data structure comprises a mapping of an identifier of the first data object to an identifier of the second data object and to an identifier of the relationship.

7. The computer-implemented method of claim 1, wherein during processing the relational query, data on the non-volatile storage is only accessed in indexed form for reading results for individual query conditions.

8. A non-transitory computer readable storage medium tangibly storing a computer program for processing a relational query, which is represented as a query tree, in a database system that includes at least one processor, wherein the relational query addresses a plurality of data objects linked by one or more relationships, the stored instructions comprising instructions that are configured to cause the processing system to:

for each data object addressed by the relational query, compute at least one result in accordance with at least one index structure, the index structure being stored in a storage device of the database system; and

merge the results computed in (a) in accordance with at least one translation data structure to produce a final result of the relational query, where each edge between nodes of the query tree is linked to a corresponding translation data structure that represents the one or more relationships between the data objects, the translation data structure being stored in a memory of the database system,

wherein the merging further comprises;

perform a first merging as part of a first pass of processing the query tree, wherein the first pass is performed recursively on nodes of the query tree, where results of a child node of a first node of the query tree are merged, using a translation data structure linked to the edge that is between the child node and the first node of the query tree, into results of the first node to obtain intermediate results for the first node, and

perform a second merging as part of a second pass, after the first pass, of processing the query tree, wherein the second pass is performed recursively on nodes of the query tree, where the intermediate results of the first node are merged, using a corresponding translation data structure linked to the edge of the query tree that is between the first node and the child of the first node, into results of the child node to obtain results for the child node.

9. A database system, comprising:

a. an interface configured to receive relational queries which address a plurality of data objects linked by one or more relationships;

b. a storage device configured to store at least one index structure;

c. a memory configured to store at least one translation data structure representing the one or more relationships between the data objects;

d. control logic that, in connection with at least one processor, is configured to at least;

as part of a first pass, for each data object addressed by the relational query, compute at least one result of a first node in a query tree of the relational query in accordance with the at least one translation index structure, where each edge between nodes of the query tree is linked to a corresponding translation index structure that is stored in the memory;

as part of the first pass, merge, using a corresponding translation index structure that is linked to the edge between a child of the first node and the first node, the computed results of the child of the first node into results with results of the first node to produce an intermediate result of the relational query for the first node;

as part of a second pass that is performed after the first pass, merge, using the corresponding translation index structure that is linked to the edge between the child of the first node and the first node, the computed intermediate results of the first node into results of the child node to obtain results for the child node.

10. The database system of claim 9, wherein the first pass is performed recursively for each node of the query tree.

11. The database system of claim 9, wherein the second pass is performed recursively for each node of the query tree.

12. The database system of claim 10, wherein the first pass and/or the second pass of processing the query tree traverses the query tree starting at the root node in a depth-first manner.