Hi Varun, Please find below some input on the current patch:

diff -urpN '--exclude=.*' 10.5-mdev8306-orig/sql/sql_class.h 10.5-mdev8306/sql/sql_class.h --- 10.5-mdev8306-orig/sql/sql_class.h 2019-07-10 11:34:00.256256952 +0300 +++ 10.5-mdev8306/sql/sql_class.h 2019-07-10 11:34:15.436604510 +0300 @@ -6037,6 +6037,15 @@ public: Copy_field *copy_field; /* Needed for SJ_Materialization scan */ };

+class NEST_INFO : public Sql_alloc

Needs better naming, there are all kinds of nests. Making the first attempt: SORT_NEST_INFO ?

+{ +public: + TMP_TABLE_PARAM tmp_table_param; + List<Item> nest_table_cols; + TABLE *table; + uint n_tables; +}; +

/* Structs used when sorting */ struct SORT_FIELD_ATTR diff -urpN '--exclude=.*' 10.5-mdev8306-orig/sql/sql_select.cc 10.5-mdev8306/sql/sql_select.cc --- 10.5-mdev8306-orig/sql/sql_select.cc 2019-07-10 11:34:00.260257044 +0300 +++ 10.5-mdev8306/sql/sql_select.cc 2019-07-10 11:34:15.448604784 +0300 @@ -8135,6 +8143,32 @@ choose_plan(JOIN *join, table_map join_t use_cond_selectivity)) DBUG_RETURN(TRUE); } + trace_plan.end(); + + for (uint tablenr=0;tablenr < join->table_count;tablenr++) + { + POSITION *pos= &join->best_positions[tablenr]; + join->order_nest_tables|= pos->table->table->map; + if (pos->ordering_achieved) + { + join->order_nest= TRUE; + break; + } + }

The above looks like query plan refinement action, very close to what is done in get_best_combination. Can this code be moved into that function?

+ + if (join->order_nest && unlikely(thd->trace_started())) + { + Json_writer_array trace_order_nest(thd, "order_nest"); + + for (uint tablenr=0;tablenr < join->table_count;tablenr++) + { + POSITION *pos= &join->best_positions[tablenr]; + trace_order_nest.add_table_name(pos->table); + if (pos->ordering_achieved) + break; + } + } +

/* Store the cost of this query into a user variable ... @@ -14041,6 +14186,132 @@ ORDER *simple_remove_const(ORDER *order, }

+/* + This function basically tries to propgate all the multiple equalites + for the Field items, so that one can use them to generate QEP that would + also take into consideration equality propagation +*/ +void propagate_equal_field_for_orderby(JOIN *join, ORDER *first_order) +{ + ORDER *order; + table_map not_const_tables= ~join->const_table_map; + for (order= first_order; order; order= order->next) + { + table_map order_tables=order->item[0]->used_tables(); + if (!(order_tables & not_const_tables)) + continue; Is the above necessary? I think we have an optimization which removes constant element from ORDER BY list. (Perhaps, that optimization is invoked after the join optimizer. If that is the case, it should be done before the join optimizer)

+ else + { + if (optimizer_flag(join->thd, OPTIMIZER_SWITCH_ORDERBY_EQ_PROP) && + order->item[0]->real_item()->type() == Item::FIELD_ITEM && + join->cond_equal) + { + Item *item= order->item[0]; + /* + TODO: equality substitution in the context of ORDER BY is + sometimes allowed when it is not allowed in the general case. + We make the below call for its side effect: it will locate the + multiple equality the item belongs to and set item->item_equal + accordingly. + */ + (void)item->propagate_equal_fields(join->thd, + Value_source:: + Context_identity(), + join->cond_equal); + } + } + } +} + +/* + This function basicall checks if by considering the current join_tab + would we be able to achieve the ordering +*/ + +bool check_join_prefix_contains_ordering(JOIN *join, JOIN_TAB *tab, + table_map previous_tables) +{ + ORDER *order; + table_map not_const_tables= ~join->const_table_map; + for (order= join->order; order; order= order->next) + { + table_map order_tables=order->item[0]->used_tables(); + if (!(order_tables & not_const_tables)) + continue; Same question as above - at this stage ORDER BY list should not have const elements.

+ else + { + Item_equal *item_eq= order->item[0]->get_item_equal(); + if (((previous_tables | tab->table->map) & order_tables) == order_tables || + (item_eq && (item_eq->used_tables() & (previous_tables | tab->table->map)))) + continue; + else + return FALSE; + } What about handling for non-const items that are not members of Item_equal? (e.g. ORDER BY left(table.col, 3)) ?)

+ } + return TRUE; +} + + +bool setup_order_nest(JOIN *join, JOIN_TAB *tab)

(Same question about how to call the nest. I would call it "sort nest")

