MICRO-PARTITION CLUSTERING BASED ON EXPRESSION PROPERTY METADATA

A method for selecting micro-partitions for a clustering operation includes: storing table data in a plurality of micro-partitions of a storage device, wherein each of the plurality of micro-partitions comprises a portion of the table data, wherein subsets of the plurality of micro-partitions are associated with a respective one of a plurality of expression property (EP) files, and wherein each of the plurality of EP files comprises an EP data region that represents the portions of the table data of the subset of the plurality of micro-partitions associated with the EP file; determining sub-ranges of the table data based on the EP data regions of the plurality of EP files; selecting a subset of the plurality of EP files for a clustering operation based on the sub-ranges of the table data; and performing the clustering operation on the micro-partitions associated with the subset of the EP files.

TECHNICAL FIELD

The present disclosure relates to databases and database management, and, more particularly, relates to clustering micro-partitions containing database data.

BACKGROUND

Databases are widely used for data storage and access in computing applications. Databases may include one or more tables that include data that can be joined, read, modified, or deleted using queries. Databases can store small or extremely large sets of data within one or more tables. This data can be accessed by various users in an organization or even be used to service public users, such as via a website or an application programming interface (API). The large amount of data that can be contained within a database can often be useful for various types of data analytics, which involves the attempt to determine conclusions and/or predictions based on analysis of the information contained in the data. When working with large volumes of data, improvements to the efficiency of database queries can provide significant improvements to the cost and time associated with the data analysis.

DETAILED DESCRIPTION

Databases are widely used for data storage and access in computing applications. A goal of database storage is to provide enormous sums of information in an organized manner so that it can be accessed, managed, and updated. In some embodiments of a database, data may be organized into rows, columns, and tables. Different database storage systems may be used for storing different types of content, such as bibliographic, full text, numeric, and/or image content. Further, in computing, different database systems may be classified according to the organization approach of the database. There are many different types of databases, including relational databases, distributed databases, cloud databases, object-oriented databases, and others.

Queries can be executed against database data to find certain data within the database and respond to a question about the database data. A database query extracts data from the database and formats it into a readable form. For example, when a user wants data from a database, the user may write a query in the language required by the database. The query may request specific information from the database. For example, if the database includes information about sales transactions made by a retail store, a query may request all transactions for a certain product during a certain time frame. The query may request any pertinent information that is stored within the database. If the appropriate data can be found to respond to the query, the database has the potential to reveal complex trends and activities.

However, when a database becomes very large and includes vast sums of data, it can be very difficult to respond to a database query. Further to the above example, if the database includes a record of all sales transactions for the retail store over an extensive time period, the database may include multiple tables that each include billions of rows of information divided into hundreds or thousands of columns. If a user requests all transactions for a certain product across the entire history of the database, it can require extensive computing resources and time to scan the entire database to find each of the requested transactions.

Databases may further include metadata, or information about the database data, to aid in organizing the database and responding to queries on the database. Metadata is data information that provides information about other data. For example, metadata about an image file may include information such as the date and time the image was captured, the camera that captured the image, the camera settings when the image was captured, a file size of the image, a name of the image, and so forth. Further for example, metadata about a table in a database may include information such as the minimum value in the table, the maximum value in the table, the number of rows in the table, the number of columns in the table, the type of data stored in the table, the subject of the data stored in the table, and so forth.

Metadata can be useful for responding to a database query. For example, metadata may be helpful in performing various types of performance enhancements for queries. One such enhancement is pruning. Pruning is described, for example, in U.S. Pat. No. 10,437,780, entitled “Data pruning based on metadata,” the entire contents of which are incorporated herein by reference. In some embodiments of data pruning, the predicates of a database query are examined to determine the ranges and/or types of data being queried. Metadata for the data stored in the table may then be used to rule out certain portions of the data storage from being scanned. By reducing the amount of data being scanned, the overall performance of the database will improve.

Pruning can be a very important part of query compilation in complex databases, such as those described herein. However, particularly in the context of a large database, the metadata itself can become very large and require extensive computing resources and time to just scan the metadata without scanning any of the database data. In certain implementations it can be useful to employ an organized and efficient metadata structure. With multi-level metadata, a database can effectively have metadata about groups of metadata. In such a hierarchical structure, higher level metadata may be queried before lower level metadata, which may allow for less of the metadata to be loaded.

However, even with such multi-level metadata, additional improvements may still be made. By aligning the groups of the metadata with underlying organization strategies of the database tables, such as data clustering, additional improvements to the metadata grouping may be achieved. Described herein are systems, methods, and computer program products that intelligently organize groups of metadata so as to reduce the amount of metadata that is loaded when query pruning and other types of database management are performed. Methods described herein reduce the amount of memory utilized for query compilation and allow for fewer resources to be used to perform other database tasks such as data compaction.

FIG.1is a block diagram of an example computing environment100in which the systems and methods disclosed herein may be implemented. In particular, a cloud computing platform110may be implemented, such as AMAZON WEB SERVICES™ (AWS), MICROSOFT AZURE™, GOOGLE CLOUD™ or GOOGLE CLOUD PLATFORM™, or the like. As known in the art, a cloud computing platform110provides computing resources and storage resources that may be acquired (purchased) or leased and configured to execute applications and store data. The cloud computing platform110may be accessed by a client101(e.g., a client device). Non-limiting examples of client devices include a smart phone101A, personal computer101B, laptop101C, tablet computer101D, server computer101E, and/or another type of device that can process data.

FIG.1and the other figures may use like reference numerals to identify like elements. A letter after a reference numeral, such as “101A,” indicates that the text refers specifically to the element having that particular reference numeral. A reference numeral in the text without a following letter, such as “101,” refers to any or all of the elements in the figures bearing that reference numeral.

In some embodiments, client devices101may access the cloud computing platform110over a network105. Network105may be a public network (e.g., the internet), a private network (e.g., a local area network (LAN) or wide area network (WAN)), or a combination thereof. In one embodiment, network105may include a wired or a wireless infrastructure, which may be provided by one or more wireless communications systems, such as a WIFI® hotspot connected with the network105and/or a wireless carrier system that can be implemented using various data processing equipment, communication towers (e.g., cell towers), etc. The network105may carry communications (e.g., data, message, packets, frames, etc.) between the various components of the cloud computing platform110and one more of the client devices101.

The cloud computing platform110may host a cloud computing service112that facilitates storage of data on the cloud computing platform110(e.g., data management and access) and analysis functions (e.g., SQL queries, analysis), as well as other computation capabilities (e.g., secure data sharing between users of the cloud computing platform110). The cloud computing platform110may include a three-tier architecture: data storage140, query processing130, and cloud services120.

Data storage140may facilitate the storing of data on the cloud computing platform110in one or more cloud databases141. Data storage140may use a storage service such as AMAZON S3 to store data and query results on the cloud computing platform110. In particular embodiments, to load data into the cloud computing platform110, data tables may be horizontally partitioned into large, immutable files which may be analogous to blocks or pages in a traditional database system. Within each file, the values of each attribute or column are grouped together and compressed using a scheme sometimes referred to as hybrid columnar. Each table has a header which, among other metadata, contains the offsets of each column within the file.

In addition to storing table data, data storage140facilitates the storage of metadata, temp data generated by query operations (e.g., joins), as well as the data contained in large query results. This may allow the system to compute large queries without out-of-memory or out-of-disk errors. Storing query results this way may simplify query processing as it removes the need for server-side cursors found in traditional database systems.

Query processing130may handle query execution by compute nodes within elastic clusters of virtual machines, referred to herein as virtual warehouses or data warehouses. Thus, query processing130may include one or more virtual warehouses131having one or more compute nodes132, which may also be referred to herein as data warehouses. The virtual warehouses131may be one or more virtual machines operating on the cloud computing platform110. The virtual warehouses131may be compute resources that may be created, destroyed, or resized at any point, on demand. This functionality may create an “elastic” virtual warehouse131that expands, contracts, or shuts down according to the user's needs. Expanding a virtual warehouse131involves generating one or more compute nodes132to the virtual warehouse131. Contracting a virtual warehouse131involves removing one or more compute nodes132from the virtual warehouse131. More compute nodes132may lead to faster compute times. For example, a data load which takes fifteen hours on a system with four nodes might take only two hours with thirty-two nodes.

