EXPLAIN FORMAT=JSONに表示されるコストを理解する旅に出た話
環境
mysql> select version(); +--------------+ | version() | +--------------+ | 8.0.28-debug | +--------------+ 1 row in set (0.00 sec) mysql> show create table test\G *************************** 1. row *************************** Table: test Create Table: CREATE TABLE `test` ( `id` int NOT NULL, `name` varchar(100) DEFAULT NULL, PRIMARY KEY (`id`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci 1 row in set (0.03 sec) mysql> select count(*) from test; +----------+ | count(*) | +----------+ | 1048584 | +----------+ 1 row in set (0.84 sec) mysql> select * from test limit 5; +----+-------+ | id | name | +----+-------+ | 1 | kubo1 | | 2 | kubo2 | | 3 | kubo3 | | 4 | kubo4 | | 5 | kubo5 | +----+-------+ 5 rows in set (0.00 sec)
EXPLAIN FORMAT=JSONでコスト表示
mysql> select * from test where name = 'kubo3'\G *************************** 1. row *************************** id: 3 name: kubo3 1 row in set (5.11 sec) mysql> explain format=json select * from test where name = 'kubo3'\G *************************** 1. row *************************** EXPLAIN: { "query_block": { "select_id": 1, "cost_info": { "query_cost": "100730.00" }, "table": { "table_name": "test", "access_type": "ALL", "rows_examined_per_scan": 984540, "rows_produced_per_join": 98454, "filtered": "10.00", "cost_info": { "read_cost": "90884.60", "eval_cost": "9845.40", "prefix_cost": "100730.00", "data_read_per_join": "38M" }, "used_columns": [ "id", "name" ], "attached_condition": "(`kubo`.`test`.`name` = 'kubo3')" } } }
オプティマイザトレースと同様に、EXPLAIN FORMAT=JSONで実行計画を表示するとどれだけのコストがかかったかを参照できる。 ただ、ふむふむと見てみても正直なんとなくしか分からない。
FORMAT=JSONの場合のEXPLAIN特有の情報を掴めるようになりたい。
そこで今回は以下のコストの意味をざっくり理解していくことにする。
"rows_examined_per_scan": 984540, "rows_produced_per_join": 98454, "filtered": "10.00", "cost_info": { "read_cost": "90884.60", "eval_cost": "9845.40", "prefix_cost": "100730.00"
これらの意味を理解していくためにソースを読んで出処を追う旅に出ることにした。
※なお、記事の最後では諸々の数値をざっくり説明してますが、eval_costだけは計算式のみでどういうコストか言語化できていないです。
Explain_format_JSON
read_costやeval_costなどでgrepすると以下のクラスExplain_format_JSONがヒットする。
/** Formatter class for EXPLAIN FORMAT=JSON output */ class Explain_format_JSON : public Explain_format { private: opt_explain_json_namespace::context *current_context; ///< current tree node public: Explain_format_JSON() : current_context(nullptr) {} bool is_hierarchical() const override { return true; } bool send_headers(Query_result *result) override; bool begin_context(enum_parsing_context context, Query_expression *subquery, const Explain_format_flags *flags) override; bool end_context(enum_parsing_context context) override; bool flush_entry() override { return false; } qep_row *entry() override; };
以下のように、先ほどのread_costやeval_costなどの文字列を表す定数が作成されている。 ではこの定数はどこで使用されているのだろうか
// JSON key names ... static const char K_ROWS[] = "rows_examined_per_scan"; static const char K_PREFIX_ROWS[] = "rows_produced_per_join"; static const char K_COST_INFO[] = "cost_info"; static const char K_READ_TIME[] = "read_cost"; static const char K_PREFIX_COST[] = "prefix_cost"; static const char K_COND_COST[] = "eval_cost"; ... static const char K_QUERY_COST[] = "query_cost"; static const char K_DATA_SIZE_QUERY[] = "data_read_per_join";
これら定数は以下の同クラスのメソッド（format_body）で利用されている。
cost_info内のコストに対応する部分について説明する（cost_info外のコストに対応する部分もほぼ同じ）。
まず、Opt_trace_object オブジェクトに json と K_COST_INFO というキーで初期化している（explain結果のcost_infoの部分に対応。中身はまだない）。 そして、32バイトの文字配列 bufにcol_read_costやcol_prefix_costなどの浮動小数点を文字列にキャストして詰め込んでいる。 最後に、そのbufと共にread _costやeval_cost,prefix_costを表していた定数をcost_infoのオブジェクトに詰め込まれている（explain結果のcost_infoの部分が完成）
bool table_base_ctx::format_body(Opt_trace_context *json, Opt_trace_object *obj) { StringBuffer<64> buff; ... if (!col_rows.is_empty()) obj->add(K_ROWS, col_rows.value); if (!col_prefix_rows.is_empty()) obj->add(K_PREFIX_ROWS, col_prefix_rows.value); if (!col_filtered.is_empty()) { char buf[32]; // 32 is enough for digits of a double print_filtered(buf, sizeof(buf), col_filtered.value); obj->add_utf8(K_FILTERED, buf); } format_extra(obj); if (!col_read_cost.is_empty()) { Opt_trace_object cost_info(json, K_COST_INFO); char buf[32]; // 32 is enough for digits of a double print_cost(buf, sizeof(buf), col_read_cost.value); cost_info.add_utf8(K_READ_TIME, buf); if (!col_cond_cost.is_empty()) { print_cost(buf, sizeof(buf), col_cond_cost.value); cost_info.add_utf8(K_COND_COST, buf); } if (!col_prefix_cost.is_empty()) { print_cost(buf, sizeof(buf), col_prefix_cost.value); cost_info.add_utf8(K_PREFIX_COST, buf); } if (!col_data_size_query.is_empty()) cost_info.add_utf8(K_DATA_SIZE_QUERY, col_data_size_query.str); } ... return format_derived(json) || format_query_expression(json); }
したがって、各コストの値はcol_hogehogeのvalueに対応していそうな事がわかる. ここまでで以下のような対応が整理できる。
"rows_examined_per_scan" → col_rows "rows_produced_per_join" → col_prefix_rows "read_cost" → col_read_cost "eval_cost" → col_cond_cost "prefix_cost" → col_prefix_cost
さて、このcol_hogehoge達は一体何者なのだろうか。
qep_row
これらcol_hogehoge達はqep_rowというクラスのpublic memberである。qep_rowはテーブルに関する各種情報をキャッシュする役割を担っている（通常のEXPLAINの場合は各出力行の情報が保存され、jsonやtree形式だと各コンテキストの情報が保存される）。
これらには以下でcol_hogehogeの各値がsetされている。 なお、fmtはexplain_thd->lex->explain_formatであり、この場合だとEXPLAIN_FORMAT_JSONである。entryメソッドによってJSONフォーマットの現在のコンテキストの情報（col_hogehogeのようなコスト情報）を抜き出している。
bool Explain_join::explain_rows_and_filtered() { if (!tab || tab->table_ref->schema_table) return false; POSITION *const pos = tab->position(); if (explain_thd->lex->sql_command == SQLCOM_EXPLAIN_OTHER && skip_records_in_range) { // Skipping col_rows, col_filtered, col_prefix_rows will set them to NULL. fmt->entry()->col_cond_cost.set(0); fmt->entry()->col_read_cost.set(0.0); fmt->entry()->col_prefix_cost.set(0); fmt->entry()->col_data_size_query.set("0"); } else { fmt->entry()->col_rows.set(static_cast<ulonglong>(pos->rows_fetched)); fmt->entry()->col_filtered.set( pos->rows_fetched ? static_cast<float>(100.0 * tab->position()->filter_effect) : 0.0f); // Print cost-related info double prefix_rows = pos->prefix_rowcount; ulonglong prefix_rows_ull = static_cast<ulonglong>(std::min(prefix_rows, ULLONG_MAX_DOUBLE)); fmt->entry()->col_prefix_rows.set(prefix_rows_ull); double const cond_cost = join->cost_model()->row_evaluate_cost(prefix_rows); fmt->entry()->col_cond_cost.set(cond_cost < 0 ? 0 : cond_cost); fmt->entry()->col_read_cost.set(pos->read_cost < 0.0 ? 0.0 : pos->read_cost); fmt->entry()->col_prefix_cost.set(pos->prefix_cost); // Calculate amount of data from this table per query char data_size_str[32]; double data_size = prefix_rows * tab->table()->s->rec_buff_length; human_readable_num_bytes(data_size_str, sizeof(data_size_str), data_size); fmt->entry()->col_data_size_query.set(data_size_str); } return false; }
ここまでで以下のような対応が整理できる。
"rows_examined_per_scan" → col_rows
→ static_cast<ulonglong>(pos->rows_fetched)
"rows_produced_per_join" → col_prefix_rows
→ static_cast<ulonglong>(std::min(prefix_rows, ULLONG_MAX_DOUBLE))
"read_cost" → col_read_cost
→ pos->read_cost < 0.0 ? 0.0: pos->read_cost
"eval_cost" → col_cond_cost
→ cond_cost < 0 ? 0 : cond_cost
"prefix_cost" → col_prefix_cost
→ pos->prefix_cost
※ double prefix_rows = pos->prefix_rowcount;
※ double const cond_cost = join->cost_model()->row_evaluate_cost(prefix_rows);
いくつかif分岐や大小比較があるが、col_hogehogeの値は大体pos→hugehugeの値が入っていると見て良いだろう。因みにjoin->cost_model()->row_evaluate_cost()は0.1倍する処理である（サーバーコストパラメータの一種。MySQL8.0ではデフォルト0.1, MySQL5.7ではデフォルト0.2）
ではposとはなんだろうか。
先程のソースの冒頭では以下のように記述されており、POSITIONオブジェクトへのポインタであると分かる。ではPOSITIONとは何だろうか。
POSITION *const pos = tab->position();
POSITION
POSITIONクラスは以下のような情報を含む。大雑把に言うと、クエリ内のテーブルに関する結合順序や結合方法についてまとめられている。結合クエリ内でどのような位置/立場(Position)にあるテーブルかを表す、と無理やり解釈するとクラス名にも合点がいく。
One POSITION element contains information about: ・Which table is accessed ・Which access method was chosen = Its cost and #of output records ・Semi-join strategy choice. Note that there are two different representation formats: The one used during join optimization The one used at plan refinement/code generation stage. We call fix_semijoin_strategies_for_picked_join_order() to switch between #1 and #2. See that function's comment for more details. ・Semi-join optimization state. When we're running join optimization, we main a state for every semi-join strategy which are various variables that tell us if/at which point we could consider applying the strategy. The variables are really a function of join prefix but they are too expensive to re-caclulate for every join prefix we consider, so we maintain current state in join->positions[#tables_in_prefix]. See advance_sj_state() for details. https://dev.mysql.com/doc/dev/mysql-server/latest/structPOSITION.html#details
このクラスの中のPublic Attributesとしてprefix_rowcountやprefix_cost、rows_fetched、read_costが存在し、以下のようにprefix_cost以外は何者か解説されている。
struct POSITION { /** The number of rows that will be fetched by the chosen access method per each row combination of previous tables. That is: rows_fetched = selectivity(access_condition) * cardinality(table) where 'access_condition' is whatever condition was chosen for index access, depending on the access method ('ref', 'range', etc.) @note For index/table scans, rows_fetched may be less than the number of rows in the table because the cost of evaluating constant conditions is included in the scan cost, and the number of rows produced by these scans is the estimated number of rows that pass the constant conditions. @see Optimize_table_order::calculate_scan_cost() . But this is only during planning; make_join_readinfo() simplifies it for EXPLAIN. */ double rows_fetched; /** Cost of accessing the table in course of the entire complete join execution, i.e. cost of one access method use (e.g. 'range' or 'ref' scan ) multiplied by estimated number of rows from tables earlier in the join sequence. read_cost does NOT include cost of processing rows within the executor (row_evaluate_cost). */ double read_cost; /** The fraction of the 'rows_fetched' rows that will pass the table conditions that were NOT used by the access method. If, e.g., "SELECT ... WHERE t1.colx = 4 and t1.coly @> 5" is resolved by ref access on t1.colx, filter_effect will be the fraction of rows that will pass the "t1.coly @> 5" predicate. The valid range is 0..1, where 0.0 means that no rows will pass the table conditions and 1.0 means that all rows will pass. It is used to calculate how many row combinations will be joined with the next table, @see prefix_rowcount below. @note With condition filtering enabled, it is possible to get a fanout = rows_fetched * filter_effect that is less than 1.0. Consider, e.g., a join between t1 and t2: "SELECT ... WHERE t1.col1=t2.colx and t2.coly OP @<something@>" where t1 is a prefix table and the optimizer currently calculates the cost of adding t2 to the join. Assume that the chosen access method on t2 is a 'ref' access on 'colx' that is estimated to produce 2 rows per row from t1 (i.e., rows_fetched = 2). It will in this case be perfectly fine to calculate a filtering effect @<0.5 (resulting in "rows_fetched * filter_effect @< 1.0") from the predicate "t2.coly OP @<something@>". If so, the number of row combinations from (t1,t2) is lower than the prefix_rowcount of t1. The above is just an example of how the fanout of a table can become less than one. It can happen for any access method. */ float filter_effect; /** prefix_rowcount and prefix_cost form a stack of partial join order costs and output sizes prefix_rowcount: The number of row combinations that will be joined to the next table in the join sequence. For a joined table it is calculated as prefix_rowcount = last_table.prefix_rowcount * rows_fetched * filter_effect @see filter_effect For a semijoined table it may be less than this formula due to duplicate elimination. */ double prefix_rowcount; double prefix_cost;
rows_fetchedはその名の通りであるが、選択されているアクセス方法によってフェッチされる行数である。全検索であれば全行になるだろうし、ユニークインデックスでの定数検索なら1行になる。この値はselectivity(access_condition) * cardinality(table)という式で計算されるみたいだ。
read_costは選択されたアクセス方法にかかるコスト（恐らく１行あたり）と見積もり行数（結合順でいう前のテーブルとの結合結果の見積もり行数）の乗算で表されるコストらしい。その名の通り読み取りのコストと呼ぶにふさわしい気がする。Executorでのフィルタリングやソートのコストは含まないとのことなので、選択されているアクセス方法によってフェッチされるコストと呼べば良さそう。
filter_effectはrows_fetched（選択されているアクセス方法によってフェッチされる行数）に対して何割がフィルタリングされるかを表す割合である。
prefix_rowcountは次のテーブルに結合される行の組み合わせの数。すなわち、選択されているアクセス方法によってフェッチされて、フィルタリングも終わった後の行数である。これはrow_fetched と filter_effectの乗算になるということである（結合順でいう前のテーブルがある場合はlast_table.prefix_rowcount、つまり前のテーブルから渡された行数の分の乗算をさらに考慮する必要がある）
なお、適当にステップ実行してたら以下のようなメソッドを発見した。 確かにコメントの通りの計算方法が確認できる。
/** Set complete estimated cost and produced rowcount for the prefix of tables up to and including this table, calculated from the cost of the previous stage, the fanout of the current stage and the cost to process a row at the current stage. @param idx Index of position object within array, if zero there is no "previous" stage that can be added. @param cm Cost model that provides the actual calculation */ void set_prefix_join_cost(uint idx, const Cost_model_server *cm) { if (idx == 0) { prefix_rowcount = rows_fetched; prefix_cost = read_cost + cm->row_evaluate_cost(prefix_rowcount); } else { prefix_rowcount = (this - 1)->prefix_rowcount * rows_fetched; prefix_cost = (this - 1)->prefix_cost + read_cost + cm->row_evaluate_cost(prefix_rowcount); } prefix_rowcount *= filter_effect; }
prefix_costについてはコメントで説明がなかったが、上記のメソッドを見る限りではread_costと0.1*prefix_rowcount（eval_cost）の和で表されるコストな様子。結合順でいう前のテーブルがある場合は、前のテーブルのprefix_costも足す様子。つまり最後の結合テーブルのprefix_costを見ると、全てのテーブルのread_costとeval_costの総和が分かるみたい。
ここまでで以下のような対応が整理できる。
"rows_examined_per_scan" → col_rows
→ static_cast<ulonglong>(pos->rows_fetched)
→ 選択されているアクセス方法によってフェッチされる行数
"rows_produced_per_join" → col_prefix_rows
→ static_cast<ulonglong>(std::min(prefix_rows, ULLONG_MAX_DOUBLE))
→ 次のテーブルに結合される行の組み合わせの数
"read_cost" → col_read_cost
→ pos->read_cost < 0.0 ? 0.0: pos->read_cost
→ 選択されているアクセス方法によって見積もり行数をフェッチするコスト
"eval_cost" → col_cond_cost
→ cond_cost < 0 ? 0 : cond_cost
→ 0.1 * rows_produced_per_join
"prefix_cost" → col_prefix_cost
→ pos->prefix_cost
→ read_cost ＋ eval_cost （＋前のテーブルのprefix_cost）
※ double prefix_rows = pos->prefix_rowcount;
※ double const cond_cost = join->cost_model()->row_evaluate_cost(prefix_rows);
eval_costは結局何のコストと評すれば良いかまだ分からない。cost_modelというのも何だろう。シンプルケースの場合でもう少し深く見積もり過程も追ってみたい。オプティマイザとレースも比較したい。
まだまだ旅をしなければ...
参考
第108回 MySQLのコスト見積もりを調整する | gihyo.jp
MySQL: anonymous_namespace{opt_explain.cc} Namespace Reference
