explain_access_path.cc File Reference

#include "sql/join_optimizer/explain_access_path.h"
#include <functional>
#include <regex>
#include <string>
#include <vector>
#include <openssl/sha.h>
#include "my_base.h"
#include "sha2.h"
#include "sql-common/json_dom.h"
#include "sql/filesort.h"
#include "sql/item_cmpfunc.h"
#include "sql/item_sum.h"
#include "sql/iterators/basic_row_iterators.h"
#include "sql/iterators/bka_iterator.h"
#include "sql/iterators/composite_iterators.h"
#include "sql/iterators/hash_join_iterator.h"
#include "sql/iterators/ref_row_iterators.h"
#include "sql/iterators/sorting_iterator.h"
#include "sql/iterators/timing_iterator.h"
#include "sql/join_optimizer/access_path.h"
#include "sql/join_optimizer/cost_model.h"
#include "sql/join_optimizer/print_utils.h"
#include "sql/join_optimizer/relational_expression.h"
#include "sql/opt_explain.h"
#include "sql/opt_explain_traditional.h"
#include "sql/query_result.h"
#include "sql/range_optimizer/group_index_skip_scan_plan.h"
#include "sql/range_optimizer/index_skip_scan_plan.h"
#include "sql/range_optimizer/internal.h"
#include "sql/range_optimizer/range_optimizer.h"
#include "sql/sql_optimizer.h"
#include "sql/table.h"
#include "template_utils.h"

Classes
struct	ExplainChild
	This structure encapsulates the information needed to create a Json object for a child access path. More...

Namespaces
namespace	anonymous_namespace{explain_access_path.cc}

Functions
template<class T , class... Args>
static bool	AddMemberToObject (Json_object *obj, const char *alias, Args &&... ctor_args)
	Convenience function to add a json field. More...
template<class T , class... Args>
static bool	AddElementToArray (const std::unique_ptr< Json_array > &array, Args &&... ctor_args)
static bool	PrintRanges (const QUICK_RANGE *const *ranges, unsigned num_ranges, const KEY_PART_INFO *key_part, bool single_part_only, const std::unique_ptr< Json_array > &range_array, string *ranges_out)
static std::unique_ptr< Json_object >	ExplainAccessPath (const AccessPath *path, const AccessPath *materialized_path, JOIN *join, bool is_root_of_join, Json_object *input_obj)
	Convert the AccessPath into a Json object that represents the EXPLAIN output This Json object may in turn be used to output in whichever required format. More...
static std::unique_ptr< Json_object >	AssignParentPath (AccessPath *table_path, const AccessPath *materialized_path, std::unique_ptr< Json_object > materialized_obj, JOIN *join)
	AccessPath objects of type TEMPTABLE_AGGREGATE, MATERIALIZE, and MATERIALIZE_INFORMATION_SCHEMA_TABLE represent a materialized set of rows. More...
static double	GetJSONDouble (const Json_object *obj, const char *key)
static bool	SetIndexInfoInObject (string *str, const char *json_index_access_type, const char *prefix, TABLE *table, const KEY *key, const char *index_access_type, const string lookup_condition, const string *ranges_text, std::unique_ptr< Json_array > range_arr, bool reverse, Item *pushed_idx_cond, Json_object *obj)
string	JoinTypeToString (JoinType join_type)
string	HashJoinTypeToString (RelationalExpression::Type join_type, string *explain_json_value)
static bool	GetAccessPathsFromItem (Item *item_arg, const char *source_text, vector< ExplainChild > *children)
static bool	GetAccessPathsFromSelectList (JOIN *join, vector< ExplainChild > *children)
static std::unique_ptr< Json_object >	ExplainMaterializeAccessPath (const AccessPath *path, JOIN *join, std::unique_ptr< Json_object > ret_obj, vector< ExplainChild > *children, bool explain_analyze)
static bool	ExplainIndexSkipScanAccessPath (Json_object *obj, const AccessPath *path, JOIN *join, string *description)
static bool	ExplainGroupIndexSkipScanAccessPath (Json_object *obj, const AccessPath *path, JOIN *join, string *description)
static bool	AddChildrenFromPushedCondition (const TABLE *table, vector< ExplainChild > *children)
static bool	AddChildrenToObject (Json_object *obj, const vector< ExplainChild > &children, JOIN *parent_join, bool parent_is_root_of_join, string alias)
static std::unique_ptr< Json_object >	ExplainQueryPlan (const AccessPath *path, THD::Query_plan const *query_plan, JOIN *join, bool is_root_of_join)
static bool	AddPathCosts (const AccessPath *path, const AccessPath *materialized_path, Json_object *obj, bool explain_analyze)
	Append the various costs. More...
