whoami

• Sergei Golubchik
• MariaDB Corporarion, Chief Architect MariaDB
• MySQL developer: 1998-2010
• MariaDB developer: 2010-…

• Tend to talk too fast ☹

Big Picture

Moment 1: Arrival

Protocol

• Vio (virtual io) layer to abstract socket/ssl/tcp from the upper level
• net_serv.cc — on-the-wire protocol, packets
  • zlib compression of packet payload

Read the packet

1202 bool do_command(THD *thd)
1203 {
1267   packet_length= my_net_read_packet(net, 1);
1292   if (packet_length == packet_error)
1330   {
1331     return_value= TRUE;
1332     goto out;
1333   }
1339 
1340   packet= (char*) net->read_pos;
1357 
1359   command= fetch_command(thd, packet);
1391   return_value= dispatch_command(command, thd,
1392         packet+1, packet_length-1, FALSE, FALSE);
1426 out:
1431   return return_value;
1432 }

Command dispatcher

1685   switch (command) {
1701   case COM_REGISTER_SLAVE:
1717   case COM_CHANGE_USER:
1782   case COM_STMT_BULK_EXECUTE:
1787   case COM_STMT_EXECUTE:
1792   case COM_STMT_FETCH:
1797   case COM_STMT_SEND_LONG_DATA:
1802   case COM_STMT_PREPARE:
1807   case COM_STMT_CLOSE:
1817   case COM_QUERY:
2063   case COM_QUIT:
2074   case COM_BINLOG_DUMP:
2106   case COM_REFRESH:
2159   case COM_SHUTDOWN:
2230   case COM_PING:
2272   case COM_DEBUG:
2368   }

mysql_parse

7991 void mysql_parse(THD *thd, char *rawbuf, uint length,
7995 {
8016   lex_start(thd);
8017   thd->reset_for_next_command();
8025   if (query_cache_send_result_to_client(thd, rawbuf, length) <= 0)
8026   {
8029     bool err= parse_sql(thd, parser_state, NULL, true);
8031     if (!err)
8076       error= mysql_execute_command(thd);
8081     else
8091       query_cache_abort(thd, &thd->query_cache_tls);
8098     thd->end_statement();
8099     thd->cleanup_after_query();
8101   }
8102   else
8110     thd->update_stats();
8119 }

Query Cache

• Caches the query as it came from the client
• And the result of a query — as network packets
• Thus it adds very little overhead to query processing
• If the query is cached, the answer is sent at once — no processing required

• Problem: one big mutex — bad concurrency ☹

Moment 2: Parsing

Parser

• entry point: parse_sql()
• LARL(1) parser built by bison, sql_yacc.yy
• Hand written lexer (sql_lex.cc) — not flex
• The query is parsed into memory data structures
  • table lists (TABLE_LIST)
  • select trees (SELECT_LEX)
  • expression trees (Item)
    · · ·

Item

• Base class for expressions
• fields, literals, functions, variables, subqueries…
• properties: name, type, maybe_null, null_value, charset, collation, used_tables, const_item, …
• methods: val_int, val_str, val_real, val_decimal; reset, add; eq, print, fix_fields, …

value= expr->val_int();  // or val_str(), val_real(), …

Preparing for execution

• Check privileges
• Open and lock tables
  • lock metadata
  • use table cache
  • parse views, triggers, stored functions
• Call item->fix_fields();
  • fields find their tables
  • items determine their basic properties (nullable? const? tables used?)

Moment 3: Optimizing

Query transformations

• Equality propagation — optimize_cond()

  WHERE t2.f2 = t1.f1 AND t1.f1 = 7

  ↓

  WHERE t1.f1 = 7 AND t2.f2 = 7

• NOT elimination — negate_expression()

  WHERE NOT t1.f1 < 7

  ↓

  WHERE t1.f1 >= 7

More query transformations

• outer join → inner join — simplify_joins()
• condition pushdown into non-mergeable derived tables and views — pushdown_cond_for_derived()
• “const” tables — join_read_const_table()
• IN (list) → IN (subquery)
• view merge
  · · ·

• in JOIN::optimize_inner()

Range optimizer

• Supports >, >=, <, <=, =, <>, IS NULL, <=>, BETWEEN, IN, LIKE, and any combination of the above combined with AND/OR
• Supports only comparison with a constant
• Asks storage engine for estimates for every key range — handler::records_in_range()
• Builds a tree of ranges

Range optimizer: example

CREATE TABLE ( ... INDEX (a,b) ... );
SELECT ... WHERE a IN (1,2) AND b IN (3,4) OR
                 a=7 AND b BETWEEN 3 AND 8 OR
                 a > 9 AND b < 5;

Execution plan

• Creates a list of possible indexes
• Considers "range" if possible
  • uses statistics otherwise
• Considers filesort, group by
• Performs greedy search for the best plan
  • best plan is the one that has the lowest cost

Statistics used

• Statistics from the storage engine
  • table scan cost (handler::scan_time)
  • index lookup cost (handler::read_time)
  • index cardinalities (handler::info)
• Engine-independent statistics
  • cardinalities (for tables, columns, indexes)
  • min/max values, nulls ratio for columns
  • histograms for columns
  • sampling

Moment 3: Executing

Join

• nested-loop joins — sub_select()
  • for every matching row in the first table
    • for every matched row in the second table
      · · ·
      • for every matched row in the last table
      • (usually) send results to the client — end_send()
• “for every matched row” means
  • get a next row — info->read_record()
  • check (part of) WHERE clause — evaluate_join_record()

Sending data

• not a separate step
• not necessarily sends anything

  class select_result;
  ├─class select_send;
  ├─class select_export;
  ├┬class select_insert;
  │└──class select_create;
  ├─class multi_update;
  └─class multi_delete;

• when it does: query cache → net_serv.cc → vio
• also it could do aggregation — end_send_group()
• or write rows to temporary table — end_write()

Temporary tables

• optimizer decides to use a temporary table: the nested-join loop populates the table

• can be used for aggregation — end_update()
• can be used for UNION, CTE, window functions, …
• can be MEMORY or Aria — create_tmp_table()

Filesort

SELECT a,b,c FROM t1 ORDER BY a LIMIT 10

• quicksort + multipass merge sort
  • of sort key + row "position"
  • or of sort key + other column values
• or binary heap

SE API

• handler
  • rnd_next(), rnd_pos(), index_read(), index_next(), ...
  • scan_time(), read_time(), records_in_range(), ...
  • open(), close(), repair(), create(), drop_table(), ...
• handlerton
  • drop_database(), close_connection(), show_status()
  • commit(), rollback(), prepare(), savepoint_set(), savepoint_rollback(), ...

Questions?