From 2775f80f7d287cb0ed478543bf135b9399f56d66 Mon Sep 17 00:00:00 2001 From: Sergey Petrunya Date: Tue, 6 Apr 2010 00:16:45 +0400 Subject: MWL#90: Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE - First code (needs cleanup). --- sql/sql_select.h | 12 ++++++++++++ 1 file changed, 12 insertions(+) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index bc2c1b0f2cf..a0a722b2fc8 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1551,7 +1551,18 @@ public: bool union_part; ///< this subselect is part of union bool optimized; ///< flag to avoid double optimization in EXPLAIN + /* + Subqueries that will need to be converted to semi-join nests (the list + is emptied when conversion is done + */ Array sj_subselects; + + /* + Subqueries that will need to be converted to JOIN_TABs + (Note this is different from the above in the respect that it's part + of WHERE clause or something like that?) + */ + //Array jtbm_subselects; /* Temporary tables used to weed-out semi-join duplicates */ List sj_tmp_tables; @@ -1575,6 +1586,7 @@ public: JOIN(THD *thd_arg, List &fields_arg, ulonglong select_options_arg, select_result *result_arg) :fields_list(fields_arg), sj_subselects(thd_arg->mem_root, 4) + //jtbm_subselects(thd_arg->mem_root, 4) { init(thd_arg, fields_arg, select_options_arg, result_arg); } -- cgit v1.2.1 From b2c57cedbfd0f8ce2b4f67021a2aca5dedf9b6c9 Mon Sep 17 00:00:00 2001 From: Sergey Petrunya Date: Sun, 25 Apr 2010 12:23:52 +0400 Subject: Code cleanup in subquery optimizations --- sql/sql_select.h | 12 ++---------- 1 file changed, 2 insertions(+), 10 deletions(-) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index a0a722b2fc8..733ea310ad3 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1552,18 +1552,11 @@ public: bool optimized; ///< flag to avoid double optimization in EXPLAIN /* - Subqueries that will need to be converted to semi-join nests (the list - is emptied when conversion is done + Subqueries that will need to be converted to semi-join nests, including + those converted to jtbm nests. The list is emptied when conversion is done. */ Array sj_subselects; - /* - Subqueries that will need to be converted to JOIN_TABs - (Note this is different from the above in the respect that it's part - of WHERE clause or something like that?) - */ - //Array jtbm_subselects; - /* Temporary tables used to weed-out semi-join duplicates */ List
sj_tmp_tables; List sjm_info_list; @@ -1586,7 +1579,6 @@ public: JOIN(THD *thd_arg, List &fields_arg, ulonglong select_options_arg, select_result *result_arg) :fields_list(fields_arg), sj_subselects(thd_arg->mem_root, 4) - //jtbm_subselects(thd_arg->mem_root, 4) { init(thd_arg, fields_arg, select_options_arg, result_arg); } -- cgit v1.2.1 From 3f595889d35c81540eb14ef3c53105cb6c4db833 Mon Sep 17 00:00:00 2001 From: Sergey Petrunya Date: Sun, 23 May 2010 23:13:18 +0400 Subject: Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE - Code cleanup - Query plan change is due to s/ha_rows JOIN_TAB::read_time/double JOIN_TAB::read_time/ --- sql/sql_select.h | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index 733ea310ad3..ab62f5f7d46 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -210,8 +210,11 @@ typedef struct st_join_table { method (but not 'index' for some reason), i.e. this matches method which E(#records) is in found_records. */ - ha_rows read_time; + double read_time; + /* Startup cost for execution */ + double startup_cost; + table_map dependent,key_dependent; uint use_quick,index; uint status; ///< Save status for cache -- cgit v1.2.1 From a15e342d0bf9e9da709fe9c9cdabbe0cd7c921b2 Mon Sep 17 00:00:00 2001 From: Sergey Petrunya Date: Tue, 25 May 2010 17:13:19 +0400 Subject: MWL#90: Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE - Remove JOIN::all_tables as it is not useful. - Better wording in comments --- sql/sql_select.h | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index ab62f5f7d46..36ab753a6ae 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1373,8 +1373,11 @@ public: JOIN_TAB *join_tab,**best_ref; JOIN_TAB **map2table; ///< mapping between table indexes and JOIN_TABs JOIN_TAB *join_tab_save; ///< saved join_tab for subquery reexecution + /* + Base tables participating in the join. After join optimization is done, the + tables are stored in the join order. + */ TABLE **table; - TABLE **all_tables; /** The table which has an index that allows to produce the requried ordering. A special value of 0x1 means that the ordering will be produced by -- cgit v1.2.1 From dad93f2c822f174f4674c4a04c2382c18a262e36 Mon Sep 17 00:00:00 2001 From: Sergey Petrunya Date: Fri, 4 Jun 2010 17:40:57 +0400 Subject: MWL#90, code movearound to unify merged and non-merged semi-join materialization processing - First code, needs cleanup. --- sql/sql_select.h | 49 ++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 46 insertions(+), 3 deletions(-) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index 36ab753a6ae..2299d4dfbdf 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -142,13 +142,25 @@ enum enum_nested_loop_state typedef enum_nested_loop_state (*Next_select_func)(JOIN *, struct st_join_table *, bool); + +/* + Function prototype for reading first record for a join tab + + RETURN + 0 - OK + -1 - Record not found + Other - Error +*/ typedef int (*Read_record_func)(struct st_join_table *tab); + Next_select_func setup_end_select_func(JOIN *join); int rr_sequential(READ_RECORD *info); +int rr_sequential_and_unpack(READ_RECORD *info); class JOIN_CACHE; class SJ_TMP_TABLE; +class JOIN_TAB_RANGE; typedef struct st_join_table { st_join_table() {} /* Remove gcc warning */ @@ -173,6 +185,14 @@ typedef struct st_join_table { st_join_table *last_inner; /**< last table table for embedding outer join */ st_join_table *first_upper; /**< first inner table for embedding outer join */ st_join_table *first_unmatched; /**< used for optimization purposes only */ + + /* + psergey2: for join tabs that are inside a bush: root of this bush. + */ + st_join_table *bush_root_tab; + bool last_leaf_in_bush; + + JOIN_TAB_RANGE *bush_children; /* Special content for EXPLAIN 'Extra' column or NULL if none */ const char *info; @@ -211,6 +231,8 @@ typedef struct st_join_table { E(#records) is in found_records. */ double read_time; + + ha_rows records_read; /* Startup cost for execution */ double startup_cost; @@ -292,7 +314,7 @@ typedef struct st_join_table { /* Semi-join strategy to be used for this join table. This is a copy of POSITION::sj_strategy field. This field is set up by the - fix_semijion_strategies_for_picked_join_order. + fix_semijoin_strategies_for_picked_join_order. */ uint sj_strategy; @@ -1365,17 +1387,29 @@ inline bool sj_is_materialize_strategy(uint strategy) } +class JOIN_TAB_RANGE: public Sql_alloc +{ +public: + JOIN_TAB *start; + JOIN_TAB *end; +}; + + class JOIN :public Sql_alloc { JOIN(const JOIN &rhs); /**< not implemented */ JOIN& operator=(const JOIN &rhs); /**< not implemented */ public: - JOIN_TAB *join_tab,**best_ref; + JOIN_TAB *join_tab, **best_ref; JOIN_TAB **map2table; ///< mapping between table indexes and JOIN_TABs JOIN_TAB *join_tab_save; ///< saved join_tab for subquery reexecution + + List join_tab_ranges; + /* Base tables participating in the join. After join optimization is done, the - tables are stored in the join order. + tables are stored in the join order (but the only really important part is + that const tables are first). */ TABLE **table; /** @@ -1387,6 +1421,13 @@ public: uint tables; /**< Number of tables in the join */ uint outer_tables; /**< Number of tables that are not inside semijoin */ uint const_tables; + /* + Number of tables in the top join_tab array. Normally this matches + (join_tab_ranges.head()->end - join_tab_ranges.head()->start). + + We keep it here so that it is saved/restored with JOIN::restore_tmp. + */ + uint top_jtrange_tables; uint send_group_parts; bool group; /**< If query contains GROUP BY clause */ /** @@ -1595,6 +1636,7 @@ public: join_tab= join_tab_save= 0; table= 0; tables= 0; + top_jtrange_tables= 0; const_tables= 0; eliminated_tables= 0; join_list= 0; @@ -1933,6 +1975,7 @@ COND *remove_eq_conds(THD *thd, COND *cond, Item::cond_result *cond_value); int test_if_item_cache_changed(List &list); void calc_used_field_length(THD *thd, JOIN_TAB *join_tab); int join_init_read_record(JOIN_TAB *tab); +int join_read_record_no_init(JOIN_TAB *tab); void set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key); inline Item * and_items(Item* cond, Item *item) { -- cgit v1.2.1 From 49568aefe7a9d95e303ccfe40614fd3d1ee5b12f Mon Sep 17 00:00:00 2001 From: Sergey Petrunya Date: Sat, 5 Jun 2010 12:37:16 +0400 Subject: MWL#90: Code cleanup: Unification of merged and non-merged SJM nests processing - Make join buffering code to take into account that JOIN_TABs are not a linear array anymore. --- sql/sql_select.h | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index 2299d4dfbdf..8319969432c 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -500,12 +500,14 @@ protected: context can be accessed. */ JOIN *join; - +#if 0 /* Cardinality of the range of join tables whose fields can be put into the cache. (A table from the range not necessarily contributes to the cache.) */ uint tables; +#endif + JOIN_TAB *start_tab; /* The total number of flag and data fields that can appear in a record -- cgit v1.2.1 From 26c3dc455ba934db40d7ad409358c3605fa196d0 Mon Sep 17 00:00:00 2001 From: Sergey Petrunya Date: Tue, 8 Jun 2010 18:22:31 +0400 Subject: MWL#90: Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE - Address feedback - Code cleanup (not finished) --- sql/sql_select.h | 23 ++++++++++++++--------- 1 file changed, 14 insertions(+), 9 deletions(-) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index 8319969432c..1dba84f7822 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -190,8 +190,15 @@ typedef struct st_join_table { psergey2: for join tabs that are inside a bush: root of this bush. */ st_join_table *bush_root_tab; - bool last_leaf_in_bush; + /* TRUE <=> This join_tab is inside a join 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; /* Special content for EXPLAIN 'Extra' column or NULL if none */ @@ -500,13 +507,13 @@ protected: context can be accessed. */ JOIN *join; -#if 0 - /* - Cardinality of the range of join tables whose fields can be put into the - cache. (A table from the range not necessarily contributes to the cache.) + /* + JOIN_TAB of the first table that can have it's fields in the join cache. + That is, tables in the [start_tab, tab) range can have their fields in the + join cache. + If a join tab in the range represents an SJM-nest, then all tables from the + nest can have their fields in the join cache, too. */ - uint tables; -#endif JOIN_TAB *start_tab; /* @@ -1505,7 +1512,6 @@ public: /* We also maintain a stack of join optimization states in * join->positions[] */ /******* Join optimization state members end *******/ - Next_select_func first_select; /* The cost of best complete join plan found so far during optimization, after optimization phase - cost of picked join order (not taking into @@ -1691,7 +1697,6 @@ public: rollup.state= ROLLUP::STATE_NONE; no_const_tables= FALSE; - first_select= sub_select; } int prepare(Item ***rref_pointer_array, TABLE_LIST *tables, uint wind_num, -- cgit v1.2.1 From e9bac8db82f54d715997cceff082452c5406d36e Mon Sep 17 00:00:00 2001 From: Sergey Petrunya Date: Fri, 11 Jun 2010 18:43:06 +0400 Subject: MWL#90, code cleanup - Remove garbage comments - fix a bug in join_tab_cmp --- sql/sql_select.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index 1dba84f7822..2344a7a59c1 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -187,11 +187,11 @@ typedef struct st_join_table { st_join_table *first_unmatched; /**< used for optimization purposes only */ /* - psergey2: for join tabs that are inside a bush: root of this bush. + For join tabs that are inside an SJM bush: root of the bush */ st_join_table *bush_root_tab; - /* TRUE <=> This join_tab is inside a join bush and is the last leaf tab here */ + /* TRUE <=> This join_tab is inside an SJM bush and is the last leaf tab here */ bool last_leaf_in_bush; /* -- cgit v1.2.1 From 946aef4a58337c6e5adf5a08d04dd397630f0c46 Mon Sep 17 00:00:00 2001 From: psergey Date: Sat, 10 Jul 2010 20:51:12 +0300 Subject: MWL#90: code cleanup - Remove deadcode - Improve comments - Do small several small TODOs --- sql/sql_select.h | 3 --- 1 file changed, 3 deletions(-) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index 2344a7a59c1..32c1eff97f7 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1247,9 +1247,6 @@ enum_nested_loop_state sub_select_cache(JOIN *join, JOIN_TAB *join_tab, bool end_of_records); enum_nested_loop_state sub_select(JOIN *join,JOIN_TAB *join_tab, bool end_of_records); -enum_nested_loop_state sub_select_sjm(JOIN *join, JOIN_TAB *join_tab, - bool end_of_records); - enum_nested_loop_state end_send_group(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)), bool end_of_records); -- cgit v1.2.1