#include "sql/join_optimizer/cost_model.h"
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <bit>
#include <iterator>
#include "mem_root_deque.h"
#include "my_base.h"
#include "sql/handler.h"
#include "sql/item_func.h"
#include "sql/item_subselect.h"
#include "sql/join_optimizer/access_path.h"
#include "sql/join_optimizer/bit_utils.h"
#include "sql/join_optimizer/find_contained_subqueries.h"
#include "sql/join_optimizer/join_optimizer.h"
#include "sql/join_optimizer/materialize_path_parameters.h"
#include "sql/join_optimizer/optimizer_trace.h"
#include "sql/join_optimizer/overflow_bitset.h"
#include "sql/join_optimizer/print_utils.h"
#include "sql/join_optimizer/relational_expression.h"
#include "sql/mem_root_array.h"
#include "sql/mysqld.h"
#include "sql/opt_costmodel.h"
#include "sql/opt_trace.h"
#include "sql/sql_class.h"
#include "sql/sql_const.h"
#include "sql/sql_lex.h"
#include "sql/sql_optimizer.h"
#include "sql/sql_planner.h"
#include "sql/system_variables.h"
#include "sql/table.h"
#include "template_utils.h"

Classes
class	anonymous_namespace{cost_model.cc}::AggregateRowEstimator
	This class finds disjoint sets of aggregation terms that form prefixes of some non-hash index, and makes row estimates for those sets based on index metadata. More...

struct	anonymous_namespace{cost_model.cc}::AggregateRowEstimator::Prefix
	A prefix of some key where each key_part corresponds to an aggregation term. More...

Namespaces
namespace	anonymous_namespace{cost_model.cc}

Typedefs
using	anonymous_namespace{cost_model.cc}::TermArray = Bounds_checked_array< const Item *const >
	Array of aggregation terms. More...

Functions
double	EstimateCostForRefAccess (THD thd, TABLE table, unsigned key_idx, double num_output_rows)

void	EstimateSortCost (THD thd, AccessPath path, double distinct_rows)
	Estimate costs and output rows for a SORT AccessPath. More...

void	AddCost (THD thd, const ContainedSubquery &subquery, double num_rows, FilterCost cost)
	Used internally by EstimateFilterCost() only. More...

FilterCost	EstimateFilterCost (THD thd, double num_rows, Item condition, const Query_block *outer_query_block)
	Estimate the cost of evaluating “condition”, “num_rows” times. More...

void	EstimateMaterializeCost (THD thd, AccessPath path)

TermArray	anonymous_namespace{cost_model.cc}::GetAggregationTerms (const JOIN &join)

double	anonymous_namespace{cost_model.cc}::EstimateDistinctRowsFromStatistics (THD *thd, TermArray terms, double child_rows)
	Estimate the number of distinct tuples in the projection defined by 'terms'. More...

template<typename FunctionLow , typename FunctionHigh >
double	anonymous_namespace{cost_model.cc}::SmoothTransition (FunctionLow function_low, FunctionHigh function_high, double lower_limit, double upper_limit, double argument)
	For a function f(x) such that: f(x) = g(x) for x<=l f(x) = h(x) for x>l. More...

double	anonymous_namespace{cost_model.cc}::EstimateRollupRowsPrimitively (double aggregate_rows, size_t grouping_expressions)
	Do a cheap rollup row estimate for small result sets. More...

double	anonymous_namespace{cost_model.cc}::EstimateRollupRowsAdvanced (THD *thd, double aggregate_rows, TermArray terms)
	Do more precise rollup row estimate for larger result sets. More...

double	anonymous_namespace{cost_model.cc}::EstimateAggregateRows (THD thd, const AccessPath child, const Query_block *query_block, bool rollup)
	Estimate the row count for an aggregate operation (including ROLLUP rows for GROUP BY ... WITH ROLLUP). More...

double	EstimateDistinctRows (THD *thd, double child_rows, TermArray terms)

void	EstimateAggregateCost (THD thd, AccessPath path, const Query_block *query_block)
	Estimate costs and result row count for an aggregate operation. More...

void	EstimateDeleteRowsCost (AccessPath *path)

void	EstimateUpdateRowsCost (AccessPath *path)

void	EstimateStreamCost (AccessPath *path)
	Estimate the costs and row count for a STREAM AccessPath. More...

void	EstimateLimitOffsetCost (AccessPath *path)
	Estimate the costs and row count for a WINDOW AccessPath. More...

void	EstimateWindowCost (AccessPath *path)
	Estimate the costs and row count for a WINDOW AccessPath. More...

double	EstimateSemijoinFanOut (THD *thd, double right_rows, const JoinPredicate &edge)
	Estimate the fan out for a left semijoin or a left antijoin. More...

Function Documentation

◆ AddCost()

