MySQL 8.2.0
Source Code Documentation
nested_join.h
Go to the documentation of this file.
1/* Copyright (c) 2017, 2023, 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
33class Item;
34class Item_field;
35struct POSITION;
36class Table_ref;
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.
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.
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*/
82
83 /// list of tables referenced 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 */
102 uint nj_total{0};
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 */
110 uint nj_counter{0};
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:3793
Definition: item.h:4317
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:932
Definition: table.h:2846
A (partial) implementation of std::deque allocating its blocks on a MEM_ROOT.
Definition: mem_root_deque.h:109
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:1573
ulonglong nested_join_map
Definition: nested_join.h:36
Common types of the Optimizer, used by optimization and execution.
int plan_idx
This represents the index of a JOIN_TAB/QEP_TAB in an array.
Definition: sql_opt_exec_shared.h:53
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
mem_root_deque< Table_ref * > m_tables
list of tables referenced in the nested join
Definition: nested_join.h:84
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
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:352
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