OnlineCycleFinder Class Reference

A fast online cycle finder, based on [Pea03]. More...

#include <online_cycle_finder.h>

Public Member Functions
	OnlineCycleFinder (MEM_ROOT *mem_root, int num_vertices)
bool	EdgeWouldCreateCycle (int a_idx, int b_idx)
bool	AddEdge (int a_idx, int b_idx)
void	DeleteEdge (int a_idx, int b_idx)
Bounds_checked_array< int >	order () const

Private Member Functions
bool	DepthFirstSearch (int node_idx, int upper_bound, int node_idx_to_avoid)
void	MoveAllMarked (int start_pos, int new_pos)
void	Allocate (int node_idx, int index_in_order)

Private Attributes
Bounds_checked_array< int >	m_order
Bounds_checked_array< int >	m_position_of_node
Bounds_checked_array< bool >	m_visited
Mem_root_array< int >	m_to_shift
mem_root_unordered_multimap< int, int >	m_edges

Detailed Description

A fast online cycle finder, based on [Pea03].

It keeps a DAG in memory, built up incrementally, and is able to reject adding edges that would create cycles (or, equivalently, test if adding an edge would create a cycle). The amortized cost of checking ϴ(E) insertions is O(V).

The basic working of the algorithm is to keep a list of all vertices, topologically sorted given the order so far. When inserting a new edge, we can quickly identify any vertices that would need to be moved in the topological sort (they are the ones stored between the two endpoints), run a DFS, and see if moving them would cause a contradiction (and thus, a cycle). See EdgeWouldCreateCycle() or the paper for more details.

Note that confusingly enough, when used from the graph simplification algorithm, the vertices in this graph represent hyperedges (joins) in the join hypergraph, not the vertices (tables) themselves. The edges in this graph are happens-before relations between those joins.

[Pea03] Pearce et al: “Online Cycle Detection and Difference Propagation for Pointer Analysis”, section 3.2.

Constructor & Destructor Documentation

OnlineCycleFinder()

OnlineCycleFinder::OnlineCycleFinder	(	MEM_ROOT *	mem_root,
		int	num_vertices
	)

Member Function Documentation

AddEdge()

bool OnlineCycleFinder::AddEdge	(	int	a_idx,
		int	b_idx
	)

Allocate()

void OnlineCycleFinder::Allocate ( int  node_idx, int  index_in_order  )

inlineprivate

DeleteEdge()

void OnlineCycleFinder::DeleteEdge	(	int	a_idx,
		int	b_idx
	)

DepthFirstSearch()

bool OnlineCycleFinder::DepthFirstSearch ( int  node_idx, int  upper_bound, int  node_idx_to_avoid  )

private

EdgeWouldCreateCycle()

bool OnlineCycleFinder::EdgeWouldCreateCycle	(	int	a_idx,
		int	b_idx
	)

MoveAllMarked()

void OnlineCycleFinder::MoveAllMarked ( int  start_pos, int  new_pos  )

private

order()

Bounds_checked_array< int > OnlineCycleFinder::order ( ) const

inline

Member Data Documentation

m_edges

mem_root_unordered_multimap<int, int> OnlineCycleFinder::m_edges

private

m_order

Bounds_checked_array<int> OnlineCycleFinder::m_order

private

m_position_of_node

Bounds_checked_array<int> OnlineCycleFinder::m_position_of_node

private

m_to_shift

Mem_root_array<int> OnlineCycleFinder::m_to_shift

private

m_visited

Bounds_checked_array<bool> OnlineCycleFinder::m_visited

private

---

The documentation for this class was generated from the following files:

• sql/join_optimizer/online_cycle_finder.h
• sql/join_optimizer/online_cycle_finder.cc