Data lake workload optimization through index modeling and recommendation

1. A distributed query processing system workload optimization method, comprising:

receiving a workload comprising a plurality of queries;

extracting sets of indexable columns from the plurality of queries, wherein each set corresponds to a respective one of the plurality of queries;

generating a set of candidate indexes based on the sets of indexable columns, said generating the set of candidate indexes comprising:

creating groups of indexable columns for the respective query based on the set of indexable columns corresponding to the respective query, each group of indexable columns corresponding to a table accessed by the respective query, and

generating a set of filter indexes and a set of join indexes for each group of indexable columns, wherein the set of candidate indexes comprises a union of the set of filter indexes and the set of join indexes generated for each group and for each query;

selecting a predetermined number of candidate indexes from the set of candidate indexes based on a determination of an estimated performance increase provided by the set of candidate indexes to performance of the workload;

building the selected candidate indexes to provide built indexes;

receiving a query;

generating for the query a query plan configured to use at least one of the built indexes; and

executing the query plan to generate a final query result.

2. The distributed query processing system workload optimization method of claim 1 , wherein indexable columns comprise columns of a query that correspond to at least one of equality predicates, range predicates, equi-join predicates, group-by lists, or projection lists.

3. The distributed query processing system workload optimization method of claim 1 , wherein a filter index and a join index each comprise indexed columns and included columns, and wherein:

for the filter index, the indexed columns comprise the indexable columns for the respective query that correspond only to equality and range predicates, and the included columns comprise all other indexable columns for the respective query; and

for the join index, the indexed columns comprise the indexable columns for the respective query that correspond only to equi-join predicates, and the included columns comprise all other indexable columns for the respective query.

4. The distributed query processing system workload optimization method of claim 3 , wherein the filter index and the join index each further comprise partitioned columns corresponding to the indexable columns for the respective query that correspond to those by which the original source data was partitioned.

5. The distributed query processing system workload optimization method of claim 1 , wherein the determination of the estimated performance increase comprises:

determining how frequently each candidate index of the set of candidate indexes corresponds to any query of the workload; and

wherein said selecting the predetermined number of candidate indexes from the set of candidate indexes comprises:

selecting the predetermined number of candidate indexes that most frequently correspond to any query of the workload.

6. The distributed query processing system workload optimization method of claim 1 , wherein the determination of the estimated performance increase comprises:

enumerating subsets of the set of candidate indexes, the subsets including the predetermined number of candidate indexes;

for each subset of the set of candidate indexes:

determining an estimated cost of each query of the workload under an assumption the candidate indexes of the respective subset of candidate indexes were built;

combining the determined estimated costs of the queries of the workload to provide an estimated workload cost for the respective subset; and

wherein selecting a predetermined number of candidate indexes from the set of candidate indexes comprises:

selecting the candidate indexes that correspond to the subset having the lowest estimated workload cost.

7. The distributed query processing system workload optimization method of claim 6 , wherein said determining the estimated cost of each query of the workload under an assumption the candidate indexes of the respective subset of candidate indexes were built comprises:

for each query of the workload:

generating a query plan;

generating an optimized query plan from the query plan by determining for each candidate index of the respective subset of candidate indexes whether the respective candidate index can be matched by a filter index rule or a join index rule to a table scan in the query plan, and

in response to the match being determined, replacing the table scan in the query plan with the respective candidate index; and

determining the estimated cost of the respective query by applying a cost model to the optimized query plan.

8. The distributed query processing system workload optimization method of claim 1 , wherein the built indexes are stored on a data lake that contains data in a native format.

9. A distributed query processing workload optimization system configured to receive a workload comprising a plurality of queries, the system comprising:

one or more processors; and

one or more memory devices accessible to the one or more processors, the one or more memory devices storing program code for execution by the one or more processors, the program code including:

a query processor, a candidate index generator and an index selector, wherein:

the candidate index generator is configured to:

extract sets of indexable columns from the plurality of queries, wherein each set corresponds to a respective one of the plurality of queries, and

generate a set of candidate indexes based on the sets of indexable columns by:

 for each query in the workload, creating groups of indexable columns for the respective query based on the set of indexable columns corresponding to the respective query, each group of indexable columns corresponding to a table accessed by the respective query; and

 for each query in the workload, generating a set of filter indexes and a set of join indexes for each group of indexable columns, wherein the set of candidate indexes comprises a union of the set of filter indexes and the set of join indexes generated for each group and for each query; and

the index selector is configured to select a predetermined number of candidate indexes from the set of candidate indexes based on a determination of the estimated performance increase provided in performing the workload by the set of candidate indexes;

the query processor configured to:

build the selected candidate indexes to provide built indexes;

receive a query;

generate a query plan for the query, wherein the query plan is optimized to use at least one of the built indexes; and

execute the query plan to generate a final query result.

