Optimizing queries to hierarchically structured data

• US 8,285,711 B2
• Filed: 11/24/2009
• Issued: 10/09/2012
• Est. Priority Date: 11/24/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bordawekar, Rajesh, Kementsietsidis, Anastasios, Lim, Lipyeow, Kok, Bryant Wei Lun
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US12/624,675
• Publication Number:
  US 20110125730A1
• Time in Patent Office: 1,050 Days
• Field of Search: 707/759, 707/760, 707/770, 707/769, 707/713, 707718-719
• 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 evaluation strategies comprising;

a first strategy which splits the query into at least two of the query partitions;

a second strategy which splits the hierarchical structure of the data; and

a third strategy which splits both the query and the hierarchical structure of the data;

selecting one of the evaluated strategies as the parallel execution plan to be executed; and

executing the selected parallel execution plan in parallel on different computer processes.

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 hierarchically structured data 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. Apparatus for processing a query directed b 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 evaluating strategies comprising;

a first strategy which splits the query into at least two of the query partitions;

a second strategy which splits the hierarchical structure of the data; and

a third strategy which splits both the query and the hierarchical structure of the data;

select one of the evaluated strategies as the parallel execution to be executed;

execute the selected parallel execution plan in parallel on different computer processes.

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

a computer processor and a computer program.

15. The apparatus of claim. 13, wherein the hierarchically structured data 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.

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

17. The apparatus of claim 13 herein e parallel execution plan splits only the query into at least two partitions.

18. The apparatus of claim 13 wherein the parallel execution plan splits both the hierarchical structure of the data and the query.

19. 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 comprising a computer readable storage medium for storing a computer readable program code which, when executed by a computer, 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 evaluating strategies comprising;

a first strategy which splits the query into at least two of the query partitions;

a second strategy which splits the hierarchical structure of the data; and

a third strategy which splits both the query and the hierarchical structure of the data;

select one of the evaluated strategies as the parallel execution plan to be executed; and

cause execution of the selected parallel execution plan in parallel on different computer processes.