MySQL 8.3.0
Source Code Documentation
hypergraph.h
Go to the documentation of this file.
1/* Copyright (c) 2020, 2023, 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 <bit>
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/// Is an edge between "left" and "right" a simple edge?
111inline bool IsSimpleEdge(NodeMap left, NodeMap right) {
112 return std::has_single_bit(left) && std::has_single_bit(right);
113}
114
115} // namespace hypergraph
116
117#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:113
Definition: hypergraph.cc:29
bool IsSimpleEdge(NodeMap left, NodeMap right)
Is an edge between "left" and "right" a simple edge?
Definition: hypergraph.h:111
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: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:31
Hypergraph(MEM_ROOT *mem_root)
Definition: hypergraph.h:91
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:116
Mem_root_array< Hyperedge > edges
Definition: hypergraph.h:93
void ModifyEdge(unsigned edge_idx, NodeMap new_left, NodeMap new_right)
Definition: hypergraph.cc:57
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