Incremental clustering of database tables

Patent metadata

Field	Value
Publication number	US-10997147-B2
Application number	US-201916514877-A
Country	US
Kind code	B2
Filing date	Jul 17, 2019
Priority date	Jul 17, 2018
Publication date	May 4, 2021
Grant date	May 4, 2021

Abstract

Automatic clustering of a database table is disclosed. A method for automatic clustering of a database table includes receiving an indication that a data modification task has been executed on a table and determining whether the table is sufficiently clustered. The method includes, in response to determining the table is not sufficiently clustered, selecting one or more micro-partitions of the table to be reclustered. The method includes assigning each of the one or more micro-partitions to an execution node to be reclustered.

First claim

What is claimed is:

1. A method comprising:
receiving an indication that a data modification task has been executed on a table;
determining whether the 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:
identifying one or more peaks in the data structure that exceed a predefined threshold; and
identifying overlapping micro-partitions within each of the one or more peaks; and

assigning each of the one or more micro-partitions to an execution node to be reclustered.

2. The method of claim 1 , wherein determining whether the table is sufficiently clustered comprises assessing the data modification task to determine whether a sufficient number of rows has been added to the table, a sufficient number of rows has been deleted from the table, and/or a sufficient number of rows has been modified in the table to necessitate the table being reclustered.

3. The method of claim 1 , wherein selecting one or more micro-partitions of the table to be reclustered further comprises:
identifying a constant micro-partition having equivalent minimum and maximum values for a cluster key column; and
removing the constant micro-partition from consideration such that the constant micro-partition is not included in the one or more micro-partitions to be reclustered.

4. The method of claim 1 , wherein the data structure comprises a stabbing count array, and selecting the one or more micro-partitions of the table to be reclustered further comprises:
extracting minimum and maximum endpoints for each micro-partition in the stabbing count array; and
computing statistics on each of the minimum and maximum endpoints.

5. The method of claim 4 , wherein selecting the one or more micro-partitions of the table to be reclustered further comprises:
sorting each of the one or more peaks in the stabbing count array based on height; and
sorting the overlapping micro-partitions based on width.

6. The method of claim 5 , wherein selecting the one or more micro-partitions of the table to be reclustered further comprises 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.

7. The method of claim 1 , further comprising defining a budget for allocating processing resources to performing reclustering operations, wherein the determining of whether the table is sufficiently clustered is based at least in part on the budget.

8. The method of claim 1 , further comprising partitioning the one or more micro-partitions of the table to be reclustered into one or more batches each comprising a grouping of micro-partitions to be reclustered.

9. The method of claim 1 , wherein selecting the one or more micro-partitions of the table to be reclustered further comprises:
determining a maximum number of levels for the table based at least on a size of the table;
dividing the table into levels;
selecting a macro-batch of micro-partitions within each level, wherein the macro-batch centers around a single peak and comprises defined boundaries; and
selecting micro-partitions from the macro-batch.

10. The method of claim 1 , wherein:
the data modification task comprises ingesting new micro-partitions into the table; and
determining whether the table is sufficiently clustered comprises:
retrieving level information for the table;
identifying a proportion of micro-partitions in lower levels of the table;
determining whether a high proportion of micro-partitions are in the lower levels;
in response to determining that a high proportion of micro-partitions are not in the lower levels, entering a stable mode in which reclustering operations will not be performed; and
in response to determining that a high proportion of micro-partitions are in the lower levels, entering a catch-up mode in which reclustering operations will be performed.

11. The method of claim 1 , wherein the data structure comprises an interval tree.

12. A system comprising:
a compute service manager for managing internal operations of a cloud-based database platform;
a plurality of shared storage devices collectively storing database data, wherein the plurality of shared storage devices being independent of the compute service manager; and
an execution platform comprising a plurality of execution nodes, the execution platform being independent of the plurality of shared storage devices and the compute service manager,
the compute service manager being configured to:
receive an indication that a data modification task has been executed on a table of the database by one or more execution nodes of the execution platform;
determine whether the table is sufficiently clustered; the table is not sufficiently clustered, select one or more micro-partitions of the table to be reclustered, the compute service manager being configured to select the one or more micro-partitions to be reclustered comprising the compute service manager being configured to:
construct a data structure for the table;
identify one or more peaks in the data structure that exceed a predefined threshold; and
identify overlapping micro-partitions within each of the one or more peaks; and

assign each of the one or more micro-partitions to an execution node to be reclustered.

13. The system of claim 12 , wherein the compute service manager is configured to determine whether the table is sufficiently clustered by assessing the data modification task to determine whether a sufficient number of rows has been added to the table, a sufficient number of rows has been deleted from the table, and/or a sufficient number of rows has been modified in the table to necessitate the table being reclustered.

14. The system of claim 12 , wherein the compute service manager being configured to select the one or more micro-partitions of the table to be reclustered further comprises the compute service manager being configured to:
identify a constant micro-partition having equivalent minimum and maximum values for a cluster key column; and
remove the constant micro-partition from consideration such that the constant micro-partition is not included in the one or more micro-partitions to be reclustered.

15. The system of claim 12 , wherein:
the data structure comprises a stabbing count array, and
the compute service manager being configured to select the one or more micro-partitions of the table to be reclustered further comprises the compute service manager being configured to:
extract minimum and maximum endpoints for each micro-partition in the stabbing count array; and
compute statistics on each of the minimum and maximum endpoints.

16. The system of claim 15 , wherein the compute service manager being configured to select the one or more micro-partitions of the table to be reclustered further comprises the compute service manager being configured to:
sort each of the one or more peaks in the stabbing count array based on height; and
sort the overlapping micro-partitions based on width.

17. The system of claim 16 , wherein the compute service manager being configured to select the one or more micro-partitions of the table to be reclustered further comprises the compute service manager being configured to select 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-partit

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