Optimizing Queries to Hierarchically Structured Data

• US 20110125730A1
• Filed: 11/24/2009
• Published: 05/26/2011
• Est. Priority Date: 11/24/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kementsietsidis, Anastasios, Bordawekar, Rajesh, Kok, Bryant Wei Lun, Lim, Lipyeow
• Granted Patent: US 8,285,711 B2
• Time in Patent Office: Days
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/8365 Query optimisation

Abstract

Techniques are disclosed for optimizing queries to hierarchically structured data. For example, a method for processing a query directed to data having a hierarchical structure with a plurality of data nodes comprises the following steps. One or more structural attributes describing the hierarchical structure of the data are identified. The query is partitioned into two or more query partitions using at least one of the one or more identified structural attributes. A parallel execution plan is determined for the query by splitting into components one or more of: the query into at least two of the query partitions; and the hierarchical structure of the data. The split components are executed in parallel on different computer processes according to the parallel execution plan.

Claims

1. A method for processing a query directed to data having a hierarchical structure with a plurality of data nodes, the method comprising steps of:

identifying one or more structural attributes describing the hierarchical structure of the data;

partitioning the query into two or more query partitions using at least one of the one or more identified structural attributes;

determining a parallel execution plan for the query by splitting into components one or more of;

the query into at least two of the query partitions; and

the hierarchical structure of the data; and

executing the split components in parallel on different computer processes according to the parallel execution plan.

2. The method of claim 1, wherein the computer processes comprise one or more of:

a computer processor and a computer program.

3. The method of claim 1, wherein the splitting step comprises counting the number of data nodes in the hierarchically structured data for one or more node types that are referenced in the query.

4. The method of claim 3, wherein the split is controlled by an optimizing function.

5. The method of claim 3, further comprising counting the number of one or more child nodes, if any, for each data node with a node type.

6. The method of claim 3, further comprising counting the number of one or more child nodes, if any, of a child node type for each data node with a node type.

7. The method of claim 3, wherein a node type is a tag.

8. The method of claim 1, wherein the parallel execution plan splits only the hierarchical structure of the data.

9. The method of claim 1, wherein the parallel execution plan splits only the query into at least two partitions.

10. The method of claim 1, wherein the parallel execution plan splits both the hierarchical structure of the data and the query.

11. The method of claim 1, wherein the parallel execution plan comprises:

one or more of;

a sequential execution of the query partitions; and

an execution of two or more query partitions together to obtain a result and then executing a next query partition over the result.

12. The method of claim 1, where the hierarchical structure of the data comprises one or more of a tree structure, an XML structure, an XPath in an XML structure, a directory, an ontology, and a tree structure derived from a database.

13. A method for partitioning queries in order to query hierarchically structured data comprising steps of:

identifying one or more structural attributes describing the hierarchically structure of the data;

partitioning one or more queries into two or more query partitions using at least one of the structural attributes; and

determining a parallel execution plan to execute at least two of the query partitions in parallel on different computer processes, wherein the parallel execution plan determines and implements an optimal choice of executing the query partitions in parallel.

14. Apparatus for processing a query directed to data having a hierarchical structure with a plurality of data nodes, the apparatus comprising:

a memory; and

one or more processor devices coupled to the memory and configured to;

identify one or more structural attributes describing the hierarchical structure of the data;

partition the query into two or more query partitions using at least one of the one or more identified structural attributes;

determine a parallel execution plan for the query by splitting into components one or more of;

the query into at least two of the query partitions; and

the hierarchical structure of the data;

such that the split components are executed in parallel on different computer processes according to the parallel execution plan.

15. The apparatus of claim 14, wherein the computer processes comprise one or more of:

a computer processor and a computer program.

16. The apparatus of claim 14, wherein the splitting operation comprises counting the number of data nodes in the hierarchically structured data for one or more node types that are referenced in the query.

17. The apparatus of claim 14, wherein the parallel execution plan splits only the hierarchical structure of the data.

18. The apparatus of claim 14, wherein the parallel execution plan splits only the query into at least two partitions.

19. The apparatus of claim 14, wherein the parallel execution plan splits both the hierarchical structure of the data and the query.

20. An article of manufacture for processing a query directed to data having a hierarchical structure with a plurality of data nodes, the article of manufacture tangibly embodying a computer readable program code which, when executed, causes the computer to:

identify one or more structural attributes describing the hierarchical structure of the data;

partition the query into two or more query partitions using at least one of the one or more identified structural attributes;

determine a parallel execution plan for the query by splitting into components one or more of;

the query into at least two of the query partitions; and

the hierarchical structure of the data; and

cause execution of the split components in parallel on different computer processes according to the parallel execution plan.