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