Cloud services120may be a collection of services (e.g., computer instruction executing on a processing device) that coordinate activities across the cloud computing service112. These services tie together all of the different components of the cloud computing service112in order to process user requests, from login to query dispatch. Cloud services120may operate on compute instances provisioned by the cloud computing service112from the cloud computing platform110. Cloud services120may include a collection of services that manage virtual warehouses, queries, transactions, data exchanges, and the metadata associated with such services, such as database schemas, access control information, encryption keys, and usage statistics. Cloud services120may include, but not be limited to, authentication engine121, infrastructure manager122, optimizer123, exchange manager124, security engine125, and metadata storage126. Though metadata storage126is illustrated as being separate from the data storage140inFIG.1, this is merely for schematic purposes and is not intended to limit the present disclosure. In some embodiments, the metadata storage126is co-located with the data storage140.

In one embodiment, the cloud computing service112can perform, or cause to be performed, data management operations on the data storage140. In some embodiments, the data management operations may include the generation of metadata for data of the data storage140. In some embodiments, multiple levels of metadata may be formed, one level of the metadata containing metadata values for a group of metadata in another level of the metadata. In some embodiments, the groups of the metadata may be organized at least partially based on data organization metrics of the data storage140. For example, in some embodiments, the groups of the metadata may be organized at least partially based on a clustering key of the data storage140.

FIG.2is a schematic diagram of a data structure200for storage of database metadata, according to some embodiments of the present disclosure. The data structure200includes table metadata202pertaining to database data stored across a table of the database. The table may be composed of multiple micro-partitions (MP)210. Each of the multiple micro-partitions210may include numerous rows and columns making up cells of database data.

In some embodiments, the plurality of micro-partitions210of the table may be provided as immutable storage devices. When a transaction is executed on such a table, all impacted micro-partitions210are recreated to generate new micro-partitions210that reflect the modifications of the transaction. After a transaction is fully executed, any original micro-partitions210that were recreated may then be removed from the database. In some embodiments, a new version of the table is generated after each transaction that is executed on the table. The table may undergo many versions over a time period if the data in the table undergoes many changes, such as inserts, deletes, updates, and/or merges.

The table metadata202may include global information about the table of a specific version. In some embodiments, the table metadata202may include a table identification and versioning information indicating, for example, how many versions of the table have been generated over a time period, which version of the table includes the most up-to-date information, how the table was changed over time, and so forth. A new table version may be generated each time a transaction is executed on the table, where the transaction may include a data manipulation language (DML) statement such as an insert, delete, merge, and/or update command. Each time a DML statement is executed on the table, and a new table version is generated, one or more new micro-partitions210may be generated that reflect the DML statement.

The data structure200further includes micro-partition metadata (MP MD)214(also referred to herein as a micro-partition metadata file214) that includes metadata about a micro-partition210of the table. In some embodiments, each of the micro-partition metadata214may include information about at least one respective micro-partition210of the table. The micro-partitions210illustrated inFIG.2may include database data that is separate from the metadata storage. In some embodiments, the micro-partition metadata214may be stored for each column of each micro-partition210of the table. The micro-partition metadata214pertaining to a particular micro-partition210may include any suitable information about data of a portion of the table (e.g., a column) stored in the micro-partition210, including for example, a minimum and maximum for the data stored in a portion of the database (e.g., a column), a type of data stored in the portion of the database, a subject of the data stored in the portion of the database, versioning information for the data stored in the portion of the database, file statistics for all micro-partitions210in the table, global cumulative expressions for columns of the table, and so forth. Each column of each micro-partition210of the table may be associated with one or more micro-partition metadata elements214. As illustrated in the example embodiment shown inFIG.2, the table metadata202includes micro-partition metadata214for each micro-partition210. However, the embodiments of the present disclosure are not limited thereto. It should be appreciated that the table may include any number of micro-partitions210and any number of micro-partition metadata214, and each micro-partition210may include any number of columns. The micro-partitions210may have the same or different columns and may have different types of columns storing different information.

The data structure200further includes a plurality of expression property files (EP or EP files)220A,220B, and220C (which may be collectively referenced herein as EP files220). The EP files220may include aggregated micro-partition statistics, cumulative column properties, and so forth about a micro-partition210or a collection of micro-partitions210of the table. A micro-partition metadata file214may be stored for each column of each micro-partition210of the table, and an EP file220may be stored for a collection of micro-partition metadata files214associated with a plurality of micro-partitions210of the table as illustrated inFIG.2.

The data structure200may include micro-partition metadata214for each micro-partition210of the table. The micro-partition metadata214may include a minimum/maximum data point for the corresponding micro-partition210, a type of data stored in the corresponding micro-partition210, a micro-partition structure of the corresponding micro-partition210, and so forth. The micro-partition metadata214may be stored as part of a micro-partition that is allocated for metadata (e.g., as opposed to data of the database). A micro-partition allocated for metadata may be persisted in immutable storage and the EP files220may also be stored within the metadata micro-partition in immutable storage. A metadata manager may maintain all metadata micro-partitions, including metadata micro-partitions comprising the EP files220and/or the micro-partition metadata214.

The cumulative table metadata202may include global information about all micro-partitions210within the applicable table. For example, the cumulative table metadata202may include a global minimum and global maximum for the entire table, which may include millions or even hundreds of millions of micro-partitions210. The cumulative table metadata202may include any suitable information about the data stored in the table, including, for example, minimum/maximum values, null count, a summary of the database data collectively stored across the table, a type of data stored across the table, a distinct version for the data stored in the table, and so forth.

The EP files220A-220C may include information about database data stored in an associated grouping240of micro-partitions210. In the example ofFIG.2, an example EP file220A is associated with a grouping240of three micro-partition metadata214that are respectively associated with three micro-partitions210. The example EP file220A may include information about those three different micro-partitions210. An EP file220may include any suitable information about the grouping240of the micro-partitions210and/or micro-partition metadata214with which it is associated. For example, an EP file220may include a cumulative minimum/maximum for the collective grouping240of micro-partitions210, a minimum/maximum for each of the micro-partitions210within the grouping240, a cumulative null count, a null count for each of the micro-partitions210within the grouping240, a cumulative summary of data collectively stored across the grouping240of micro-partitions210, a summary of data stored in each of the micro-partitions210in the grouping240, and so forth.

The EP files220illustrated inFIG.2provide valuable cumulative metadata pertaining to a collection of micro-partition metadata214and micro-partitions210of the database. Further, each of the micro-partition metadata214provide valuable information about respective ones of the micro-partitions210of the table.

FIG.3illustrates an example grouping240of micro-partitions210, micro-partition metadata214, and EP files220ofFIG.2, according to some embodiments of the present disclosure. The grouping240is an example to illustrate the EP files220, and is not intended to limit the embodiments of the present disclosure.

Referring toFIG.3, the data structure200may include grouping240of micro-partitions210. More specifically, the example grouping240may include micro-partition210A, micro-partition210B, and micro-partition210C (referred to collectively as micro-partitions210). Each of the micro-partitions may be respectively associated with a micro-partition metadata file214. For example, micro-partition metadata file214A may be associated with micro-partition210A, micro-partition metadata file214B may be associated with micro-partition210B, and micro-partition metadata file214C may be associated with micro-partition210C. An EP file220A may be associated with the micro-partition210A, micro-partition210B, and micro-partition210C, as well as their associated micro-partition metadata files214(e.g., micro-partition metadata files214A,214B,214C).

As described herein, the micro-partitions210may contain one or more portions of data from a database. For example, the micro-partitions210may contain one or more columns and/or rows from a table of the database. Example data is provided inFIG.3to aid in understanding. For example, micro-partition210A contains a first column including data elements180,200, and150along with a second column including data elements “Alpha,” “Beta,” and “Gamma.” Micro-partition210B contains the first column including data element values450,500, and400along with the second column including data element values “Delta,” “Epsilon,” and “Zeta.” Micro-partition210C contains the first column including data element values175,220, and180along with the second column including data elements “Eta,” “Theta,” and “Iota.” As previously noted, these data values are merely examples and not intended to limit the embodiments of the present disclosure.

Each of the micro-partitions210may be associated with at least one micro-partition metadata file214. The micro-partition metadata file214may maintain, in part, metadata describing the data values of the micro-partitions210. InFIG.3, an example is shown for metadata of the micro-partition metadata file214regarding the maximum (max) and minimum (min) of data of the micro-partition210. However, as described herein, a number of different types of metadata may be maintained in the micro-partition metadata file214. For example, the metadata214of the micro-partition210may include values tracking null values of the data of the micro-partition210, length of the data, and so on.

