Details
-
Technical task
-
Status: Open (View Workflow)
-
Major
-
Resolution: Unresolved
-
None
-
None
-
None
Description
Currently in the code where we pick the best join order (the funtion is best_extension_by_limited_search), there are ways in which we do pruning so that we don't need to go through all the possible combinations of join order. There are 2 cases currently
1) Partial plan pruned by the cost of the best plan
2) Partial plan is pruned by another partial plan at the same level (this happens when we set optimizer_prune_level =1).
Case 1 is not a problem when we consider the join order that takes case of the ordering
Case 2 is a problem because the partial plan got pruned but maybe after the ordering is achieved and limit would shortcut the rest of the execution we could get a better plan, the cases are not considered.
An example would be
Tables: t1,t2,t3
For sorting you need t1,t3
let say
t1,t2 pruned t1,t3 by case 2, then we would not be able to consider the case of putting a nest around t1,t3. that is order_nest<t1,t3>, t2 would not be considered.
Attachments
Activity
| Field | Original Value | New Value |
|---|---|---|
| Description |
Currently in the code where we pick the best join order (the funtion is best_extension_by_limited_search), there are ways in which we do pruning so that we don't need to go through all the possible combinations of join order. There are 2 cases currently
1) Partial plan pruned by the cost of the best plan 2) Partial plan is pruned by another partial plan at the same level (this happens when we set optimizer_prune_level =1). Case 1 is not a problem when we consider the join order that takes case of the ordering Case 2 is a problem because the partial plan got pruned but maybe after the ordering is achieved and limit would shortcut the rest of the execution we could get a better plan, the cases are not considered. An example would be t1,t2,t3 for sorting you need t1,t3 let say t1,t2 pruned t1,t3 by case 2, then we would not be able to consider the case of putting a nest around t1,t3. that is order_nest<t1,t3>, t2 would not be considered |
| Description |
Currently in the code where we pick the best join order (the funtion is best_extension_by_limited_search), there are ways in which we do pruning so that we don't need to go through all the possible combinations of join order. There are 2 cases currently
1) Partial plan pruned by the cost of the best plan 2) Partial plan is pruned by another partial plan at the same level (this happens when we set optimizer_prune_level =1). Case 1 is not a problem when we consider the join order that takes case of the ordering Case 2 is a problem because the partial plan got pruned but maybe after the ordering is achieved and limit would shortcut the rest of the execution we could get a better plan, the cases are not considered. An example would be t1,t2,t3 for sorting you need t1,t3 let say t1,t2 pruned t1,t3 by case 2, then we would not be able to consider the case of putting a nest around t1,t3. that is order_nest<t1,t3>, t2 would not be considered |
Currently in the code where we pick the best join order (the funtion is best_extension_by_limited_search), there are ways in which we do pruning so that we don't need to go through all the possible combinations of join order. There are 2 cases currently
1) Partial plan pruned by the cost of the best plan 2) Partial plan is pruned by another partial plan at the same level (this happens when we set optimizer_prune_level =1). Case 1 is not a problem when we consider the join order that takes case of the ordering Case 2 is a problem because the partial plan got pruned but maybe after the ordering is achieved and limit would shortcut the rest of the execution we could get a better plan, the cases are not considered. An example would be Tables: t1,t2,t3 For sorting you need t1,t3 let say t1,t2 pruned t1,t3 by case 2, then we would not be able to consider the case of putting a nest around t1,t3. that is order_nest<t1,t3>, t2 would not be considered. |
| Comment |
[ h2. Implementation details
h4. Finding if the Query can consider use the cost based approach for ORDER BY with LIMIT * sort_nest_allowed() * is_order_by_expensive() h4. Equality propagation for Order BY Items Propagate the multiple equalities to all the items in the ORDER BY list, this helps us to consider various other join order that can have prefix that can resolve the ORDER BY clause * propagate_equal_field_for_orderby() * remove_const_from_order_by() h4. Find indexes that can resolve the ORDER BY clause Walk through all the usable indexes for a table and find a map of keys for table that can resolve the ORDER BY clause * find_keys_that_can_achieve_ordering() h4. Get the cardinality estimate for the join Run the join planner to get the estimate of the cardinality of the join. This is needed as we want to apply the limit selectivity later while calculating the cost of the best plan. * estimate_cardinality_for_join() h4. Run the join planner to get the best plan that will consider using a sort nest *optimizer_prune_level=0* This means no heuristic pruning of partial plans, only partial plans are pruned by the cost of the best plan at that instance For each prefix if the ORDER BY clause can be resolved by the tables in the prefix then a) We consider adding a nest around the prefix. A separate call is added for best_extension_by_limited_search * consider_adding_sort_nest() b) Add the cost of sorting. * sort_nest_oper_cost() c) Apply the limit selectivity. This is done because after the nest is considered we can shortcut the execution, we only consider the fraction of rows that we would read from the nest to get the resulting rows in the output. So this is how we take the cost of the shortcut into consideration. * set_fraction_output_for_nest d) Also special case when one can use indexes to resolve ORDER BY clause are considered here as well. We calculate the cost to access the index which can resolve the ORDER BY clause on the first non-const table. This can help in shortcutting join execution. * get_best_index_for_order_by_limit() * find_cost_of_index_with_ordering() h4. After the best plan is picked, we create the sort-nest info structure if the best plan uses a sort-nest. * check_if_sort_nest_present() * create_sort_nest_info() h4. For the first non-const table that uses an index to resolve ordering setup range/index scan * setup_index_use_for_ordering() * setup_range_scan() h4. Creating the temp table for the sort-nest We create a list of field items of the tables inside the nest which are needed to be stored in the temporary table. Then we also create a list of items of the fields of the temporary table * make_sort_nest() h4. Join buffering is disabled as it can break ordering * is_join_buffering_allowed() h4. Substitution of items belonging to tables inside the nest with the items of the temp table of the nest Here we substitute the items of the tables inside the sort-nest with items of the temporary table of the sort-nest. The clauses where this substitution happens are: # SELECT LIST # ON-EXPR # REF ACCESS items [for SJM lookup also] # WHERE clause # ORDER BY clause * substitute_base_with_nest_field_items() transform() is called with the function Item::replace_with_nest_items sent as a callback function h4. Materializing the result inside the temp table of the sort-nest At the execution phase we materialize the result of the inner tables inside the sort-nest and then continue the execution. * end_nest_materialization() ] |
This has been implemented along with MDEV-8306, so it is in review
| Fix Version/s | 10.6 [ 24028 ] | |
| Fix Version/s | 10.5 [ 23123 ] |
| Assignee | Varun Gupta [ varun ] | Sergei Petrunia [ psergey ] |
| Fix Version/s | 10.7 [ 24805 ] | |
| Fix Version/s | 10.6 [ 24028 ] |
| Fix Version/s | 10.8 [ 26121 ] | |
| Fix Version/s | 10.7 [ 24805 ] |
| Workflow | MariaDB v3 [ 97733 ] | MariaDB v4 [ 141352 ] |
| Fix Version/s | 10.10 [ 27530 ] | |
| Fix Version/s | 10.8 [ 26121 ] |
| Fix Version/s | 10.11 [ 27614 ] | |
| Fix Version/s | 10.10 [ 27530 ] |
| Fix Version/s | 10.12 [ 28320 ] | |
| Fix Version/s | 10.11 [ 27614 ] |
| Description |
Currently in the code where we pick the best join order (the funtion is best_extension_by_limited_search), there are ways in which we do pruning so that we don't need to go through all the possible combinations of join order. There are 2 cases currently
1) Partial plan pruned by the cost of the best plan 2) Partial plan is pruned by another partial plan at the same level (this happens when we set optimizer_prune_level =1). Case 1 is not a problem when we consider the join order that takes case of the ordering Case 2 is a problem because the partial plan got pruned but maybe after the ordering is achieved and limit would shortcut the rest of the execution we could get a better plan, the cases are not considered. An example would be Tables: t1,t2,t3 For sorting you need t1,t3 let say t1,t2 pruned t1,t3 by case 2, then we would not be able to consider the case of putting a nest around t1,t3. that is order_nest<t1,t3>, t2 would not be considered. |
Currently in the code where we pick the best join order (the funtion is best_extension_by_limited_search), there are ways in which we do pruning so that we don't need to go through all the possible combinations of join order. There are 2 cases currently 1) Partial plan pruned by the cost of the best plan 2) Partial plan is pruned by another partial plan at the same level (this happens when we set optimizer_prune_level =1). Case 1 is not a problem when we consider the join order that takes case of the ordering Case 2 is a problem because the partial plan got pruned but maybe after the ordering is achieved and limit would shortcut the rest of the execution we could get a better plan, the cases are not considered. An example would be Tables: t1,t2,t3 For sorting you need t1,t3 let say t1,t2 pruned t1,t3 by case 2, then we would not be able to consider the case of putting a nest around t1,t3. that is order\_nest<t1,t3>, t2 would not be considered. |
| Fix Version/s | 11.2 [ 28603 ] | |
| Fix Version/s | 11.0 [ 28320 ] |
| Fix Version/s | 11.3 [ 28565 ] | |
| Fix Version/s | 11.2 [ 28603 ] |
| Fix Version/s | 11.4 [ 29301 ] | |
| Fix Version/s | 11.3 [ 28565 ] |
| Fix Version/s | 11.5 [ 29506 ] | |
| Fix Version/s | 11.4 [ 29301 ] |
| Fix Version/s | 11.6 [ 29515 ] | |
| Fix Version/s | 11.5 [ 29506 ] |
| Fix Version/s | 11.6 [ 29515 ] |
The approach used here is that we set optimizer_prune_level = 0 for the queries that have order by limit. So this would help us not pruning any partial plans and the plans would only be pruned by the cost of the best plan.