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