graph_simplification.cc File Reference

#include "sql/join_optimizer/graph_simplification.h"
#include <assert.h>
#include <stdint.h>
#include <algorithm>
#include <cmath>
#include <new>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
#include "my_alloc.h"
#include "sql/handler.h"
#include "sql/join_optimizer/access_path.h"
#include "sql/join_optimizer/bit_utils.h"
#include "sql/join_optimizer/cost_model.h"
#include "sql/join_optimizer/hypergraph.h"
#include "sql/join_optimizer/make_join_hypergraph.h"
#include "sql/join_optimizer/node_map.h"
#include "sql/join_optimizer/online_cycle_finder.h"
#include "sql/join_optimizer/print_utils.h"
#include "sql/join_optimizer/relational_expression.h"
#include "sql/join_optimizer/subgraph_enumeration.h"
#include "sql/join_optimizer/trivial_receiver.h"
#include "sql/mem_root_allocator.h"
#include "sql/mem_root_array.h"
#include "sql/sql_array.h"
#include "sql/sql_class.h"
#include "sql/sql_const.h"
#include "sql/table.h"

Classes
struct	anonymous_namespace{graph_simplification.cc}::JoinStatus

Namespaces
namespace	anonymous_namespace{graph_simplification.cc}

Functions
bool	anonymous_namespace{graph_simplification.cc}::IsSubjoin (Hyperedge a, Hyperedge b)
	Returns whether A is already a part of B, ie., whether it is impossible to execute B before A. More...
bool	anonymous_namespace{graph_simplification.cc}::CombiningWouldViolateConflictRules (const Mem_root_array< ConflictRule > &conflict_rules, const int *in_component, int left_component, int right_component)
int	anonymous_namespace{graph_simplification.cc}::GetComponent (const NodeMap *components, const int *in_component, NodeMap tables)
template<class Func >
void	anonymous_namespace{graph_simplification.cc}::ConnectComponentsThroughJoins (const JoinHypergraph &graph, const OnlineCycleFinder &cycles, Func &&callback_on_join, NodeMap *components, int *in_component)
	Helper algorithm for GetCardinality() and GraphIsJoinable(); given a set of components (each typically connecting a single table at the start), connects them incrementally up through joins and calls a given callback every time we do it. More...
double	anonymous_namespace{graph_simplification.cc}::GetCardinality (NodeMap tables_to_join, const JoinHypergraph &graph, const OnlineCycleFinder &cycles)
	For a given set of tables, try to estimate the cardinality of joining them together. More...
double	anonymous_namespace{graph_simplification.cc}::GetCardinalitySingleJoin (NodeMap left, NodeMap right, double left_rows, double right_rows, const JoinHypergraph &graph, const JoinPredicate &pred)
	A special, much faster version of GetCardinality() that can be used when joining two partitions along a known edge. More...
OnlineCycleFinder	anonymous_namespace{graph_simplification.cc}::FindJoinDependencies (const Hypergraph &graph, MEM_ROOT *mem_root)
	Initialize a DAG containing all inferred join dependencies from the hypergraph. More...
bool	anonymous_namespace{graph_simplification.cc}::IsQueryGraphSimpleEnough (THD *thd, const JoinHypergraph &graph, int subgraph_pair_limit, MEM_ROOT *mem_root, int *seen_subgraph_pairs)
void	anonymous_namespace{graph_simplification.cc}::SetNumberOfSimplifications (int num_simplifications, GraphSimplifier *simplifier)
JoinStatus	anonymous_namespace{graph_simplification.cc}::SimulateJoin (JoinStatus left, JoinStatus right, const JoinPredicate &pred)
	Simulate the (total) costs and cardinalities of joining two sets of tables, without actually having an AccessPath for each (which is a bit heavyweight for just cost and cardinality). More...
JoinStatus	anonymous_namespace{graph_simplification.cc}::SimulateJoin (double left_rows, JoinStatus right, const JoinPredicate &pred)
JoinStatus	anonymous_namespace{graph_simplification.cc}::SimulateJoin (JoinStatus left, double right_rows, const JoinPredicate &pred)
JoinStatus	anonymous_namespace{graph_simplification.cc}::SimulateJoin (double left_rows, double right_rows, const JoinPredicate &pred)
bool	anonymous_namespace{graph_simplification.cc}::GraphIsJoinable (const JoinHypergraph &graph, const OnlineCycleFinder &cycles)
	See if a given hypergraph is impossible to join, in any way. More...
void	SimplifyQueryGraph (THD *thd, int subgraph_pair_limit, JoinHypergraph *graph, string *trace)
	Repeatedly apply simplifications (in the order of most to least safe) to the given hypergraph, until it is below “subgraph_pair_limit” subgraph pairs or we can simplify it no more. More...

Function Documentation

SimplifyQueryGraph()

void SimplifyQueryGraph	(	THD *	thd,
		int	subgraph_pair_limit,
		JoinHypergraph *	graph,
		string *	trace
	)

Repeatedly apply simplifications (in the order of most to least safe) to the given hypergraph, until it is below “subgraph_pair_limit” subgraph pairs or we can simplify it no more.

Since we cannot know ahead of time exactly how many simplification steps required, we need to do this iteratively, running DPhyp (with all the actual and expensive costing removed, only subgraph pair counting) as we go.

On the assumption that running DPhyp over the graph is significantly more expensive than applying a simplification step, we do this by means of binary search (what the paper calls “the full algorithm”). We apply first 1, 2, 4, 8, 16, etc. steps until we find a number that takes us below the limit. Then, we apply a simple binary search between that value and the previous one. Once we find the border between too complicated and just simple enough, we set the graph to the latter, and the actual query planning will start afresh.