MySQL 9.0.0
Source Code Documentation
trivial_receiver.h
Go to the documentation of this file.
1/* Copyright (c) 2021, 2024, 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 designed to work 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 either included with
13 the program or referenced in the documentation.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
23
24#ifndef SQL_JOIN_OPTIMIZER_TRIVIAL_RECEIVER_H_
25#define SQL_JOIN_OPTIMIZER_TRIVIAL_RECEIVER_H_
26
29
30/**
31 A very simple receiver to be used with DPhyp; all it does is
32 to keep track of which subgraphs it has seen (which is required
33 for the algorithm to test connectedness), count them, and stop
34 if we reach a given limit.
35
36 This is usable both from unit tests (although we don't actually
37 currently use it for such) and for making a cheap test of whether
38 the number of subgraph pairs is below a given limit; see GraphSimplifier
39 for the latter. (The graph simplification paper, [Neu09], mentions
40 running a special mode where we don't check for subgraph complements
41 at all, only connected subgraphs, but we haven't investigated
42 to what degree this would be possible for our implementation,
43 or whether it would be advantageous at all.)
44 */
46 public:
48 int subgraph_pair_limit)
50 m_graph(&graph),
51 m_subgraph_pair_limit(subgraph_pair_limit) {}
52
53 bool HasSeen(hypergraph::NodeMap subgraph) const {
54 return m_seen_subgraphs.count(subgraph) != 0;
55 }
56 bool FoundSingleNode(int node_idx) {
57 ++seen_nodes;
58 m_seen_subgraphs.insert(TableBitmap(node_idx));
59 return false;
60 }
61
62 // Called EmitCsgCmp() in the paper.
64 int edge_idx [[maybe_unused]]) {
65 const JoinPredicate *edge = &m_graph->edges[edge_idx];
66 if (!PassesConflictRules(left | right, edge->expr)) {
67 return false;
68 }
70 if (m_subgraph_pair_limit >= 0 &&
72 return true;
73 }
74 assert(left != 0);
75 assert(right != 0);
76 assert((left & right) == 0);
77 m_seen_subgraphs.insert(left | right);
78 return false;
79 }
80
81 int seen_nodes = 0;
83
84 private:
88};
89
90#endif // SQL_JOIN_OPTIMIZER_TRIVIAL_RECEIVER_H_
constexpr uint64_t TableBitmap(unsigned x)
Definition: bit_utils.h:178
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:45
int seen_subgraph_pairs
Definition: trivial_receiver.h:82
bool HasSeen(hypergraph::NodeMap subgraph) const
Definition: trivial_receiver.h:53
TrivialReceiver(const JoinHypergraph &graph, MEM_ROOT *mem_root, int subgraph_pair_limit)
Definition: trivial_receiver.h:47
const JoinHypergraph * m_graph
Definition: trivial_receiver.h:86
const int m_subgraph_pair_limit
Definition: trivial_receiver.h:87
mem_root_unordered_set< hypergraph::NodeMap > m_seen_subgraphs
Definition: trivial_receiver.h:85
int seen_nodes
Definition: trivial_receiver.h:81
bool FoundSubgraphPair(hypergraph::NodeMap left, hypergraph::NodeMap right, int edge_idx)
Definition: trivial_receiver.h:63
bool FoundSingleNode(int node_idx)
Definition: trivial_receiver.h:56
std::unordered_set, but allocated on a MEM_ROOT.
Definition: map_helpers.h:270
static MEM_ROOT mem_root
Definition: client_plugin.cc:114
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:40
bool PassesConflictRules(hypergraph::NodeMap joined_tables, const RelationalExpression *expr)
Definition: relational_expression.h:261
A struct containing a join hypergraph of a single query block, encapsulating the constraints given by...
Definition: make_join_hypergraph.h:88
Mem_root_array< JoinPredicate > edges
Definition: make_join_hypergraph.h:190
A specification that two specific relational expressions (e.g., two tables, or a table and a join bet...
Definition: access_path.h:78
RelationalExpression * expr
Definition: access_path.h:79
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:83