In the example ofFIG.3, micro-partition metadata file214A is associated with micro-partition210A. The metadata of the micro-partition metadata file214A tracks that the maximum (max) of the data of the first column of the micro-partition210A is 200 and the minimum (min) of the data of the first column of the micro-partition210A is 150. Micro-partition metadata file214B is associated with micro-partition210B. The metadata of the micro-partition metadata file214B tracks that the maximum (max) of the data of the first column of the micro-partition210B is 500 and the minimum (min) of the data of the first column of the micro-partition210B is 400. Micro-partition metadata file214C is associated with micro-partition210C. The metadata of the micro-partition metadata file214C tracks that the maximum (max) of the data of the first column of the micro-partition210C is 220 and the minimum (min) of the data of the first column of the micro-partition210C is 175. The minimum and maximum data values maintained by the respective micro-partition metadata214represents a smallest value and a largest value, respectively, of the data for a particular column (e.g., the first column) for a respective micro-partition210.

The micro-partition metadata files214A,214B, and214C may be associated with an EP file220. In the example ofFIG.3, micro-partition metadata files214A,214B, and214C are each associated with EP file220A. The metadata of the EP file220A tracks that the maximum (max) of the metadata of the first column tracked by the micro-partition metadata files214A,214B, and214C is 500 and the minimum (min) of the metadata of the first column tracked by the micro-partition metadata files214A,214B, and214C is 150. The minimum and maximum data values maintained by the EP file220represents a smallest value and a largest value, respectively of the metadata for a particular column (e.g., the first column) for the micro-partition metadata files214within the grouping240.

The use of the micro-partition metadata files214and the EP files220may increase the efficiency of query processing. For example, as part of data pruning for a query, it may be determined that a particular query utilizes a predicate that restricts data values returned to those in which the first column has a value less than 100. By reviewing the min and max of the EP file220, it can be determined that none of the micro-partition metadata files214associated with the EP file220have a data value in the first column that would match this query. Subsequently, the micro-partitions210of the grouping240may be skipped in a scan of data to find values that should be returned for the query.

As another example, as part of data pruning for a query, it may be determined that a particular query utilizes a predicate that restricts data values returned to those in which the first column has a value less than 200. By reviewing the min and max of the EP file220, it can be determined that at least one of the micro-partition metadata files214associated with the EP file220has a data value in the first column that would match this query. Responsive to this determination, the metadata for the micro-partition metadata files214associated with the EP file220may be examined. From that examination, it can be determined that the micro-partition metadata files214A and214C have min and max values indicating that their respective micro-partitions210contain data that would match this query. Subsequently, the micro-partition210B of the grouping240may be skipped and the micro-partitions210A and210C may be examined in a scan of data to find values that should be returned for the query.

The data structure200shown inFIGS.2and3increases efficiency when responding to database queries. A database query may request any collection of data from the database and may be used to create advanced analyses and metrics about the database data. Some queries, particularly for a very large database, can be extremely costly to run both in time and computing resources. When it is necessary to scan metadata and/or database data for each file or micro-partition of each table of a database, it can take many minutes or even hours to respond to a query. In certain implementations this may not be an acceptable use of computing resources. The data structure200disclosed herein provides increased metadata granularity and enables multi-level pruning of database data.

During compilation and optimization of a query on the database, a processing device may scan the cumulative table metadata202to determine if the table includes information pertaining to the query. In response to determining, based on the cumulative table metadata202, that the table includes information pertaining to the query, the processing device may scan each of the EP files220to determine which grouping of micro-partitions210of the table include information pertaining to the query. In response to determining, based on a first EP file220, that a first grouping240of micro-partitions210does not include information pertaining to the query, the processing device may discontinue database scanning of that first grouping240of micro-partitions210.

In response to determining, based on a second EP file220, that a second grouping240of micro-partitions210includes information pertaining to the query, the processing device may proceed to scan micro-partition metadata files214for that second grouping240of micro-partitions210. The processing device may efficiently determine which micro-partitions210include pertinent data and which columns of which micro-partitions210do not include pertinent data. The processing device may proceed to scan only the relevant column(s) and micro-partition(s)210that include information relevant to a database query. This provides a cost efficient means for responding to a database query by way of multi-level pruning based on multi-level table metadata.

Further to increase the cost efficiency of database queries, a resource manager (e.g., cloud services120ofFIG.1) may store the cumulative table metadata202in a cache for faster retrieval. Metadata for the database may be stored in a metadata store separate and independent of a plurality of shared storage devices collectively storing database data. In some embodiments, metadata for the database may be stored within the plurality of shared storage devices collectively storing database data. In some embodiments, metadata may be stored in metadata-specific micro-partitions that do not include database data, and/or may be stored within micro-partitions that also include database data. The metadata may be stored across disk storage, such as the plurality of shared storage devices, and it may also be stored in cache within the resource manager.

Though the use of multi-level metadata may provide benefits, it may still introduce challenges. For example, the generation of the groupings240may be made in a naive manner. For example, as new micro-partitions210are created (along with new micro-partition metadata files214), they may be grouped based on time of creation and/or registration. This may result in configurations that are suboptimal.FIG.4illustrates an example modification of a micro-partition210, according to some embodiments of the present disclosure.

The example ofFIG.4illustrates a scenario in which the micro-partition metadata214and the micro-partitions210are stored in immutable storage. In such a scenario, a modification to data within a micro-partition210may result in the formation of a new micro-partition210rather than an in-situ modification of the current micro-partition210containing the data. Though the example ofFIG.4concerns immutable storage, the embodiments of the present disclosure are not limited to such a configuration.

In the example ofFIG.4, it is assumed that a data modification is performed to the data of micro-partition210B (e.g., as a result of a DML transaction). For example, the data of the first column that previously had a value of 450 (illustrated by reference number410) may be changed to have a value of 50. In such a scenario, new micro-partitions210D and210E may be created.

For example, micro-partition210D contains a first column including data element values500and400along with a second column including data elements “Epsilon” and “Zeta.” The data of micro-partition210D may be the data from the original micro-partition210B that has been moved, e.g., due to the immutability of micro-partition210B. Micro-partition210E contains the first column including data element50along with the second column including the data element “Delta.” The data of micro-partition210E may be the data from the original micro-partition210B that has been updated, e.g., due to the immutability of micro-partition210B. In some embodiments, two new micro-partitions210D,210E may be created rather than forming a single new micro-partition210for a number of potential reasons. For example, as will be discussed further herein, the data of the micro-partitions210may be organized based on clustering keys associated with the data.

Each of the new micro-partitions210D,210E will each be associated with a micro-partition metadata file214. For example, micro-partition metadata214D is associated with micro-partition210D. The metadata of the micro-partition metadata214D tracks that the maximum (max) of the data of the first column of the micro-partition210D is 500 and the minimum (min) of the data of the first column of the micro-partition210D is 400. Micro-partition metadata214E is associated with micro-partition210E. The metadata of the micro-partition metadata214E tracks that the maximum (max) of the data of the first column as well as the minimum (min) of the data of the first column of the micro-partition210E is 50.

The micro-partition metadata files214D,214E may also be associated with EP file220A′. Due to the update of the data that resulted in the formation of the new micro-partition210E, the minimum (min) of the metadata tracked by the micro-partition metadata file214E may now be 50. The EP file220A′ may either be an updated form of the previous EP file220A, or may be a new EP file220A′ formed due to the EP file220A being formed in immutable storage. The updated EP file220A′ may include micro-partition metadata files214A,214C,214D, and214E.

The update of the minimum value of the EP file220A′ to 50 now means that the minimum and maximum values of the EP file220A′ cover a much larger range. As a result of covering a much larger range, the efficiency of the pruning may be impacted because the pruning may not be able to deselect as many micro-partition metadata files214(and their associated micro-partitions210) for scanning. For example, in the prior-discussed scenario in which a predicate of a query selected data based on the data of the first column being less than 100, pruning would allow all of the micro-partitions210to be skipped in the example ofFIG.3. With this update to the data, the same query will now require all of the micro-partition metadata214to be scanned, despite the fact that only one of the micro-partitions210, micro-partition210E, meets this predicate.

In some embodiments, since the data represented by the micro-partitions210may include different types of data having different values, clustering may be performed based on metadata associated with a particular data value and/or values of the micro-partitions210. For example, in some embodiments, the metadata that is used for determining membership in an EP file220may be based on a clustering key used to organize the micro-partitions210. A clustering key is a subset of columns in a table (or expressions on a table, such as SQL expressions) that are designated to co-locate the data in the table in the same micro-partitions210. When specified, the clustering key may be utilized to identify portions of the table which are to be used for making decisions about which data to co-locate within a micro-partition210. For example, if a particular column of a table is identified as a clustering key, values of the data of that particular column may be utilized to identify rows of the table that are to be co-located in a same micro-partition210. For example, rows of the table having values of the first particular column that are relatively close to one another (e.g., within a threshold numeric distance if the first column is a numeric value) may be located in a same micro-partition210. In some embodiments, the clustering key may be specified by the administrator, such as when a database table is created. In some embodiments, the clustering keys that are utilized to co-locate data in micro-partitions210may also be utilized for determining the membership in EP files220. Clustering keys, as well as clustering in general, are discussed in U.S. Pat. No. 10,817,540, entitled “Incremental clustering maintenance of a table,” the entire contents of which are incorporated herein by reference.

