/* Copyright (c) 2020, 2024, Oracle and/or its affiliates.

Copyright (c) 2023, 2025, GreatDB Software Co., Ltd.

This program is free software; you can redistribute it and/or modify

it under the terms of the GNU General Public License, version 2.0,

as published by the Free Software Foundation.

This program is designed to work with certain software (including

but not limited to OpenSSL) that is licensed under separate terms,

as designated in a particular file or component or in included license

documentation. The authors of MySQL hereby grant you an additional

permission to link the program and your derivative works with the

separately licensed software that they have either included with

the program or referenced in the documentation.

This program is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

GNU General Public License, version 2.0, for more details.

You should have received a copy of the GNU General Public License

along with this program; if not, write to the Free Software

Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */

#include "sql/join_optimizer/join_optimizer.h"

#include <assert.h>

#include <float.h>

#include <stdint.h>

#include <stdio.h>

#include <string.h>

#include <sys/types.h>

#include <algorithm>

#include <bit>

#include <bitset>

#include <cmath>

#include <initializer_list>

#include <iterator>

#include <limits>

#include <ostream>

#include <string>

#include <string_view>

#include <unordered_map>

#include <utility>

#include <vector>

#include "ft_global.h"

#include "map_helpers.h"

#include "mem_root_deque.h"

#include "my_alloc.h"

#include "my_base.h"

#include "my_bitmap.h"

#include "my_dbug.h"

#include "my_inttypes.h"

#include "my_sqlcommand.h"

#include "my_sys.h"

#include "my_table_map.h"

#include "mysql/components/services/bits/psi_bits.h"

#include "mysql/udf_registration_types.h"

#include "mysqld_error.h"

#include "prealloced_array.h"

#include "scope_guard.h"

#include "sql/field.h"

#include "sql/filesort.h"

#include "sql/handler.h"

#include "sql/item.h"

#include "sql/item_cmpfunc.h"

#include "sql/item_func.h"

#include "sql/item_sum.h"

#include "sql/join_optimizer/access_path.h"

#include "sql/join_optimizer/bit_utils.h"

#include "sql/join_optimizer/build_interesting_orders.h"

#include "sql/join_optimizer/compare_access_paths.h"

#include "sql/join_optimizer/cost_model.h"

#include "sql/join_optimizer/estimate_selectivity.h"

#include "sql/join_optimizer/explain_access_path.h"

#include "sql/join_optimizer/find_contained_subqueries.h"

#include "sql/join_optimizer/graph_simplification.h"

#include "sql/join_optimizer/hypergraph.h"

#include "sql/join_optimizer/interesting_orders.h"

#include "sql/join_optimizer/interesting_orders_defs.h"

#include "sql/join_optimizer/make_join_hypergraph.h"

#include "sql/join_optimizer/node_map.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/join_optimizer/secondary_engine_costing_flags.h"

#include "sql/join_optimizer/subgraph_enumeration.h"

#include "sql/join_optimizer/walk_access_paths.h"

#include "sql/join_type.h"

#include "sql/key.h"

#include "sql/key_spec.h"

#include "sql/mem_root_array.h"

#include "sql/olap.h"

#include "sql/opt_costmodel.h"

#include "sql/opt_hints.h"

#include "sql/parse_tree_node_base.h"

#include "sql/partition_info.h"

#include "sql/query_options.h"

#include "sql/range_optimizer/group_index_skip_scan_plan.h"

#include "sql/range_optimizer/index_range_scan_plan.h"

#include "sql/range_optimizer/index_skip_scan_plan.h"

#include "sql/range_optimizer/internal.h"

#include "sql/range_optimizer/path_helpers.h"

#include "sql/range_optimizer/range_analysis.h"

#include "sql/range_optimizer/range_opt_param.h"

#include "sql/range_optimizer/range_optimizer.h"

#include "sql/range_optimizer/rowid_ordered_retrieval_plan.h"

#include "sql/range_optimizer/tree.h"

#include "sql/sql_array.h"

#include "sql/sql_base.h"

#include "sql/sql_class.h"

#include "sql/sql_cmd.h"

#include "sql/sql_const.h"

#include "sql/sql_executor.h"

#include "sql/sql_lex.h"

#include "sql/sql_list.h"

#include "sql/sql_opt_exec_shared.h"

#include "sql/sql_optimizer.h"

#include "sql/sql_partition.h"

#include "sql/sql_select.h"

#include "sql/system_variables.h"

#include "sql/table.h"

#include "sql/table_function.h"

#include "sql/uniques.h"

#include "sql/window.h"

#include "template_utils.h"

class Temp_table_param;

using hypergraph::Hyperedge;

using hypergraph::Node;

using hypergraph::NodeMap;

using std::all_of;

using std::any_of;

using std::find_if;

using std::has_single_bit;

using std::min;

using std::none_of;

using std::pair;

using std::popcount;

using std::string;

using std::swap;

