WL#12074: Volcano iterator executor base

Affects: Server-8.0   —   Status: Complete   —   Priority: Medium

Building on WL#11785 (Volcano iterator design), this worklog aims to deliver
the basics of a new SQL executor, using a consistent iterator design.
No (new) functional requirements. All queries should remain the same. Even 
performance schema results should be the same, except for some unusual queries as 
detailed in “Performance considerations”.

No (new) non-functional requirements. Performance should not regress.
The new executor will not replace the old one immediately; the two will live
side-by-side for some time. (However, removing the old one is a prerequisite
for a new join optimizer, as the new join optimizer will want to output e.g.
bushy joins, which do not have a natural representation in the data structures
used by the old one.) This is to reduce the scope of this worklog, and also
mitigate risk should there be unexpected issues.

Repeating and expanding on the long-term goals from WL#11785:

  * An execution structure that can trivially support bushy joins, if the
    optimizer wants to output them.
  * A framework enabling better EXPLAIN and EXPLAIN ANALYZE, as the entire
    query execution is modelled with an iterator tree (where each call can be
    timed by inserting timing/counting iterators), instead of a flat list.
  * Making nested loop no longer hard-wired into the executor; in particular,
    hash joins would be on equal footing with nested loop, making it
    significantly easier to implement (Erik already has a working prototype,
    although a production-ready implementation would also need a new join
  * More composable and reusable structures with clearer separation of
    concern; e.g., aggregation (GROUP BY) is implemented twice today, with one
    copy for temporary tables and one for sending directly to the user
    (both intertwined with logic for HAVING and actually sending the finished

After this specific worklog, the new executor will support queries consisting
of primary and const tables, joins (except semijoins), filtering (WHERE/HAVING),
grouping (except rollup), limit/offset and some forms of materialization
(derived tables, and materialization before e.g. a final sorting). In 
this means it does not support SELECT DISTINCT, CTEs, windowing functions,
semijoins, loose scan or BNL/BKA; however, it is a useful subset, and will allow
us to run e.g. nearly all DBT-3 queries, assuming BNL is turned off. MySQL will
transparently fall back to the old executor whenever an unsupported query is 

New iterators include:

 * FilterIterator: Implements WHERE/HAVING (but see below).
 * LimitOffsetIterator: Implements LIMIT/OFFSET (except for SQL_CALC_ROWS,
   in which case it will only implement OFFSET).
 * AggregateIterator: Implements aggregate functions, and does grouping if
   GROUP BY is active.
 * NestedLoopiterator: Joins two iterators using a nested-loop join
   (inner join, outer join or anti-join).
 * MaterializeIterator: Reads from another iterator, puts the results into
   a temporary table and then reads those results back one or more times.
 * FakeSingleRowIterator: Returns a single row and then nothing. Used only in
   certain situations with const tables (e.g., if we only have const tables,
   we still need an iterator to read that single row from).

The optimizer will not be changed as part of this worklog; we have to parse
the existing structures set up for the old optimizer and construct our iterator
tree from that. When we remove the old executor, we can make the optimizer
output more suitable data structures, e.g. a set of simple structures
corresponding directly to an iterator tree.

In general, queries will return the same result 1:1, but there is one exception: 
For the MySQL extension dealing with aliases in HAVING, nondeterministic 
functions may be executed a different number of times from what the user 
expects. (A partial fix for this was added in 5.7, with a full fix coming in as 
a side effect of implementing window functions; this worklog effectively reverts 
to 5.7 behavior.) Given that this is an extension, only appears in very specific 
cases involving HAVING and temporary tables, and the number of executions of 
nondeterministic functions is poorly specified anyway, this was deemed 

Regular EXPLAIN will not change at this time. However, we will support an
experimental (unsupported, subject to change in later versions) tree format
(e.g. EXPLAIN FORMAT=TREE SELECT ...), which will output the generated iterator
tree, helping the user understand how execution was actually set up. The tree
format needs more visual space but is also much more precise than the old
EXPLAIN format; e.g., instead of just “Using filesort”, it will mark clearly
what is sorted, and on which columns, and references to internal jargon will
be removed (e.g. it says “Buffered reference lookup” instead of “eq_ref”).
There will be no costs in this tree at the current stage.

An example EXPLAIN output from a DBT-3 query, with some lines truncated for the
benefit of the WL system:

-> Aggregate: sum((lineitem.l_extendedprice * (1 - lineitem.l_discount)))
    -> Nested loop inner join
        -> Filter: (((part.p_brand = 'Brand#22') and (part.p_container [...]
            -> Table scan: part
        -> Filter: (((lineitem.l_shipinstruct = 'DELIVER IN PERSON') and [...]
            -> Reference lookup on lineitem using i_l_partkey