In some embodiments, to avoid and/or reduce issues in which the EP files220and/or the micro-partitions210cover large ranges, rendering pruning inefficient, the EP files220and/or the micro-partitions210may be re-clustered (e.g., periodically). Clustering may include reorganizing the data of the EP files220and/or the micro-partitions210to form EP files220and/or the micro-partitions210that cover smaller ranges. In a system in which the EP files220and/or the micro-partitions210are stored in immutable storage, clustering may include forming new EP files220and/or new micro-partitions210having different data and/or micro-partition metadata214, as described, for example, with respect toFIG.4.

In some embodiments, the selection of micro-partitions210for clustering members of an EP file220may be performed based on how well-clustered the EP files220of the database are determined to be. A table may be defined as clustered based on a certain order-preserving function which takes data in each row as input if rows that are close in evaluation of this function are also close together in their physical ordering. The degree of clustering (clustering ratio) of a table may be determined by the proportion of rows in the physical layout of the table that satisfy such ordering criteria. Perfect clustering is achieved when for any two rows in the table that are adjacent in their physical layout, no third row can be found that yields a closer distance to both rows according to the ordering function. For tables stored as micro-partitions210, clustering improves the probability that rows closer according to the ordering function should reside in the same micro-partition210.

In some embodiments, the micro-partitions210may be scanned to determine if the clustering ratio may be improved and, if so, clustering may be performed on the micro-partitions210. If the micro-partitions210are stored in immutable storage, the clustering of the micro-partitions210may involve the deletion and recreation of micro-partitions210. When the micro-partitions210are recreated, they may be associated with micro-partition metadata files214, which may subsequently be organized into EP files220, as described herein.

In a similar manner, the EP files220may be scanned to determine if the clustering ratio of the metadata range encompassed by the EP file220may be improved. If so, the members of the EP file220may be re-clustered. The clustering of the EP file220may involve the movement of assignments of micro-partition metadata files214between EP files220. For example, a micro-partition metadata file214may be removed from one EP file220to another EP file220. In some embodiments, selection of micro-partition metadata files214for membership in an EP file220may be performed in a similar matter as described herein (e.g., based on a metadata range for a data value, such as a clustering key, and/or a time of creation/registration). If the EP files220are stored in immutable storage, the clustering of the EP files220may involve the deletion and recreation of EP files220. In some embodiments, an improvement to the clustering quality of the micro-partitions210may also involve the deletion and recreation of the micro-partitions210, which may cause the EP files220to be modified based on modifications to the underlying micro-partitions210.

Clustering the EP files220and/or the micro-partitions210may be performed by looking at how storage of a clustering key is represented within the EP files220and/or the micro-partitions210and reforming the EP files220and/or the micro-partitions210to more closely locate values of the clustering keys stored in the micro-partitions210within a same EP file220and/or the micro-partition210. In a theoretical scenario, all of the micro-partitions210of a given database could be analyzed during clustering, and new micro-partitions210formed in which values of the clustering key that were close to one another within a data range were also clustered within a same micro-partition210. New micro-partition metadata214could then be formed for the data ranges of the new micro-partitions210, and new EP files220could be formed based on the new micro-partition metadata214. However, in a practical sense, analysis of all of the micro-partitions210and/or micro-partition metadata214may take an unreasonable amount of time and/or computing resources. For example, to understand how the different ranges of the clustering key are stored across large numbers of micro-partitions210, large amounts of data may be cached, which may make such an analysis impractical. Moreover, if all of the micro-partitions210are potentially re-clustered, it may set up a scenario in which a large number of the EP files220associated with the micro-partitions210are also re-clustered due to the changes in the micro-partitions210. This may cause extensive churn within the database and negatively affect performance.

Embodiments of the present disclosure arise, at least in part, from a recognition that clustering may be improved by selectively analyzing a subset of the micro-partitions210for clustering. By focusing clustering on micro-partitions210that are more likely to have overlapping values (e.g., with respect to the data values of a clustering key) micro-partitions210may be selected that have a high potential of providing improvements to the clustering of the data storage. Embodiments according to the present disclosure may be far more memory efficient and may reduce churn across the entire table, which can affect query performance when EP files220are to be reloaded into the cache. By selecting micro-partitions210from a subset of EP files220, a number of the EP files220that are to be reloaded may be limited, and this may also improve the efficiency of clustering of the micro-partitions210because it may reduce the amount of work associated with the clustering and allow the clustering of the micro-partitions210to converge.

Embodiments of the present disclosure may improve an operation of the computer by reducing an amount of memory and/or processing resources utilized to provide a database operation. Moreover, embodiments of the present disclosure may improve the technology associated with databases and database processing by providing a more effective mechanism to cluster data within the database storage and, thereby, improve an efficiency and/or speed of a data query (e.g., via pruning).

It may be understood that the clustering of the EP files220may be independent of a clustering of the micro-partitions210. For example, in some embodiments, a clustering ratio of the micro-partitions210may be at least partially independent of the clustering ratio of the EP file220. For example, in some embodiments, clustering of the EP files220may be performed regardless of a clustering state of the micro-partitions210. In some embodiments, clustering of the micro-partitions210may be performed regardless of a clustering state of the EP files220.

In some embodiments, clustering of the micro-partitions210may be performed based on one or more clustering statistics of the EP files220and/or the micro-partition metadata files214of the micro-partitions210. Statistics that may be used to determine a clustering level of an EP file220may include: a number of micro-partitions210per micro-partition metadata file214; an average depth and overlap per micro-partition metadata file214; an average depth and overlap for the micro-partition metadata files214of the EP file220; a maximum depth and/or overlap per micro-partition metadata file214; a maximum depth and/or overlap for the micro-partition metadata files214of the EP file220; a median depth and/or overlap per micro-partition metadata file214; a median depth and/or overlap for the micro-partition metadata files214of the EP file220; a distribution (e.g., a percentile) of the depth and/or overlap for the micro-partition metadata files214; a distribution (e.g., a percentile) of the depth and/or overlap for the micro-partition metadata files214of the EP file220; and/or an average range of the EP file220. The depth for a micro-partition210may be the maximum number of intersected micro-partitions210at any given range. The overlap for a particular micro-partition210is the total number of other micro-partitions210intersected with the particular micro-partition210. A first micro-partition210may overlap a second micro-partition210if the data values between the minimum and maximum data values (e.g., of the clustering key) of the first micro-partition210intersect the data values between the minimum and maximum data values (e.g., of the clustering key) of the second micro-partition intersection210. The above characteristics are merely examples, and not intended to limit the embodiments of the present disclosure.

FIG.5is a block diagram illustrating techniques for the selection of micro-partitions210for clustering, according to some embodiments of the present disclosure. A description of elements ofFIG.5that have been previously described will be omitted for brevity. The data structures ofFIG.5are for the purposes of an example, and are not intended to limit the embodiments of the present disclosure.

In some embodiments, the selection of the micro-partition metadata files214and/or EP files220may be performed based on an average depth and an overlap of the micro-partition metadata files214and/or EP files220. Once selected for clustering, a given micro-partition metadata file214and/or EP file220may be recreated and/or reorganized according to embodiments described herein. For example, a selection of data for membership in a micro-partition210and/or a selection of micro-partition metadata files214and their associated micro-partitions210for membership in an EP file220during clustering may be performed in a similar matter as described herein (e.g., based on a metadata range for a data value, such as a clustering key).

FIG.5illustrates an example of a data structure500having a plurality of EP files220, each having micro-partition metadata214, as described herein. In some embodiments, each of the micro-partition metadata files214may respectively represent a micro-partition210. However, for purposes of description, only the micro-partition metadata files214and the EP files220are illustrated inFIG.5. For example, the data structure500may include a first EP file220A, a second EP file220B, a third EP file220C, and a fourth EP file220D. The first EP file220A may include a first micro-partition metadata file214A, a second micro-partition metadata file214B, a third micro-partition metadata file214C, and a fourth micro-partition metadata file214D. The second EP file220B may include a fifth micro-partition metadata file214E and a sixth micro-partition metadata file214F. The third EP file220C may include a seventh micro-partition metadata file214G, an eighth micro-partition metadata file214H, a ninth micro-partition metadata file214I, and a tenth micro-partition metadata file214J. The fourth EP file220D may include an eleventh micro-partition metadata file214K, a twelfth micro-partition metadata file214L, a thirteenth micro-partition metadata file214M, and a fourteenth micro-partition metadata file214N.

