Extreme value computation

• US 9,501,534 B1
• Filed: 01/28/2016
• Issued: 11/22/2016
• Est. Priority Date: 01/28/2016
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Schiller, Oliver, Trumpp, Mathias, Brodt, Andreas, Schwind, Marc, Stolze, Knut
• Primary Examiner(s): Pham, Khanh
• Application Number:
  US15/008,960
• Time in Patent Office: 299 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24578 using ranking

Abstract

Determining an extremum value of an attribute of a first data table. The first data table includes a set of data blocks. Assigning each data block of the set of data blocks an attribute value information indicative of a range of values of the attribute. Assigning the attribute value information results in an extremum set of indicative maximum and minimum values of the attribute. Determining a reference value as the infimum or supremum of the extremum set. If the extremum is a minimum, selecting a subset of the set of data blocks, each having a respective minimum value of the attribute smaller than the reference value. If the extremum is a maximum, selecting a subset of the set of data blocks, each having a respective maximum value of the attribute higher than the reference value. Processing at least part of the subset of data blocks for identifying the extremum value.

Claims

1. A computer implemented method for determining an extremum value of an attribute of a first data table, wherein the first data table includes at least a set of data blocks, the method comprising:

generating a multidimensional data structure for representing the set of data blocks;

assigning, by a computer, to each data block of the set of data blocks a plurality of attribute value information indicative of a range of a plurality of values of an attribute in the data block, wherein assigning results in an extremum set of a plurality of indicative maximum values of the attribute and a plurality of indicative minimum values of the attribute;

determining a reference value as an infimum or a supremum of the extremum set based on each extremum in the extremum set;

in case the extremum is a minimum, selecting a subset of the set of data blocks, wherein each data block within the subset has a respective minimum value of the attribute that is smaller than the reference value;

in case the extremum is a maximum, selecting a subset of the set of data blocks, wherein each data block within the subset has a respective maximum value of the attribute that is higher than the reference value;

receiving a second data table;

joining the selected subset of data blocks with the received second data table;

sorting the joined subset of data blocks; and

processing at least a part of the joined subset of data blocks for identifying an extremum value.

2. The method of claim 1, wherein, in case the extremum being a minimum, processing of the selected subset of data blocks further comprises:

processing a current data block of the subset of data blocks only in response to determining that the respective minimum value of the attribute of the current data block is smaller than a minimum value of a previously processed data block of the subset of data blocks.

3. The method of claim 1, wherein, in case the extremum being a maximum, processing of the subset of data blocks further comprises:

processing a current data block of the subset of data blocks only in response to determining that the respective maximum value of the attribute of the current data block is higher than a maximum value of a previously processed data block of the subset of data blocks.

4. The method of claim 1, wherein, in case the extremum being a minimum, processing of the subset of data blocks further comprises:

sorting, in an ascending order, the subset of minimum values of the subset of data blocks;

processing a first ordered data block for identifying the minimum value;

in case the identified minimum value is smaller than the minimum value of the following data block, using the identified minimum value as the extremum value to be determined; and

in case the identified minimum value is not smaller than the minimum value of the following data block, processing and using a subsequent ordered data block.

5. The method of claim 1, wherein, in case the extremum being a maximum, processing of the subset of data blocks further comprises:

sorting, in a descending order, the subset of maximum values of the subset of data blocks;

processing a first ordered data block for identifying the maximum value;

in case the identified maximum value is higher than the maximum value of the following data block, using the identified maximum value as the extremum value to be determined; and

in case the identified maximum value is smaller than the maximum value of the following data block, processing and using a subsequent ordered data block.

6. The method of claim 1, further comprising:

receiving a query for determining the extremum value, wherein the query indicates a predefined condition of an attribute of the first data table, and wherein the selecting of the subset of data blocks further comprises;

in response to determining that the subset of data blocks does not additionally satisfy the predefined condition, repeating determining the reference value and selecting the subset using the extremum set without the plurality of extremum values of the subset of the plurality of data blocks, wherein repeating is performed until at least part of the subset of the plurality of data blocks satisfies the predefined condition or until all of the plurality of data blocks of the first data table have been processed.

7. The method of claim 1, further comprising:

receiving a request for determining the minimum value of the attribute in a joined table resulting from a join of the first data table and the second data table, and processing comprising;

in response to determining that the at least part of the subset of data blocks is empty, repeating determining the reference value and selecting the subset using the extremum set without the plurality of extremum values of the subset of the plurality of data blocks, wherein the repeating being performed until the at least part of the subset of the plurality of data blocks is not empty or until all of the plurality of data blocks of the first data table have been processed.

8. The method of claim 1, wherein the first data table being stored on a disk storage.

9. The method of claim 1, wherein the first data table being an in-memory data table.

10. A computer system for determining extremum values of an attribute of a first data table, wherein the first data table includes at least a set of data blocks;

the computer system being configured for;

one or more processors, one or more computer-readable memories, one or more computer-readable tangible storage medium, and program instructions stored on at least one of the one or more tangible storage medium for execution by at least one of the one or more processors via at least one of the one or more memories, wherein the computer system is capable of performing a method comprising;

generating a multidimensional data structure for representing the set of data blocks;

assigning to each data block of the set of data blocks a plurality of attribute value information indicative of a range of values of an attribute in the data block, wherein assigning results in an extremum set of a plurality of indicative maximum values and a plurality of indicative minimum values of the attribute;

