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