MySQL 8.0.29
Source Code Documentation
graph_simplification.cc File Reference
#include "sql/join_optimizer/graph_simplification.h"
#include <assert.h>
#include <math.h>
#include <stdint.h>
#include <algorithm>
#include <memory>
#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 A before B. 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.