MySQL 8.0.29
Source Code Documentation
estimate_selectivity.cc File Reference
#include "sql/join_optimizer/estimate_selectivity.h"
#include <sys/types.h>
#include <algorithm>
#include <initializer_list>
#include <string>
#include "my_bitmap.h"
#include "my_table_map.h"
#include "sql/field.h"
#include "sql/handler.h"
#include "sql/item.h"
#include "sql/item_cmpfunc.h"
#include "sql/item_func.h"
#include "sql/join_optimizer/bit_utils.h"
#include "sql/join_optimizer/print_utils.h"
#include "sql/key.h"
#include "sql/sql_bitmap.h"
#include "sql/sql_const.h"
#include "sql/sql_select.h"
#include "sql/table.h"
#include "template_utils.h"

Functions

static double EstimateFieldSelectivity (Field *field, double *selectivity_cap, string *trace)
 Estimate the selectivity of (equi)joining a given field to any other field using cardinality information from indexes, if possible. More...
 
double EstimateSelectivity (THD *thd, Item *condition, string *trace)
 For the given condition, to try estimate its filtering selectivity, on a 0..1 scale (where 1.0 lets all records through). More...
 

Function Documentation

◆ EstimateFieldSelectivity()

static double EstimateFieldSelectivity ( Field field,
double *  selectivity_cap,
string *  trace 
)
static

Estimate the selectivity of (equi)joining a given field to any other field using cardinality information from indexes, if possible.

Assumes equal distribution and zero correlation between the two fields, so if there are e.g. 100 records and 4 distinct values (A,B,C,D) for the field, it assumes 25% of the values will be A, 25% B, etc. (equal distribution), and thus, when joining a row from some other table against this one, 25% of the records will match (equal distribution, zero correlation).

If there are multiple ones, we choose the one with the largest selectivity (least selective). There are two main reasons for this:

  • Databases generally tend to underestimate join cardinality (due to assuming uncorrelated relations); if we're wrong, it would better be towards overestimation to try to compensate.
  • Overestimating the number of rows generally leads to safer choices that are a little slower for few rows (e.g., hash join). Underestimating, however, leads to choices that can be catastrophic for many rows (e.g., nested loop against table scans). We should clearly prefer the least risky choice here.

Returns -1.0 if no index was found. Lifted from Item_equal::get_filtering_effect.

◆ EstimateSelectivity()

double EstimateSelectivity ( THD thd,
Item condition,
string *  trace 
)

For the given condition, to try estimate its filtering selectivity, on a 0..1 scale (where 1.0 lets all records through).

TODO(sgunders): In some cases, composite indexes might allow us to do better for joins with multiple predicates.