Self-optimizing value range synopsis in analytical databases

Patent metadata

Field	Value
Publication number	US-10929400-B2
Application number	US-201615335082-A
Country	US
Kind code	B2
Filing date	Oct 26, 2016
Priority date	Oct 26, 2016
Publication date	Feb 23, 2021
Grant date	Feb 23, 2021

Abstract

A method, a computer program product and a computer system are provided. Attribute value information contains at least a minimum value representing a smallest value of a first attribute and a maximum value representing a largest value of the first attribute, thereby defining a first range of values of the first attribute. A received query against a data table requests one or more values of at least the first attribute that are covered by the first range of values. The attribute value information may be used for selecting a data block of the data table as a candidate potentially including at least part of the requested one or more values and scanning the data block. In response to determining that the data block does not include the one or more requested values, the attribute value information may be updated accordingly.

First claim

We claim as our invention:

1. A computer program product comprising one or more computer-readable storage media collectively having computer-readable program code embodied therewith, when the computer-readable program code is executed by at least one processing system, the at least one processing system is configured to: receive a range query against a data table including a plurality of data blocks, each respective data block of the plurality of data blocks including a plurality of records and involving at least a first attribute, stored attribute value information associated with the each respective data block including at least one range of values of the first attribute included in the respective data block, each range of values of the at least one range of values including a first value representing a smallest value of the first attribute for the range of values and a second value of the first attribute representing a largest value of the first attribute for the range of values, the received range query requesting values of the first attribute that are covered by the at least one range of values of at least one of the respective data blocks; use the stored attribute value information for selecting a data block of the plurality of data blocks of the data table as a candidate potentially comprising at least part of the requested values; scan the selected data block; and in response to determining that the selected data block does not have the requested values, update the attribute value information associated with the selected data block to indicate an absence of values of the first attribute corresponding to the requested values of the range query, the update comprising: find a range of values of the first attribute of the at least one range of values in the stored attribute value information for the selected data block covering at least part of a range of the range query, and change at least one of the first value and the second value of the found range of values to indicate that the found range of values excludes values covered by the range query, the change further comprising: responsive to determining that all of the requested values of the range query are greater than the smallest value of the found range of values and are less than the largest value of the found range of values, replace the found range of values of the first attribute with exactly two new ranges of values, each of which includes at least one respective value in the associated data block, and set first values and second values of the two new ranges of values to indicate coverage of a combined range equivalent to a range of the found range of values with a gap in a range identified by the range query, and responsive to determining that the found range of values is completely covered by the range query, delete the found range of values from the stored attribute value information; wherein the update of the stored attribute value information associated with the selected data block reduces an occurrence of false positives with respect to the selecting of the data block of the plurality of data blocks of the data table as the candidate.

2. A computer system comprising a processor and a memory for updating stored attribute value information associated with at least one data block of a plurality of data blocks of a data table, where each respective data block of the plurality of data blocks of the data table has a plurality of records and involves at least a first attribute, the stored attribute value information associated with the each respective data block including at least one range of values of the first attribute included in the respective data block, each range of values of the at least one range of values including a first value representing a smallest value of the first attribute for the range of values and a second value of the first attribute representing a largest value of the first attribute for the range of values, the computer system being configured for: receiving a range query against the data table requesting values of the first attribute that are covered by the at least one range of values for at least one of the respective data blocks; using the stored attribute value information for selecting a data block of the plurality of data blocks of the data table as a candidate potentially comprising at least part of the requested values; scanning the selected data block; and in response to determining that the selected data block does not have the requested values, updating the stored attribute value information associated with the selected data block to indicate an absence of values of the first attribute corresponding to the requested values of the range query, the updating comprising: finding a range of values of the first attribute of the at least one range of values in the stored attribute value information for the selected data block covering at least part of a range of the range query, and changing at least one of the first value and the second value of the found range of values to indicate that the found range of values excludes values covered by the range query, the changing further comprising: responsive to determining that all of the requested values of the range query are greater than the smallest value of the found range of values and are less than the largest value of the found range of values, replacing the found range of values of the first attribute with exactly two new ranges of values, each of which includes at least one respective value in the associated data block, and setting first values and second values of the two new ranges of values to indicate coverage of a combined range equivalent to a range of the found range of values with a gap in a range identified by the range query, and responsive to determining that the found range of values is completely covered by the range query, delete the found range of values from the stored attribute value information; wherein the updating of the stored attribute value information associated with the selected data block reduces an occurrence of false positives with respect to the selecting of the data block of the plurality of data blocks of the data table as the candidate.

3. The computer system of claim 2 , further comprising a query executor and an updater, wherein:
the query executor is configured for determining that the selected data block does not include the one or more requested values and for saving a false positive report in a buffer of the computer system, the false positive report indicating the selected data block and the one or more requested values not included in the selected data block; and
the updater is configured for reading the buffer for the updating of the attribute value information associated with the selected data block.

4. The computer program product of claim 1 , wherein when the computer-readable program code is executed by the at least one processing system, the at least one processing system is further configured to:
receive a second query against the data table, the received second query being a point query;
use the stored attribute value information for selecting a second data block of the plurality of data blocks of the data table as the candidate potentially comprising at least a requested value of the point query;
scan the selected second data block; and
in response to determining that the selected second data block does not have the requested value of the point query, the update of the attribute value information for the selected second data block comprises adding to the attribute value information for the selected second data block a list comprising the requested value for supporting query processing against the data table using both the at least one range of values and the list from the attribute value information for the selected second data block.

5. The comp

Assignees

• IBM

Inventors

• Beier Felix O
• Brodt Andreas
• Hrle Namik
• Schiller Oliver

Classifications

• G06F16/24553 Primary

  of query operations · CPC title

• G06F16/2455 Primary

  Query execution · CPC title

• G06F16/2308

  Concurrency control (transaction processing G06F9/466) · CPC title

• G06F16/2329

  using versioning · CPC title