void AddCost	(	THD *	thd,
		const ContainedSubquery &	subquery,
		double	num_rows,
		FilterCost *	cost
	)

Used internally by EstimateFilterCost() only.

◆ EstimateAggregateCost()

void EstimateAggregateCost	(	THD *	thd,
		AccessPath *	path,
		const Query_block *	query_block
	)

Estimate costs and result row count for an aggregate operation.

Parameters

[in,out]	thd	The current thread.
[in,out]	path	The AGGREGATE path.
[in]	query_block	The Query_block to which 'path' belongs.

◆ EstimateCostForRefAccess()

double EstimateCostForRefAccess	(	THD *	thd,
		TABLE *	table,
		unsigned	key_idx,
		double	num_output_rows
	)

◆ EstimateDeleteRowsCost()

void EstimateDeleteRowsCost ( AccessPath * path )

◆ EstimateDistinctRows()

double EstimateDistinctRows	(	THD *	thd,
		double	child_rows,
		TermArray	terms
	)

◆ EstimateFilterCost()

FilterCost EstimateFilterCost	(	THD *	thd,
		double	num_rows,
		Item *	condition,
		const Query_block *	outer_query_block
	)

Estimate the cost of evaluating “condition”, “num_rows” times.

This is a fairly rudimentary estimation, but it includes the cost of any subqueries that may be present and that need evaluation.

◆ EstimateLimitOffsetCost()

void EstimateLimitOffsetCost ( AccessPath * path )

Estimate the costs and row count for a WINDOW AccessPath.

As described in

See also: AccessPath::m_init_cost, the cost to read k out of N rows would be init_cost + (k/N) * (cost - init_cost).

◆ EstimateMaterializeCost()

void EstimateMaterializeCost	(	THD *	thd,
		AccessPath *	path
	)

◆ EstimateSemijoinFanOut()

double EstimateSemijoinFanOut	(	THD *	thd,
		double	right_rows,
		const JoinPredicate &	edge
	)

Estimate the fan out for a left semijoin or a left antijoin.

The fan out is defined as the number of result rows, divided by the number of input rows from the left hand relation. For a semijoin, J1:

SELECT ... FROM t1 WHERE EXISTS (SELECT ... FROM t2 WHERE predicate)

we know that the fan out of the corresponding inner join J2:

SELECT ... FROM t1, t2 WHERE predicate

is: F(J2) = CARD(t2) * SELECTIVITY(predicate) , where CARD(t2)=right_rows, and SELECTIVITY(predicate)=edge.selectivity. If 'predicate' is a deterministic function of t1 and t2 rows, then J1 is equivalent to an inner join J3:

SELECT ... FROM t1 JOIN (SELECT DISTINCT f1,..fn FROM t2) d ON predicate

where f1,..fn are those fields from t2 that appear in the predicate.

Then F(J1) = F(J3) = F(J2) * CARD(d) / CARD(t2) = CARD(d) * SELECTIVITY(predicate).

This function therefore collects f1..fn and estimates CARD(d). As a special case, 'predicate' may be independent of t2. The query is then equivalent to:

SELECT ... FROM t1 WHERE predicate AND (SELECT COUNT(*) FROM t2) > 0

The fan out is then the selectivity of 'predicate' multiplied by the probability of t2 having at least one row.

Parameters

thd	The current thread.
right_rows	The number of input rows from the right hand relation.
edge	Join edge.

Returns: fan out.

◆ EstimateSortCost()

void EstimateSortCost	(	THD *	thd,
		AccessPath *	path,
		double	distinct_rows = `kUnknownRowCount`
	)

Estimate costs and output rows for a SORT AccessPath.

Parameters

thd	Current thread.
path	the AccessPath.
distinct_rows	An estimate of the number of distinct rows, if remove_duplicates==true and we have an estimate already.

◆ EstimateStreamCost()

void EstimateStreamCost ( AccessPath * path )

Estimate the costs and row count for a STREAM AccessPath.

◆ EstimateUpdateRowsCost()

void EstimateUpdateRowsCost ( AccessPath * path )

◆ EstimateWindowCost()

void EstimateWindowCost ( AccessPath * path )

Estimate the costs and row count for a WINDOW AccessPath.

Classes

Namespaces

Typedefs

Functions

Function Documentation

◆ AddCost()

◆ EstimateAggregateCost()

◆ EstimateCostForRefAccess()

◆ EstimateDeleteRowsCost()

◆ EstimateDistinctRows()

◆ EstimateFilterCost()

◆ EstimateLimitOffsetCost()

◆ EstimateMaterializeCost()

◆ EstimateSemijoinFanOut()

◆ EstimateSortCost()

◆ EstimateStreamCost()

◆ EstimateUpdateRowsCost()

◆ EstimateWindowCost()