# US 11,442,917 B2 · Incremental reclustering based on local maxima of partition overlap > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,442,917 B2 - Document ID: US11442917B2 - Status: Granted - Kind: B2 - Application number: 17/243,795 - Filed: 2021-04-29 - Published: 2021-08-12 - Granted: 2022-09-13 - Earliest claimed: 2018-07-17 - Assignees: Snowflake Inc. - Applicants: Snowflake Inc. - Inventors: Jiaqi Yan; Thierry Cruanes; Jeffrey Rosen; William Waddington; Prasanna Rajaperumal; Abdul Munir - Web page: https://patentgrep.com/patent/US11442917B2 ## CPC - G06F 16/2282: {Tablespace storage structures; Management thereof} - G06F 7/08: Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry (by merging two or more sets of carriers in ordered sequence G06F7/16) - G06F 16/217: {Database tuning (G06F16/2282 takes precedence; database performance monitoring G06F11/3409)} - G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning} - G06F 16/285: {Clustering or classification} - G06F 16/22: Indexing; Data structures therefor; Storage structures - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Disclosed herein are systems and methods for incremental reclustering of database tables based on local maxima of partition overlap. In an embodiment, a database platform makes a determination, based on one or more incremental-reclustering criteria, to incrementally recluster a database table, which has a clustering key and which is stored across a plurality of partitions. In response to making the determination, the database platform selects a subset of the partitions, and at least incrementally reclusters the selected subset. The selecting of the subset includes identifying a local maximum of a quantity of overlapping partitions in the plurality of partitions with respect to a domain of the clustering key of the table, where the overlapping partitions overlap with respect to the clustering key. ## Claims ### Claim 1 A method performed by a database platform executing instructions on at least one hardware processor, the method comprising: making an incremental-reclustering determination to at least partially recluster a database table based on a clustering key of the database table, the database table comprising table data stored across a plurality of partitions; selecting, in response to making the incremental-reclustering determination, a subset of the plurality of partitions, the selecting of the subset comprising: identifying, a point on a domain of the clustering key that corresponds to a local maximum number of overlapping partitions with respect to the domain of the clustering key; and selecting, as the subset, a group of the overlapping partitions that are (i) within a peak that corresponds to the identified point on the domain of the clustering key and (ii) above a reduction goal that is measured in number of overlapping partitions; and at least partially reclustering the selected subset based on the clustering key. ### Claim 2 (depends on 1) The method of claim 1, wherein making the incremental-reclustering determination comprises making the incremental-reclustering determination based on a budget of one or more available computing resources. ### Claim 3 (depends on 1) The method of claim 1, wherein the local maximum number of overlapping partitions is also a global maximum number of overlapping partitions with respect to the domain of the clustering key. ### Claim 4 (depends on 1) The method of claim 1, wherein the local maximum number of overlapping partitions is not a global maximum number of overlapping partitions with respect to the domain of the clustering key. ### Claim 5 (depends on 1) The method of claim 1, wherein selecting, as the subset, a group of the overlapping partitions that are within the peak comprises selecting, as the subset, a group of the overlapping partitions that are within an uppermost portion of the peak. ### Claim 6 (depends on 1) The method of claim 1, wherein selecting, as the subset, a group of the overlapping partitions that are within the peak comprises selecting, as the subset, a group of the overlapping partitions that are (i) within the peak, (ii) above the reduction goal, and (iii) have the greatest widths. ### Claim 7 (depends on 1) The method of claim 1, wherein at least partially reclustering the selected subset comprises reclustering the entire selected subset. ### Claim 8 (depends on 7) The method of claim 7, wherein reclustering the entire selected subset comprises distributing the entire selected subset among a plurality of workers to be reclustered. ### Claim 9 A database platform comprising: at least one hardware processor; and one or more non-transitory computer readable storage media containing instructions that, when executed by the at least one hardware processor, cause the database platform to perform operations comprising: making an incremental-reclustering determination to at least partially recluster a database table based on a clustering key of the database table, the database table comprising table data stored across a plurality of partitions; selecting, in response to making the incremental-reclustering determination, a subset of the plurality of partitions, the selecting of the subset comprising: identifying, a point on a domain of the clustering key that corresponds to a local maximum number of overlapping partitions with respect to the domain of the clustering key; and selecting, as the subset, a group of the overlapping partitions that are (i) within a peak that corresponds to the identified point on the domain of the clustering key and (ii) above a reduction goal that is measured in number of overlapping partitions; and at least partially reclustering the selected subset based on the clustering key. ### Claim 10 (depends on 9) The database platform of claim 9, wherein making the incremental-reclustering determination comprises making the incremental-reclustering determination based on a budget of one or more available computing resources. ### Claim 11 (depends on 9) The database platform of claim 9, wherein the local maximum number of overlapping partitions is also a global maximum number of overlapping partitions with respect to the domain of the clustering key. ### Claim 12 (depends on 9) The database platform of claim 9, wherein the local maximum number of overlapping partitions is not a global maximum number of overlapping partitions with respect to the domain of the clustering key. ### Claim 13 (depends on 9) The database platform of claim 9, wherein selecting, as the subset, a group of the overlapping partitions that are within the peak comprises selecting, as the subset, a group of the overlapping partitions that are within an uppermost portion of the peak. ### Claim 14 (depends on 9) The database platform of claim 9, wherein selecting, as the subset, a group of the overlapping partitions that are within the peak comprises selecting, as the subset, a group of the overlapping partitions within the peak that have the greatest widths. ### Claim 15 (depends on 9) The database platform of claim 9, wherein at least partially reclustering the selected subset comprises reclustering the entire selected subset. ### Claim 16 (depends on 15) The database platform of claim 15, wherein reclustering the entire selected subset comprises distributing the entire selected subset among a plurality of workers to be reclustered. ### Claim 17 One or more non-transitory computer readable storage media containing instructions that, when executed by at least one hardware processor of a database platform, cause the database platform to perform operations comprising: making an incremental-reclustering determination to at least partially recluster a database table based on a clustering key of the database table, the database table comprising table data stored across a plurality of partitions; selecting, in response to making the incremental-reclustering determination, a subset of the plurality of partitions, the selecting of the subset comprising: identifying, a point on a domain of the clustering key that corresponds to a local maximum number of overlapping partitions with respect to the domain of the clustering key; and selecting, as the subset, a group of the overlapping partitions that are (i) within a peak that corresponds to the identified point on the domain of the clustering key and (ii) above a reduction goal that is measured in number of overlapping partitions; and at least partially reclustering the selected subset based on the clustering key. ### Claim 18 (depends on 17) The one or more non-transitory computer readable storage media of claim 17, wherein making the incremental-reclustering determination comprises making the incremental-reclustering determination based on a budget of one or more available computing resources. ### Claim 19 (depends on 17) The one or more non-transitory computer readable storage media of claim 17, wherein the local maximum number of overlapping partitions is also a global maximum number of overlapping partitions with respect to the domain of the clustering key. ### Claim 20 (depends on 17) The one or more non-transitory computer readable storage media of claim 17, wherein the local maximum number of overlapping partitions is not a global maximum number of overlapping partitions with respect to the domain of the clustering key. ### Claim 21 (depends on 17) The one or more non-transitory computer readable storage media of claim 17, wherein selecting, as the subset, a group of the overlapping partitions that are within the peak comprises selecting, as the subset, a group of the overlapping partitions that are within an uppermost portion of the peak. ### Claim 22 (depends on 17) The one or more non-transitory computer readable storage media of claim 17, wherein selecting, as the subset, a group of the overlapping partitions that are within the peak comprises selecting, as the subset, a group of the overlapping partitions within the peak that have the greatest widths. ### Claim 23 (depends on 17) The one or more non-transitory computer readable storage media of claim 17, wherein at least partially reclustering the selected subset comprises reclustering the entire selected sub set. ### Claim 24 (depends on 23) The one or more non-transitory computer readable storage media of claim 23, wherein reclustering the entire selected subset comprises distributing the entire selected subset among a plurality of workers to be reclustered.