#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.

Classes

Namespaces

Functions

Variables

Function Documentation

◆ AddChildrenFromPushedCondition()

◆ AddChildrenToObject()

◆ AddElementToArray()

◆ AddMemberToObject()

◆ AddPathCosts()

◆ AssignParentPath()

◆ ExplainAccessPath()

◆ ExplainGroupIndexSkipScanAccessPath()

◆ ExplainIndexSkipScanAccessPath()

◆ ExplainMaterializeAccessPath()

◆ ExplainQueryPlan()

◆ GetAccessPathsFromItem()

◆ GetAccessPathsFromSelectList()

◆ GetForceSubplanToken() [1/2]

◆ GetForceSubplanToken() [2/2]

◆ GetJSONDouble()

◆ HashJoinTypeToString()

◆ JoinTypeToString()

◆ PrintQueryPlan() [1/2]

◆ PrintQueryPlan() [2/2]

◆ PrintRanges()

◆ SetIndexInfoInObject()

◆ SetObjectMembers()