MySQL 8.0.40
Source Code Documentation
hypergraph.h
Go to the documentation of this file.
1/* Copyright (c) 2020, 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_HYPERGRAPH_H_
25#define SQL_JOIN_OPTIMIZER_HYPERGRAPH_H_ 1
26
27/**
28 @file
29 Definition of an undirected (join) hypergraph. A hypergraph in this context
30 is an undirected graph consisting of nodes and hyperedges, where hyperedges
31 are edges that can have more than one node in each side of the edge.
32 For instance, in a graph with nodes {A, B, C, D}, a regular undirected edge
33 could be e.g. (A,B), while in a hypergraph, an edge such as ({A,C},B) would
34 also be allowed. Note that this definition of hypergraphs differs from that
35 on Wikipedia.
36
37 The main user of Hypergraph is subgraph_enumeration.h.
38 */
39
40#include <stddef.h>
41#include <algorithm>
42#include <vector>
43
45#include "sql/mem_root_array.h"
46
47struct MEM_ROOT;
48
49namespace hypergraph {
50
51struct Node {
52 // List of edges (indexes into the hypergraph's “edges” array) that touch this
53 // node. We split these into simple edges (only one node on each side) and
54 // complex edges (all others), because we can often quickly discard all simple
55 // edges by testing the set of interesting nodes against the
56 // “simple_neighborhood” bitmap.
57 //
58 // For optimization purposes, the edges are stored as if they were directed,
59 // even though the hypergraph is fundamentally undirected. That is, a (u,v)
60 // edge will be duplicated internally to (v,u), and the version that is posted
61 // in a node's edge list is the one where the node itself is on the left side.
62 // This saves a lot of duplicate code, and also reduces the amount of branch
63 // mispredictions significantly (it helps something like 30% on the overall
64 // speed).
65 std::vector<unsigned> complex_edges, simple_edges;
66
67 // All nodes on the “right” side of an edge in simple_edges.
69
70 private:
71 // Speeds up BM_HyperStar17_ManyHyperedges by 5–10%.
72 // (MSVC with debug STL will get a dummy byte here, since the struct is
73 // already more than 64 bytes.)
74 static constexpr int Size =
75 sizeof(std::vector<unsigned>) * 2 + sizeof(NodeMap);
76 char padding[std::max<int>(1, 64 - Size)];
77};
78static_assert(sizeof(Node) >= 64);
79
80struct Hyperedge {
81 // The endpoints (hypernodes) of this hyperedge. See the comment about
82 // duplicated edges in Node.
83 //
84 // left and right may not overlap, and both must have at least one bit set.
87};
88
89struct Hypergraph {
90 public:
92 Mem_root_array<Node> nodes; // Maximum 8*sizeof(NodeMap) elements.
94
95 void AddNode();
96 void AddEdge(NodeMap left, NodeMap right);
97
98 // NOTE: Since every edge is stored twice (see AddEdge), also updates the
99 // corresponding opposite-direction edge automatically. Also note that this
100 // will shift internal edge lists around, so even after no-op changes,
101 // you are not guaranteed to get back subgraph pairs in the same order
102 // as before.
103 void ModifyEdge(unsigned edge_idx, NodeMap new_left, NodeMap new_right);
104
105 private:
106 void AttachEdgeToNodes(size_t left_first_idx, size_t right_first_idx,
107 NodeMap left, NodeMap right);
108};
109
110} // namespace hypergraph
111
112#endif // SQL_JOIN_OPTIMIZER_HYPERGRAPH_H_
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:426
static MEM_ROOT mem_root
Definition: client_plugin.cc:110
Definition: hypergraph.cc:30
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
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:83
Definition: hypergraph.h:80
NodeMap left
Definition: hypergraph.h:85
NodeMap right
Definition: hypergraph.h:86
Definition: hypergraph.h:89
Mem_root_array< Node > nodes
Definition: hypergraph.h:92
void AddNode()
Definition: hypergraph.cc:32
Hypergraph(MEM_ROOT *mem_root)
Definition: hypergraph.h:91
void AddEdge(NodeMap left, NodeMap right)
Definition: hypergraph.cc:34
void AttachEdgeToNodes(size_t left_first_idx, size_t right_first_idx, NodeMap left, NodeMap right)
Definition: hypergraph.cc:118
Mem_root_array< Hyperedge > edges
Definition: hypergraph.h:93
void ModifyEdge(unsigned edge_idx, NodeMap new_left, NodeMap new_right)
Definition: hypergraph.cc:58
Definition: hypergraph.h:51
char padding[std::max< int >(1, 64 - Size)]
Definition: hypergraph.h:76
std::vector< unsigned > complex_edges
Definition: hypergraph.h:65
static constexpr int Size
Definition: hypergraph.h:74
NodeMap simple_neighborhood
Definition: hypergraph.h:68
std::vector< unsigned > simple_edges
Definition: hypergraph.h:65