static std::unique_ptr< Json_object >	SetObjectMembers (std::unique_ptr< Json_object > ret_obj, const AccessPath *path, const AccessPath *materialized_path, JOIN *join, vector< ExplainChild > *children)
	Given a json object, update it's appropriate json fields according to the input path. More...
std::string	PrintQueryPlan (THD *ethd, const THD *query_thd, Query_expression *unit)
	Print out an access path and all of its children (if any) in a tree. More...
std::string	PrintQueryPlan (int level, AccessPath *path, JOIN *join, bool is_root_of_join)
	For debugging purposes. More...
static string	GetForceSubplanToken (const Json_object *obj, const string &children_digest)
string	GetForceSubplanToken (AccessPath *path, JOIN *join)
	Generate a digest based on the subplan that the given access path represents. More...
int	anonymous_namespace{explain_access_path.cc}::IntegerDigits (double d)
	Find the number of integer digits (i.e. More...
std::string	anonymous_namespace{explain_access_path.cc}::DecimalFormat (double d, int log_precision)
	Format 'd' as a decimal number with enough decimals to get a rounding error less than d*10^log_precision, without any trailing fractional zeros. More...
std::string	anonymous_namespace{explain_access_path.cc}::EngineeringFormat (double d)
	Format 'd' in engineering format, i.e. More...
std::string	anonymous_namespace{explain_access_path.cc}::NumFormat (double d)
	Format 'd' for "EXPLAIN FORMAT=TREE" output. More...
constexpr uint64_t	anonymous_namespace{explain_access_path.cc}::Power (uint64_t base, int power)
	Integer exponentiation. More...
std::string	anonymous_namespace{explain_access_path.cc}::NumFormat (uint64_t l)
	Format 'l' for "EXPLAIN FORM=TREE" output. More...

Variables
constexpr int	anonymous_namespace{explain_access_path.cc}::kPlainNumberLength = 6
	The maximal number of digits we use in decimal numbers (e.g. More...
constexpr int	anonymous_namespace{explain_access_path.cc}::kMantissaLength = 3
	The maximal number of digits in engineering format mantissas, e.g. More...
constexpr double	anonymous_namespace{explain_access_path.cc}::kMinNonZeroNumber = 1.0e-12
	The smallest number (absolute value) that we do not format as "0". More...
constexpr int	anonymous_namespace{explain_access_path.cc}::kLogPrecision = -2
	For decimal numbers, include enough decimals to ensure that any rounding error is less than <number>*10^kLogPrecision (i.e. More...
const double	anonymous_namespace{explain_access_path.cc}::kMinPlainFormatNumber
	The smallest number (absolute value) that we format as decimal (rather than engineering format). More...

Function Documentation

AddChildrenFromPushedCondition()

static bool AddChildrenFromPushedCondition ( const TABLE *  table, vector< ExplainChild > *  children  )

static

AddChildrenToObject()

static bool AddChildrenToObject ( Json_object *  obj, const vector< ExplainChild > &  children, JOIN *  parent_join, bool  parent_is_root_of_join, string  alias  )

static

AddElementToArray()

template<class T , class... Args>

static bool AddElementToArray ( const std::unique_ptr< Json_array > &  array, Args &&...  ctor_args  )

static

AddMemberToObject()

template<class T , class... Args>

static bool AddMemberToObject ( Json_object *  obj, const char *  alias, Args &&...  ctor_args  )

static

Convenience function to add a json field.

AddPathCosts()

static bool AddPathCosts ( const AccessPath *  path, const AccessPath *  materialized_path, Json_object *  obj, bool  explain_analyze  )

static

Append the various costs.

Parameters

path	the path that we add costs for.
materialized_path	the MATERIALIZE path for which 'path' is the table_path, or nullptr 'path' is not a table_path.
obj	the JSON object describing 'path'.
explain_analyze	true if we run an 'eaxplain analyze' command.

Returns

true iff there was an error.

AssignParentPath()

static std::unique_ptr< Json_object > AssignParentPath ( AccessPath *  table_path, const AccessPath *  materialized_path, std::unique_ptr< Json_object >  materialized_obj, JOIN *  join  )

static

AccessPath objects of type TEMPTABLE_AGGREGATE, MATERIALIZE, and MATERIALIZE_INFORMATION_SCHEMA_TABLE represent a materialized set of rows.

These materialized AccessPaths have a another path member (called table_path) that iterates over the materialized rows.

So codewise, table_path is a child of the materialized path, even if it is logically the parent, as it consumes the results from the materialized path. For that reason, we present table_path above the materialized path in 'explain' output (

See also

AddPathCost for details).

This function therefore sets the JSON object for the materialized path to be the leaf descendant of the table_path JSON object. (Note that in some cases table_path does not operate directly on materialized_path. Instead, table_path is the first in a chain of paths where the final path is typically a TABLE_SCAN of REF access path that the iterates over the materialized rows.)

Parameters

table_path	the head of the chain of paths that iterates over the materialized rows.
materialized_path	if (the leaf descendant of) table_path iterates over the rows from a MATERIALIZE path, then 'materialized_path' is that path. Otherwise it is nullptr.
materialized_obj	the JSON object describing the materialized path.
join	the JOIN to which 'table_path' belongs.

Returns

the JSON object describing table_path.

ExplainAccessPath()

static std::unique_ptr< Json_object > ExplainAccessPath ( const AccessPath *  path, const AccessPath *  materialized_path, JOIN *  join, bool  is_root_of_join, Json_object *  input_obj  )

static

Convert the AccessPath into a Json object that represents the EXPLAIN output This Json object may in turn be used to output in whichever required format.

Parameters

path	the path to describe.
materialized_path	if 'path' is the table_path of a MATERIALIZE path, then materialized_path is that path. Otherwise it is nullptr.
join	the JOIN to which 'path' belongs.
is_root_of_join	'true' if 'path' is the root path of a Query_expression that is not a union.
input_obj	The JSON object describing 'path', or nullptr if a new object should be allocated..

Returns

the root of the tree of JSON objects generated from 'path'. (In most cases a single object.)

ExplainGroupIndexSkipScanAccessPath()

static bool ExplainGroupIndexSkipScanAccessPath ( Json_object *  obj, const AccessPath *  path, JOIN *  join, string *  description  )

static

ExplainIndexSkipScanAccessPath()

static bool ExplainIndexSkipScanAccessPath ( Json_object *  obj, const AccessPath *  path, JOIN *  join, string *  description  )

static

ExplainMaterializeAccessPath()

static std::unique_ptr< Json_object > ExplainMaterializeAccessPath ( const AccessPath *  path, JOIN *  join, std::unique_ptr< Json_object >  ret_obj, vector< ExplainChild > *  children, bool  explain_analyze  )

static

ExplainQueryPlan()

static std::unique_ptr< Json_object > ExplainQueryPlan ( const AccessPath *  path, THD::Query_plan const *  query_plan, JOIN *  join, bool  is_root_of_join  )

static

GetAccessPathsFromItem()

static bool GetAccessPathsFromItem ( Item *  item_arg, const char *  source_text, vector< ExplainChild > *  children  )

static

GetAccessPathsFromSelectList()

static bool GetAccessPathsFromSelectList ( JOIN *  join, vector< ExplainChild > *  children  )

static

GetForceSubplanToken() [1/2]

string GetForceSubplanToken	(	AccessPath *	path,
		JOIN *	join
	)

Generate a digest based on the subplan that the given access path represents.

This can be used by developers to force a given subplan, to investigate e.g. whether a given choice is actually faster in practice, force-apply a plan from the old join optimizer (or at least the types of subplans that are ever considered; e.g. aggregation through temporary tables are not) into the hypergraph join optimizer (to see how it's costed), or whether a given plan is even generated. If DEBUG contains force_subplan_0x<token>, subplans with the given token are unconditionally preferred over all others.

The token returned is “0x<digest>”, where <digest> is the first 64 bits of the SHA-256 sum of this string:

desc1,desc2,...,[child1_desc:]0xchild1,[child2_desc:]0xchild2,<more children>

where desc1, desc2, etc. are the description lines given by EXPLAIN, and 0xchild1 is the token for children. The normal way to generate such tokens is to use SET DEBUG='+d,subplan_tokens' and look at the EXPLAIN FORMAT=tree, but in a pinch, you can also write them by hand and use sha256sum or a similar tool.

Only the hypergraph join optimizer honors token preferences, but EXPLAIN FORMAT=tree shows computed tokens for both optimizers.

GetForceSubplanToken() [2/2]

static string GetForceSubplanToken ( const Json_object *  obj, const string &  children_digest  )

static

GetJSONDouble()

static double GetJSONDouble ( const Json_object *  obj, const char *  key  )

inlinestatic

HashJoinTypeToString()

string HashJoinTypeToString	(	RelationalExpression::Type	join_type,
		string *	explain_json_value
	)

JoinTypeToString()

string JoinTypeToString

(

JoinType

join_type

)

PrintQueryPlan() [1/2]

std::string PrintQueryPlan	(	int	level,
		AccessPath *	path,
		JOIN *	join,
		bool	is_root_of_join
	)

For debugging purposes.

PrintQueryPlan() [2/2]

std::string PrintQueryPlan	(	THD *	ethd,
		const THD *	query_thd,
		Query_expression *	unit
	)

Print out an access path and all of its children (if any) in a tree.

PrintRanges()

static bool PrintRanges ( const QUICK_RANGE *const *  ranges, unsigned  num_ranges, const KEY_PART_INFO *  key_part, bool  single_part_only, const std::unique_ptr< Json_array > &  range_array, string *  ranges_out  )

static

SetIndexInfoInObject()

static bool SetIndexInfoInObject ( string *  str, const char *  json_index_access_type, const char *  prefix, TABLE *  table, const KEY *  key, const char *  index_access_type, const string  lookup_condition, const string *  ranges_text, std::unique_ptr< Json_array >  range_arr, bool  reverse, Item *  pushed_idx_cond, Json_object *  obj  )

static

SetObjectMembers()

static std::unique_ptr< Json_object > SetObjectMembers ( std::unique_ptr< Json_object >  ret_obj, const AccessPath *  path, const AccessPath *  materialized_path, JOIN *  join, vector< ExplainChild > *  children  )

static

Given a json object, update it's appropriate json fields according to the input path.

Also update the 'children' with a flat list of direct children of the passed object. In most of cases, the returned object is same as the input object, but for some paths it can be different. So callers should use the returned object.

Note: This function has shown to consume excessive stack space, particularly in debug builds. Hence make sure this function does not directly or indirectly create any json children objects recursively. It may cause stack overflow. Hence json children are created only after this function returns in function ExplainAccessPath().

Parameters

ret_obj	The JSON object describing 'path'.
path	the path to describe.
materialized_path	if 'path' is the table_path of a MATERIALIZE path, then materialized_path is that path. Otherwise it is nullptr.
join	the JOIN to which 'path' belongs.
children	the paths that are the children of the path that the returned JSON object represents (i.e. the next paths to be explained).

Returns

either ret_obj or a new JSON object with ret_obj as a descendant.