namespace {

string PrintAccessPath(const AccessPath &path, const JoinHypergraph &graph,

const char *description_for_trace);

void PrintJoinOrder(const AccessPath *path, string *join_order);

AccessPath *CreateMaterializationPath(THD *thd, JOIN *join, AccessPath *path,

TABLE *temp_table,

Temp_table_param *temp_table_param,

bool copy_items);

AccessPath *GetSafePathToSort(THD *thd, JOIN *join, AccessPath *path,

bool need_rowid,

bool force_materialization = false);

// Represents a candidate row-id ordered scan. For a ROR compatible

// range scan, it stores the applied and subsumed predicates.

struct PossibleRORScan {

unsigned idx;

OverflowBitset applied_predicates;

OverflowBitset subsumed_predicates;

};

using AccessPathArray = Prealloced_array<AccessPath *, 4>;

/**

CostingReceiver contains the main join planning logic, selecting access paths

based on cost. It receives subplans from DPhyp (see enumerate_subgraph.h),

assigns them costs based on a cost model, and keeps the ones that are

cheapest. In the end, this means it will be left with a root access path that

gives the lowest total cost for joining the tables in the query block, ie.,

without ORDER BY etc.

Currently, besides the expected number of produced rows (which is the same no

matter how we access the table) we keep only a single value per subplan

(total cost), and thus also only a single best access path. In the future,

we will have more dimensions to worry about, such as initial cost versus total

cost (relevant for LIMIT), ordering properties, and so on. At that point,

there is not necessarily a single “best” access path anymore, and we will need

to keep multiple ones around, and test all of them as candidates when building

larger subplans.

*/

class CostingReceiver {

public:

CostingReceiver(

THD *thd, Query_block *query_block, JoinHypergraph &graph,

const LogicalOrderings *orderings,

const Mem_root_array<SortAheadOrdering> *sort_ahead_orderings,

const Mem_root_array<ActiveIndexInfo> *active_indexes,

const Mem_root_array<SpatialDistanceScanInfo> *spatial_indexes,

const Mem_root_array<FullTextIndexInfo> *fulltext_searches,

NodeMap fulltext_tables, uint64_t sargable_fulltext_predicates,

table_map update_delete_target_tables,

table_map immediate_update_delete_candidates, bool need_rowid,

SecondaryEngineFlags engine_flags, int subgraph_pair_limit,

secondary_engine_modify_access_path_cost_t secondary_engine_cost_hook,

secondary_engine_check_optimizer_request_t

secondary_engine_planning_complexity_check_hook)

: m_thd(thd),

m_query_block(query_block),

m_access_paths(thd->mem_root),

m_graph(&graph),

m_orderings(orderings),

m_sort_ahead_orderings(sort_ahead_orderings),

m_active_indexes(active_indexes),

m_spatial_indexes(spatial_indexes),

m_fulltext_searches(fulltext_searches),

m_fulltext_tables(fulltext_tables),

m_sargable_fulltext_predicates(sargable_fulltext_predicates),

m_update_delete_target_nodes(GetNodeMapFromTableMap(

update_delete_target_tables, graph.table_num_to_node_num)),

m_immediate_update_delete_candidates(GetNodeMapFromTableMap(

immediate_update_delete_candidates, graph.table_num_to_node_num)),

m_need_rowid(need_rowid),

m_engine_flags(engine_flags),

m_subgraph_pair_limit(subgraph_pair_limit),

m_secondary_engine_cost_hook(secondary_engine_cost_hook),

m_secondary_engine_planning_complexity_check(

secondary_engine_planning_complexity_check_hook) {

// At least one join type must be supported.

assert(Overlaps(engine_flags,

MakeSecondaryEngineFlags(

SecondaryEngineFlag::SUPPORTS_HASH_JOIN,

SecondaryEngineFlag::SUPPORTS_NESTED_LOOP_JOIN)));

}

// Not copyable, but movable so that we can reset it after graph

// simplification if needed.

CostingReceiver &operator=(const CostingReceiver &) = delete;

CostingReceiver &operator=(CostingReceiver &&) = default;

CostingReceiver(const CostingReceiver &) = delete;

CostingReceiver(CostingReceiver &&) = default;

bool HasSeen(NodeMap subgraph) const {

return m_access_paths.count(subgraph) != 0;

}

bool FoundSingleNode(int node_idx);

bool evaluate_secondary_engine_optimizer_state_request();

// Called EmitCsgCmp() in the DPhyp paper.

bool FoundSubgraphPair(NodeMap left, NodeMap right, int edge_idx);

const AccessPathArray root_candidates() {

const auto it =

m_access_paths.find(TablesBetween(0, m_graph->nodes.size()));

if (it == m_access_paths.end()) {

return {};

}

return it->second.paths;

}

FunctionalDependencySet active_fds_at_root() const {

const auto it =

m_access_paths.find(TablesBetween(0, m_graph->nodes.size()));

if (it == m_access_paths.end()) {

return {};

}

return it->second.active_functional_dependencies;

}

size_t num_subplans() const { return m_access_paths.size(); }

size_t num_access_paths() const {

size_t access_paths = 0;

for (const auto &[nodes, pathset] : m_access_paths) {

access_paths += pathset.paths.size();

}

return access_paths;

}

int subgraph_pair_limit() const { return m_subgraph_pair_limit; }

/// True if the result of the join is found to be always empty, typically

/// because of an impossible WHERE clause.

bool always_empty() const {

const auto it =

m_access_paths.find(TablesBetween(0, m_graph->nodes.size()));

return it != m_access_paths.end() && it->second.always_empty;

}

AccessPath *ProposeAccessPath(AccessPath *path,

AccessPathArray *existing_paths,

OrderingSet obsolete_orderings,

const char *description_for_trace) const;

bool HasSecondaryEngineCostHook() const {

return m_secondary_engine_cost_hook != nullptr;

}

private:

THD *m_thd;

/// The query block we are planning.

Query_block *m_query_block;

/**

Besides the access paths for a set of nodes (see m_access_paths),

AccessPathSet contains information that is common between all access

paths for that set. One would believe num_output_rows would be such

a member (a set of tables should produce the same number of output

rows no matter the join order), but due to parameterized paths,

different access paths could have different outputs. delayed_predicates

is another, but currently, it's already efficiently hidden space-wise

due to the use of a union.

*/

struct AccessPathSet {

AccessPathArray paths;

FunctionalDependencySet active_functional_dependencies{0};

// Once-interesting orderings that we don't care about anymore,

// e.g. because they were interesting for a semijoin but that semijoin

// is now done (with or without using the ordering). This reduces

// the number of access paths we have to keep in play, since they are

// de-facto equivalent.

//

// Note that if orderings were merged, this could falsely prune out

// orderings that we would actually need, but as long as all of the

// relevant ones are semijoin orderings (which are never identical,

// and never merged with the relevant-at-end orderings), this

// should not happen.

OrderingSet obsolete_orderings{0};

// True if the join of the tables in this set has been found to be always

// empty (typically because of an impossible WHERE clause).

bool always_empty{false};

};

/**

For each subset of tables that are connected in the join hypergraph,

keeps the current best access paths for producing said subset.

There can be several that are best in different ways; see comments

on ProposeAccessPath().

Also used for communicating connectivity information back to DPhyp

(in HasSeen()); if there's an entry here, that subset will induce

a connected subgraph of the join hypergraph.

*/

mem_root_unordered_map<NodeMap, AccessPathSet> m_access_paths;

/**

How many subgraph pairs we've seen so far. Used to give up

if we end up allocating too many resources (prompting us to

create a simpler join graph and try again).

*/

int m_num_seen_subgraph_pairs = 0;

/// The graph we are running over.

JoinHypergraph *m_graph;

/// Whether we have applied clamping due to a multi-column EQ_REF at any

/// point. There is a known issue (see bug #33550360) where this can cause

/// row count estimates to be inconsistent between different access paths.

/// Obviously, we should fix this bug by adjusting the selectivities

/// (and we do for single-column indexes), but for multipart indexes,

/// this is nontrivial. See the bug for details on some ideas, but the

/// gist of it is that we probably will want a linear program to adjust

/// multi-selectivities so that they are consistent, and not above 1/N

/// (for N-row tables) if there are unique indexes on them.

///

/// The only reason why we collect this information, like

/// JoinHypergraph::has_reordered_left_joins, is to be able to assert

/// on inconsistent row counts between APs, excluding this (known) issue.

bool has_clamped_multipart_eq_ref = false;

/// Whether we have a semijoin where the inner child is parameterized on the

/// outer child, and the row estimate of the inner child is possibly clamped,

/// for example because of some other semijoin. In this case, we may see

/// inconsistent row count estimates between the ordinary semijoin plan and

/// the rewrite_semi_to_inner plan, because it's hard to tell how much the

/// already-applied-as-sargable selectivity affected the row count estimate of

/// the child.

///

/// The only reason why we collect this information, is to be able to assert

/// on inconsistent row counts between access paths, excluding this known

/// issue.

bool has_semijoin_with_possibly_clamped_child = false;

/// Keeps track of interesting orderings in this query block.

/// See LogicalOrderings for more information.

const LogicalOrderings *m_orderings;

/// List of all orderings that are candidates for sort-ahead

/// (because they are, or may eventually become, an interesting ordering).

const Mem_root_array<SortAheadOrdering> *m_sort_ahead_orderings;

/// List of all indexes that are active and that we can apply in this query.

/// Indexes can be useful in several ways: We can use them for ref access,

/// for index-only scans, or to get interesting orderings.

const Mem_root_array<ActiveIndexInfo> *m_active_indexes;

/// List of all active spatial indexes that we can apply in this query.

const Mem_root_array<SpatialDistanceScanInfo> *m_spatial_indexes;

/// List of all active full-text indexes that we can apply in this query.

const Mem_root_array<FullTextIndexInfo> *m_fulltext_searches;

/// A map of tables that are referenced by a MATCH function (those tables that

/// have Table_ref::is_fulltext_searched() == true). It is used for

/// preventing hash joins involving tables that are full-text searched.

NodeMap m_fulltext_tables = 0;

/// The set of WHERE predicates which are on a form that can be satisfied by a

/// full-text index scan. This includes calls to MATCH with no comparison

/// operator, and predicates on the form MATCH > const or MATCH >= const

/// (where const must be high enough to make the comparison return false for

/// documents with zero score).

uint64_t m_sargable_fulltext_predicates = 0;

/// The target tables of an UPDATE or DELETE statement.

NodeMap m_update_delete_target_nodes = 0;

/// The set of tables that are candidates for immediate update or delete.

/// Immediate update/delete means that the rows from the table are deleted

/// while reading the rows from the topmost iterator. (As opposed to buffered

/// update/delete, where the row IDs are stored in temporary tables, and only

/// updated or deleted after the topmost iterator has been read to the end.)

/// The candidates are those target tables that are only referenced once in

/// the query. The requirement for immediate deletion is that the deleted row

/// will not have to be read again later. Currently, at most one of the

/// candidate tables is chosen, and it is always the outermost table in the

/// join tree.

NodeMap m_immediate_update_delete_candidates = 0;

/// Whether we will be needing row IDs from our tables, typically for

/// a later sort. If this happens, derived tables cannot use streaming,

/// but need an actual materialization, since filesort expects to be

/// able to go back and ask for a given row. (This is different from

/// when we need row IDs for weedout, which doesn't preclude streaming.

/// The hypergraph optimizer does not use weedout.)

bool m_need_rowid;

/// The flags declared by the secondary engine. In particular, it describes

/// what kind of access path types should not be created.

SecondaryEngineFlags m_engine_flags;

/// The maximum number of pairs of subgraphs we are willing to accept,

/// or -1 if no limit. If this limit gets hit, we stop traversing the graph

/// and return an error; the caller will then have to modify the hypergraph

/// (see GraphSimplifier) to make for a graph with fewer options, so that

/// planning time will come under an acceptable limit.

int m_subgraph_pair_limit;

/// Pointer to a function that modifies the cost estimates of an access path

/// for execution in a secondary storage engine, or nullptr otherwise.

secondary_engine_modify_access_path_cost_t m_secondary_engine_cost_hook;

/// Pointer to a function that returns what state should hypergraph progress

/// for optimization with secondary storage engine, or nullptr otherwise.

secondary_engine_check_optimizer_request_t

m_secondary_engine_planning_complexity_check;

/// A map of tables that can never be on the right side of any join,

/// ie., they have to be leftmost in the tree. This only affects recursive

/// table references (ie., when WITH RECURSIVE is in use); they work by

/// continuously tailing new records, which wouldn't work if we were to

/// scan them multiple times or put them in a hash table. Naturally,

/// there must be zero or one bit here; the common case is zero.

NodeMap forced_leftmost_table = 0;

/// A special MEM_ROOT for allocating OverflowBitsets that we might end up

/// discarding, ie. for AccessPaths that do not yet live in m_access_paths.

/// For any AccessPath that is to have a permanent life (ie., not be

/// immediately discarded as inferior), the OverflowBitset _must_ be taken

/// out of this MEM_ROOT and onto the regular one, as it is cleared often.

/// (This significantly reduces the amount of memory used in situations

/// where lots of AccessPaths are produced and discarded. Of course,

/// it only matters for queries with >= 64 predicates.)

///

/// The copying is using CommitBitsetsToHeap(). ProposeAccessPath() will

/// automatically call CommitBitsetsToHeap() for accepted access paths,

/// but it will not call it on any of their children. Thus, if you've

/// added more than one AccessPath in the chain (e.g. if you add a join,

/// then a sort of that join, and then propose the sort), you will need

/// to make sure there are no stray bitsets left on this MEM_ROOT.

///

/// Because this can be a source of subtle bugs, you should be conservative

/// about what bitsets you put here; really, only the ones you could be

/// allocating many of (like joins) should be candidates.

MEM_ROOT m_overflow_bitset_mem_root;

/// A special MEM_ROOT for temporary data for the range optimizer.

/// It can be discarded immediately after we've decided on the range scans

/// for a given table (but we reuse its memory as long as there are more

/// tables left to scan).

MEM_ROOT m_range_optimizer_mem_root;

/// For trace use only.

string PrintSet(NodeMap x) const {

std::string ret = "{";

bool first = true;

for (size_t node_idx : BitsSetIn(x)) {

if (!first) {

ret += ",";

}

first = false;

ret += m_graph->nodes[node_idx].table()->alias;

}

return ret + "}";

}

/// For trace use only.

string PrintSubgraphHeader(const JoinPredicate *edge,

const AccessPath &join_path, NodeMap left,

NodeMap right) const;

/// Checks whether the given engine flag is active or not.

bool SupportedEngineFlag(SecondaryEngineFlag flag) const {

return Overlaps(m_engine_flags, MakeSecondaryEngineFlags(flag));

}

bool FindIndexRangeScans(int node_idx, bool *impossible,

double *num_output_rows_after_filter);

void ProposeIndexMerge(TABLE *table, int node_idx, const SEL_IMERGE &imerge,

int pred_idx, bool inexact,

bool allow_clustered_primary_key_scan,

int num_where_predicates,

double num_output_rows_after_filter,

RANGE_OPT_PARAM *param,

bool *has_clustered_primary_key_scan);

void ProposeRowIdOrderedUnion(TABLE *table, int node_idx,

const SEL_IMERGE &imerge, int pred_idx,

bool inexact, int num_where_predicates,

double num_output_rows_after_filter,

const RANGE_OPT_PARAM *param,

const Mem_root_array<AccessPath *> &paths);

void ProposeAllRowIdOrderedIntersectPlans(

TABLE *table, int node_idx, SEL_TREE *tree, int num_where_predicates,

const Mem_root_array<PossibleRORScan> &possible_ror_scans,

double num_output_rows_after_filter, const RANGE_OPT_PARAM *param);

void ProposeRowIdOrderedIntersect(

TABLE *table, int node_idx, int num_where_predicates,

const Mem_root_array<PossibleRORScan> &possible_ror_scans,

const Mem_root_array<ROR_SCAN_INFO *> &ror_scans, ROR_SCAN_INFO *cpk_scan,

double num_output_rows_after_filter, const RANGE_OPT_PARAM *param,

OverflowBitset needed_fields);

void ProposeIndexSkipScan(int node_idx, RANGE_OPT_PARAM *param,

AccessPath *skip_scan_path, TABLE *table,

OverflowBitset all_predicates,

size_t num_where_predicates, size_t predicate_idx,

double num_output_rows_after_filter, bool inexact);

void TraceAccessPaths(NodeMap nodes);

void ProposeAccessPathForBaseTable(int node_idx,

double force_num_output_rows_after_filter,

const char *description_for_trace,

AccessPath *path);

void ProposeAccessPathForIndex(int node_idx,

OverflowBitset applied_predicates,

OverflowBitset subsumed_predicates,

double force_num_output_rows_after_filter,

const char *description_for_trace,

AccessPath *path);

void ProposeAccessPathWithOrderings(NodeMap nodes,

FunctionalDependencySet fd_set,

OrderingSet obsolete_orderings,

AccessPath *path,

const char *description_for_trace);

bool ProposeTableScan(TABLE *table, int node_idx,

double force_num_output_rows_after_filter);

bool ProposeIndexScan(TABLE *table, int node_idx,

double force_num_output_rows_after_filter,

unsigned key_idx, bool reverse, int ordering_idx);

bool ProposeDistanceIndexScan(TABLE *table, int node_idx,

double force_num_output_rows_after_filter,

const SpatialDistanceScanInfo &order_info,

int ordering_idx);

bool ProposeRefAccess(TABLE *table, int node_idx, unsigned key_idx,

double force_num_output_rows_after_filter, bool reverse,

table_map allowed_parameter_tables, int ordering_idx);

bool ProposeAllUniqueIndexLookupsWithConstantKey(int node_idx, bool *found);

bool RedundantThroughSargable(

OverflowBitset redundant_against_sargable_predicates,

const AccessPath *left_path, const AccessPath *right_path, NodeMap left,

NodeMap right);

inline pair<bool, bool> AlreadyAppliedAsSargable(

Item *condition, const AccessPath *left_path,

const AccessPath *right_path);

bool ProposeAllFullTextIndexScans(TABLE *table, int node_idx,

double force_num_output_rows_after_filter);

bool ProposeFullTextIndexScan(TABLE *table, int node_idx,

Item_func_match *match, int predicate_idx,

int ordering_idx,

double force_num_output_rows_after_filter);

void ProposeNestedLoopJoin(NodeMap left, NodeMap right, AccessPath *left_path,

AccessPath *right_path, const JoinPredicate *edge,

bool rewrite_semi_to_inner,

FunctionalDependencySet new_fd_set,

OrderingSet new_obsolete_orderings,

bool *wrote_trace);

void ProposeHashJoin(NodeMap left, NodeMap right, AccessPath *left_path,

AccessPath *right_path, const JoinPredicate *edge,

FunctionalDependencySet new_fd_set,

OrderingSet new_obsolete_orderings,

bool rewrite_semi_to_inner, bool *wrote_trace);

void ApplyPredicatesForBaseTable(int node_idx,

OverflowBitset applied_predicates,

OverflowBitset subsumed_predicates,

bool materialize_subqueries,

AccessPath *path,

FunctionalDependencySet *new_fd_set);

void ApplyDelayedPredicatesAfterJoin(

NodeMap left, NodeMap right, const AccessPath *left_path,

const AccessPath *right_path, int join_predicate_first,

int join_predicate_last, bool materialize_subqueries,

AccessPath *join_path, FunctionalDependencySet *new_fd_set);

double FindAlreadyAppliedSelectivity(const JoinPredicate *edge,

const AccessPath *left_path,

const AccessPath *right_path,

NodeMap left, NodeMap right);

void CommitBitsetsToHeap(AccessPath *path) const;

bool BitsetsAreCommitted(AccessPath *path) const;

};

/// Lists the current secondary engine flags in use. If there is no secondary

/// engine, will use a default set of permissive flags suitable for

/// non-secondary engine use.

SecondaryEngineFlags EngineFlags(const THD *thd) {

if (const handlerton *secondary_engine = SecondaryEngineHandlerton(thd);

secondary_engine != nullptr) {

return secondary_engine->secondary_engine_flags;

}

return MakeSecondaryEngineFlags(

SecondaryEngineFlag::SUPPORTS_HASH_JOIN,

SecondaryEngineFlag::SUPPORTS_NESTED_LOOP_JOIN);

}

/// Gets the secondary storage engine cost modification function, if any.

secondary_engine_modify_access_path_cost_t SecondaryEngineCostHook(

const THD *thd) {

const handlerton *secondary_engine = SecondaryEngineHandlerton(thd);

if (secondary_engine == nullptr) {

return nullptr;

} else {

return secondary_engine->secondary_engine_modify_access_path_cost;

}

}

/// Gets the secondary storage engine hypergraph state hook function, if any.

secondary_engine_check_optimizer_request_t SecondaryEngineStateCheckHook(

const THD *thd) {

const handlerton *secondary_engine = SecondaryEngineHandlerton(thd);

if (secondary_engine == nullptr) {

return nullptr;

}

return secondary_engine->secondary_engine_check_optimizer_request;

}

bool IsClusteredPrimaryKey(unsigned key_index, const TABLE &table) {

return key_index == table.s->primary_key &&

table.file->primary_key_is_clustered();

}

/// Returns the MATCH function of a predicate that can be pushed down to a

/// full-text index. This can be done if the predicate is a MATCH function,

/// or in some cases (see IsSargableFullTextIndexPredicate() for details)

/// where the predicate is a comparison function which compares the result

/// of MATCH with a constant. For example, predicates on this form could be

/// pushed down to a full-text index:

///

/// WHERE MATCH (x) AGAINST ('search string') AND @<more predicates@>

///

/// WHERE MATCH (x) AGAINST ('search string') > 0.5 AND @<more predicates@>

///

/// Since full-text index scans return documents with positive scores only, an

/// index scan can only be used if the predicate excludes negative or zero

/// scores.

Item_func_match *GetSargableFullTextPredicate(const Predicate &predicate) {

Item_func *func = down_cast<Item_func *>(predicate.condition);

switch (func->functype()) {

case Item_func::MATCH_FUNC:

// The predicate is MATCH (x) AGAINST ('search string'), which can be

// pushed to the index.

return down_cast<Item_func_match *>(func->get_arg(0))->get_master();

case Item_func::LT_FUNC:

case Item_func::LE_FUNC:

// The predicate is const < MATCH or const <= MATCH, with a constant value

// which makes it pushable.

assert(func->get_arg(0)->const_item());

return down_cast<Item_func_match *>(func->get_arg(1))->get_master();

case Item_func::GT_FUNC:

case Item_func::GE_FUNC:

// The predicate is MATCH > const or MATCH >= const, with a constant value

// which makes it pushable.

assert(func->get_arg(1)->const_item());

return down_cast<Item_func_match *>(func->get_arg(0))->get_master();

default:

// The predicate is not on a form that can be pushed to a full-text index

// scan. We should not get here.

assert(false);

return nullptr;

}

}

/// Is the current statement a DELETE statement?

bool IsDeleteStatement(const THD *thd) {

return thd->lex->sql_command == SQLCOM_DELETE ||

thd->lex->sql_command == SQLCOM_DELETE_MULTI;

}

/// Is the current statement a DELETE statement?

bool IsUpdateStatement(const THD *thd) {

return thd->lex->sql_command == SQLCOM_UPDATE ||

thd->lex->sql_command == SQLCOM_UPDATE_MULTI;

}

void CostingReceiver::TraceAccessPaths(NodeMap nodes) {

auto it = m_access_paths.find(nodes);

if (it == m_access_paths.end()) {

Trace(m_thd) << " - " << PrintSet(nodes)

<< " has no access paths (this should not normally happen)\n";

return;

}

Trace(m_thd) << " - current access paths for " << PrintSet(nodes) << ": ";

bool first = true;

for (const AccessPath *path : it->second.paths) {

if (!first) {

Trace(m_thd) << ", ";

}

Trace(m_thd) << PrintAccessPath(*path, *m_graph, "");

first = false;

}

Trace(m_thd) << ")\n";

}

/**

Called for each table in the query block, at some arbitrary point before we

start seeing subsets where it's joined to other tables.

We support table scans and ref access, so we create access paths for both

(where possible) and cost them. In this context, “tables” in a query block

also includes virtual tables such as derived tables, so we need to figure out

if there is a cost for materializing them.

*/

bool CostingReceiver::FoundSingleNode(int node_idx) {

if (m_thd->is_error()) return true;

m_graph->secondary_engine_costing_flags &=

~SecondaryEngineCostingFlag::HAS_MULTIPLE_BASE_TABLES;

TABLE *table = m_graph->nodes[node_idx].table();

Table_ref *tl = table->pos_in_table_list;

if (TraceStarted(m_thd)) {

Trace(m_thd) << StringPrintf("\nFound node %s [rows=%llu]\n",

m_graph->nodes[node_idx].table()->alias,

table->file->stats.records);

}

// First look for unique index lookups that use only constants.

{

bool found_eq_ref = false;

if (ProposeAllUniqueIndexLookupsWithConstantKey(node_idx, &found_eq_ref)) {

return true;

}

// If we found an unparameterized EQ_REF path, we can skip looking for

// alternative access methods, like parameterized or non-unique index

// lookups, index range scans or table scans, as they are unlikely to be any

// better. Returning early to reduce time spent planning the query, which is

// especially beneficial for point selects.

if (found_eq_ref) {

if (TraceStarted(m_thd)) {

TraceAccessPaths(TableBitmap(node_idx));

}

return false;

}

}

// We run the range optimizer before anything else, because we can use

// its estimates to adjust predicate selectivity, giving us consistent

// row count estimation between the access paths. (It is also usually

// more precise for complex range conditions than our default estimates.

// This is also the reason why we run it even if HA_NO_INDEX_ACCESS is set.)

double range_optimizer_row_estimate = -1.0;

{

auto cleanup_mem_root = create_scope_guard([this, node_idx] {

if (node_idx == 0) {

// We won't be calling the range optimizer anymore, so we don't need

// to keep its temporary allocations around. Note that FoundSingleNode()

// counts down from N-1 to 0, not up.

m_range_optimizer_mem_root.Clear();

} else {

m_range_optimizer_mem_root.ClearForReuse();

}

});

if (!tl->is_recursive_reference()) {

// Note that true error returns in itself is not enough to fail the query;

// the range optimizer could be out of RAM easily enough, which is

// nonfatal. That just means we won't be using it for this table.

bool impossible = false;

if (FindIndexRangeScans(node_idx, &impossible,

&range_optimizer_row_estimate) &&

m_thd->is_error()) {

return true;

}

if (impossible) {

const char *const cause = "WHERE condition is always false";

if (!IsBitSet(tl->tableno(), m_graph->tables_inner_to_outer_or_anti)) {

// The entire top-level join is going to be empty, so we can abort the

// planning and return a zero rows plan.

m_query_block->join->zero_result_cause = cause;

return true;

}

AccessPath *table_path =

NewTableScanAccessPath(m_thd, table, /*count_examined_rows=*/false);

AccessPath *zero_path = NewZeroRowsAccessPath(m_thd, table_path, cause);

// We need to get the set of functional dependencies right,

// even though we don't need to actually apply any filters.

FunctionalDependencySet new_fd_set;

ApplyPredicatesForBaseTable(

node_idx,

/*applied_predicates=*/

MutableOverflowBitset{m_thd->mem_root, m_graph->predicates.size()},

/*subsumed_predicates=*/

MutableOverflowBitset{m_thd->mem_root, m_graph->predicates.size()},

/*materialize_subqueries=*/false, zero_path, &new_fd_set);

zero_path->filter_predicates =

MutableOverflowBitset{m_thd->mem_root, m_graph->predicates.size()};

zero_path->ordering_state =

m_orderings->ApplyFDs(zero_path->ordering_state, new_fd_set);

ProposeAccessPathWithOrderings(TableBitmap(node_idx), new_fd_set,

/*obsolete_orderings=*/0, zero_path, "");

if (TraceStarted(m_thd)) {

TraceAccessPaths(TableBitmap(node_idx));

}

return false;

}

}

}

if (ProposeTableScan(table, node_idx, range_optimizer_row_estimate)) {

return true;

}

if (Overlaps(table->file->ha_table_flags(), HA_NO_INDEX_ACCESS) ||

tl->is_recursive_reference()) {

// We can't use any indexes, so end here.

if (TraceStarted(m_thd)) {

TraceAccessPaths(TableBitmap(node_idx));

}

return false;

}

// Propose index scan (for getting interesting orderings).

// We only consider those that are more interesting than a table scan;

// for the others, we don't even need to create the access path and go

// through the tournament.

for (const ActiveIndexInfo &order_info : *m_active_indexes) {

if (order_info.table != table) {

continue;

}

const int forward_order =

m_orderings->RemapOrderingIndex(order_info.forward_order);

const int reverse_order =

m_orderings->RemapOrderingIndex(order_info.reverse_order);

for (bool reverse : {false, true}) {

if (reverse && reverse_order == 0) {

continue;

}

const int order = reverse ? reverse_order : forward_order;

const int key_idx = order_info.key_idx;

// An index scan is more interesting than a table scan if it follows an

// interesting order that can be used to avoid a sort later, or if it is

// covering so that it can reduce the volume of data to read. A scan of a

// clustered primary index reads as much data as a table scan, so it is

// not considered unless it follows an interesting order.

if (order != 0 || (table->covering_keys.is_set(key_idx) &&

!IsClusteredPrimaryKey(key_idx, *table))) {

if (ProposeIndexScan(table, node_idx, range_optimizer_row_estimate,

key_idx, reverse, order)) {

return true;

}

}

// Propose ref access using only sargable predicates that reference no

// other table.

if (ProposeRefAccess(table, node_idx, key_idx,

range_optimizer_row_estimate, reverse,

/*allowed_parameter_tables=*/0, order)) {

return true;

}

// Propose ref access using all sargable predicates that also refer to

// other tables (e.g. t1.x = t2.x). Such access paths can only be used

// on the inner side of a nested loop join, where all the other

// referenced tables are among the outer tables of the join. Such path

// is called a parameterized path.

//

// Since indexes can have multiple parts, the access path can also end

// up being parameterized on multiple outer tables. However, since

// parameterized paths are less flexible in joining than

// non-parameterized ones, it can be advantageous to not use all parts

// of the index; it's impossible to say locally. Thus, we enumerate all

// possible subsets of table parameters that may be useful, to make sure

// we don't miss any such paths.

table_map want_parameter_tables = 0;

for (const SargablePredicate &sp :

m_graph->nodes[node_idx].sargable_predicates()) {

if (sp.field->table == table && sp.field->part_of_key.is_set(key_idx) &&

!Overlaps(sp.other_side->used_tables(),

PSEUDO_TABLE_BITS | table->pos_in_table_list->map())) {

want_parameter_tables |= sp.other_side->used_tables();

}

}

for (table_map allowed_parameter_tables :

NonzeroSubsetsOf(want_parameter_tables)) {

if (ProposeRefAccess(table, node_idx, key_idx,

range_optimizer_row_estimate, reverse,

allowed_parameter_tables, order)) {

return true;

}

}

}

}

for (const SpatialDistanceScanInfo &order_info : *m_spatial_indexes) {

if (order_info.table != table) {

continue;

}

const int order = m_orderings->RemapOrderingIndex(order_info.forward_order);

if (order != 0) {

if (ProposeDistanceIndexScan(table, node_idx,

range_optimizer_row_estimate, order_info,

order)) {

return true;

}

}

}

if (tl->is_fulltext_searched()) {

if (ProposeAllFullTextIndexScans(table, node_idx,

range_optimizer_row_estimate)) {

return true;

}

}

if (TraceStarted(m_thd)) {

TraceAccessPaths(TableBitmap(node_idx));

}

return false;

}

// Figure out which predicates we have that are not applied/subsumed

// by scanning this specific index; we already did a check earlier,

// but that was on predicates applied by scanning _any_ index.

// The difference is those that

//

// a) Use a field that's not part of this index.

// b) Use a field that our index is only partial for; these are still

// counted as applied for selectivity purposes (which is possibly

// overcounting), but need to be rechecked (ie., not subsumed).

// c) Use a field where we've been told by get_ranges_from_tree()

// that it had to set up a range that was nonexact (because it was

// part of a predicate that had a non-equality condition on an

// earlier keypart). These are handled as for b).

//

// We use this information to build up sets of which fields an

// applied or subsumed predicate is allowed to reference,

// then check each predicate against those lists.

void FindAppliedAndSubsumedPredicatesForRangeScan(

THD *thd, KEY *key, unsigned used_key_parts, unsigned num_exact_key_parts,

TABLE *table, OverflowBitset tree_applied_predicates,

OverflowBitset tree_subsumed_predicates, const JoinHypergraph &graph,

OverflowBitset *applied_predicates_out,

OverflowBitset *subsumed_predicates_out) {

MutableOverflowBitset applied_fields{thd->mem_root, table->s->fields};

MutableOverflowBitset subsumed_fields{thd->mem_root, table->s->fields};

MutableOverflowBitset applied_predicates(thd->mem_root,

graph.predicates.size());

MutableOverflowBitset subsumed_predicates(thd->mem_root,

graph.predicates.size());

for (unsigned keypart_idx = 0; keypart_idx < used_key_parts; ++keypart_idx) {

const KEY_PART_INFO &keyinfo = key->key_part[keypart_idx];

applied_fields.SetBit(keyinfo.field->field_index());

if (keypart_idx < num_exact_key_parts &&

!Overlaps(keyinfo.key_part_flag, HA_PART_KEY_SEG)) {

subsumed_fields.SetBit(keyinfo.field->field_index());

}

}

for (int predicate_idx : BitsSetIn(tree_applied_predicates)) {

Item *condition = graph.predicates[predicate_idx].condition;

bool any_not_applied =

WalkItem(condition, enum_walk::POSTFIX, [&applied_fields](Item *item) {