InFIG.5, each of the micro-partition metadata files214is illustrated along a representative data range510. The length of a line associated with each of the micro-partition metadata files214is intended to illustrate a given range (e.g., a minimum data value to a maximum data value) for the data values of the clustering key represented by a particular micro-partition metadata file214(e.g., the data values of the clustering key stored in the micro-partitions210associated with the particular micro-partition metadata file214). For example, when two of the micro-partition metadata files214are illustrated as being overlapping, that is intended to convey that the data ranges (e.g., of the clustering key) covered by the micro-partitions210represented by the micro-partition metadata files214may overlap. InFIG.5, the illustrations are shown with respect to the range of the micro-partition metadata files214, but it will be understood that the micro-partition metadata files214also represent micro-partitions210.

In some embodiments, whether to perform clustering a given EP file220and/or micro-partition metadata file214may be made based on a calculation of an average depth of the micro-partition metadata files214within an EP file220and/or an overlap of the EP files220. However, the embodiments of the present disclosure are not limited to such a configuration.

A depth of a first micro-partition metadata file214and/or micro-partition210may be defined to be, at any given data point, the maximum number of other micro-partition metadata files214within the EP file220covering that same data. For a given EP file220, a depth may be calculated for each micro-partition metadata file214(and its associated micro-partition210) of the EP file220, and an average depth for the EP file220may be calculated based on the calculated depth for each of the member micro-partitions210. An overlap of a first EP file220may be defined to be the number of other EP file220whose data ranges overlap the first EP file220.

Referring toFIG.5, within the first EP file220A, the first micro-partition metadata file214A may have a depth of 1 (e.g., itself). The second micro-partition metadata file214B may have a depth of 2. The third micro-partition metadata file214C may have a depth of 2. The fourth micro-partition metadata file214D may have a depth of 2. The first EP file220A may have an average depth of 1.75.

Within the second EP file220B, both the fifth micro-partition metadata file214E and the sixth micro-partition metadata file214F may have a depth of 1. The second EP file220B may have an average depth of 1.

Within the third EP file220C, each of the seventh micro-partition metadata file214G, the eighth micro-partition metadata file214H, the ninth micro-partition metadata file214I, and the tenth micro-partition metadata file214J may have a depth of 3. The third EP file220C may have an average depth of 3.

Within the fourth EP file220D, the eleventh micro-partition metadata file214K may have a depth of 2. The twelfth micro-partition metadata file214L may have a depth of 3. The thirteenth micro-partition metadata file214M may have a depth of 3. The fourteenth micro-partition metadata file214N may have a depth of 3. The fourth EP file220D may have an average depth of 2.75.

In addition to being calculated at a level of the micro-partition metadata file214, the depth and the overlap may also be calculated at the level of the EP file220as well. In some embodiments, the range of the EP files220may extend from the minimum value of all of the data ranges of the member micro-partition metadata files214of the EP file220to the maximum value of all of the data ranges of the member micro-partition metadata files214of the EP file220. Thus, an EP-file-level overlap and an EP-file-level depth may be calculated as well. For example, the EP-file-level overlap for a particular EP file220may be calculated as the number of other EP files220containing member micro-partition metadata files214overlapping the particular EP file22. In addition, the EP-file-level depth for a particular EP file220may be calculated as the maximum number of other EP files220covering a same data point within the particular EP file220.

Referring toFIG.5, an EP-file-level overlap value of the first EP file220A may be calculated as 3 and the EP-file-level depth value of the first EP file220A may be calculated as 3. An EP-file-level overlap of the second EP file220B may be calculated as 2 and the EP-file-level depth of the second EP file220B may be calculated as 3. An EP-file-level overlap of the third EP file220C may be calculated as 2 and the EP-file-level depth of the third EP file220C may be calculated as 3. An EP-file-level overlap of the fourth EP file220D may be calculated as 3 and the EP-file-level depth of the fourth EP file220D may be calculated as 3.

In some embodiments, the average depth of the micro-partition metadata files214and the depth and overlap of the EP files220may be utilized to select which of the EP files220and or micro-partition metadata files214(and their associated micro-partitions210) are to be selected for clustering (e.g., based on a clustering key). As will be described further herein, an average depth of the various micro-partition metadata files214of an EP file220may be utilized to select a particular target sub-ranges of the data range510, and EP files220, and their associated micro-partitions210, that overlap these ranges may be selected for clustering.

FIG.6is a flow diagram of one embodiment of a method600for selecting micro-partitions210for clustering, according to some embodiments of the present disclosure. In general, the method600may be performed by processing logic that may include hardware (e.g., processing device, circuitry, dedicated logic, programmable logic, microcode, hardware of a device, integrated circuit, etc.), software (e.g., instructions run or executed on a processing device), or a combination thereof.

With reference toFIG.6, method600illustrates example functions used by various embodiments. Although specific function blocks (“blocks”) are disclosed in method600, such blocks are examples. That is, embodiments are well suited to performing various other blocks or variations of the blocks recited in method600. It is appreciated that the blocks in method600may be performed in an order different than presented, and that not all of the blocks in method600may be performed.

The operations ofFIG.6are described with respect to the data structure ofFIG.7.FIG.7is a diagram of a data structure700illustrating an example scenario of EP files220for the selection of micro-partitions210for clustering, according to some embodiments of the present disclosure. The data structure700ofFIG.7illustrates a configuration of EP files220whose configuration will be used to provide examples for the operations provided herein. The configuration ofFIG.7is merely an example, and is not intended to limit the embodiments of the present disclosure. A description of elements ofFIG.7that have been previously described will be omitted for brevity.

InFIG.7, a plurality of EP files220are illustrated, each having an EP data region720. The EP files220are examples of the EP files220similar to those described herein. Thus, each of the plurality of EP files220may contain a plurality of micro-partition metadata214, each corresponding to a micro-partition210, as described herein. For ease of description, the micro-partition metadata214and the micro-partitions210are not illustrated inFIG.7. The EP data region720may encompass a range of data values, within the data range710, between a minimum data value (e.g., of a clustering key) of the micro-partitions210of the EP file220and a maximum data value (e.g., of the clustering key) of the micro-partitions210of the EP file220.

For example, the data structure700may include a first EP file220A having a first EP data region720A, a second EP file220B having a second EP data region720B, a third EP file220C having a third EP data region720C, a fourth EP file220D having a fourth EP data region720D, a fifth EP file220E having a fifth EP data region720E, a sixth EP file220F having a sixth EP data region720F, a seventh EP file220G having a seventh EP data region720G, and an eighth EP file220H having an eighth EP data region720H. InFIG.7, each of the EP files220is illustrated along a representative data range710. The length of a line associated with each of the EP files220is intended to illustrate a given range (e.g., a minimum data value to a maximum data value) of the EP data region720for the data values of the clustering key represented by the micro-partitions210of the EP file220(e.g., the data values of the clustering key stored in the micro-partitions210associated with the particular EP file220). For example, when two of the EP files220are illustrated as having EP data regions720that overlap, that is intended to convey that the data ranges (e.g., of the clustering key) covered by the EP files220may overlap.

The EP files220ofFIG.7are illustrated in a different configuration than those ofFIG.5and, as such, will have different metadata. For purposes of the following description, the data structure700is presumed to have the following configuration:

In the table above, values for the average depth and number of micro-partitions210are shown for each EP file220. The average depth for a micro-partition210may be calculated as described herein with respect toFIG.5. The number of micro-partitions210may represent the number of micro-partitions210(and associated micro-partition metadata files214) that are grouped within the particular EP file220.

Referring toFIGS.6and7, method600may begin at operation610, where a plurality of sub-ranges730may be determined based on the respective EP data regions720of a plurality of EP files220. To determine the sub-ranges730, a minimum data value740and a maximum data value745may be selected for each of the EP data regions720of each of the plurality of EP files220. The minimum data value740may represent a minimum value of the data of the micro-partitions210of the EP file220(e.g., the left side of the EP data region720). The maximum data value745may represent a maximum value of the data of the micro-partitions210of the EP file220(e.g., the right side of the EP data region720).

The collections of minimums740and maximums745may be utilized to delineate sub-ranges730within the overall data range710. For example, a sub-range730may be defined between a first minimum value740or maximum value745and the nearest adjacent minimum value740or maximum value745. Thus, the sub-ranges730are the intervals of the data range710between adjacent minimum and maximum values740,745of the EP data regions720. In the example ofFIG.7, fifteen sub-ranges730are illustrated. For example, a first sub-range R1, a second sub-range R2, a third sub-range R3, a fourth sub-range R4, a fifth sub-range R5, a sixth sub-range R6, a seventh sub-range R7, an eighth sub-range R8, a ninth sub-range R9, a tenth sub-range R10, an eleventh sub-range R11, a twelfth sub-range R12, a thirteenth sub-range R13, a fourteenth sub-range R14, and a fifteenth sub-range R15 are illustrated inFIG.7.

