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