Candidate projection enumeration based query response generation

1. An apparatus comprising:

at least one processor; and

a non-transitory computer readable medium storing machine readable instructions that when executed by the at least one processor cause the at least one processor to:

obtain a query;

identify, based on the query, a plurality of candidate columns from at least one table to respond to the query;

analyze, using a tree-based model, the plurality of candidate columns to generate a candidate set of projections to respond to the query, wherein each candidate projection of the candidate set of projections includes a sort order associated with at least one candidate column of the plurality of candidate columns, a segmentation key value associated with at least one candidate column of the plurality of candidate columns, and a replication value associated with the candidate projection;

generate, for each candidate projection of the candidate set of projections, a state vector that is analyzed to control expansion of the tree-based model; and

generate, based on the candidate set of projections, a response to the query.

2. The apparatus according to claim 1 , wherein the state vector includes:

sort orders associated with all of the candidate columns;

segmentation key values associated with all of the candidate columns; and

the replication value associated with the candidate projection.

3. The apparatus according to claim 2 , wherein the instructions to analyze, using the tree-based model, the plurality of candidate columns to generate the candidate set of projections to respond to the query further cause the processor to:

determine, for each candidate projection of the candidate set of projections, based on an analysis of the state vector, a score associated with the state vector by analyzing a join operation associated with the query and the candidate projection.

4. The apparatus according to claim 2 , wherein the instructions to analyze, using the tree-based model, the plurality of candidate columns to generate the candidate set of projections to respond to the query further cause the processor to:

determine, for each candidate projection of the candidate set of projections, based on an analysis of the state vector, a score associated with the state vector by analyzing a group-by operation associated with the query and the candidate projection.

5. The apparatus according to claim 2 , wherein the instructions to analyze, using the tree-based model, the plurality of candidate columns to generate the candidate set of projections to respond to the query further cause the processor to:

determine, for each candidate projection of the candidate set of projections, based on an analysis of the state vector, a score associated with the state vector by analyzing an order-by operation associated with the query and the candidate projection.

6. The apparatus according to claim 2 , wherein the instructions to analyze, using the tree-based model, the plurality of candidate columns to generate the candidate set of projections to respond to the query further cause the processor to:

expand, for each candidate column of the plurality of candidate columns that includes an associated sort order, a branch of the tree-based model with respect to the sort order associated with the candidate column to add an added candidate projection; and

determine, for each added candidate projection, based on an analysis of the state vector, a score associated with the state vector.

7. The apparatus according to claim 6 , wherein the instructions further cause the processor to:

determine, for each added candidate projection, whether the score associated with the state vector is less than a score associated with a state vector of a previously added candidate projection; and

based on a determination that the score associated with the state vector is less than the score associated with the state vector of the previously added candidate projection, stop expansion of the branch of the tree-based model.

8. The apparatus according to claim 6 , wherein the instructions further cause the processor to:

expand, for each candidate column of the plurality of candidate columns that includes the associated sort order, the branch of the tree-based model for which the score for the added candidate projection is greater than a score for another added candidate projection of another branch.

9. The apparatus according to claim 2 , wherein the instructions to analyze, using the tree-based model, the plurality of candidate columns to generate the candidate set of projections to respond to the query further cause the processor to:

expand, for each candidate column of the plurality of candidate columns that includes an associated segmentation key value, a branch of the tree-based model with respect to the segmentation key value associated with the candidate column to add a candidate projection; and

determine, for each added candidate projection, based on an analysis of the state vector, a score associated with the state vector.

10. The apparatus according to claim 9 , wherein the instructions further cause the processor to:

determine, for each added candidate projection, whether the score associated with the state vector is less than a score associated with a state vector of a previously added candidate projection; and

based on a determination that the score associated with the state vector is less than the score associated with the state vector of the previously added candidate projection, stop expansion of the branch of the tree-based model.

11. The apparatus according to claim 1 , wherein the instructions to analyze, using the tree-based model, the candidate columns to generate the candidate set of projections to respond to the query further cause the processor to:

expand a branch of the tree-based model with respect to the replication value associated with the candidate projection.

12. A computer implemented method comprising:

identifying, by a processor, based on a query, a plurality of candidate columns from at least one table to respond to the query;

analyzing, by the processor, using a tree-based model, the plurality of candidate columns to generate a candidate set of projections to respond to the query, wherein each candidate projection of the candidate set of projections includes a sort order associated with at least one candidate column of the plurality of candidate columns, a segmentation key value associated with at least one candidate column of the plurality of candidate columns, and a replication value associated with the candidate projection;

generating, by the processor, for each candidate projection of the candidate set of projections, a state vector that is analyzed to control expansion of the tree-based model; and

generating, by the processor, based on the candidate set of projections, a response to the query.

13. The method according to claim 12 , wherein generating, by the processor, for each candidate projection of the candidate set of projections, the state vector that is analyzed to control expansion of the tree-based model further comprises:

generating, by the processor, for each candidate projection of the candidate set of projections,

the state vector that includes:

sort orders associated with all of the plurality of candidate columns;

segmentation key values associated with all of the plurality of candidate columns; and

the replication value associated with the candidate projection.

14. The method according to claim 12 , wherein analyzing, by the processor, using the tree-based model, the plurality of candidate columns to generate the candidate set of projections to respond to the query further comprises:

determining, by the processor, for each candidate projection of the candidate set of projections, based on an analysis of the state vector, a score associated with the state vector by analyzing at least one of a join operation, a group-by operation, or an order-by operation associated with the query and the candidate projection.

15. A non-transitory computer readable medium having stored thereon machine readable instructions, the machine readable instructions, when executed, cause a processor to:

identify, based on a query, a plurality of candidate columns from at least one table to respond to the query;

analyze, using a tree-based model, the plurality of candidate columns to generate a candidate set of projections to respond to the query, wherein each candidate projection of the candidate set of projections includes a sort order and a segmentation key value associated with at least one candidate column of the plurality of candidate columns, and a replication value associated with the candidate projection;

generate, for each candidate projection of the candidate set of projections, a state vector that includes:

sort orders and segmentation key values associated with all of the plurality of candidate columns, and

the replication value associated with the candidate projection; and

generate, based on the candidate set of projections, a response to the query.

16. The non-transitory computer readable medium according to claim 15 , wherein the machine readable instructions to analyze, using the tree-based model, the plurality of candidate columns to generate the candidate set of projections to respond to the query, when executed, further cause the processor to:

expand, for each candidate column of the plurality of candidate columns that includes an associated sort order, a branch of the tree-based model with respect to the sort order associated with the candidate column to add a candidate projection; and

determine, for each added candidate projection, based on an analysis of the state vector, a score associated with the state vector.

17. The non-transitory computer readable medium according to claim 16 , wherein the machine readable instructions, when executed, further cause the processor to:

determine, for each added candidate projection, whether the score associated with the state vector is less than a score associated with a state vector of a previously added candidate projection; and

based on a determination that the score associated with the state vector is less than the score associated with the state vector of the previously added candidate projection, stop expansion of the branch of the tree-based model.

18. The non-transitory computer readable medium according to claim 16 , wherein the machine readable instructions, when executed, further cause the processor to:

expand, for each candidate column of the plurality of candidate columns that includes the associated sort order, the branch of the tree-based model for which the score for the added candidate projection is greater than a score for another added candidate projection of another branch.

19. The non-transitory computer readable medium according to claim 15 , wherein the machine readable instructions to analyze, using the tree-based model, the plurality of candidate columns to generate the candidate set of projections to respond to the query, when executed, further cause the processor to:

expand, for each candidate column of the plurality of candidate columns that includes an associated segmentation key value, a branch of the tree-based model with respect to the segmentation key value associated with the candidate column to add a candidate projection; and

determine, for each added candidate projection, based on an analysis of the state vector, a score associated with the state vector.

20. The non-transitory computer readable medium according to claim 19 , wherein the machine readable instructions, when executed, further cause the processor to:

determine, for each added candidate projection, whether the score associated with the state vector is less than a score associated with a state vector of a previously added candidate projection; and

based on a determination that the score associated with the state vector is less than the score associated with the state vector of the previously added candidate projection, stop expansion of the branch of the tree-based model.