Referring back toFIG.6, in operation620, a seed EP data region820is selected based on the sub-ranges730determined in operation610.FIG.8Ais a flow diagram of one embodiment of a method800for selecting a seed EP data region820, according to some embodiments of the present disclosure. In general, the method800may be performed by processing logic that may include hardware (e.g., processing device, circuitry, dedicated logic, programmable logic, microcode, hardware of a device, integrated circuit, etc.), software (e.g., instructions run or executed on a processing device), or a combination thereof.FIG.8Bis a block diagram of the data structure700illustrating an example scenario of selecting the seed EP data region820, according to some embodiments of the present disclosure.

With reference toFIG.8A, method800illustrates example functions used by various embodiments. Although specific function blocks (“blocks”) are disclosed in method800, such blocks are examples. That is, embodiments are well suited to performing various other blocks or variations of the blocks recited in method800. It is appreciated that the blocks in method800may be performed in an order different than presented, and that not all of the blocks in method800may be performed.

With reference toFIGS.8A and8B, the method800may begin at operation810in which a deepest sub-range830of the sub-ranges730is selected. The deepest sub-range830may be selected based on a total average depth of the sub-range730. The total average depth for a given sub-range730may be a sum of the average depths of the EP data regions720that overlap the sub-range730. For example, referring toFIG.8B, the sixth sub-range R6 may be selected as the deepest sub-range830. This selection may be based on the arrangement where the sixth sub-range R6 is overlapped by the first EP data region720A which has an average depth of 3, the second EP data region720B which has an average depth of 7, the sixth EP data region720F which has an average depth of 3, and the eighth EP data region720H which has an average depth of 2, for a total average depth for the overlapping EP data regions of 15. This total average depth is higher than the total average depth for any of the other sub-ranges730. As a result, the sixth sub-range R6 will be selected as the deepest sub-range830.

Referring toFIG.8A, in operation812, a candidate EP data region720may be selected from the EP data regions720that overlap the deepest sub-range830. The EP data regions720that overlap the deepest sub-range830may also be referred to herein as deep EP data regions. Referring to the example ofFIG.8B, four EP data regions720overlap the deepest sub-range830: the first EP data region720A, the second EP data region720B, the sixth EP data region720F, and the eighth EP data region720H. As an example, the first EP data region720A may be selected as the candidate EP data region720.

Referring toFIG.8A, in operation814, the deep EP data regions720that overlap the candidate EP data region720and the deepest sub-range830may be determined, and a total number of micro-partitions210represented by those overlapping EP data regions720may be calculated. For example, referring to the example ofFIG.8B, if the first EP data region720A is selected as the candidate EP data region720, it is overlapped by seven other EP data regions720(720B,720A,720C,720D,720E,720F,720G, and720H), for a total number of represented micro-partitions210of1600(per Table 1, above).

In operation816, it may be determined if all of the EP data regions720that overlap the deepest sub-range830determined in operation810have been processed. If not, operation812and814may be repeated for each of the EP data regions720that overlap the deepest sub-range830. In the example illustrated inFIG.8B, these operations would further result in analysis of the second EP data region720B (overlapped by720A,720E,720F, and720H, for 500 total micro-partitions210), the sixth EP data region720F (overlapped by720A,720B,720C, and720H, for 750 total micro-partitions210), and the eighth EP data region720H (overlapped by720A,720B,720C, and720F, for 750 total micro-partitions210).

After the total number of micro-partitions210of all of the EP data regions720that overlap the deepest sub-range830have been processed, the seed EP data region820may be selected as the EP data region720that overlaps the deepest sub-range830(e.g., a deep EP data region) and also overlaps the highest number of micro-partitions210of the EP data regions720. In the example illustrated inFIG.8B, the seed EP data region820is selected as the first EP data region720A based on its overlap of the deepest sub-range R6 and the number of micro-partitions210represented by the EP data regions720(e.g.,1600) that overlap the first EP data region720A.

Referring back toFIG.6, in operation630, a plurality of clustering EP data regions may be selected based on the seed EP data region820determined in operation620.FIG.9Ais a flow diagram of one embodiment of a method900for selecting clustering EP data regions920, according to some embodiments of the present disclosure. In general, the method900may be performed by processing logic that may include hardware (e.g., processing device, circuitry, dedicated logic, programmable logic, microcode, hardware of a device, integrated circuit, etc.), software (e.g., instructions run or executed on a processing device), or a combination thereof.FIG.9Bis a block diagram of the data structure700illustrating an example scenario of selecting the clustering EP data regions920, according to some embodiments of the present disclosure.

With reference toFIG.9A, method900illustrates example functions used by various embodiments. Although specific function blocks (“blocks”) are disclosed in method900, such blocks are examples. That is, embodiments are well suited to performing various other blocks or variations of the blocks recited in method900. It is appreciated that the blocks in method900may be performed in an order different than presented, and that not all of the blocks in method900may be performed.

With reference toFIGS.9A and9B, the method900may begin at operation950in which deep EP data regions920are selected as EP data regions720that overlap the deepest sub-range830. These deep EP data regions920may be the same as the overlapping EP data regions720described with respect to operation812ofFIG.8A. In the example illustrated inFIG.9B, the deep EP data regions920may be identified as the first EP data region720A,920A, which is also the seed EP data region820, the second EP data region720B,920B, the sixth EP data region720F,920F, and the eighth EP data region720H,920H.

Referring back toFIG.9A, the number of micro-partitions210represented by the deep EP data regions920may be counted. For example, in the configuration ofFIG.9B, the number of micro-partitions210represented by the deep EP data regions920is 700 (per Table 1). At operation952, it may be determined if the number of micro-partitions210represented by the deep EP data regions920is greater than a defined threshold (e.g., one thousand micro-partitions210).

If the number of micro-partitions210represented by the deep EP data regions920is not greater than the threshold (operation952:N), the method600continues to expand the number of EP data regions720that are used for the clustering operation. Those operations will be described with respect toFIGS.10A and10Bherein.

If the number of micro-partitions210represented by the deep EP data regions920is greater than the threshold (operation952:Y), enough micro-partitions210may be available for clustering. In such an event, the method900may continue to operation954in which the deep EP data regions920may be sorted by their average local depth. In the example ofFIG.9B, the deep EP data regions920include the first deep EP data region920A with an average depth of 3, the second deep EP data region920B with an average depth of 7, the sixth deep EP data region920F with an average depth of 3, and the eighth deep EP data region920H with an average depth of 2. Sorting these deep EP data regions920may result in an ordering of920H,920A/920B,920F.

At operation956, the deep EP data region920having the smallest average local depth (the eighth deep EP data region920H in the example ofFIG.9B) may be removed from the deep EP data regions920, and the number of micro-partitions210remaining in the deep EP data regions920may be examined to determine if the number of micro-partitions210represented by the remaining deep EP data regions920is less than the threshold. If not (operation958:N) the method900may revert to operation956where another of the deep EP data regions920is removed. The process may continue until the number of micro-partitions210represented by the remaining deep EP data regions920is less than the threshold (operation958:N).

For example, referring to the example ofFIG.9B, if it were to be assumed that the threshold was 650, the number of micro-partitions210represented by the deep EP data regions920calculated for operation952is 700. Following the operations of operation954, the eighth deep EP data region920H would have the smallest average local depth, and would be removed from the deep EP data regions920in operation956. This would leave the first deep EP data region920A, the second deep EP data region920B, and the sixth deep EP data region920F with a total number of600represented micro-partitions210, which would be less than the threshold at operation958.

In operation960, once the deep EP data regions920are adjusted to be below the threshold, the deep EP data regions920may be returned as the clustering EP data regions720for clustering (e.g., as a result of operation630ofFIG.6).

As previously noted, if the number of micro-partitions210of the deep EP data regions920determined in operation952are not greater than the threshold, additional EP data regions920may be identified for inclusion.FIG.10Ais a flow diagram of one embodiment of a method1000for selecting clustering EP data regions1020, according to some embodiments of the present disclosure. In general, the method1000may be performed by processing logic that may include hardware (e.g., processing device, circuitry, dedicated logic, programmable logic, microcode, hardware of a device, integrated circuit, etc.), software (e.g., instructions run or executed on a processing device), or a combination thereof.FIG.10Bis a diagram of the data structure700illustrating an example scenario of selecting the clustering EP data regions1020, according to some embodiments of the present disclosure.

