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