BACKGROUND

Database management systems (DBMSs) are generally used to allow users and applications to interact with data stored in databases. For example, DBMSs allow databases to be defined and data in such databases to be created, queried, updated, removed, etc. Different DBMSs can process commands differently. In some cases, when a DBMS receives a query for a database, the DBMS may generate one or more query execution plans that specifies operations for accessing data in the database. The DBMS then selects an optimum query execution plan and executes it in order to generate the results of the query. The DBMS then returns the results of the query to the requestor.

SUMMARY

In some embodiments, a non-transitory machine-readable medium stores a program. The program receives a query for data that includes a join operation. The program further generates a plurality of candidate query execution plans based on the query, each candidate query execution plan comprising a set of reduction operations. The program also determines a plurality of execution costs associated with the plurality of sets of reduction operations in the plurality of candidate query execution plans. The program further selects a query execution plan from the plurality of candidate query execution plans based on the plurality of execution costs. The program also executes the query execution plan to generate a set of query results for the query.

In some embodiments, the set of reduction operations in a particular candidate query execution plan of the plurality of candidate query execution plans includes a reducing a first table to a second table based on a common attribute of the first and second tables used in the join operation. The execution cost associated with the particular candidate query execution plan may be based on a number of distinct values in the attribute of the first table. The program may further send the set of query results to a requestor from which the query is received.

In some embodiments, determining the execution cost associated with the particular candidate query execution plan includes determining a total number of rows in the first table. Determining the execution cost associated with the particular candidate query execution plan may further include selecting a subset of the total number of rows in the first table. Determining the execution cost associated with the particular candidate query execution plan may also include determining a number of distinct values in the common attribute of the subset of the total number of rows in the first table. Determining the execution cost associated with the particular candidate query execution plan may further include determining a number of distinct values in the first table based on the number of distinct values in the common attribute of the subset of the total number of rows in the first table.

In some embodiments, a method receives a query for data that includes a join operation. The method further generates a plurality of candidate query execution plans based on the query, each candidate query execution plan comprising a set of reduction operations.

The method also determines a plurality of execution costs associated with the plurality of sets of reduction operations in the plurality of candidate query execution plans. The method further selects a query execution plan from the plurality of candidate query execution plans based on the plurality of execution costs. The method also executes the query execution plan to generate a set of query results for the query.

In some embodiments, the set of reduction operations in a particular candidate query execution plan of the plurality of candidate query execution plans includes a reducing a first table to a second table based on a common attribute of the first and second tables used in the join operation. The execution cost associated with the particular candidate query execution plan may be based on a number of distinct values in the attribute of the first table. The method may further send the set of query results to a requestor from which the query is received.

In some embodiments, determining the execution cost associated with the particular candidate query execution plan includes determining a total number of rows in the first table. Determining the execution cost associated with the particular candidate query execution plan may further include selecting a subset of the total number of rows in the first table. Determining the execution cost associated with the particular candidate query execution plan may also include determining a number of distinct values in the common attribute of the subset of the total number of rows in the first table. Determining the execution cost associated with the particular candidate query execution plan may further include determining a number of distinct values in the first table based on the number of distinct values in the common attribute of the subset of the total number of rows in the first table.

In some embodiments, a system includes a set of processing units and a non-transitory computer-readable medium storing instructions. The instructions cause at least one processing unit to receive a query for data that includes a join operation. The instructions further cause the at least one processing unit to generate a plurality of candidate query execution plans based on the query, each candidate query execution plan comprising a set of reduction operations. The instructions also cause the at least one processing unit to determine a plurality of execution costs associated with the plurality of sets of reduction operations in the plurality of candidate query execution plans. The instructions further cause the at least one processing unit to select a query execution plan from the plurality of candidate query execution plans based on the plurality of execution costs. The instructions also cause the at least one processing unit to execute the query execution plan to generate a set of query results for the query.

In some embodiments, the set of reduction operations in a particular candidate query execution plan of the plurality of candidate query execution plans includes a reducing a first table to a second table based on a common attribute of the first and second tables used in the join operation. The execution cost associated with the particular candidate query execution plan may be based on a number of distinct values in the attribute of the first table.

In some embodiments, determining the execution cost associated with the particular candidate query execution plan includes determining a total number of rows in the first table. Determining the execution cost associated with the particular candidate query execution plan may further include selecting a subset of the total number of rows in the first table. Determining the execution cost associated with the particular candidate query execution plan may also include determining a number of distinct values in the common attribute of the subset of the total number of rows in the first table. Determining the execution cost associated with the particular candidate query execution plan may further include determining a number of distinct values in the first table based on the number of distinct values in the common attribute of the subset of the total number of rows in the first table.

The following detailed description and accompanying drawings provide a better understanding of the nature and advantages of the present invention.