With reference toFIG.10A, method1000illustrates example functions used by various embodiments. Although specific function blocks (“blocks”) are disclosed in method1000, such blocks are examples. That is, embodiments are well suited to performing various other blocks or variations of the blocks recited in method1000. It is appreciated that the blocks in method1000may be performed in an order different than presented, and that not all of the blocks in method1000may be performed.

With reference toFIGS.10A and10B, method1000may begin operation (after the operations described herein with respect toFIG.9A) at operation1050in which a plurality of target EP data regions1020are selected. The target EP data regions1020may be selected as those EP data regions720that overlap the seed EP data region820(described herein with respect toFIGS.8A and8B) but not the deepest sub-range830. In the example ofFIG.10B, the target EP data regions1020include the third EP data region720C,1020C, the fourth EP data region720D,1020D, the fifth EP data region720E,1020E, and the seventh EP data region720G,1020G.

In operation1052, the number of micro-partitions210represented by the deep EP data regions920(seeFIGS.9A and9B) and the target EP data regions1020may be compared to the threshold value. In the example ofFIG.10B, the number of micro-partitions210represented by the deep EP data regions920(seeFIGS.9A and9B) and the target EP data regions1020is 1600 (per Table 1). If the number of micro-partitions210represented by the deep EP data regions920(seeFIGS.9A and9B) and the target EP data regions1020is not greater than the threshold (operation1052:N), the method1000may continue to operation1080in which the deep EP data regions920and the target EP data regions1020may be returned as the clustering EP data regions720for clustering (e.g., as a result of operation630ofFIG.6).

If the number of micro-partitions210represented by the deep EP data regions920(seeFIGS.9A and9B) and the target EP data regions1020is greater than the threshold (operation1052:Y), the method1000may continue to operation1054to adjust the members of the target EP data regions1020. In operation1054, a lower target EP data region1020_L may be determined. The lower target EP data region1020_L may be determined by identifying a lowest maximum data value745_L (e.g., of the data range710of the clustering key) of the maximum data values745of the target EP data regions1020that overlap with the seed EP data region820. The lower target EP data region1020_L may be determined as the target EP data region1020that does not overlap with the lowest maximum data value745_L. In the example ofFIG.10B, the lower target EP data region1020_L is the fifth EP data region720E. Once the lower target EP data region1020_L is determined, the number of micro-partitions210represented by the members of the deep EP data regions920(seeFIGS.9A and9B) that overlap the lower target EP data region1020_L may be calculated. In the example ofFIG.10B, the first deep EP data region920A and the second deep EP data region920B overlap the fifth EP data region720E, so the number of micro-partitions210represented by the members of the deep EP data regions920that overlap the fifth EP data region720E is 500 (per Table 1). This number will be designated as LD.

In operation1056, an upper target EP data region1020_U may be determined. The upper target EP data region1020_U may be determined by identifying a highest minimum data value740_U (e.g., of the data range710of the clustering key) of the minimum data values740of the target EP data regions1020that overlap with the seed EP data region820. The upper target EP data region1020_U may be determined as the target EP data region1020that does not overlap with the highest minimum data value740_U. In the example ofFIG.10B, the upper target EP data region1020_U is the seventh EP data region720G. Once the upper target EP data region1020_U is determined, the number of micro-partitions210represented by the members of the deep EP data regions920that overlap the upper target EP data region1020_U may be calculated. In the example ofFIG.10B, only the first deep EP data region920A overlaps the seventh EP data region720G, so the number of micro-partitions210represented by the members of the deep EP data regions920that overlap the seventh EP data region720G is 100 (per Table 1). This number will be designated as UD.

In operation1058, UDis compared to LD. If UDis not equal to LD(operation1058:N), the EP data region720that is associated with the lower of UDor LDis removed from the target EP data regions1020in operation1070. In the example ofFIG.10B, the seventh EP data region720G would be removed from the target EP data regions1020. After the target EP data regions1020are adjusted in operation1070, the method1000may revert back to operation1052to compare the number of micro-partitions210represented by the deep EP data regions920and the target EP data regions1020to the threshold value.

If UDis equal to LD(operation1058:Y), the method1000may continue to operation1060. In operation1060, the number of micro-partitions210represented by the EP data regions720that overlap the lower target EP data region1020_L and the seed EP data region820may be calculated. In the example ofFIG.10B, the second EP data region720B overlaps the lower target EP data region1020_L (the fifth EP data region720E), so the number of micro-partitions210represented by the members of the EP data regions720that overlap the lower target EP data region1020_L and the seed EP data region820is 400 (per Table 1). This number will be designated as LC.

In operation1062, the number of micro-partitions210represented by the EP data regions720that overlap the upper target EP data region1020_U and the seed EP data region820may be calculated. In the example ofFIG.10B, the fourth EP data region720D overlaps the upper target EP data region1020_U (the seventh EP data region720G), so the number of micro-partitions210represented by the members of the EP data regions720that overlap the upper target EP data region1020_U and the seed EP data region820is 50 (per Table 1). This number will be designated as UC.

In operation1064, the EP data region720that is associated with the lower of LCor UCis removed from the target EP data regions1020in operation1064. In the example ofFIG.10B, had LDbeen equal to UD, the seventh EP data region720G would have been removed from the target EP data regions1020. After the target EP data regions1020are adjusted in operation1064, the method1000may revert back to operation1052to compare the number of micro-partitions210represented by the deep EP data regions920and the target EP data regions1020to the threshold value. The operations of the method1000may continue until the number of micro-partitions210represented by the deep EP data regions920and the target EP data regions is less than the threshold value and operation1080is executed, in which the remaining target EP data regions1020and the deep EP data regions920are returned as the clustering EP data regions720for clustering in the method600ofFIG.6.

Referring back toFIG.6, as a result of the methods900,1000described with respect toFIGS.7to10B, a plurality of clustering EP data regions720may be identified. In some embodiments, the method600may continue with operation640, in which additional EP data regions720may be added to the clustering EP data regions720. In some embodiments, additional EP data regions720may be identified by performing the operations ofFIGS.7to10Bagain utilizing a higher threshold and/or a different range. For example, the embodiments ofFIGS.7to10Bmay operate on the range of the seed EP data region820identified in method800ofFIG.8A. In some embodiments, the range may be increased beyond that of the seed EP data region820, and the operations ofFIGS.7to10Bmay be repeated.

In some embodiments, rather than adjusting the range and/or threshold, additional clustering EP data regions720by repeating the operations ofFIGS.7to10Bafter removing the EP data regions720identified in operation630from the group of EP data regions720being considered. The clustering EP data region selection algorithm may work on the adjusted batch of EP data regions720without touching the EP data regions720selected in the previous iteration.

This solution may have two advantages. First, each iteration may pick the EP data regions720overlapping with the deepest data sub-range830. As a result, this solution can reduce the depth of multiple ranges in one micro-partition clustering. Second, this solution is more efficient because one EP data region720is only processed once in the EP data regions720selection phase. In each iteration, the EP data regions720selection phase processes a limited number of EP data regions720such that it will not utilize large amounts of memory.

In operation650, a clustering operation may be performed on the micro-partitions210that are represented by the clustering EP data regions720selected in operations630and/or640. The clustering operation may examine the data ranges of the micro-partitions210represented by the clustering EP data regions720that were selected to determine if the ranges of some of the micro-partitions210may be reduced and/or micro-partitions can be combined. For example, data of the micro-partitions may be moved and/or recombined between micro-partitions210so there is less overlap between micro-partitions210and/or EP data regions720. In some embodiments, the clustering may be performed based on the data ranges of the clustering key. In some embodiments, the micro-partitions210are stored in immutable storage, so moving and/or recombining the data between micro-partitions210may include generating new micro-partitions210that contain different combinations of the data.

Clustering the micro-partitions210so that they have less overlap may allow for more efficient data query pruning, as described herein. Moreover, by utilizing the mechanisms described herein to select the micro-partitions210, only a subset of all of the EP data regions720may be analyzed during the clustering operation. By reducing the number of EP data regions720that are analyzed for the clustering operation, less memory may be used and the clustering operation may be performed more quickly. In addition, embodiments of the present disclosure attempt to select the micro-partitions210that will have the highest impact on clustering by focusing the selection of the EP data regions720for clustering based on the deepest data sub-range830. The deepest data sub-range830may include the micro-partitions210having a large amount of overlap.

The operations of the method600may be repeated during the operation of the database. For example, once a clustering operation has been performed, the ranges of the EP files220and their associated micro-partitions210will have changed. As a result, a repeat of the operations of the method600may select different EP files220with different respective EP data regions720for clustering on a subsequent iteration. Because the method600selects only a subset of the EP files220for clustering in each iteration, it may utilize less memory and/or processing time while continually improving the organization of the data in the database.