+{ + if (!tab->is_order_nest) + return FALSE; + THD *thd= join->thd; + Field_iterator_table field_iterator; + + JOIN_TAB *start_tab= join->join_tab+join->const_tables, *j; + NEST_INFO* order_nest_info= join->order_nest_info; + + /* This needs to be added to JOIN structure, looks the best option or we + can have a seperate struture NEST_INFO to hold it + */ + + for (j= start_tab; j < tab; j++) + { + TABLE *table= start_tab->table; + field_iterator.set_table(table); + for (; !field_iterator.end_of_fields(); field_iterator.next()) + { + Field *field= field_iterator.field(); + if (!bitmap_is_set(table->read_set, field->field_index)) + continue; + Item *item; + if (!(item= field_iterator.create_item(thd))) + return TRUE; + order_nest_info->nest_table_cols.push_back(item, thd->mem_root); + } + } + + /* + TODO also add ORDER ITEMS that are expressions, only fields are covered above + */ + DBUG_ASSERT(!tab->table); + + order_nest_info->tmp_table_param.init(); + order_nest_info->tmp_table_param.bit_fields_as_long= TRUE; + order_nest_info->tmp_table_param.field_count= order_nest_info->nest_table_cols.elements; + order_nest_info->tmp_table_param.force_not_null_cols= FALSE; + + const LEX_CSTRING order_nest_name= { STRING_WITH_LEN("order-nest") }; + if (!(tab->table= create_tmp_table(thd, &order_nest_info->tmp_table_param, + order_nest_info->nest_table_cols, (ORDER*) 0, + FALSE /* distinct */, + 0, /*save_sum_fields*/ + thd->variables.option_bits | TMP_TABLE_ALL_COLUMNS, + HA_POS_ERROR /*rows_limit */, + &order_nest_name))) + return TRUE; /* purecov: inspected */ + + //tab->tmp_table_param= &order_nest_info->tmp_table_param; + tab->type= JT_ALL; + + /* + add_sort_to_table(); + */ + + return false; +} + static int return_zero_rows(JOIN *join, select_result *result, List<TABLE_LIST> &tables, List<Item> &fields, bool send_row, ulonglong select_options, @@ -28550,6 +28821,26 @@ select_handler *SELECT_LEX::find_select_ return 0; }

+double postjoin_oper_cost(THD *thd, double join_record_count, uint rec_len, uint idx)

+{ + double cost= 0; + /* + For only one table in the order_nest, we don't need a fill the temp table, we can + just read the data into the filesort buffer and read the sorted data from the buffers. + */ + if (idx) Comparing idx with zero seems odd here. If we check whether this is the first

The name of the function is confusing. I see the function is modeled after spl_postjoin_oper_cost(), but that name is not readable either. Is this the cost of using a sort nest? table, we should compare with join->const_tables (This applies to spl_postjoin_oper_cost, too. Need to ask Igor about that one).

+ cost= get_tmp_table_write_cost(thd, join_record_count,rec_len) * + join_record_count; // cost to fill tmp table + + cost+= get_tmp_table_lookup_cost(thd, join_record_count,rec_len) * + join_record_count; // cost to perform post join operation used here + cost+= get_tmp_table_lookup_cost(thd, join_record_count, rec_len) + + (join_record_count == 0 ? 0 : + join_record_count * log2 (join_record_count)) * + SORT_INDEX_CMP_COST; // cost to perform sorting + return cost; +} +

/** @} (end of group Query_Optimizer) diff -urpN '--exclude=.*' 10.5-mdev8306-orig/sql/sql_select.h 10.5-mdev8306/sql/sql_select.h --- 10.5-mdev8306-orig/sql/sql_select.h 2019-07-10 11:34:00.260257044 +0300 +++ 10.5-mdev8306/sql/sql_select.h 2019-07-10 11:34:15.448604784 +0300 @@ -289,13 +289,14 @@ typedef struct st_join_table {

/* TRUE <=> This join_tab is inside an SJM bush and is the last leaf tab here */ bool last_leaf_in_bush; - + /* ptr - this is a bush, and ptr points to description of child join_tab range NULL - this join tab has no bush children */ JOIN_TAB_RANGE *bush_children; + JOIN_TAB_RANGE *order_nest_children;

This is not yet used anywhere? Is there any reason to have both bush_children and order_nest_children? I would suggest using bush_children pointer for both SJ-Materialization nests and sort nests. Another variable in the JOIN_TAB will be used to specify what kind of nest it is. (One JOIN_TAB cannot be both a SJ-Mat nest and a sort nest).

/* Special content for EXPLAIN 'Extra' column or NULL if none */ enum explain_extra_tag info; @@ -524,6 +525,12 @@ typedef struct st_join_table { /* Becomes true just after the used range filter has been built / filled */ bool is_rowid_filter_built;

+ /* + Set to true if we consider creating a nest for a prefix of the JOIN order + that satisfies the ordering + */ + bool is_order_nest;

This is a member of JOIN_TAB. If we get here, we are not considering, we've firmly decided to use a sort nest. I would prefer the name "sort nest" rather than order_nest.

+ void build_range_rowid_filter_if_needed();

void cleanup(); @@ -991,6 +998,9 @@ typedef struct st_position /* Cost info for the range filter used at this position */ Range_rowid_filter_cost_info *range_rowid_filter_info;

+ /* Flag to be set to TRUE if the join prefix satisfies the ORDER BY CLAUSE */ + bool ordering_achieved;

As far as I understand, this is set to true if we have decided to add a sort_nest. We can add a sort nest when the join prefix covers the ORDER BY, but we don't have to. So, the name is confusing and should be changed to something like "sort_nest_operation_here"

+ } POSITION;

typedef Bounds_checked_array<Item_null_result*> Item_null_array;

BR Sergei -- Sergei Petrunia, Software Developer MariaDB Corporation | Skype: sergefp | Blog: http://s.petrunia.net/blog