SYSTEM AND METHOD FOR PARALLEL QUERY EVALUATION

• US 20090271385A1
• Filed: 04/28/2009
• Published: 10/29/2009
• Est. Priority Date: 04/28/2008
• Status: Active Grant

• Current Assignee: Infosys Limited
• Original Assignee: Infosys Technologies Limited (Infosys Limited)
• Inventors: Gagrani, Aakanksha, Achutharao, Prahalad Haldhoderi, S., Shanmugavel, Krishnamoorthy, Srikumar
• Granted Patent: US 8,386,508 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries

Abstract

A method and system for parallel query processing is provided. The method includes estimating a number of sub-queries that may be formed corresponding to an input query. The method further includes fragmenting the input query into a plurality of sub queries by adding one or more filter predicates to the input query without altering the semantics of the input query. Further, processing of the sub queries is scheduled. Thereafter, one or more query execution plans are generated and processed. Following the processing of the query execution plans, the results of the processed sub queries are collated, aggregated and presented in a required format.

Claims

1. A system for parallel query processing comprising:

a. a query fragment identifier module for estimating a number of sub-queries that may be formed corresponding to an input query based on a number of query evaluator nodes available for processing the input query and processing characteristics of the available query evaluator nodes, the query evaluator nodes accessing one or more databases being referenced by the input query for processing the input query;

b. a query splitter module for fragmenting the input query into a plurality of sub queries by adding one or more filter predicates to the input query without altering the semantics of the input query;

c. a scheduler for scheduling the processing of the sub queries;

d. a result aggregator module for aggregating results of the processed sub queries;

e. a streaming module for streaming results of the processed sub queries; and

f. a metadata manager for storing processing characteristics of the one or more query evaluator nodes and information regarding the one or more databases being referenced by the input query.

2. The system as claimed in claim 1 further comprises a plurality of query optimizer nodes for generating optimal query plans comprising one or more query partitions for processing the fragmented input query.

3. The system as claimed in claim 1 wherein the input query is written in a structured query language.

4. The system as claimed in claim 1 wherein the query fragment identifier module estimates the number of sub-queries that may be formed corresponding to the input query as equal to a number of healthy query evaluator nodes available for processing the input query;

a query evaluator node being selected as healthy based on memory required for storing each record of a predetermined table of a predetermined database being referenced by the input query and available memory and processing speed of the evaluator node.

5. The system as claimed in claim 1 wherein the scheduler schedules the sub queries for processing by using a round robin algorithm.

6. The system as claimed in claim 1 wherein the metadata manager is updated periodically and comprises a machine characteristics repository and a database characteristics repository.

7. The system as claimed in claim 6 wherein the database characteristics repository stores physical and logical metadata information corresponding to the one or more databases being referenced by the input query;

logical metadata information comprising information regarding schema of the one or more databases being referenced by the input query;

physical metadata information comprising information regarding statistics of the one or more databases being referenced by the input query.

8. The system as claimed in claim 6 wherein the database characteristics repository stores names of the one or more databases being referenced by the input query, names of the one or more tables being referenced by the input query, attribute names obtained from the one or more tables being referenced by the input query as active keys, data types of the active keys, and ranges of the active keys.

9. A method for parallel query processing comprising the steps of:

a. estimating a number of sub-queries that may be formed corresponding to an input query;

b. fragmenting the input query into a plurality of sub queries by adding one or more filter predicates to the input query without altering the semantics of the input query;

c. scheduling the processing of the sub queries;

d. generating one or more query execution plans comprising one or more query partitions corresponding to each sub query;

e. processing the generated one or more query execution plans; and

f. collating, aggregating and presenting results of the processed sub queries in a required format.

10. The method as claimed in claim 9 further comprising the step of streaming the results of the processed sub queries in a required format.

11. The method as claimed in claim 9 wherein the step of estimating a number of sub-queries that may be formed corresponding to an input query comprises the steps of:

a. parsing the input query and extracting one or more query attributes for obtaining references to one or more databases and tables corresponding to the input query;

b. selecting a first database that corresponds to at least one of the extracted attributes and table combination as a base database;