determining a first reference value as a supremum of the extremum set;

determining a second reference value as an infimum of the extremum set;

selecting a first subset of the set of data blocks, wherein each data block within the first subset has a respective minimum value of the attribute that is smaller than the first reference value;

selecting a second subset of the set of data blocks, wherein each data block within the second subset has a respective maximum value of the attribute that is higher than the second reference value;

receiving a second data table;

joining the selected first subset of data blocks and the second subset of data blocks with the received second data table;

sorting the joined first subset of data blocks and the joined second subset of data blocks; and

processing at least part of the joined first subset or at least a part of the joined second subset for identifying a plurality of extremum values.

11. The computer system of claim 10, wherein processing at least part of the subset of the first subset and at least a part of the second subset further comprises:

determining a plurality of common data blocks between the first subset of data blocks and the second subset of data blocks;

processing the plurality of common data blocks for identifying both a plurality of minimum values and a plurality of maximum values, thereby obtaining a first minimum value and a first maximum value;

processing the first subset of the plurality of data blocks excluding the plurality of common data blocks for identifying a second minimum value;

processing the second subset of the plurality of data blocks excluding the plurality of common data blocks for identifying a second maximum value; and

selecting a smallest of the first minimum value and the second minimum value and a largest of the first maximum value and the second maximum value.

12. A computer program product for determining an extremum value of an attribute of a first data table, wherein the first data table includes at least a set of data blocks, the computer program product comprising:

one or more computer-readable tangible storage medium and program instructions stored on at least one of the one or more tangible storage medium, the program instructions executable by a processor, the program instructions comprising;

program instructions to generate a multidimensional data structure for representing the set of data blocks;

program instructions to assign to each data block of the set of data blocks a plurality of attribute value information indicative of a range of a plurality of values of an attribute in the data block, wherein assigning results in an extremum set of a plurality of indicative maximum values and a plurality of indicative minimum values of the attribute;

program instructions to determine a reference value as an infimum or a supremum of the extremum set based on each extremum in the extremum set;

in case the extremum is a minimum, program instructions to select a subset of the set of data blocks, wherein each data block within the subset has a respective minimum value of the attribute that is smaller than the reference value;

in case the extremum is a maximum, program instructions to select a subset of the set of data blocks, wherein each data block within the subset has a respective maximum value of the attribute that is higher than the reference value;

program instructions to receive a second data table;

program instructions to join the selected subset of data blocks with the received second data table;

program instructions to sort the joined subset of data blocks; and

program instructions to process at least a part of the joined subset of data blocks for identifying an extremum value.

13. The computer program product of claim 12, wherein, in case the extremum being a minimum, processing of the subset of data blocks further comprises:

program instructions to process a current data block of the subset of data blocks only in response to determining that the respective minimum value of the attribute of the current data block is smaller than a minimum value of a previously processed data block of the subset of data blocks.

14. The computer program product of claim 12, wherein, in case the extremum being a maximum, processing of the subset of data blocks further comprises:

program instructions to process a current data block of the subset of data blocks only in response to determining that the respective maximum value of the attribute of the current data block is higher than a maximum value of a previously processed data block of the subset of data blocks.

15. The computer program product of claim 12, wherein, in case the extremum being a minimum, processing of the subset of data blocks further comprises:

program instructions to sort, in an ascending order, the subset of minimum values of the subset of data blocks;

program instructions to process a first ordered data block for identifying the minimum value;

in case the identified minimum value is smaller than the minimum value of the following data block, program instructions to use the identified minimum value as the extremum value to be determined; and

in case the identified minimum value is higher than the minimum value of the following data block, program instructions to process and use a subsequent ordered data block.

16. The computer program product of claim 12, wherein, in case the extremum being a maximum, processing of the subset of data blocks further comprises:

program instructions to sort, in a descending order, the subset of maximum values of the subset of data blocks;

program instructions to process a first ordered data block for identifying the maximum value;

in case the identified maximum value is higher than the maximum value of the following data block, program instructions to use the identified maximum value as the extremum value to be determined; and

in case the identified maximum value is smaller than the maximum value of the following data block, program instructions to process and use a subsequent ordered data block.

17. The computer program product of claim 12, further comprising:

program instructions to receive a query for determining the extremum value, wherein the query indicates a predefined condition of an attribute of the first data table, and wherein selecting of the subset of data blocks further comprises;

in response to determining that the subset of data blocks does not additionally satisfy the predefined condition, program instructions to repeat determining the reference value and selecting the subset using the extremum set without the plurality of extremum values of the subset of the plurality of data blocks, wherein repeating is performed until at least part of the subset of the plurality of data blocks satisfies the predefined condition or until all of the plurality of data blocks of the first data table have been processed.

18. The computer program product of claim 12, further comprising:

program instructions to receive a request for determining the minimum value of the attribute in a joined table resulting from a join of the first data table and the second data table, and processing comprising;

in response to determining that the at least part of the subset of data blocks is empty, program instructions to repeat determining the reference value and selecting the subset using the extremum set without the plurality of extremum values of the subset of the plurality of data blocks, wherein repeating is performed until the at least part of the subset of the plurality of data blocks is not empty or until all of the plurality of data blocks of the first data table have been processed.

19. The computer program product of claim 12, wherein the first data table being stored on a disk storage.

20. The computer program product of claim 12, wherein the first data table being an in-memory data table.