Modular query optimizer
Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for modular query optimizer. In one aspect, a method includes selecting one or more projections from a set of projections for each table in a database query wherein each of the selected projections for the table has leads to an estimated lower execution cost for the query as compared to non-selected projections; generating join orders for the query based on data distribution of one or more of the selected projections among sites in a computer network wherein the join orders reflect different combinations of data distribution operations applied to the output of one or more of the query's joins; and selecting a join order from the join orders based on evaluation of the join orders using a cost model.
1. A computer-implemented method, comprising:
providing a join classifier to a join order generator wherein the join classifier is configured to classify joins in a database query;
providing a join ranker to the join order generator wherein the join ranker is configured to rank each join based on the join's respective category;
using, by the join order generator, the provided join classifier and the join ranker to produce join plans in order of join ranks; and
wherein the database is a column-oriented database, a row-oriented database, or a hybrid row and column oriented database.
2. The method of claim 1 wherein a join category is one of join constraint, join selectivity, and join output size.
3. The method of claim 1 , further comprising providing the query to a projection set generator wherein the projection set generator is configured to provide projection sets for the query to the join order generator for use in determining the join plans.
4. The method of claim 3 wherein a projection set is determined based on physical properties of the projection set's projections.
5. The method of claim 1 , further comprising providing the join plans and a cost model to a cost predictor wherein the cost predictor is configured to use the cost model to select a lowest cost join plan in the join plans for executing the query.
6. The method of claim 1 wherein the database is a distributed database.
7. The method of claim 6 wherein data in the database is distributed by one or more of replication and segmentation.
8. The method of claim 1 , further comprising:
for each table in a database query, selecting one or more projections that reduce an estimated cost for executing the query for the table, based on a segmentation or sort order of the selected projections;
based on a data distribution of one or more of the selected projections among sites in a computer network, generating, for the query, possible join orders that represent different combinations of data distribution operations applied to the outputs of one or more of the query's joins; and
evaluating the join orders based on a cost model.
9. The method of claim 8 wherein the estimated execution cost for the query is based on whether the selected projections allow for one or more local joins in an execution plan for the query.
10. The method of claim 8 wherein, in a join order, many-to-one joins occur before many-to-many joins.
11. The method of claim 8 wherein, in a join order, more selective joins occur before less selective joins.
12. The method of claim 8 wherein, a local join in a join order that occurs before a subsequent join that would destroy the locality of the local join is given the same order as the subsequent join.
13. The method of claim 8 wherein a data distribution operation is at least one of: re-segmentation according to a join key, broadcast, and filtering on a join key.
14. The method of claim 8 also comprising selecting a join order based on the evaluation.
15. The method of claim 14 in which selecting a join order further comprises selecting the join order with the lowest cost.
16. A computer program product, encoded on a computer-readable storage medium, including instructions operable to cause data processing apparatus to perform operations comprising:
providing a join classifier to a join order generator wherein the join classifier is configured to classify joins in a database query;
providing a join ranker to the join order generator wherein the join ranker is configured to rank each join based on the join's respective category;
using, by the join order generator, the provided join classifier and the join ranker to produce join plans in order of join ranks; and
wherein the database is a column-oriented database, a row-oriented database, or a hybrid row and column oriented database.
17. The program product of claim 16 wherein a join category is one of join constraint, join selectivity, and join output size.
18. The program product of claim 16 , further comprising providing the query to a projection set generator wherein the projection set generator is configured to provide projection sets for the query to the join order generator for use in determining the join plans.
19. The program product of claim 18 wherein a projection set is determined based on physical properties of the projection set's projections.
20. The program product of claim 16 , further comprising providing the join plans and a cost model to a cost predictor wherein the cost predictor is configured to use the cost model to select a lowest cost join plan in the join plans for executing the query.
21. The program product of claim 16 wherein the database is a distributed database.
22. The program product of claim 21 wherein data in the database is distributed by one or more of replication and segmentation.