SYSTEM, METHOD, AND COMPUTER-READABLE MEDIUM FOR OPTIMIZING PROCESSING OF GROUP-BY QUERIES FEATURING MAXIMUM OR MINIMUM EQUALITY CONDITIONS IN A PARALLEL PROCESSING SYSTEM

• US 20100332791A1
• Filed: 06/25/2009
• Published: 12/30/2010
• Est. Priority Date: 06/25/2009
• Status: Abandoned Application

• Current Assignee: Teradata Corporation
• Original Assignee: Teradata Corporation
• Inventors: Xu, Yu
• Application Number:
  US12/491,312
• Publication Number:
  US 20100332791A1
• Time in Patent Office: Days
• US Class Current: 711/216
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

A system, method, and computer-readable medium for optimized processing of queries that feature maximum or minimum equality conditions are provided. The disclosed mechanisms provide for a single-scan of the table on which the group-by query is applied. When the table is scanned, each processing module dynamically keeps track of the row(s) having a value of the attribute on which the equality condition is applied that equals or exceeds the maximum attribute value (assuming a maximum equality condition is applied) previously encountered by the processing module. Subsequently, a global aggregation process is then performed to compute the query'"'"'s result without rescanning the table. Queries featuring a minimum equality condition are similarly processed in accordance with the disclosed embodiments.

Claims

1. A method of optimizing processing of a query specifying an equality condition on an attribute of a table in a parallel processing system, comprising:

receiving, by a processing module of a plurality of processing modules deployed in the parallel processing system, the query, wherein the processing module has a subset of rows of the table allocated thereto;

initializing, by the processing module, a hash table including a first field for a selected attribute of the query and at least one second field for the attribute on which the equality condition is applied and a row of the subset of rows;

identifying, by the processing module, each row of the subset of rows that satisfies the equality condition;

storing, by the processing module, the selected attribute of each row of the subset of rows identified as satisfying the equality condition in the first field of a respective row of the hash table, and the value of attribute on which the equality condition is applied and the row identified as satisfying the equality condition in the at least one second field of the respective row of the hash table;

redistributing each row of the hash table to a respective one of the plurality of processing modules based on a hash value of the selected attribute; and

receiving, by the processing module, a global value of each attribute of the table on which the equality condition is applied that respectively specifies a maximum value of the attribute on which the equality condition is applied for a corresponding selected attribute in the event the equality condition comprises a maximum equality condition and that respectively specifies a minimum value of the attribute on which the equality condition is applied for a corresponding selected attribute in the event the equality condition comprises a minimum equality condition.

2. The method of claim 1, wherein identifying each row of the subset of rows comprises:

evaluating, by the processing module, the selected attribute of each row of the subset of rows; and

determining if a row of the hash table includes a row having the selected attribute.

3. The method of claim 2, wherein the processing module determines the hash table does not include a row having the selected attribute of an evaluated row, the method further comprising inserting a row in the hash table including the selected attribute of the evaluated row in the first field, and the attribute value of the attribute on which the equality condition is applied of the evaluated row and the evaluated row in the at least one second field.

4. The method of claim 2, wherein the processing module determines the hash table includes a row having the selected attribute of an evaluated row, the method further comprising;

comparing a value of the attribute on which the equality condition is applied of the evaluated row with an attribute value of the row of the hash table;

determining the value of the attribute on which the equality condition is applied of the evaluated row exceeds the attribute value of the row of the hash table in the event the equality condition comprises a maximum equality condition or is less than the attribute value of the row of the hash table in the event the equality condition comprises a minimum equality condition;

replacing the value of the attribute in the row of the hash table with the value of the attribute on which the equality condition is applied from the evaluated row; and

replacing the row stored in the hash table with the currently evaluated row.

5. The method of claim 1, further comprising:

comparing each global value of each attribute with a value of the attribute on which the equality condition is applied of a corresponding selected attribute stored in the hash table; and

discarding a row of the hash table in the event the value of the attribute of the row of the hash table is less than the global value for the selected attribute in the event the equality condition comprises a maximum equality condition.

6. The method of claim 1, further comprising:

comparing each global value of each attribute with a value of the attribute on which the equality condition is applied of a corresponding selected attribute stored in the hash table; and

discarding a row of the hash table in the event the value of the attribute of the row of the hash table is greater than the global value for the selected attribute in the event the equality condition comprises a minimum equality condition.

7. The method of claim 1, further comprising:

comparing each global value of each attribute with a value of the attribute on which the equality condition is applied of a corresponding selected attribute stored in the hash table; and

maintaining a row of the hash table in the event the value of the attribute of the row of the hash table equals the global value for the selected attribute.

8. A computer-readable medium having computer-executable instructions for execution by a processing system, the computer-executable instructions for optimizing processing of a query specifying an equality condition on an attribute of a table in a parallel processing system, the computer-executable instructions, when executed, cause the processing system to:

receive, by a processing module of a plurality of processing modules deployed in the parallel processing system, the query, wherein the processing module has a subset of rows of the table allocated thereto;

initialize, by the processing module, a hash table including a first field for a selected attribute of the query and at least one second field for the attribute on which the equality condition is applied and a row of the subset of rows;

identify, by the processing module, each row of the subset of rows that satisfies the equality condition;

store, by the processing module, the selected attribute of each row of the subset of rows identified as satisfying the equality condition in the first field of a respective row of the hash table, and the value of attribute on which the equality condition is applied and the row identified as satisfying the equality condition in the at least one second field of the respective row of the hash table;

redistribute each row of the hash table to a respective one of the plurality of processing modules based on a hash value of the selected attribute; and