10. The distributed query processing workload optimization system of claim 9 , wherein indexable columns comprise columns of a query that correspond to at least one of equality predicates, range predicates, equi-join predicates, group-by lists, or projection lists.

11. The distributed query processing workload optimization system of claim 9 , wherein a filter index and a join index each comprise indexed columns and included columns, and wherein:

for the filter index, the indexed columns comprise the indexable columns for the respective query that correspond only to equality and range predicates, and the included columns comprise all other indexable columns for the respective query; and

for the join index, the indexed columns comprise the indexable columns for the respective query that correspond only to equi-join predicates, and the included columns comprise all other indexable columns for the respective query.

12. The distributed query processing workload optimization system of claim 11 , wherein the filter index and the join index each further comprise partitioned columns corresponding to the indexable columns for the respective query that correspond to those by which the original source data was partitioned.

13. The distributed query processing workload optimization system of claim 9 , wherein the determination of the estimated performance increase comprises:

a determination of how frequently each candidate index of the set of candidate indexes corresponds to any query of the workload; and

wherein said the index selector is further configured to select the predetermined number of candidate indexes from the set of candidate indexes by selecting the predetermined number of candidate indexes that most frequently correspond to any query of the workload.

14. The distributed query processing workload optimization system of claim 9 , wherein the index selector is further configured to determine the estimated performance by:

enumerating subsets of the set of candidate indexes, the subsets including the predetermined number of candidate indexes;

for each subset of the set of candidate indexes:

determining an estimated cost of each query of the workload under an assumption the candidate indexes of the respective subset of candidate indexes were built;

combining the determined estimated costs of the queries of the workload to provide an estimated workload cost for the respective subset; and

wherein the index selector is further configured to select the predetermined number of candidate indexes from the set of candidate indexes by selecting the candidate indexes that correspond to the subset having the lowest estimated workload cost.

15. The distributed query processing workload optimization system of claim 14 , wherein said determining the estimated cost of each query of the workload under an assumption the candidate indexes of the respective subset of candidate indexes were built comprises:

for each query of the workload:

generating a query plan;

generating an optimized query plan from the query plan by determining for each candidate index of the respective subset of candidate indexes whether the respective candidate index can be matched by a filter index rule or a join index rule to a table scan in the query plan, and

in response to the match being determined, replacing the table scan in the query plan with the respective candidate index; and

determining the estimated cost of the respective query by applying a cost model to the optimized query plan.

16. The distributed query processing workload optimization system of claim 9 , wherein the built indexes are stored on a data lake that contains data in a native format.

17. A computer program product comprising a computer-readable memory device having computer program logic recorded thereon that when executed by at least one processor of a computing device causes the at least one processor to perform operations for optimizing a workload in a distributed query processing system, the operations comprising:

receiving a workload comprising a plurality of queries;

extracting sets of indexable columns from the plurality of queries, wherein each set corresponds to a respective one of the plurality of queries;

generating a set of candidate indexes based on the sets of indexable columns, said generating the set of candidate indexes comprising:

creating groups of indexable columns for the respective query based on the set of indexable columns corresponding to the respective query, each group of indexable columns corresponding to a table accessed by the respective query, and

generating a set of filter indexes and a set of join indexes for each group of indexable columns, wherein the set of candidate indexes comprises a union of the set of filter indexes and the set of join indexes generated for each group and for each query;

selecting a predetermined number of candidate indexes from the set of candidate indexes based on a determination of an estimated performance increase provided by the set of candidate indexes to performance of the workload;

building the selected candidate indexes to provide built indexes;

receiving a query;

generating for the query a query plan configured to use at least one of the built indexes; and

executing the query plan to generate a final query result.

18. The computer program product of claim 17 , wherein said operations further comprise determining the estimated performance increase by:

enumerating subsets of the set of candidate indexes, the subsets including the predetermined number of candidate indexes;

for each subset of the set of candidate indexes:

determining an estimated cost of each query of the workload under an assumption the candidate indexes of the respective subset of candidate indexes were built;

combining the determined estimated costs of the queries of the workload to provide an estimated workload cost for the respective subset; and

wherein selecting a predetermined number of candidate indexes from the set of candidate indexes comprises:

selecting the candidate indexes that correspond to the subset having the lowest estimated workload cost.

19. The computer program product of claim 18 , wherein said operations further comprise determining the estimated cost of each query of the workload under an assumption the candidate indexes of the respective subset of candidate indexes were built by:

for each query of the workload:

generating a query plan;

generating an optimized query plan from the query plan by determining for each candidate index of the respective subset of candidate indexes whether the respective candidate index can be matched by a filter index rule or a join index rule to a table scan in the query plan, and

in response to the match being determined, replacing the table scan in the query plan with the respective candidate index; and

determining the estimated cost of the respective query by applying a cost model to the optimized query plan.

20. The computer program product of claim 17 , wherein the built indexes are stored on a data lake that contains data in a native format.