Shuffle-less reclustering of clustered tables

Patent metadata

Field	Value
Publication number	US-11436261-B2
Application number	US-202016848810-A
Country	US
Kind code	B2
Filing date	Apr 14, 2020
Priority date	Apr 14, 2020
Publication date	Sep 6, 2022
Grant date	Sep 6, 2022

Abstract

A method for shuffle-less reclustering of clustered tables includes receiving a first and second group of clustered data blocks sorted by a clustering key value. A range of clustering key values of one or more the data blocks in the second group overlaps with the range of clustering key values of a data block in the first group. The method also includes generating split points for partitioning the first and second groups of clustered data blocks into a third group. The method also includes partitioning using the split points, the first and second groups into the third group. Each data block in the third group includes a range of clustering key values that do not overlap with any other data block in the third group. Each split point defines an upper limit or lower limit for the range of clustering key values a data block in the third group.

First claim

What is claimed is:

1. A method comprising:
receiving, at data processing hardware, a first group of clustered data blocks sorted by a clustering key value, each clustered data block in the first group of clustered data blocks comprising a respective range of the clustering key values that do not overlap with any of the ranges of clustering key values of the other clustered data blocks in the first group of clustered data blocks;
receiving, at the data processing hardware, a second group of clustered data blocks sorted by the clustering key value, each clustered data block in the second group of clustered data blocks comprising a respective range of clustering key values that do not overlap with any of the ranges of clustering key values of the other clustered data blocks in the second group of clustered data blocks;
generating, by the data processing hardware, one or more split points for partitioning the first and second groups of clustered data blocks into a third group of clustered data blocks;
partitioning, by the data processing hardware, using the one or more generated split points, the first and second groups of clustered data blocks into the third group of clustered data blocks, each clustered data block in the third group of clustered data blocks comprising a respective range of clustering key values that do not overlap with any of the ranges of clustering key values of the other clustered data blocks in the third group of clustered data blocks, wherein each split point of the one or more generated split points defines an upper limit or a lower limit for the respective range of clustering key values of one of the clustered data blocks in the third group of clustered data blocks;
determining, by the data processing hardware, a first sum of data values associated with the first and second groups of clustered data blocks;
determining, by the data processing hardware, a second sum of data values associated with the third group of clustered data blocks; and
verifying, by the data processing hardware, that the first sum is equivalent to the second sum.

2. The method of claim 1 , wherein a columnar database table stores the first and second groups of clustered data blocks.

3. The method of claim 1 , wherein a number of the one or more split points generated is based on a number of data blocks in the first and second groups of clustered data blocks and a size of each of the data blocks.

4. The method of claim 1 , wherein partitioning the first and second groups of clustered data blocks into the third group of clustered data blocks occurs without performing any shuffling operation on the data blocks in the first and second groups of clustered data blocks.

5. The method of claim 1 , wherein partitioning the first and second groups of clustered data blocks into the third group of clustered data blocks comprises:
identifying which clustering key values in the first group of clustered data blocks and the second group of clustered data blocks fall between adjacent split points; and
for each clustered data block in the third group of clustered data blocks, merging the identified clustering key values that fall within the corresponding adjacent split points.

6. The method of claim 1 , wherein at least one clustered data block in the third group of clustered data blocks comprises a portion of the respective range from one of the data blocks of the first or second groups of clustered data blocks that does not overlap with any of the respective ranges of the other clustered data blocks of the other one of the first or second groups of clustered data blocks.

7. The method of claim 1 , wherein at least one clustered data block in the third group of clustered data blocks comprises a portion of the respective range from one of the data blocks of the first or second groups of clustered data blocks and one of the data blocks from the other one of the first or second groups of clustered data blocks.

8. The method of claim 1 , wherein at least one clustered data block in the third group of clustered data blocks comprises a portion of the respective range from two of the data blocks of the first or second groups of clustered data blocks and one of the data blocks from the other one of the first or second groups of clustered data blocks.

9. The method of claim 1 , wherein generating the one or more split points comprises determining a plurality of quantiles for the first and second groups of clustered data blocks.

10. The method of claim 9 , wherein each split point of the one or more split points corresponds to a different quantile of the plurality of quantiles.

11. The method of claim 1 , wherein the respective range of clustering key values of one or more the clustered data blocks in the second group of clustered data blocks overlaps with the respective range of clustering key values of at least one of the clustered data blocks in the first group of clustered data blocks.

12. A system comprising:
data processing hardware; and
memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising:
receiving a first group of clustered data blocks sorted by a clustering key value, each clustered data block in the first group of clustered data blocks comprising a respective range of the clustering key values that do not overlap with any of the ranges of clustering key values of the other clustered data blocks in the first group of clustered data blocks;
receiving a second group of clustered data blocks sorted by the clustering key value, each clustered data block in the second group of clustered data blocks comprising a respective range of clustering key values that do not overlap with any of the ranges of clustering key values of the other clustered data blocks in the second group of clustered data blocks, wherein the respective range of clustering key values of one or more the clustered data blocks in the second group of clustered data blocks overlaps with the respective range of clustering key values of at least one of the clustered data blocks in the first group of clustered data blocks;
generating one or more split points for partitioning the first and second groups of clustered data blocks into a third group of clustered data blocks;
partitioning using the one or more generated split points, the first and second groups of clustered data blocks into the third group of clustered data blocks, each clustered data block in the third group of clustered data blocks comprising a respective range of clustering key values that do not overlap with any of the ranges of clustering key values of the other clustered data blocks in the third group of clustered data blocks, wherein each split point of the one or more generated split points defines an upper limit or a lower limit for the respective range of clustering key values of one of the clustered data blocks in the third group of clustered data blocks determining a first sum of data values associated with the first and second groups of clustered data blocks;
determining a second sum of data values associated with the third group of clustered data blocks; and
verifying that the first sum is equivalent to the second sum.

13. The system of claim 12 , wherein a columnar database table stores the first and second groups of clustered data blocks.

14. The system of claim 12 , wherein a number of the one or more split points generated is based on a number of data blocks in the first and second groups of clustered data blocks and a size of each of the data bloc

Assignees

• Google Llc

Inventors

• Zhang Hua
• Edara Pavan
• Nguyen Nhan

Classifications

• G06F16/2379

  Updates performed during online database operations; commit processing · CPC title

• G06F16/221 Primary

  Column-oriented storage; Management thereof · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F16/278

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title

• G06F16/285 Primary

  Clustering or classification · CPC title