receive, by the processing module, a global value of each attribute of the table on which the equality condition is applied that respectively specifies a maximum value of the attribute on which the equality condition is applied for a corresponding selected attribute in the event the equality condition comprises a maximum equality condition and that respectively specifies a minimum value of the attribute on which the equality condition is applied for a corresponding selected attribute in the event the equality condition comprises a minimum equality condition.

9. The computer-readable medium of claim 8, wherein the instructions that identify each row of the subset of rows further comprise instructions that, when executed, cause the processing system to:

evaluate, by the processing module, the selected attribute of each row of the subset of rows; and

determine if a row of the hash table includes a row having the selected attribute.

10. The computer-readable medium of claim 9, wherein the processing module determines the hash table does not include a row having the selected attribute of an evaluated row, the computer-readable medium further comprising instructions that, when executed, cause the processing system to insert a row in the hash table including the selected attribute of the evaluated row in the first field, and the attribute value of the attribute on which the equality condition is applied of the evaluated row and the evaluated row in the at least one second field.

11. The computer-readable medium of claim 9, wherein the processing module determines the hash table includes a row having the selected attribute of an evaluated row, the computer-readable medium further comprising instructions that, when executed, cause the processing system to:

compare a value of the attribute on which the equality condition is applied of the evaluated row with an attribute value of the row of the hash table;

determine the value of the attribute on which the equality condition is applied of the evaluated row exceeds the attribute value of the row of the hash table in the event the equality condition comprises a maximum equality condition or is less than the attribute value of the row of the hash table in the event the equality condition comprises a minimum equality condition;

replace the value of the attribute in the row of the hash table with the value of the attribute on which the equality condition is applied from the evaluated row; and

replace the row stored in the hash table with the currently evaluated row.

12. The computer-readable medium of claim 8, further comprising instructions that, when executed, cause the processing system to:

compare each global value of each attribute with a value of the attribute on which the equality condition is applied of a corresponding selected attribute stored in the hash table; and

discard a row of the hash table in the event the value of the attribute of the row of the hash table is less than the global value for the selected attribute in the event the equality condition comprises a maximum equality condition.

13. The computer-readable medium of claim 8, further comprising instructions that, when executed, cause the processing system to:

compare each global value of each attribute with a value of the attribute on which the equality condition is applied of a corresponding selected attribute stored in the hash table; and

discard a row of the hash table in the event the value of the attribute of the row of the hash table is greater than the global value for the selected attribute in the event the equality condition comprises a minimum equality condition.

14. The computer-readable medium of claim 8, further comprising instructions that, when executed, cause the processing system to:

compare each global value of each attribute with a value of the attribute on which the equality condition is applied of a corresponding selected attribute stored in the hash table; and

maintain a row of the hash table in the event the value of the attribute of the row of the hash table equals the global value for the selected attribute.

15. A parallel processing system configured to optimize processing of a query specifying an equality condition on an attribute of a table in the parallel processing system, comprising:

at least one storage facility on which a database table is stored; and

a plurality of processing modules each allocated a respective subset of rows of the table, wherein a processing module of the plurality of processing modules receives the query, initializes a hash table including a first field for a selected attribute of the query and at least one second field for the attribute on which the equality condition is applied and a row of the subset of rows, identifies each row of the subset of rows that satisfies the equality condition, stores the selected attribute of each row of the subset of rows identified as satisfying the equality condition in the first field of a respective row of the hash table, the value of the attribute on which the equality condition is applied and the row identified as satisfying the equality condition in the at least one second field of the respective row of the hash table, redistributes each row of the hash table to a respective one of the plurality of processing modules based on a hash value of the selected attribute, and receives a global value of each attribute of the table on which the equality condition is applied that respectively specifies a maximum value of the attribute on which the equality condition is applied for a corresponding selected attribute in the event the equality condition comprises a maximum equality condition and that respectively specifies a minimum value of the attribute on which the equality condition is applied for a corresponding selected attribute in the event the equality condition comprises a minimum equality condition.

16. The system of claim 15, wherein the processing module identifies each row of the subset of rows by evaluating the selected attribute of each row of the subset of rows, and determines if a row of the hash table includes a row having the selected attribute.

17. The system of claim 16, wherein the processing module determines the hash table does not include a row having the selected attribute of an evaluated row, wherein the processing module inserts a row in the hash table including the selected attribute of the evaluated row in the first field, and the attribute value of the attribute on which the equality condition is applied of the evaluated row and the evaluated row in the at least one second field.

18. The system of claim 16, wherein the processing module determines the hash table includes a row having the selected attribute of an evaluated row, wherein the processing module compares a value of the attribute on which the equality condition is applied of the evaluated row with an attribute value of the row of the hash table and determines the value of the attribute on which the equality condition is applied of the evaluated row exceeds the attribute value of the row of the hash table in the event the equality condition comprises a maximum equality condition or is less than the attribute value of the row of the hash table in the event the equality condition comprises a minimum equality condition, and wherein the processing module further replaces the value of the attribute in the row of the hash table with the value of the attribute on which the equality condition is applied from the evaluated row and replaces the row stored in the hash table with the currently evaluated row.

19. The system of claim 15, wherein the processing module compares each global value of each attribute with a value of the attribute on which the equality condition is applied of a corresponding selected attribute stored in the hash table and discards a row of the hash table in the event the value of the attribute of the row of the hash table is less than the global value for the selected attribute in the event the equality condition comprises a maximum equality condition.

20. The system of claim 15, wherein the processing module compares each global value of each attribute with a value of the attribute on which the equality condition is applied of a corresponding selected attribute stored in the hash table and discards a row of the hash table in the event the value of the attribute of the row of the hash table is greater than the global value for the selected attribute in the event the equality condition comprises a minimum equality condition.