MySQL 8.0.29
Source Code Documentation
trivial_receiver.h
Go to the documentation of this file.
1/* Copyright (c) 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_JOIN_OPTIMIZER_TRIVIAL_RECEIVER_H_
24#define SQL_JOIN_OPTIMIZER_TRIVIAL_RECEIVER_H_
25
28
29/**
30 A very simple receiver to be used with DPhyp; all it does is
31 to keep track of which subgraphs it has seen (which is required
32 for the algorithm to test connectedness), count them, and stop
33 if we reach a given limit.
34
35 This is usable both from unit tests (although we don't actually
36 currently use it for such) and for making a cheap test of whether
37 the number of subgraph pairs is below a given limit; see GraphSimplifier
38 for the latter. (The graph simplification paper, [Neu09], mentions
39 running a special mode where we don't check for subgraph complements
40 at all, only connected subgraphs, but we haven't investigated
41 to what degree this would be possible for our implementation,
42 or whether it would be advantageous at all.)
43 */
45 public:
47 int subgraph_pair_limit)
49 m_graph(&graph),
50 m_subgraph_pair_limit(subgraph_pair_limit) {}
51
52 bool HasSeen(hypergraph::NodeMap subgraph) const {
53 return m_seen_subgraphs.count(subgraph) != 0;
54 }
55 bool FoundSingleNode(int node_idx) {
56 ++seen_nodes;
57 m_seen_subgraphs.insert(TableBitmap(node_idx));
58 return false;
59 }
60
61 // Called EmitCsgCmp() in the paper.
63 int edge_idx [[maybe_unused]]) {
64 const JoinPredicate *edge = &m_graph->edges[edge_idx];
65 if (!PassesConflictRules(left | right, edge->expr)) {
66 return false;
67 }
69 if (m_subgraph_pair_limit >= 0 &&
71 return true;
72 }
73 assert(left != 0);
74 assert(right != 0);
75 assert((left & right) == 0);
76 m_seen_subgraphs.insert(left | right);
77 return false;
78 }
79
80 int seen_nodes = 0;
82
83 private:
87};
88
89#endif // SQL_JOIN_OPTIMIZER_TRIVIAL_RECEIVER_H_
uint64_t TableBitmap(unsigned x)
Definition: bit_utils.h:185
A very simple receiver to be used with DPhyp; all it does is to keep track of which subgraphs it has ...
Definition: trivial_receiver.h:44
int seen_subgraph_pairs
Definition: trivial_receiver.h:81
bool HasSeen(hypergraph::NodeMap subgraph) const
Definition: trivial_receiver.h:52
TrivialReceiver(const JoinHypergraph &graph, MEM_ROOT *mem_root, int subgraph_pair_limit)
Definition: trivial_receiver.h:46
const JoinHypergraph * m_graph
Definition: trivial_receiver.h:85
const int m_subgraph_pair_limit
Definition: trivial_receiver.h:86
mem_root_unordered_set< hypergraph::NodeMap > m_seen_subgraphs
Definition: trivial_receiver.h:84
int seen_nodes
Definition: trivial_receiver.h:80
bool FoundSubgraphPair(hypergraph::NodeMap left, hypergraph::NodeMap right, int edge_idx)
Definition: trivial_receiver.h:62
bool FoundSingleNode(int node_idx)
Definition: trivial_receiver.h:55
std::unordered_set, but allocated on a MEM_ROOT.
Definition: map_helpers.h:260
static MEM_ROOT mem_root
Definition: client_plugin.cc:109
Definition of an undirected (join) hypergraph.
uint64_t NodeMap
Since our graphs can never have more than 61 tables, node sets and edge lists are implemented using 6...
Definition: node_map.h:39
bool PassesConflictRules(hypergraph::NodeMap joined_tables, const RelationalExpression *expr)
Definition: relational_expression.h:183
A struct containing a join hypergraph of a single query block, encapsulating the constraints given by...
Definition: make_join_hypergraph.h:70
Mem_root_array< JoinPredicate > edges
Definition: make_join_hypergraph.h:110
A specification that two specific relational expressions (e.g., two tables, or a table and a join bet...
Definition: access_path.h:74
RelationalExpression * expr
Definition: access_path.h:75
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:82