MySQL  8.0.18
Source Code Documentation
nested_join.h
Go to the documentation of this file.
1 /* Copyright (c) 2017, 2018, 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"
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 */
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 
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
61  /// Cost to make one lookup in the temptable
63  /// Cost of scanning the materialized table
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 {
78  List<TABLE_LIST> join_list; /* list of elements in the nested join */
79  table_map used_tables{0}; /* bitmap of tables in the nested join */
80  table_map not_null_tables{0}; /* tables that rejects nulls */
81  /**
82  Used for pointing out the first table in the plan being covered by this
83  join nest. It is used exclusively within make_outerjoin_info().
84  */
86  /**
87  Set to true when natural join or using information has been processed.
88  */
90  /**
91  Number of tables and outer join nests administered by this nested join
92  object for the sake of cost analysis. Includes direct member tables as
93  well as tables included through semi-join nests, but notice that semi-join
94  nests themselves are not counted.
95  */
97  /**
98  Used to count tables in the nested join in 2 isolated places:
99  1. In make_outerjoin_info().
100  2. check_interleaving_with_nj/backout_nj_state (these are called
101  by the join optimizer.
102  Before each use the counters are zeroed by SELECT_LEX::reset_nj_counters.
103  */
105  /**
106  Bit identifying this nested join. Only nested joins representing the
107  outer join structure need this, other nests have bit set to zero.
108  */
110  /**
111  Tables outside the semi-join that are used within the semi-join's
112  ON condition (ie. the subquery WHERE clause and optional IN equalities).
113  Also contains lateral dependencies from materialized derived tables
114  contained inside the semi-join inner tables.
115  */
117  /**
118  Outer non-trivially correlated tables, a true subset of sj_depends_on.
119  Also contains lateral dependencies from materialized derived tables
120  contained inside the semi-join inner tables.
121  */
123  /**
124  Query block id if this struct is generated from a subquery transform.
125  */
127 
128  /// Bitmap of which strategies are enabled for this semi-join nest
130 
131  /*
132  Lists of trivially-correlated expressions from the outer and inner tables
133  of the semi-join, respectively.
134  */
137 };
138 
139 #endif // SQL_NESTED_JOIN_INCLUDED
uint sj_enabled_strategies
Bitmap of which strategies are enabled for this semi-join nest.
Definition: nested_join.h:129
Definition: item.h:3341
unsigned long long int ulonglong
Definition: my_inttypes.h:55
ulonglong table_map
Definition: my_table_map.h:32
bool lookup_allowed
True if data types allow the MaterializeLookup semijoin strategy.
Definition: nested_join.h:54
Some integer typedefs for easier portability.
Cost_estimate scan_cost
Cost of scanning the materialized table.
Definition: nested_join.h:64
table_map not_null_tables
Definition: nested_join.h:80
Semijoin_mat_optimize sjm
Definition: nested_join.h:136
Common types of the Optimizer, used by optimization and execution.
int8 plan_idx
This represents the index of a JOIN_TAB/QEP_TAB in an array.
Definition: sql_opt_exec_shared.h:39
double expected_rowcount
Expected number of rows in the materialized table.
Definition: nested_join.h:58
table_map used_tables
Definition: nested_join.h:79
bool natural_join_processed
Set to true when natural join or using information has been processed.
Definition: nested_join.h:89
Struct NESTED_JOIN is used to represent how tables are connected through outer join operations and se...
Definition: nested_join.h:77
uint nj_counter
Used to count tables in the nested join in 2 isolated places:
Definition: nested_join.h:104
uint nj_total
Number of tables and outer join nests administered by this nested join object for the sake of cost an...
Definition: nested_join.h:96
List< Item > sj_outer_exprs
Definition: nested_join.h:135
Cost_estimate lookup_cost
Cost to make one lookup in the temptable.
Definition: nested_join.h:62
Definition: item.h:668
unsigned int uint
Definition: uca-dump.cc:29
ulonglong nested_join_map
Definition: nested_join.h:36
List< Item > sj_inner_exprs
Definition: nested_join.h:135
table_map sj_corr_tables
Outer non-trivially correlated tables, a true subset of sj_depends_on.
Definition: nested_join.h:122
A position of table within a join order.
Definition: sql_select.h:345
plan_idx first_nested
Used for pointing out the first table in the plan being covered by this join nest.
Definition: nested_join.h:85
uint query_block_id
Query block id if this struct is generated from a subquery transform.
Definition: nested_join.h:126
table_map sj_depends_on
Tables outside the semi-join that are used within the semi-join&#39;s ON condition (ie.
Definition: nested_join.h:116
List< TABLE_LIST > join_list
Definition: nested_join.h:78
POSITION * positions
Optimal join order calculated for inner tables of this semijoin op.
Definition: nested_join.h:52
Definition: table.h:2468
bool scan_allowed
True if data types allow the MaterializeScan semijoin strategy.
Definition: nested_join.h:56
Used to store optimizer cost estimates.
Definition: handler.h:3284
Semijoin_mat_optimize collects data used when calculating the cost of executing a semijoin operation ...
Definition: nested_join.h:50
nested_join_map nj_map
Bit identifying this nested join.
Definition: nested_join.h:109
Cost_estimate materialization_cost
Materialization cost - execute sub-join and write rows to temp.table.
Definition: nested_join.h:60
Item_field ** mat_fields
Array of pointers to fields in the materialized table.
Definition: nested_join.h:66