c. selecting a table from the base database based on a number of records contained in the table;

d. computing memory required for storing the selected table;

e. obtaining available memory and processing speed of each evaluator node available for processing the input query;

f. selecting an evaluator node available for processing the input query as a healthy evaluator node if the available memory corresponding to the evaluator node is greater than or equal to half of the computed and if the processing speed of the evaluator node is greater than a predetermined threshold; and

g. estimating a number of sub-queries that may be formed corresponding to the input query as the number of selected healthy evaluator nodes.

12. The method as claimed in claim 9 wherein the step of fragmenting the input query into a plurality of sub queries by adding one or more filter predicates to the input query without altering the semantics of the input query comprises the steps of:

a. classifying the input query into query sub-segments;

b. determining suitability of the input query for fragmentation by analyzing the query sub-segments;

c. determining if a ‘

where’

sub-segment of the input query comprises an ‘

OR’

operation and does not comprise a ‘

group-by’

operator;

d. fragmenting the input query into one or more sub queries by using the ‘

OR’

operator if the ‘

where’

sub-segment of the input query comprises an ‘

OR’

operation and does not comprise a ‘

group-by’

operator; and

e. fragmenting the input query into one or more sub queries by using an active key of the database table being referenced by the input query if the ‘

where’

sub-segment of the input query comprises an ‘

OR’

operation and does not comprise a ‘

group-by’

operator.

13. A computer program product comprising a computer usable medium having a computer readable program code embodied therein for parallel query processing comprising:

a. program instruction means for estimating a number of sub-queries that may be formed corresponding to an input query;

b. program instruction means for fragmenting the input query into a plurality of sub queries by adding one or more filter predicates to the input query without altering the semantics of the input query;

c. program instruction means for scheduling the processing of the sub queries;

d. program instruction means for generating one or more query execution plans comprising one or more query partitions corresponding to each sub query;

e. program instruction means for processing the generated one or more query execution plans; and

f. program instruction means for collating, aggregating and presenting results of the processed sub queries in a required format.

14. The computer program product as claimed in claim 13 further comprising program instruction means for streaming the results of the processed sub queries in a required format.

15. The computer program product as claimed in claim 13 wherein the program instruction means for estimating a number of sub-queries that may be formed corresponding to an input query comprises:

a. program instruction means for parsing the input query and extracting one or more query attributes for obtaining references to one or more databases and tables corresponding to the input query;

b. program instruction means for selecting a first database that corresponds to at least one of the extracted attributes and table combination as a base database;

c. program instruction means for selecting a table from the base database based on a number of records contained in the table;

d. program instruction means for computing memory required for storing the selected table;

e. program instruction means for obtaining available memory and processing speed of each evaluator node available for processing the input query;

f. program instruction means for selecting an evaluator node available for processing the input query as a healthy evaluator node if the available memory corresponding to the evaluator node is greater than or equal to half of the computed and if the processing speed of the evaluator node is greater than a predetermined threshold; and

g. program instruction means for estimating a number of sub-queries that may be formed corresponding to the input query as the number of selected healthy evaluator nodes.

16. The computer program product as claimed in claim 13 wherein the program instruction means for fragmenting the input query into a plurality of sub queries by adding one or more filter predicates to the input query without altering the semantics of the input query comprises:

a. program instruction means for classifying the input query into query sub-segments;

b. program instruction means for determining suitability of the input query for fragmentation by analyzing the query sub-segments;

c. program instruction means for determining if a ‘

where’

sub-segment of the input query comprises an ‘

OR’

operation and does not comprise a ‘

group-by’

operator;

d. program instruction means for fragmenting the input query into one or more sub queries by using the ‘

OR’

operator if the ‘

where’

sub-segment of the input query comprises an ‘

OR’

operation and does not comprise a ‘

group-by’

operator; and

e. program instruction means for fragmenting the input query into one or more sub queries by using an active key of the database table being referenced by the input query if the ‘

where’

sub-segment of the input query comprises an ‘

OR’

operation and does not comprise a ‘

group-by’

operator.