MySQL 8.0.29
Source Code Documentation
online_cycle_finder.h
Go to the documentation of this file.
1/* Copyright (c) 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_ONLINE_CYCLE_FINDER_H_
24#define SQL_JOIN_OPTIMIZER_ONLINE_CYCLE_FINDER_H_
25
26#include "map_helpers.h"
27#include "sql/mem_root_array.h"
28#include "sql/sql_array.h"
29
30struct MEM_ROOT;
31
32/**
33 A fast online cycle finder, based on [Pea03]. It keeps a DAG in memory,
34 built up incrementally, and is able to reject adding edges that would create
35 cycles (or, equivalently, test if adding an edge would create a cycle).
36 The amortized cost of checking ϴ(E) insertions is O(V).
37
38 The basic working of the algorithm is to keep a list of all vertices,
39 topologically sorted given the order so far. When inserting a new edge,
40 we can quickly identify any vertices that would need to be moved in the
41 topological sort (they are the ones stored between the two endpoints),
42 run a DFS, and see if moving them would cause a contradiction (and thus,
43 a cycle). See EdgeWouldCreateCycle() or the paper for more details.
44
45 Note that confusingly enough, when used from the graph simplification
46 algorithm, the vertices in this graph represent hyperedges (joins) in the join
47 hypergraph, _not_ the vertices (tables) themselves. The edges in this graph
48 are happens-before relations between those joins.
49
50 [Pea03] Pearce et al: “Online Cycle Detection and Difference Propagation for
51 Pointer Analysis”, section 3.2.
52 */
54 public:
55 OnlineCycleFinder(MEM_ROOT *mem_root, int num_vertices);
56
57 // Returns true iff this would create a cycle.
58 bool EdgeWouldCreateCycle(int a_idx, int b_idx);
59
60 // Adds edge A -> B (A must be before B).
61 // Returns true iff this would create a cycle.
62 bool AddEdge(int a_idx, int b_idx);
63
64 // Remove edge A -> B. The edge must have been added earlier with AddEdge
65 // (or we will assert-fail).
66 void DeleteEdge(int a_idx, int b_idx);
67
68 // Returns a topological sort, respecting the added edges.
69 // Note that the ordering is entirely arbitrary except for that,
70 // and can be changed by e.g. EdgeWouldCreateCycle() calls.
72
73 private:
74 bool DepthFirstSearch(int node_idx, int upper_bound, int node_idx_to_avoid);
75 void MoveAllMarked(int start_pos, int new_pos);
76 void Allocate(int node_idx, int index_in_order) {
77 m_order[index_in_order] = node_idx;
78 m_position_of_node[node_idx] = index_in_order;
79 }
80
81 // List of nodes, in topological order. Called i2n in the paper.
83
84 // For each node index, where in m_order is it?
85 // Called n2i in the paper.
87
88 // For each node, was it seen during this search or not?
90
91 // Used as a temporary during MoveAllMarked().
93
94 // All edges that have been added, keyed by index of the from-node.
96};
97
98#endif // SQL_JOIN_OPTIMIZER_ONLINE_CYCLE_FINDER_H_
A wrapper class which provides array bounds checking.
Definition: sql_array.h:46
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:421
A fast online cycle finder, based on [Pea03].
Definition: online_cycle_finder.h:53
void DeleteEdge(int a_idx, int b_idx)
Definition: online_cycle_finder.cc:150
Bounds_checked_array< int > m_position_of_node
Definition: online_cycle_finder.h:86
OnlineCycleFinder(MEM_ROOT *mem_root, int num_vertices)
Definition: online_cycle_finder.cc:37
Mem_root_array< int > m_to_shift
Definition: online_cycle_finder.h:92
void MoveAllMarked(int start_pos, int new_pos)
Definition: online_cycle_finder.cc:131
bool AddEdge(int a_idx, int b_idx)
Definition: online_cycle_finder.cc:87
mem_root_unordered_multimap< int, int > m_edges
Definition: online_cycle_finder.h:95
Bounds_checked_array< int > m_order
Definition: online_cycle_finder.h:82
Bounds_checked_array< bool > m_visited
Definition: online_cycle_finder.h:89
bool EdgeWouldCreateCycle(int a_idx, int b_idx)
Definition: online_cycle_finder.cc:49
void Allocate(int node_idx, int index_in_order)
Definition: online_cycle_finder.h:76
bool DepthFirstSearch(int node_idx, int upper_bound, int node_idx_to_avoid)
Definition: online_cycle_finder.cc:95
Bounds_checked_array< int > order() const
Definition: online_cycle_finder.h:71
std::unordered_multimap, but allocated on a MEM_ROOT.
Definition: map_helpers.h:297
static MEM_ROOT mem_root
Definition: client_plugin.cc:109
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:82