FIG.11is a flow diagram of one embodiment of a method1100for selecting micro-partitions210for a clustering operation, according to some embodiments of the present disclosure. In general, the method1100may be performed by processing logic that may include hardware (e.g., processing device, circuitry, dedicated logic, programmable logic, microcode, hardware of a device, integrated circuit, etc.), software (e.g., instructions run or executed on a processing device), or a combination thereof.

With reference toFIG.11, method1100illustrates example functions used by various embodiments. Although specific function blocks (“blocks”) are disclosed in method1100, such blocks are examples. That is, embodiments are well suited to performing various other blocks or variations of the blocks recited in method1100. It is appreciated that the blocks in method1100may be performed in an order different than presented, and that not all of the blocks in method1100may be performed.

Method1100begins at operation1110, which includes storing table data in a plurality of micro-partitions of a storage device. Each of the plurality of micro-partitions may include a portion of the table data. Subsets of the plurality of micro-partitions may be associated with a respective one of a plurality of EP files. Each of the plurality of EP files may include an EP data region that represents the portions of the table data of the subset of the plurality of micro-partitions associated with the EP file. The micro-partitions may be similar to the micro-partitions210described herein with respect toFIGS.1to10B. The EP files may be similar to the EP files220described herein with respect toFIGS.2to10B. The EP data regions may be similar to the EP data regions720described herein with respect toFIGS.7to10B. The EP data regions may be similar to the EP data regions720described herein with respect toFIGS.7to10B.

In operation1120, the method1100may include determining sub-ranges of the table data based on the plurality of EP data regions of the plurality of EP files. The sub-ranges may be similar to the sub-ranges730described herein with respect toFIGS.7to10B.

In operation1130, the method1100may include selecting (e.g., by a processing device) a subset of the plurality of EP files for a clustering operation based on the sub-ranges of the table data. The subset of the plurality of EP files may be similar to the EP files220associated with the clustering EP data regions720selected for clustering described herein with respect toFIGS.6to10B.

In some embodiments, selecting the subset of the plurality of EP files for the clustering operation based on the sub-ranges of the table data includes selecting EP files of the plurality of EP files that comprise table data having values that overlap a sub-range that is associated with highest average micro-partition depth, as described herein with respect toFIGS.1to10B.

In some embodiments, selecting the subset of the plurality of EP files for the clustering operation based on the sub-ranges of the table data may include, for each sub-range of the sub-ranges, calculating a total average micro-partition depth of ones of the plurality of EP data regions comprising table data that overlaps the sub-range, selecting the sub-range having a highest total average micro-partition depth as a deepest sub-range of the sub-ranges, and selecting the subset of the plurality of EP files for the clustering operation based on the deepest sub-range. The deepest sub-range may be similar to the deepest sub-range830described herein with respect toFIGS.8to10B.

In some embodiments, selecting the subset of the plurality of EP files for the clustering operation based on the deepest sub-range includes determining a group of overlapping EP data regions that comprise table data that overlap the deepest sub-range, selectively removing at least one of the overlapping EP data regions from the group of the overlapping EP data regions until a sum of the micro-partitions associated with the group of the overlapping EP data regions is less than a threshold value, and returning the EP files associated with the group of overlapping EP data regions as the subset of the EP files. The selective removal of the overlapping EP data regions is described herein, for example, with respect toFIGS.9A and9B.

In some embodiments, selecting the subset of the plurality of EP files for the clustering operation based on the deepest sub-range includes determining deep EP data regions of the plurality of EP data regions that overlap the deepest sub-range, selecting a seed EP data region from the deep EP data regions, and selecting the EP files associated with the EP data regions of the plurality of EP data regions that overlap the seed EP data region as the subset of the plurality of EP files for the clustering operation. The determination of the deep EP data regions and the selection of the seed EP data region is described herein, for example, with respect toFIGS.8A to10B.

In some embodiments, selecting the seed EP data region includes, for each deep EP data region of the deep EP data regions, determining a set of the plurality of EP data regions comprising table data that overlaps with table data of the deep EP data region, calculating a sum of micro-partitions associated with each of the sets of the EP data regions, and selecting the seed EP data region as the deep EP data region associated with the set of EP data regions having a highest sum of micro-partitions. The determination of the seed EP data region is described herein, for example, with respect toFIGS.8A and8B.

In some embodiments, selecting the EP files associated with the EP data regions of the plurality of EP data regions that overlap the seed EP data region as the subset of the plurality of EP files for the clustering operation includes determining a group of target EP data regions that comprise table data that overlaps the table data of the seed EP data region but not the deepest sub-range, selectively removing at least one of the target EP data regions from the group of the target EP data regions based on a number of micro-partitions associated with the at least one target EP data region to generate adjusted target EP data regions, and selecting the EP files associated with the adjusted target EP data regions and the deep EP data regions as the subset of the plurality of EP files for the clustering operation. The selective removal of the target EP data regions is described herein, for example, with respect toFIGS.10A and10B.

In operation1140, the method1100may include performing the clustering operation on the micro-partitions associated with the subset of the plurality of EP files. The clustering operation may be similar to the clustering operation described herein, such as with respect toFIGS.2to5.

The example computing device1200may include a processing device (e.g., a general purpose processor, a PLD, etc.)1202, a main memory1204(e.g., synchronous dynamic random access memory (DRAM), read-only memory (ROM)), a static memory1206(e.g., flash memory) and a data storage device1218, which may communicate with each other via a bus1230.

Processing device1202may be provided by one or more general-purpose processing devices such as a microprocessor, central processing unit, or the like. In an illustrative example, processing device1202may comprise a complex instruction set computing (CISC) microprocessor, reduced instruction set computing (RISC) microprocessor, very long instruction word (VLIW) microprocessor, or a processor implementing other instruction sets or processors implementing a combination of instruction sets. Processing device1202may also comprise one or more special-purpose processing devices such as an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), a digital signal processor (DSP), network processor, or the like. The processing device1202may be configured to execute the operations described herein, in accordance with one or more aspects of the present disclosure, for performing the operations and steps discussed herein. In one embodiment, processing device1202represents a processing device of cloud computing platform110ofFIG.1.

Computing device1200may further include a network interface device1208which may communicate with a network1220. The computing device1200also may include a video display unit1210(e.g., a liquid crystal display (LCD) or a cathode ray tube (CRT)), an alphanumeric input device1212(e.g., a keyboard), a cursor control device1214(e.g., a mouse) and an acoustic signal generation device1216(e.g., a speaker). In one embodiment, video display unit1210, alphanumeric input device1212, and cursor control device1214may be combined into a single component or device (e.g., an LCD touch screen).

Data storage device1218may include a computer-readable (also referred to herein as machine-readable) storage medium1228on which may be stored one or more sets of instructions1225, such as instructions for executing the cloud services component120, e.g., instructions for carrying out the operations described herein, in accordance with one or more aspects of the present disclosure. Cloud services instructions120may also reside, completely or at least partially, within main memory1204and/or within processing device1202during execution thereof by computing device1200, the main memory1204and processing device1202also constituting computer-readable media. The instructions1225may further be transmitted or received over a network1220via network interface device1208.

Unless specifically stated otherwise, terms such as “storing,” “determining,” “selecting,” “performing,” “calculating,” “removing,” or the like, refer to actions and processes performed or implemented by computing devices that manipulates and transforms data represented as physical (electronic) quantities within the computing device's registers and memories into other data similarly represented as physical quantities within the computing device memories or registers or other such information storage, transmission or display devices. Also, the terms “first,” “second,” “third,” “fourth,” etc., as used herein are meant as labels to distinguish among different elements and may not necessarily have an ordinal meaning according to their numerical designation.

Embodiments may also be implemented in cloud computing environments. In this description and the following claims, “cloud computing” may be defined as a model for enabling ubiquitous, convenient, on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services) that can be rapidly provisioned (including via virtualization) and released with minimal management effort or service provider interaction and then scaled accordingly. A cloud model can be composed of various characteristics (e.g., on-demand self-service, broad network access, resource pooling, rapid elasticity, and measured service), service models (e.g., Software as a Service (“SaaS”), Platform as a Service (“PaaS”), and Infrastructure as a Service (“IaaS”)), and deployment models (e.g., private cloud, community cloud, public cloud, and hybrid cloud). The flow diagrams and block diagrams in the attached figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present disclosure. In this regard, each block in the flow diagrams or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It will also be noted that each block of the block diagrams or flow diagrams, and combinations of blocks in the block diagrams or flow diagrams, may be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions. These computer program instructions may also be stored in a computer-readable medium that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable medium produce an article of manufacture including instruction means which implement the function/act specified in the flow diagram and/or block diagram block or blocks.