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

• US 20100153429A1
• Filed: 12/11/2008
• Published: 06/17/2010
• Est. Priority Date: 12/11/2008
• Status: Active Grant

• Current Assignee: Teradata Corporation
• Original Assignee: Teradata Corporation
• Inventors: Kostamaa, Olli Pekka, Xu, Yu
• Granted Patent: US 8,234,292 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/2445 Data retrieval commands; View definitions
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases

Abstract

A system, method, and computer-readable medium for optimized processing of queries that feature maximum or minimum equality conditions are provided. A table on which the query is applied is scanned a single time. Rows of the table distributed to respective processing modules are scanned by the processing modules. Each processing module maintains identification of any rows distributed to the respective processing module that have attribute values that equal the maximum or minimum attribute value locally identified by the processing module. Subsequently, a global aggregation mechanism is invoked to compute the query result without requiring an additional rescan of the table. Further, the disclosed mechanisms may be extended to compute top N queries featuring maximum or minimum equality conditions.

Claims

1. A method of optimizing processing of a query specifying a maximum 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 variable to maintain a local value of the attribute encountered by the processing module to a value that is less than a value that may be stored by the attribute;

initializing, by the processing module, a result spool to maintain at least one row of the table having an attribute value that at least equals the variable;

iteratively evaluating attribute values of the rows allocated to the processing module; and

determining to add a first row to the result spool responsive to determining the attribute value of the first row equals or exceeds the local value of the variable.

2. The method of claim 1, wherein determining to add the first row comprises determining to add the first row responsive to determining the attribute value of the first row exceeds the local value, the method further comprising:

deleting any rows of the result spool maintained by the processing module;

resetting the local value of the variable to the attribute value of the first row; and

adding the first row to the result spool.

3. The method of claim 1, wherein evaluating attribute values of the rows comprises evaluating an attribute value of a second row, the method further comprising:

determining the attribute value of the second row equals the local value; and

adding the second row to the result spool.

4. The method of claim 1, wherein evaluating attribute values of the rows comprises evaluating an attribute value of a second row, the method further comprising:

determining the attribute value of the second row is less than the local value; and

deleting the second row by the processing module.

5. The method of claim 1, further comprising:

completing evaluation of all rows allocated to the processing module;

transmitting the local value of the variable to a central node;

receiving, from the central node, a global maximum attribute value; and

comparing the global maximum value to the local value.

6. The method of claim 5, further comprising:

determining the global maximum attribute value exceeds the local value; and

deleting all rows from the result spool.

7. The method of claim 5, further comprising:

determining the global maximum attribute value equals the local value; and

maintaining rows of the result spool for final results of processing of the query.

8. The method of claim 1, wherein the query includes a selection of top N rows from the table based on attribute values of the top N rows, the method further comprising:

storing, in a heap, the top N rows having attribute values that satisfy the selection of the top N rows; and

transmitting, by the processing module, values of the attributes of the top N rows with the top N rows to a central node.

9. A method of optimizing processing of a query specifying a minimum 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 variable to maintain a local value of the attribute encountered by the processing module to a maximum value that may be stored by the attribute;

initializing, by the processing module, a result spool to maintain at least one row of the table having an attribute value that is less than or equals the local value;

iteratively evaluating attribute values of the rows allocated to the processing module; and

determining to add a first row to the result spool responsive to determining the attribute value of the first row is less than or equals the local value.

10. The method of claim 9, wherein determining to add the first row comprises determining to add the first row responsive to determining the attribute value of the first row is less than the local value, the method further comprising:

deleting any rows of the result spool maintained by the processing module;

resetting the local value of the variable to the attribute value of the first row; and

adding the first row to the result spool.

11. The method of claim 9, wherein evaluating attribute values of the rows comprises evaluating an attribute value of a second row, the method further comprising:

determining the attribute value of the second row equals the local value; and

adding the second row to the result spool.

12. The method of claim 9, wherein evaluating attribute values of the rows comprises evaluating an attribute value of a second row, the method further comprising:

determining the attribute value of the second row is greater than the local value; and

deleting the second row by the processing module.

13. The method of claim 9, further comprising:

completing evaluation of all rows allocated to the processing module;

transmitting the local value of the variable to a central node;

receiving, from the central node, a global minimum attribute value; and

comparing the global minimum value to the local value.

14. The method of claim 13, further comprising:

determining the global minimum attribute value is less than the local value; and

deleting all rows from the result spool.

15. The method of claim 13, further comprising:

determining the global minimum attribute value equals the local value; and

maintaining rows of the result spool for final results of processing of the query.

16. 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 a maximum 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 variable to maintain a local value of the attribute encountered by the processing module, wherein the variable is initialized to a value that is less than a minimum value that may be stored by the attribute;

initialize, by the processing module, a result spool to maintain at least one row of the table having an attribute value that at least equals the variable;

iteratively evaluate attribute values of the rows allocated to the processing module; and

