Reclustering of database tables based on peaks and widths

Patent metadata

Field	Value
Publication number	US-10956394-B2
Application number	US-202016941215-A
Country	US
Kind code	B2
Filing date	Jul 28, 2020
Priority date	Jul 17, 2018
Publication date	Mar 23, 2021
Grant date	Mar 23, 2021

Abstract

The subject technology determines whether a table is sufficiently clustered. The subject technology in response to determining the table is not sufficiently clustered, selects one or more micro-partitions of the table to be reclustered. The subject technology constructs a data structure for the table. The subject technology extracts minimum and maximum endpoints for each micro-partition in the data structure. The subject technology sorts each of one or more peaks in the data structure based on height. The subject technology sorts overlapping micro-partitions based on width. The subject technology selects based on which micro-partitions are within the tallest peaks of the one or more peaks and further based on which of the overlapping micro-partitions have the widest widths.

First claim

What is claimed is:

1. A method performed by a database platform comprising at least one hardware processor, the method comprising:
determining whether a table is sufficiently clustered:
in response to determining that the table is not sufficiently clustered, selecting one or more micro-partitions of the table to be reclustered, the selecting comprising:
constructing a data structure for the table;
extracting minimum and maximum endpoints for each micro-partition in the data structure;
sorting each of one or more peaks in the data structure based on height;
sorting overlapping micro-partitions based on width; and
selecting based on which micro-partitions are within the tallest peaks of the one or more peaks and further based on which of the overlapping micro-partitions have the widest widths; and

reclustering the selected one or more micro-partitions of the table.

2. The method of claim 1 , further comprising:
defining a constant micro-partition having equivalent minimum and maximum values for a cluster key column; and
removing the constant micro-partition from the selected one or more micro-partitions of the table prior to the reclustering.

3. The method of claim 1 , wherein the selecting further comprises:
identifying the one or more peaks in the data structure as those that are taller than a predefined threshold; and
identifying the overlapping micro-partitions within each of the one or more peaks.

4. The method of claim 1 , wherein the data structure comprises a stabbing count array or an interval tree.

5. The method of claim 1 , further comprising determining a budget for allocating resources to perform reclustering operations.

6. The method of claim 5 , wherein the determining whether the table is sufficiently clustered is based at least in part on the budget.

7. The method of claim 1 , further comprising partitioning the selected one or more micro-partitions of the table into one or more batches each comprising a grouping of micro-partitions.

8. The method of claim 1 , further comprising receiving an indication that a data modification task has been executed on the table, wherein the executing of the data modification task on the table comprises ingesting new micro-partitions into the table.

9. The method of claim 1 , further comprising entering a catch-up mode in which, based at least in part on a high proportion of database partitions being within lower levels of the table, reclustering operations are performed.

10. The method of claim 1 , further comprising entering a stable mode in which, based at least in part on a low proportion of database partitions being within lower levels of the table, no reclustering operations are performed.

11. A system comprising:
at least one hardware processor; and
a memory device including instructions that, when executed by the at least one hardware processor, cause the at least one hardware processor to perform operations comprising:
determining whether a table is sufficiently clustered;
in response to determining that the table is not sufficiently clustered, selecting one or more micro-partitions of the table to be reclustered, the selecting comprising:
constructing a data structure for the table;
extracting minimum and maximum endpoints for each micro-partition in the data structure;
sorting each of one or more peaks in the data structure based on height;
sorting overlapping micro-partitions based on width; and
selecting based on which micro-partitions are within the tallest peaks of the one or more peaks and further based on which of the overlapping micro-partitions have the widest widths; and

reclustering the selected one or more micro-partitions of the table.

12. The system of claim 11 , the operations further comprising:
defining a constant micro-partition having equivalent minimum and maximum values for a cluster key column; and
removing the constant micro-partition from the selected one or more micro-partitions of the table prior to the reclustering.

13. The system of claim 11 , wherein the selecting further comprises:
identifying the one or more peaks in the data structure as those that are taller than a predefined threshold; and
identifying the overlapping micro-partitions within each of the one or more peaks.

14. The system of claim 11 , wherein the data structure comprises a stabbing count array or an interval tree.

15. The system of claim 11 , the operations further comprising determining a budget for allocating resources to perform reclustering operations.

16. The system of claim 15 , wherein the determining whether the table is sufficiently clustered is based at least in part on the budget.

17. The system of claim 11 , the operations further comprising partitioning the selected one or more micro-partitions of the table into one or more batches each comprising a grouping of micro-partitions.

18. The system of claim 11 , the operations further comprising receiving an indication that a data modification task has been executed on the table, wherein the executing of the data modification task on the table comprises ingesting new micro-partitions into the table.

19. The system of claim 11 , the operations further comprising entering a catch-up mode in which, based at least in part on a high proportion of database partitions being within lower levels of the table, reclustering operations are performed.

20. The system of claim 11 , the operations further comprising entering a stable mode in which, based at least in part on a low proportion of database partitions being within lower levels of the table, no reclustering operations are performed.

21. A non-transitory computer-readable medium comprising instructions that, when executed by at least one hardware processor, cause the at least one hardware processor to perform operations comprising:
determining whether a table is sufficiently clustered;
in response to determining that the table is not sufficiently clustered, selecting one or more micro-partitions of the table to be reclustered, the selecting comprising:
constructing a data structure for the table;
extracting minimum and maximum endpoints for each micro-partition in the data structure;
sorting each of one or more peaks in the data structure based on height;
sorting overlapping micro-partitions based on width; and
selecting based on which micro-partitions are within the tallest peaks of the one or more peaks and further based on which of the overlapping micro-partitions have the widest widths; and

reclustering the selected one or more micro-partitions of the table.

22. The non-transitory computer-readable medium of claim 21 , the operations further comprising:
defining a constant micro-partition having equivalent minimum and maximum values for a cluster key column; and
removing the constant micro-partition from the selected one or more micro-partitions of the table prior to the reclustering.

23. The non-transitory computer-readable medium of claim 21 , wherein the selecting further comprises:
identifying the one or more peaks in the data structure as those that are taller than a predefined threshold; and
identifying the overlapping micro-partitions within each of the one or more peaks.

24. The non-transitory computer-readable medium of claim 21 , wherein the data structure comprises a stabbing count array or an interval tree.

25. The non-transitory computer-readable medium of claim 21 , the operatio

Assignees

• Snowflake Inc

Inventors

• Yan Jiaqi
• Cruanes Thierry
• Rosen Jeffrey
• Waddington William
• Rajaperumal Prasanna
• Munir Abdul

Classifications

• G06F16/285

  Clustering or classification · CPC title

• G06F16/278

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

• G06F16/22

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/217

  Database tuning (G06F16/2282 takes precedence; database performance monitoring G06F11/3409) · CPC title

• G06F16/2282 Primary

  Tablespace storage structures; Management thereof · CPC title