# US 11,907,263 B1 · Automated interleaved clustering recommendation for database zone maps > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,907,263 B1 - Document ID: US11907263B1 - Status: Granted - Kind: B1 - Application number: 17/963,756 - Filed: 2022-10-11 - Granted: 2024-02-20 - Earliest claimed: 2022-10-11 - Assignees: Oracle International Corporation - Applicants: Oracle International Corporation - Inventors: Suratna Budalakoti - Web page: https://patentgrep.com/patent/US11907263B1 ## CPC - G06F 16/2455: Query execution - G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning} - 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/24554: {Unary operations; Data partitioning operations} - G06F 16/285: {Clustering or classification} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A computer measures for each column in many rows, a respective frequency of statements that filter the column in a workload of database statements, a respective count of distinct values used for filtration on the column in each statement individually, a respective frequency of each of the counts of distinct values used for filtration on the column across all of the database statements, and a respective value range of the column for each of many storage zones. A respective efficiency is measured for each of many distinct interleaved sorts. Each interleaved sort uses a respective distinct subset of the columns. Each interleaved sort is based on portions of each of the values for each row in a sampled subset of rows in each column of the subset of the columns of the interleaved sort. Efficiency measurement is based on frequencies of statements, value ranges of columns for each storage zone, and frequencies of counts of distinct values. ## Claims ### Claim 1 A method comprising: automatically measuring for each column of a plurality of columns in a plurality of rows: a respective frequency of statements that filter the column in a plurality of database statements, a respective count of distinct values used for filtration on the column in each statement in the plurality of database statements, a respective frequency of each respective count of distinct values used for filtration on the column in the plurality of database statements, and a respective value range of the column for each storage zone of a plurality of storage zones, wherein each storage zone in the plurality of storage zones contains a respective disjoint subset of the plurality of rows; randomly selecting a sampled subset of the plurality of rows; measuring a respective efficiency for each interleaved sort of a plurality of distinct interleaved sorts, wherein: each column of the plurality of columns contains a respective value for each row in the sampled subset of the plurality of rows, the interleaved sort has a respective distinct subset of the plurality of columns, the interleaved sort is based on a plurality of portions of each value of said values for each row in the sampled subset of the plurality of rows in each column of the respective disjoint subset of the plurality of columns of the interleaved sort, and the measuring the respective efficiency is based on: a) said respective frequencies of statements, b) said respective value ranges of the plurality of columns for each storage zone of a plurality of storage zones, and c) said respective frequencies of each respective count of distinct values; measuring a new efficiency based on a best interleaved sort of a plurality of distinct interleaved sorts that has a highest efficiency and said respective value ranges of the plurality of columns, excluding a particular column of the plurality of columns; generating, when the new efficiency exceeds a threshold, a mapping from each column of the plurality of columns, excluding the particular column, to said respective value ranges of the column; and sorting the plurality of rows based on said mapping that excludes the particular column. ### Claim 2 (depends on 1) The method of claim 1 further comprising generating, for each partition of a plurality of horizontal partitions of the plurality of rows, a respective mapping from a particular column of the plurality of columns to said respective value range of the particular column for each storage zone of a plurality of storage zones in the partition. ### Claim 3 (depends on 1) The method of claim 1 wherein the best interleaved sort is based on a null value in values that consists of no portions in said portions of each value of said values. ### Claim 4 (depends on 1) The method of claim 1 wherein the best interleaved sort is based on a particular portion in said plurality of portions of each value of said values that consists of one selected from the group consisting of: a plurality of bits, a byte, and a text character. ### Claim 5 (depends on 1) The method of claim 1 further comprising generating the plurality of distinct interleaved sorts based on a priority queue that contains multiple distinct subsets of the plurality of columns, wherein the priority queue prioritizes based on efficiencies of applied interleaved sorts. ### Claim 6 (depends on 1) The method of claim 1 further comprising: generating the plurality of distinct interleaved sorts based on a queue that contains unapplied interleaved sorts; appending onto the queue at least one selected from the group consisting of an empty subset of the plurality of columns and a first subset of the plurality of columns that contains fewer columns than a second subset of the plurality of columns that was appended onto the queue before the first subset of the plurality of columns. ### Claim 7 (depends on 1) The method of claim 1 further comprising performing an operation selected from the group consisting of shrinking a table that contains said plurality of rows, executing a SELECT INTO statement, and executing an AS SELECT statement, wherein said performing said operation causes said measuring the respective efficiency of the best interleaved sort. ### Claim 8 (depends on 1) The method of claim 1 further comprising: detecting a particular column has a configuration selected from the group consisting of a timestamp and no duplicate values; excluding, based on said detecting, the particular column from the plurality of columns. ### Claim 9 (depends on 1) The method of claim 1 wherein each storage zone of the plurality of storage zones consists of a respective disjoint contiguous sequence of storage blocks. ### Claim 10 (depends on 1) The method of claim 1 wherein: the plurality of storage zones comprises a first zone and a second zone; the first zone contains a different count of objects than the second zone; the objects are selected from the group consisting of bytes, rows, and values. ### Claim 11 One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause: automatically measuring for each column of a plurality of columns in a plurality of rows: a respective frequency of statements that filter the column in a plurality of database statements, a respective count of distinct values used for filtration on the column in each statement in the plurality of database statements, a respective frequency of each respective count of distinct values used for filtration on the column in the plurality of database statements, and a respective value range of the column for each storage zone of a plurality of storage zones, wherein each storage zone in the plurality of storage zones contains a respective disjoint subset of the plurality of rows; randomly selecting a sampled subset of the plurality of rows; measuring a respective efficiency for each interleaved sort of a plurality of distinct interleaved sorts, wherein: each column of the plurality of columns contains a respective value for each row in the sampled subset of the plurality of rows, the interleaved sort has a respective distinct subset of the plurality of columns, the interleaved sort is based on a plurality of portions of each value of said values for each row in the sampled subset of the plurality of rows in each column of the respective disjoint subset of the plurality of columns of the interleaved sort, and the measuring the respective efficiency is based on: a) said respective frequencies of statements, b) said respective value ranges of the plurality of columns for each storage zone of a plurality of storage zones, and c) said respective frequencies of each respective count of distinct values; measuring a new efficiency based on a best interleaved sort of a plurality of distinct interleaved sorts that has a highest efficiency and said respective value ranges of the plurality of columns, excluding a particular column of the plurality of columns; generating, when the new efficiency exceeds a threshold, a mapping from each column of the plurality of columns, excluding the particular column, to said respective value ranges of the column; and sorting the plurality of rows based on said mapping that excludes the particular column. ### Claim 12 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein the instructions further cause generating, for each partition of a plurality of horizontal partitions of the plurality of rows, a respective mapping from a particular column of the plurality of columns to said respective value range of the particular column for each storage zone of a plurality of storage zones in the partition. ### Claim 13 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein the best interleaved sort is based on a null value in values that consists of no portions in said portions of each value of said values. ### Claim 14 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein the best interleaved sort is based on a particular portion in said plurality of portions of each value of said values that consists of one selected from the group consisting of: a plurality of bits, a byte, and a text character. ### Claim 15 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein the instructions further cause generating the plurality of distinct interleaved sorts based on a priority queue that contains multiple distinct subsets of the plurality of columns, wherein the priority queue prioritizes based on efficiencies of applied interleaved sorts. ### Claim 16 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein the instructions further cause: generating the plurality of distinct interleaved sorts based on a queue that contains unapplied interleaved sorts; appending onto the queue at least one selected from the group consisting of an empty subset of the plurality of columns and a first subset of the plurality of columns that contains fewer columns than a second subset of the plurality of columns that was appended onto the queue before the first subset of the plurality of columns. ### Claim 17 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein the instructions further cause performing an operation selected from the group consisting of shrinking a table that contains said plurality of rows, executing a SELECT INTO statement, and executing an AS SELECT statement, wherein said performing said operation causes said measuring the respective efficiency of the best interleaved sort. ### Claim 18 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein the instructions further cause: detecting a particular column has a configuration selected from the group consisting of a timestamp and no duplicate values; excluding, based on said detecting, the particular column from the plurality of columns.