determine to add a first row to the result spool responsive to determining the attribute value of the first row equals or exceeds a value of the variable.

17. The computer-readable medium of claim 16, wherein the instructions that determine to add the first row comprise instructions that determine to add the first row responsive to determining the attribute value of the first row exceeds the local value, the computer-readable medium further comprising instructions that, when executed, cause the processing system to:

delete any rows of the result spool maintained by the processing module;

reset the local value of the variable to the attribute value of the first row; and

add the first row to the result spool.

18. The computer-readable medium of claim 16, wherein the instructions that evaluate attribute values of the rows comprise instructions that evaluate an attribute value of a second row, the computer-readable medium further comprising instructions that, when executed, cause the processing system to:

determine the attribute value of the second row equals the local value; and

add the second row to the result spool.

19. The computer-readable medium of claim 16, wherein the instructions that evaluate attribute values of the rows comprise instructions that evaluate an attribute value of a second row, the computer-readable medium further comprising instructions that, when executed, cause the processing system to:

determine the attribute value of the second row is less than the local value; and

delete the second row by the processing module.

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

complete evaluation of all rows allocated to the processing module;

transmit the local value of the variable to a central node;

receive, from the central node, a global maximum attribute value; and

compare the global maximum value to the local value.

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

determine the global maximum attribute value exceeds the local value; and

delete all rows from the result spool.

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

determine the global maximum attribute value equals the local value; and

maintain rows of the result spool for final results of processing of the query.

23. The computer-readable medium of claim 16, wherein the query includes a selection of top N rows from the table based on attribute values of the top N rows, the computer-readable medium further comprising instructions that, when executed, cause the processing system to:

store, in a heap, the top N rows having attribute values that satisfy the selection of the top N rows; and

transmit, by the processing module, values of the attributes of the top N rows with the top N rows to a central node.

24. 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 a minimum 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 variable to maintain a local value of the attribute encountered by the processing module, wherein the variable is initialized to a maximum value that may be stored by the attribute;

initialize, by the processing module, a result spool to maintain at least one row of the table having an attribute value that is less than or equals the local value;

iteratively evaluate attribute values of the rows allocated to the processing module; and

determine to add a first row to the result spool responsive to determining the attribute value of the first row is less than or equals the local value.

25. The computer-readable medium of claim 24, wherein the instructions that determine to add the first row determine to add the first row responsive to determining the attribute value of the first row is less than the local value, the computer-readable medium further comprising instructions that, when executed, cause the processing system to:

delete any rows of the result spool maintained by the processing module;

reset the local value of the variable to the attribute value of the first row; and

add the first row to the result spool.

26. The computer-readable medium of claim 24, wherein the instructions that evaluate attribute values of the rows evaluate an attribute value of a second row, the computer-readable medium further comprising instructions that, when executed, cause the processing system to:

determine the attribute value of the second row equals the local value; and

add the second row to the result spool.

27. The computer-readable medium of claim 24, wherein the instructions that evaluate attribute values of the rows evaluate an attribute value of a second row, the computer-readable medium further comprising instructions that, when executed, cause the processing system to:

determine the attribute value of the second row is greater than the local value; and

delete the second row by the processing module.

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

complete evaluation of all rows allocated to the processing module;

transmit the local value of the variable to a central node;

receive, from the central node, a global minimum attribute value; and

compare the global minimum value to the local value.

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

determine the global minimum attribute value is less than the local value; and

delete all rows from the result spool.

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

determine the global minimum attribute value equals the local value; and

maintain rows of the result spool for final results of processing of the query.

31. A parallel processing system configured to optimize processing of a query specifying a maximum equality condition applied to an attribute of a table, comprising:

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

a plurality of processing modules each allocated a portion of rows of the table, a variable that maintains a local maximum value of the attribute of one or more rows allocated to the processing module, and a respective result spool in which the one or more rows having the local maximum value are stored, wherein each of the plurality of processing modules reports the local maximum value to a central node, receives a global maximum value therefrom, compares the global maximum value with the local maximum value, and determines whether to delete the rows of the result spool based on results of the comparison of the global maximum value with the local maximum value.

32. The system of claim 31, wherein each of the plurality of processing modules deletes rows of the respective result spool if the global maximum value exceeds the local maximum value.

33. A parallel processing system configured to optimize processing of a query specifying a minimum equality condition applied to an attribute of a table, comprising:

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

a plurality of processing modules each allocated a portion of rows of the table, a variable that maintains a local minimum value of the attribute of one or more rows allocated to the processing module, and a respective result spool in which the one or more rows having the local minimum value are stored, wherein each of the plurality of processing modules reports the local minimum value to a central node, receives a global minimum value therefrom, compares the global minimum value with the local minimum value, and determines whether to delete the rows of the result spool based on results of the comparison of the global minimum value with the local minimum value.

34. The system of claim 33, wherein each of the plurality of processing modules deletes rows of the respective result spool if the global minimum value is less than the local minimum value.