1 /* Copyright (c) 2017, 2019, Oracle and/or its affiliates. All rights reserved. 2 3 This program is free software; you can redistribute it and/or modify 4 it under the terms of the GNU General Public License, version 2.0, 5 as published by the Free Software Foundation. 6 7 This program is also distributed with certain software (including 8 but not limited to OpenSSL) that is licensed under separate terms, 9 as designated in a particular file or component or in included license 10 documentation. The authors of MySQL hereby grant you an additional 11 permission to link the program and your derivative works with the 12 separately licensed software that they have included with MySQL. 13 14 This program is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License, version 2.0, for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with this program; if not, write to the Free Software 21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ 22 23 #ifndef SQL_NESTED_JOIN_INCLUDED 24 #define SQL_NESTED_JOIN_INCLUDED 25 26 #include <sys/types.h> 27 #include "my_inttypes.h" 28 #include "my_table_map.h" 29 #include "sql/handler.h" 30 #include "sql/sql_list.h" 31 #include "sql/sql_opt_exec_shared.h" 32 33 class Item; 34 class Item_field; 35 struct POSITION; 36 struct TABLE_LIST; 37 38 /* 39 Used to identify NESTED_JOIN structures within a join (applicable to 40 structures representing outer joins that have not been simplified away). 41 */ 42 typedef ulonglong nested_join_map; 43 44 /** 45 Semijoin_mat_optimize collects data used when calculating the cost of 46 executing a semijoin operation using a materialization strategy. 47 It is used during optimization phase only. 48 */ 49 50 struct Semijoin_mat_optimize { 51 /// Optimal join order calculated for inner tables of this semijoin op. 52 POSITION *positions{nullptr}; 53 /// True if data types allow the MaterializeLookup semijoin strategy 54 bool lookup_allowed{false}; 55 /// True if data types allow the MaterializeScan semijoin strategy 56 bool scan_allowed{false}; 57 /// Expected number of rows in the materialized table 58 double expected_rowcount{0.0}; 59 /// Materialization cost - execute sub-join and write rows to temp.table 60 Cost_estimate materialization_cost; 61 /// Cost to make one lookup in the temptable 62 Cost_estimate lookup_cost; 63 /// Cost of scanning the materialized table 64 Cost_estimate scan_cost; 65 /// Array of pointers to fields in the materialized table. 66 Item_field **mat_fields{nullptr}; 67 }; 68 69 /** 70 Struct NESTED_JOIN is used to represent how tables are connected through 71 outer join operations and semi-join operations to form a query block. 72 Out of the parser, inner joins are also represented by NESTED_JOIN 73 structs, but these are later flattened out by simplify_joins(). 74 Some outer join nests are also flattened, when it can be determined that 75 they can be processed as inner joins instead of outer joins. 76 */ 77 struct NESTED_JOIN { NESTED_JOINNESTED_JOIN78 NESTED_JOIN() : join_list(*THR_MALLOC) {} 79 80 mem_root_deque<TABLE_LIST *> 81 join_list; /* list of elements in the nested join */ 82 table_map used_tables{0}; /* bitmap of tables in the nested join */ 83 table_map not_null_tables{0}; /* tables that rejects nulls */ 84 /** 85 Used for pointing out the first table in the plan being covered by this 86 join nest. It is used exclusively within make_outerjoin_info(). 87 */ 88 plan_idx first_nested{0}; 89 /** 90 Set to true when natural join or using information has been processed. 91 */ 92 bool natural_join_processed{false}; 93 /** 94 Number of tables and outer join nests administered by this nested join 95 object for the sake of cost analysis. Includes direct member tables as 96 well as tables included through semi-join nests, but notice that semi-join 97 nests themselves are not counted. 98 */ 99 uint nj_total{0}; 100 /** 101 Used to count tables in the nested join in 2 isolated places: 102 1. In make_outerjoin_info(). 103 2. check_interleaving_with_nj/backout_nj_state (these are called 104 by the join optimizer. 105 Before each use the counters are zeroed by SELECT_LEX::reset_nj_counters. 106 */ 107 uint nj_counter{0}; 108 /** 109 Bit identifying this nested join. Only nested joins representing the 110 outer join structure need this, other nests have bit set to zero. 111 */ 112 nested_join_map nj_map{0}; 113 /** 114 Tables outside the semi-join that are used within the semi-join's 115 ON condition (ie. the subquery WHERE clause and optional IN equalities). 116 Also contains lateral dependencies from materialized derived tables 117 contained inside the semi-join inner tables. 118 */ 119 table_map sj_depends_on{0}; 120 /** 121 Outer non-trivially correlated tables, a true subset of sj_depends_on. 122 Also contains lateral dependencies from materialized derived tables 123 contained inside the semi-join inner tables. 124 */ 125 table_map sj_corr_tables{0}; 126 /** 127 Query block id if this struct is generated from a subquery transform. 128 */ 129 uint query_block_id{0}; 130 131 /// Bitmap of which strategies are enabled for this semi-join nest 132 uint sj_enabled_strategies{0}; 133 134 /* 135 Lists of trivially-correlated expressions from the outer and inner tables 136 of the semi-join, respectively. 137 */ 138 List<Item> sj_outer_exprs, sj_inner_exprs; 139 Semijoin_mat_optimize sjm; 140 }; 141 142 #endif // SQL_NESTED_JOIN_INCLUDED 143